spica - npm Package Compare versions

Comparing version 0.0.707 to 0.0.708

heap.test.ts

@@ -7,3 +7,3 @@ import { Heap } from './heap';
     function inspect<T>(heap: Heap<T>) {
-      return Array.from(heap['array']);
+      return Object.values(heap['array']);
     }
@@ -10,0 +10,0 @@

heap.ts

@@ -12,5 +12,2 @@ import { List } from './list';
 
-let size = 16;
-assert([size = 0]);
-
 export namespace Heap {
@@ -35,3 +32,3 @@ export interface Options {
   private readonly stable: boolean;
-  private array: Node<T, O>[] = Array(size);
+  private array: Record<number, Node<T, O>> = {};
   private $length = 0;
@@ -112,3 +109,3 @@ public get length(): number {
   public clear(): void {
-    this.array = Array(size);
+    this.array = {};
     this.$length = 0;
@@ -120,3 +117,3 @@ }
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -142,3 +139,3 @@ length: number,
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -161,3 +158,3 @@ ): boolean {
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -193,3 +190,3 @@ length: number,
 
-function swap<T, O>(array: Node<T, O>[], index1: number, index2: number): void {
+function swap<T, O>(array: Record<number, Node<T, O>>, index1: number, index2: number): void {
   assert(index1 && index2);
@@ -207,10 +204,21 @@ if (index1 === index2) return;
 
-class MultiNode<T, O> extends List.Node {
+class MList<T, O> extends List<MNode<T, O>> {
   constructor(
-    public list: List<MultiNode<T, O>>,
+    public readonly order: O,
+    heap: Heap<MList<T, O>, O>,
+  ) {
+    super();
+    this.heap = heap.insert(this, order);
+  }
+  public readonly heap: Heap.Node<MList<T, O>, O>;
+}
+class MNode<T, O> implements List.Node {
+  constructor(
+    public list: MList<T, O>,
     public order: O,
     public value: T,
   ) {
-    super();
   }
+  public next?: this = undefined;
+  public prev?: this = undefined;
 }
@@ -230,4 +238,2 @@
 export class MultiHeap<T, O = T> {
-  private static readonly order = Symbol('order');
-  private static readonly heap = Symbol('heap');
   public static readonly max = Heap.max;
@@ -243,9 +249,6 @@ public static readonly min = Heap.min;
   private readonly clean: boolean;
-  private readonly heap: Heap<List<MultiNode<T, O>>, O>;
-  private readonly dict = new Map<O, List<MultiNode<T, O>>>();
-  private readonly list = memoize<O, List<MultiNode<T, O>>>(order => {
-    const list = new List<MultiNode<T, O>>();
-    list[MultiHeap.order] = order;
-    list[MultiHeap.heap] = this.heap.insert(list, order);
-    return list;
+  private readonly heap: Heap<MList<T, O>, O>;
+  private readonly dict = new Map<O, MList<T, O>>();
+  private readonly list = memoize<O, MList<T, O>>(order => {
+    return new MList<T, O>(order, this.heap);
   }, this.dict);
@@ -264,3 +267,3 @@ private $length = 0;
   public insert(value: T, order: O): MultiHeap.Node<T, O>;
-  public insert(value: T, order?: O): MultiNode<T, O> {
+  public insert(value: T, order?: O): MNode<T, O> {
     if (arguments.length === 1) {
@@ -271,3 +274,3 @@ order = value as any;
     ++this.$length;
-    const node = new MultiNode(this.list(order), order, value);
+    const node = new MNode(this.list(order), order, value);
     node.list.push(node);
@@ -283,3 +286,3 @@ return node;
       this.heap.extract();
-      this.clean && this.dict.delete(list[MultiHeap.order]);
+      this.clean && this.dict.delete(list.order);
     }
@@ -289,3 +292,3 @@ return value;
   public delete(node: MultiHeap.Node<T, O>): T;
-  public delete(node: MultiNode<T, O>): T {
+  public delete(node: MNode<T, O>): T {
     if (node.next === undefined) throw new Error('Invalid node');
@@ -295,4 +298,4 @@ const list = node.list;
     if (list.length === 1) {
-      this.heap.delete(list[MultiHeap.heap]);
-      this.clean && this.dict.delete(list[MultiHeap.order]);
+      this.heap.delete(list.heap);
+      this.clean && this.dict.delete(list.order);
     }
@@ -302,3 +305,3 @@ return list.delete(node).value;
   public update(node: MultiHeap.Node<T, O>, order: O, value?: T): MultiHeap.Node<T, O>;
-  public update(node: MultiNode<T, O>, order?: O, value?: T): MultiHeap.Node<T, O> {
+  public update(node: MNode<T, O>, order?: O, value?: T): MultiHeap.Node<T, O> {
     const list = node.list;
@@ -310,9 +313,6 @@ if (list === undefined) throw new Error('Invalid node');
     }
-    if (this.cmp(list[MultiHeap.order], order) === 0) return node;
+    if (this.cmp(list.order, order) === 0) return node;
     this.delete(node);
     return this.insert(node.value, order);
   }
-  public find(order: O): List<MultiNode<T, O>> | undefined {
-    return this.dict.get(order);
-  }
   public clear(): void {
@@ -319,0 +319,0 @@ this.heap.clear();

list/ixlist.ts

@@ -47,3 +47,10 @@ import { max, min, isArray } from '../alias';
   public index(offset: number, index = this.head): number {
-    if (offset === 0) return this.nexts[index];
+    switch (offset) {
+      case 0:
+        return index;
+      case 1:
+        return this.nexts[index];
+      case -1:
+        return this.prevs[index];
+    }
     if (offset > 0) {
@@ -50,0 +57,0 @@ const pointers = this.nexts;

package.json

 {
   "name": "spica",
-  "version": "0.0.707",
+  "version": "0.0.708",
   "description": "Supervisor, Coroutine, Channel, select, AtomicPromise, Cancellation, Cache, List, Queue, Stack, and some utils.",
@@ -5,0 +5,0 @@ "private": false,

src/heap.test.ts

@@ -7,3 +7,3 @@ import { Heap } from './heap';
     function inspect<T>(heap: Heap<T>) {
-      return Array.from(heap['array']);
+      return Object.values(heap['array']);
     }
@@ -10,0 +10,0 @@

src/heap.ts

@@ -12,5 +12,2 @@ import { List } from './list';
 
-let size = 16;
-assert([size = 0]);
-
 export namespace Heap {
@@ -35,3 +32,3 @@ export interface Options {
   private readonly stable: boolean;
-  private array: Node<T, O>[] = Array(size);
+  private array: Record<number, Node<T, O>> = {};
   private $length = 0;
@@ -112,3 +109,3 @@ public get length(): number {
   public clear(): void {
-    this.array = Array(size);
+    this.array = {};
     this.$length = 0;
@@ -120,3 +117,3 @@ }
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -142,3 +139,3 @@ length: number,
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -161,3 +158,3 @@ ): boolean {
   cmp: (a: O, b: O) => number,
-  array: Node<T, O>[],
+  array: Record<number, Node<T, O>>,
   index: number,
@@ -193,3 +190,3 @@ length: number,
 
-function swap<T, O>(array: Node<T, O>[], index1: number, index2: number): void {
+function swap<T, O>(array: Record<number, Node<T, O>>, index1: number, index2: number): void {
   assert(index1 && index2);
@@ -207,10 +204,21 @@ if (index1 === index2) return;
 
-class MultiNode<T, O> extends List.Node {
+class MList<T, O> extends List<MNode<T, O>> {
   constructor(
-    public list: List<MultiNode<T, O>>,
+    public readonly order: O,
+    heap: Heap<MList<T, O>, O>,
+  ) {
+    super();
+    this.heap = heap.insert(this, order);
+  }
+  public readonly heap: Heap.Node<MList<T, O>, O>;
+}
+class MNode<T, O> implements List.Node {
+  constructor(
+    public list: MList<T, O>,
     public order: O,
     public value: T,
   ) {
-    super();
   }
+  public next?: this = undefined;
+  public prev?: this = undefined;
 }
@@ -230,4 +238,2 @@
 export class MultiHeap<T, O = T> {
-  private static readonly order = Symbol('order');
-  private static readonly heap = Symbol('heap');
   public static readonly max = Heap.max;
@@ -243,9 +249,6 @@ public static readonly min = Heap.min;
   private readonly clean: boolean;
-  private readonly heap: Heap<List<MultiNode<T, O>>, O>;
-  private readonly dict = new Map<O, List<MultiNode<T, O>>>();
-  private readonly list = memoize<O, List<MultiNode<T, O>>>(order => {
-    const list = new List<MultiNode<T, O>>();
-    list[MultiHeap.order] = order;
-    list[MultiHeap.heap] = this.heap.insert(list, order);
-    return list;
+  private readonly heap: Heap<MList<T, O>, O>;
+  private readonly dict = new Map<O, MList<T, O>>();
+  private readonly list = memoize<O, MList<T, O>>(order => {
+    return new MList<T, O>(order, this.heap);
   }, this.dict);
@@ -264,3 +267,3 @@ private $length = 0;
   public insert(value: T, order: O): MultiHeap.Node<T, O>;
-  public insert(value: T, order?: O): MultiNode<T, O> {
+  public insert(value: T, order?: O): MNode<T, O> {
     if (arguments.length === 1) {
@@ -271,3 +274,3 @@ order = value as any;
     ++this.$length;
-    const node = new MultiNode(this.list(order), order, value);
+    const node = new MNode(this.list(order), order, value);
     node.list.push(node);
@@ -283,3 +286,3 @@ return node;
       this.heap.extract();
-      this.clean && this.dict.delete(list[MultiHeap.order]);
+      this.clean && this.dict.delete(list.order);
     }
@@ -289,3 +292,3 @@ return value;
   public delete(node: MultiHeap.Node<T, O>): T;
-  public delete(node: MultiNode<T, O>): T {
+  public delete(node: MNode<T, O>): T {
     if (node.next === undefined) throw new Error('Invalid node');
@@ -295,4 +298,4 @@ const list = node.list;
     if (list.length === 1) {
-      this.heap.delete(list[MultiHeap.heap]);
-      this.clean && this.dict.delete(list[MultiHeap.order]);
+      this.heap.delete(list.heap);
+      this.clean && this.dict.delete(list.order);
     }
@@ -302,3 +305,3 @@ return list.delete(node).value;
   public update(node: MultiHeap.Node<T, O>, order: O, value?: T): MultiHeap.Node<T, O>;
-  public update(node: MultiNode<T, O>, order?: O, value?: T): MultiHeap.Node<T, O> {
+  public update(node: MNode<T, O>, order?: O, value?: T): MultiHeap.Node<T, O> {
     const list = node.list;
@@ -310,9 +313,6 @@ if (list === undefined) throw new Error('Invalid node');
     }
-    if (this.cmp(list[MultiHeap.order], order) === 0) return node;
+    if (this.cmp(list.order, order) === 0) return node;
     this.delete(node);
     return this.insert(node.value, order);
   }
-  public find(order: O): List<MultiNode<T, O>> | undefined {
-    return this.dict.get(order);
-  }
   public clear(): void {
@@ -319,0 +319,0 @@ this.heap.clear();

src/list/ixlist.ts

@@ -47,3 +47,10 @@ import { max, min, isArray } from '../alias';
   public index(offset: number, index = this.head): number {
-    if (offset === 0) return this.nexts[index];
+    switch (offset) {
+      case 0:
+        return index;
+      case 1:
+        return this.nexts[index];
+      case -1:
+        return this.prevs[index];
+    }
     if (offset > 0) {
@@ -50,0 +57,0 @@ const pointers = this.nexts;

No alert changes

Improved metrics

Total package byte prevSize

1164922

Lines of code

32589

increased by0.05%

No dependency changes