data-footstone - npm Package Compare versions

Comparing version 0.1.18 to 0.1.20-beta.1

dist_cjs/tree.js

@@ -6,4 +6,2 @@ 'use strict';
 
-// 需要添加该type
-// to test
 class BinaryTreeNode {
@@ -74,2 +72,10 @@ constructor(v) {
     }
+    attachAsLeft(parent, node) {
+        parent.left = node;
+        node && (node.parent = parent);
+    }
+    attachAsRight(parent, node) {
+        parent.right = node;
+        node && (node.parent = parent);
+    }
     _preOrderTraverse(cb, node) {
@@ -213,3 +219,2 @@ if (node) {
     // 每个节点的出度是 0 或 2.  
-    // to test
     isProper() {
@@ -245,3 +250,2 @@ if (!this.root) {
     // 叶子节点在最后一层上的真二叉树。
-    // to test
     isFull() {
@@ -253,3 +257,2 @@ let p = this.height();
     // 非最后一层为满二叉树，最后一层从左到右分布。
-    // to test
     isComplete() {
@@ -307,3 +310,7 @@ let h = this.height();
     clone() {
-        return new BinarySearchTreeNode(this.key, this.value);
+        let res = new BinarySearchTreeNode(this.key, this.value);
+        res.left = this.left;
+        res.right = this.right;
+        res.parent = this.parent;
+        return res;
     }
@@ -382,3 +389,2 @@ 'operator<'(otherNode) {
 }
-// to test
 class BinarySearchTree extends BinaryTree {
@@ -388,2 +394,3 @@ constructor() {
         this.root = null;
+        // this._hot = null // 记忆热点
     }
@@ -432,7 +439,15 @@ createBSTNode(k, v) {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
+    // searchIn(k: N, node: BinarySearchTreeNodeOrNull<T>) {
+    //   if (!node || k === node.key) {
+    //     return node
+    //   }
+    //   this._hot = node
+    //   return this.searchIn(k, k < node.key ? node.left : node.right)
+    // }
     // 若存在则返回节点，否则返回null
     search(k, node = this.root) {
+        // return this.searchIn(k, node)
         if (!node || node.key === k) {
@@ -557,3 +572,2 @@ return node;
 }
-// to test
 class AVLTree extends BinarySearchTree {
@@ -618,6 +632,6 @@ constructor() {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
-    // _insertNode(node: AVLTN<T>, newNode: AVLTN<T>): AVLTN<T> {
+    // _insertNode(node: BSTN<T>, newNode: BSTN<T>): BSTN<T> {
     //   if (!node) {
@@ -697,5 +711,2 @@ //     node = newNode
         c.parent = b;
-        // console.log('a', a)
-        // console.log('b', b)
-        // console.log('c', c)
         return b; // 返回该子树的根节点
@@ -708,8 +719,4 @@ }
         let g = p.parent;
-        // console.log('v', v)
-        // console.log('p', p)
-        // console.log('g', g)
         if (p['operator==='](g.left)) {
             if (v['operator==='](p.left)) {
-                // console.log('left left p')
                 // v p g
@@ -719,3 +726,2 @@ return this._connect34(v, p, g, v.left, v.right, p.right, g.right);
             else {
-                // console.log('left right p')
                 // p v g
@@ -726,5 +732,3 @@ return this._connect34(p, v, g, p.left, v.left, v.right, g.right);
         else {
-            // console.log('right g')
             if (v['operator==='](p.left)) {
-                // console.log('right left p')
                 // g v p
@@ -734,3 +738,2 @@ return this._connect34(g, v, p, g.left, v.left, v.right, p.right);
             else {
-                // console.log('right right p')
                 // g p v
@@ -737,0 +740,0 @@ return this._connect34(g, p, v, g.left, p.left, v.left, v.right);

dist_esm/tree.js

 import { Queue } from './queue.js';
 import { Stack } from './stack.js';
 
-// 需要添加该type
-// to test
 class BinaryTreeNode {
@@ -71,2 +69,10 @@ constructor(v) {
     }
+    attachAsLeft(parent, node) {
+        parent.left = node;
+        node && (node.parent = parent);
+    }
+    attachAsRight(parent, node) {
+        parent.right = node;
+        node && (node.parent = parent);
+    }
     _preOrderTraverse(cb, node) {
@@ -210,3 +216,2 @@ if (node) {
     // 每个节点的出度是 0 或 2.  
-    // to test
     isProper() {
@@ -242,3 +247,2 @@ if (!this.root) {
     // 叶子节点在最后一层上的真二叉树。
-    // to test
     isFull() {
@@ -250,3 +254,2 @@ let p = this.height();
     // 非最后一层为满二叉树，最后一层从左到右分布。
-    // to test
     isComplete() {
@@ -304,3 +307,7 @@ let h = this.height();
     clone() {
-        return new BinarySearchTreeNode(this.key, this.value);
+        let res = new BinarySearchTreeNode(this.key, this.value);
+        res.left = this.left;
+        res.right = this.right;
+        res.parent = this.parent;
+        return res;
     }
@@ -379,3 +386,2 @@ 'operator<'(otherNode) {
 }
-// to test
 class BinarySearchTree extends BinaryTree {
@@ -385,2 +391,3 @@ constructor() {
         this.root = null;
+        // this._hot = null // 记忆热点
     }
@@ -429,7 +436,15 @@ createBSTNode(k, v) {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
+    // searchIn(k: N, node: BinarySearchTreeNodeOrNull<T>) {
+    //   if (!node || k === node.key) {
+    //     return node
+    //   }
+    //   this._hot = node
+    //   return this.searchIn(k, k < node.key ? node.left : node.right)
+    // }
     // 若存在则返回节点，否则返回null
     search(k, node = this.root) {
+        // return this.searchIn(k, node)
         if (!node || node.key === k) {
@@ -554,3 +569,2 @@ return node;
 }
-// to test
 class AVLTree extends BinarySearchTree {
@@ -615,6 +629,6 @@ constructor() {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
-    // _insertNode(node: AVLTN<T>, newNode: AVLTN<T>): AVLTN<T> {
+    // _insertNode(node: BSTN<T>, newNode: BSTN<T>): BSTN<T> {
     //   if (!node) {
@@ -694,5 +708,2 @@ //     node = newNode
         c.parent = b;
-        // console.log('a', a)
-        // console.log('b', b)
-        // console.log('c', c)
         return b; // 返回该子树的根节点
@@ -705,8 +716,4 @@ }
         let g = p.parent;
-        // console.log('v', v)
-        // console.log('p', p)
-        // console.log('g', g)
         if (p['operator==='](g.left)) {
             if (v['operator==='](p.left)) {
-                // console.log('left left p')
                 // v p g
@@ -716,3 +723,2 @@ return this._connect34(v, p, g, v.left, v.right, p.right, g.right);
             else {
-                // console.log('left right p')
                 // p v g
@@ -723,5 +729,3 @@ return this._connect34(p, v, g, p.left, v.left, v.right, g.right);
         else {
-            // console.log('right g')
             if (v['operator==='](p.left)) {
-                // console.log('right left p')
                 // g v p
@@ -731,3 +735,2 @@ return this._connect34(g, v, p, g.left, v.left, v.right, p.right);
             else {
-                // console.log('right right p')
                 // g p v
@@ -734,0 +737,0 @@ return this._connect34(g, p, v, g.left, p.left, v.left, v.right);

package.json

 {
   "name": "data-footstone",
-  "version": "0.1.18",
+  "version": "0.1.20-beta.1",
   "description": "data structure",
@@ -9,2 +9,3 @@ "author": "feigebaobei <[e-mail]>",
   "type": "module",
+  "types": "./tscDist/src/index.d.ts",
   "directories": {
@@ -16,4 +17,4 @@ "lib": "lib",
     ".": {
-      "import": "./dist_esm/index.js",
-      "require": "./dist_cjs/index.js"
+      "import": "./tscDist/index.js",
+      "types": "./tscDist/src/index.d.ts"
     }
@@ -30,2 +31,3 @@ },
     "rollup": "rollup -c",
+    "build": "rollup -c rollup_ts.config.js",
     "clean": "echo 'fo clean'",
@@ -47,9 +49,9 @@ "compile": "tsc && npm run rollup",
     "dist_cjs",
-    "dist_esm"
+    "dist_esm",
+    "typings"
   ],
   "keywords": [
-    "data",
-    "structure",
     "data-footstone",
     "data",
+    "footstone",
     "structure",
@@ -86,2 +88,3 @@ "construction",
     "@jest/globals": "^29.3.1",
+    "@rollup/plugin-typescript": "^11.1.2",
     "@types/jest": "^29.2.4",
@@ -94,3 +97,3 @@ "@types/node": "^14.11.2",
   },
-  "gitHead": "3a87c44524b56a0772f9a3ce4b47bcf1ea9d6771"
+  "gitHead": "78bbeaff332c959b3eccef9563a139d434923f4d"
 }

README.md

@@ -12,6 +12,22 @@ # data-footstone
 - queue
+  - PriorityQueue
+- chain
+  - SingleChain
+  - DoublyChain
+  - SingleCircleChain
+  - DoublyCircleChain
 - hashMap
+  - hash 方法
 - tree
-- ……
-- graph 简单
+  - BinaryTree
+  - BinarySearchTree
+  - AVLTree
+- graph
+  - DirectionGraph
+  - UndirectionGraph
+- sort
+- cache
+  - fifo
+  - lru
+  - lfu
 
@@ -27,8 +43,11 @@ ## install
 let s = new Stack()
-s.push(1, 2, 3, 4)
+s.push(1) // 压入栈
+s.push(2)
+s.push(3)
+s.push(4)
 s.toArray() // [1,2,3,4]
-s.pop() // 4
+s.pop() // 4 弹出栈顶元素
 s.pop() // 3
-s.peek() // 2
-s.isEmpty() // false
+s.peek() // 2 返回栈顶元素
+s.isEmpty() // false 是否空栈
 s.clear() // 清空栈
@@ -35,0 +54,0 @@ ```

tscDist/src/tree.js

 import { Queue } from './queue';
 import { Stack } from './stack';
-// 需要添加该type
-// to test
 class BinaryTreeNode {
@@ -70,2 +68,10 @@ constructor(v) {
     }
+    attachAsLeft(parent, node) {
+        parent.left = node;
+        node && (node.parent = parent);
+    }
+    attachAsRight(parent, node) {
+        parent.right = node;
+        node && (node.parent = parent);
+    }
     _preOrderTraverse(cb, node) {
@@ -209,3 +215,2 @@ if (node) {
     // 每个节点的出度是 0 或 2.  
-    // to test
     isProper() {
@@ -241,3 +246,2 @@ if (!this.root) {
     // 叶子节点在最后一层上的真二叉树。
-    // to test
     isFull() {
@@ -249,3 +253,2 @@ let p = this.height();
     // 非最后一层为满二叉树，最后一层从左到右分布。
-    // to test
     isComplete() {
@@ -305,3 +308,7 @@ let h = this.height();
     clone() {
-        return new BinarySearchTreeNode(this.key, this.value);
+        let res = new BinarySearchTreeNode(this.key, this.value);
+        res.left = this.left;
+        res.right = this.right;
+        res.parent = this.parent;
+        return res;
     }
@@ -380,3 +387,2 @@ 'operator<'(otherNode) {
 }
-// to test
 class BinarySearchTree extends BinaryTree {
@@ -386,2 +392,3 @@ constructor() {
         this.root = null;
+        // this._hot = null // 记忆热点
     }
@@ -430,7 +437,15 @@ createBSTNode(k, v) {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
+    // searchIn(k: N, node: BinarySearchTreeNodeOrNull<T>) {
+    //   if (!node || k === node.key) {
+    //     return node
+    //   }
+    //   this._hot = node
+    //   return this.searchIn(k, k < node.key ? node.left : node.right)
+    // }
     // 若存在则返回节点，否则返回null
     search(k, node = this.root) {
+        // return this.searchIn(k, node)
         if (!node || node.key === k) {
@@ -555,3 +570,2 @@ return node;
 }
-// to test
 class AVLTree extends BinarySearchTree {
@@ -616,6 +630,6 @@ constructor() {
             }
-            // return newNode // 考虑是否返回插入的节点
+            return newNode; // 考虑是否返回插入的节点
         }
     }
-    // _insertNode(node: AVLTN<T>, newNode: AVLTN<T>): AVLTN<T> {
+    // _insertNode(node: BSTN<T>, newNode: BSTN<T>): BSTN<T> {
     //   if (!node) {
@@ -695,5 +709,2 @@ //     node = newNode
         c.parent = b;
-        // console.log('a', a)
-        // console.log('b', b)
-        // console.log('c', c)
         return b; // 返回该子树的根节点
@@ -706,8 +717,4 @@ }
         let g = p.parent;
-        // console.log('v', v)
-        // console.log('p', p)
-        // console.log('g', g)
         if (p['operator==='](g.left)) {
             if (v['operator==='](p.left)) {
-                // console.log('left left p')
                 // v p g
@@ -717,3 +724,2 @@ return this._connect34(v, p, g, v.left, v.right, p.right, g.right);
             else {
-                // console.log('left right p')
                 // p v g
@@ -724,5 +730,3 @@ return this._connect34(p, v, g, p.left, v.left, v.right, g.right);
         else {
-            // console.log('right g')
             if (v['operator==='](p.left)) {
-                // console.log('right left p')
                 // g v p
@@ -732,3 +736,2 @@ return this._connect34(g, v, p, g.left, v.left, v.right, p.right);
             else {
-                // console.log('right right p')
                 // g p v
@@ -768,2 +771,121 @@ return this._connect34(g, p, v, g.left, p.left, v.left, v.right);
 }
+class SplayTree extends BinarySearchTree {
+    constructor() {
+        super();
+    }
+    splay(v) {
+        if (!v) {
+            return null;
+        }
+        let p = v.parent;
+        if (!p) {
+            return v;
+        } // 已经是根节点就不用再伸展了。
+        let g = p.parent;
+        while (p && g) {
+            let gg = g.parent; // 未旋转时v的曾祖父。是旋转后v的父。
+            if (v.isLeft()) {
+                if (p.isLeft()) {
+                    // 当前结构
+                    //     g
+                    //   p
+                    // v
+                    // zig-zig
+                    this.attachAsLeft(g, p.right);
+                    this.attachAsRight(p, g);
+                    this.attachAsLeft(p, v.right);
+                    this.attachAsRight(v, p);
+                }
+                else {
+                    // 当前结构
+                    // g
+                    //      p
+                    //    v
+                    // zig-zag
+                    this.attachAsRight(g, v.left);
+                    this.attachAsLeft(v, g);
+                    this.attachAsRight(v, p);
+                    this.attachAsLeft(p, v.right);
+                }
+            }
+            else {
+                if (p.isRight()) {
+                    // zag-zag
+                    this.attachAsRight(g, p.left);
+                    this.attachAsLeft(p, g);
+                    this.attachAsRight(p, v.left);
+                    this.attachAsLeft(v, p);
+                }
+                else {
+                    // zag-zig
+                    this.attachAsLeft(g, v.right);
+                    this.attachAsRight(v, g);
+                    this.attachAsRight(p, v.left);
+                    this.attachAsLeft(v, p);
+                }
+            }
+            if (!gg) {
+                // 可删除
+                v.parent = null; // 根节点parent=null
+            }
+            else {
+                if (gg.left['operator=='](g)) {
+                    this.attachAsLeft(gg, v);
+                }
+                else {
+                    this.attachAsRight(gg, v);
+                }
+            }
+            p = v.parent;
+            if (p) {
+                g = p.parent;
+            }
+            else {
+                g = null;
+            }
+        }
+        if (p && p['operator==='](v.parent)) { // 最后一次可能是单旋转
+            if (v.isLeft()) {
+                this.attachAsLeft(p, v.right);
+                this.attachAsRight(v, p);
+            }
+            else {
+                this.attachAsRight(p, v.left);
+                this.attachAsLeft(v, p);
+            }
+        }
+        v.parent = null; // 到达树根后，设置parent=null
+        this.root = v;
+        return v;
+    }
+    searchSplayTreeNode(k) {
+        let node = this.search(k);
+        return this.splay(node);
+    }
+    insertSplayTreeNode(k, v) {
+        let node = this.insert(k, v);
+        // 若不是节点类型，则不执行伸展。
+        if (node instanceof BinarySearchTreeNode) {
+            return this.splay(node);
+        }
+        else {
+            return node;
+        }
+    }
+}
+// class BTreeNode<T> implements BTNodeIf<T> {
+//   constructor () {
+//     // this.order = order
+//   }
+//   search(k) {
+//   }
+// }
+// class BTree<T> implements BTreeIf<T> {
+//   order: BTreeIf<T>['order']
+//   constructor (order) {
+//     this.order = order
+//   }
+//   search(k: N) {
+//   }
+// }
 // class RedBackTree<T> extends BinarySearchTree<T> implements RBT<T> {
@@ -777,4 +899,5 @@ //   constructor() {
 // BTN,
-BinaryTree, BinarySearchTree, BinarySearchTreeNode, AVLTree,
+BinaryTree, BinarySearchTree, BinarySearchTreeNode, AVLTree, SplayTree,
+// BTree,
 // RedBackTree,
  };

No alert changes

Improved metrics

Total package byte prevSize

741798

34.54%

Number of package files

113

34.52%

Lines of code

10990

32.38%

Number of lines in readme file

57

50%

Worsened metrics

Dev dependency count

12

9.09%

No dependency changes