data-footstone - npm Package Compare versions

Comparing version 0.1.5 to 0.1.6

dist_cjs/chain.js

 'use strict';
 
+// 考虑添加exchange功能
+// 可以使用removeAt() + insert()实现
 class BaseChain {
@@ -94,2 +96,3 @@ constructor() {
     }
+    // 对外不暴露数据结构。所心不提供appendNode方法。
     append(p) {
@@ -96,0 +99,0 @@ let node = this.createNode(p, this.length);

dist_cjs/index.js

@@ -33,3 +33,4 @@ 'use strict';
 exports.Fifo = store.Fifo;
+exports.Lfu = store.Lfu;
 exports.Lru = store.Lru;
 //# sourceMappingURL=index.js.map

dist_cjs/queue.js

 'use strict';
 
-class Queue {
-    constructor(...p) {
-        this.items = p;
+// 可以抽象出BaseQueue
+class BaseQueue {
+    constructor() {
+        this.items = [];
     }
-    enqueue(...p) {
-        this.items.push(...p);
-        return this.size();
-    }
-    dequeue() {
-        return this.items.shift();
-    }
-    toArray() {
-        return this.items;
-    }
     getHead() {
-        // 有可能是undefined
         return this.items[0];
@@ -31,4 +21,21 @@ }
     clear() {
+        // return
         this.items = [];
     }
+}
+class Queue extends BaseQueue {
+    constructor(...p) {
+        super();
+        this.enqueue(...p);
+    }
+    enqueue(...p) {
+        this.items.push(...p);
+        return this.size();
+    }
+    dequeue() {
+        return this.items.shift();
+    }
+    toArray() {
+        return this.items;
+    }
     reverse() {
@@ -40,5 +47,6 @@ this.items.reverse();
 // 优先队列
-class PriorityQueue {
+class PriorityQueue extends BaseQueue {
     constructor(defaultPriority = 0) {
-        this.items = [];
+        super();
+        // this.items = []
         this.defaultPriority = defaultPriority;
@@ -68,33 +76,43 @@ }
     }
-    createElement(p, t) {
+    createNode(v, p = this.defaultPriority, position = -1) {
         return {
-            value: p,
-            priority: t ?? this.lowestPriority(),
+            value: v,
+            position: position,
+            priority: p,
         };
     }
     // 使一个元素入队列
-    enqueue(element, priority = this.defaultPriority) {
+    // 优先级高在前面
+    // positionFlag 是否放在同优先级的后面
+    // 考虑把参数处理为options
+    enqueue(element, priority = this.defaultPriority, positionFlag = true, needSetPosition = true) {
         let len = this.size();
-        let node = this.createElement(element, priority);
+        let node = this.createNode(element, priority);
         if (!len) {
             this.items.push(node);
-            return;
+            needSetPosition && this.setPosition();
         }
-        if (this._getHead().priority < node.priority) {
-            this.items.unshift(node);
-        }
-        else if (this._getTail().priority >= node.priority) {
-            this.items.push(node);
-        }
         else {
-            let index = 0;
-            while (index < len - 1) {
-                if (this.items[index].priority >= node.priority &&
-                    this.items[index + 1].priority < node.priority) {
-                    this.items.splice(index + 1, 0, node);
-                    break;
+            let positionPriority = positionFlag ? node.priority : node.priority + 1;
+            if (this._getHead().priority < positionPriority) {
+                this.items.unshift(node);
+                needSetPosition && this.setPosition();
+            }
+            else if (this._getTail().priority >= positionPriority) {
+                this.items.push(node);
+                needSetPosition && this.setPosition(this.size() - 1);
+            }
+            else {
+                let index = 0;
+                while (index < len - 1) {
+                    if (this.items[index].priority >= positionPriority &&
+                        this.items[index + 1].priority < positionPriority) {
+                        this.items.splice(index + 1, 0, node);
+                        break;
+                    }
+                    else {
+                        index++;
+                    }
                 }
-                else {
-                    index++;
-                }
+                needSetPosition && this.setPosition(index + 1);
             }
@@ -131,2 +149,30 @@ }
     }
+    setPosition(from = 0) {
+        let index = 0;
+        let size = this.size();
+        while (index < size) {
+            if (index >= from) {
+                this.items[index].position = index;
+            }
+            index++;
+        }
+    }
+    isValidRange(p) {
+        return 0 <= p && p < this.items.length;
+    }
+    updatePriorityAt(p, priority, positionFlag = false) {
+        let res = false;
+        if (this.isValidRange(p)) {
+            let [node] = this.items.splice(p, 1);
+            this.enqueue(node.value, node.priority + priority, positionFlag, false);
+            this.setPosition();
+            res = true;
+        }
+        return res;
+    }
+    updateDimension(v) {
+        this.items.forEach((item) => {
+            item.priority += v;
+        });
+    }
 }
@@ -133,0 +179,0 @@

dist_cjs/store.js

@@ -112,5 +112,112 @@ 'use strict';
 }
+// 最近多频使用
+// 如果数据过去被访问多次，那么将来被访问的频率也更高
+class Lfu {
+    constructor(capacity) {
+        this.capacity = capacity;
+        this.chain = new chain.DoublyChain();
+    }
+    _createNode(k, v, count = 0) {
+        return {
+            key: k,
+            value: v,
+            count,
+        };
+    }
+    _get(k) {
+        let res = undefined;
+        let cur = this.chain.head;
+        if (cur) {
+            while (cur) {
+                if (cur.value.key === k) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            res = cur;
+        }
+        return res;
+    }
+    get(k) {
+        let node = this._get(k);
+        let res = undefined;
+        if (node) {
+            res = node.value.value;
+            // 整理结构
+            this.chain.removeAt(node.position);
+            let newCount = node.value.count + 1;
+            let newNode = this._createNode(node.value.key, node.value.value, newCount);
+            if (this.chain.length) {
+                if (this.chain.tail.value.count > newCount) {
+                    this.chain.append(newCount);
+                }
+                else {
+                    let cur = this.chain.head;
+                    while (cur) {
+                        if (cur.value.count <= newCount) {
+                            break;
+                        }
+                        cur = cur.next;
+                    }
+                    this.chain.insert(newNode, cur.position);
+                }
+            }
+            else {
+                this.chain.append(newNode);
+            }
+        }
+        return res;
+    }
+    put(k, v) {
+        let node = this._get(k);
+        if (node) {
+            // 有
+            this.chain.removeAt(node.position);
+            node.value.count++;
+            node.value.value = v;
+            let cur = this.chain.head;
+            while (cur) {
+                if (cur.value.count <= node.value.count) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            this.chain.insert(node, cur.position);
+        }
+        else {
+            // 没有
+            while (this.chain.length >= this.capacity) {
+                this.chain.removeAt(this.chain.length - 1);
+            }
+            let newNode = this._createNode(k, v, 1);
+            this.chain.append(newNode);
+        }
+        return this.size();
+    }
+    size() {
+        return this.chain.length;
+    }
+    keys() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.key);
+            cur = cur.next;
+        }
+        return res;
+    }
+    values() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.value);
+            cur = cur.next;
+        }
+        return res;
+    }
+}
 
 exports.Fifo = Fifo;
+exports.Lfu = Lfu;
 exports.Lru = Lru;
 //# sourceMappingURL=store.js.map

dist_esm/chain.js

@@ -0,1 +1,3 @@
+// 考虑添加exchange功能
+// 可以使用removeAt() + insert()实现
 class BaseChain {
@@ -92,2 +94,3 @@ constructor() {
     }
+    // 对外不暴露数据结构。所心不提供appendNode方法。
     append(p) {
@@ -94,0 +97,0 @@ let node = this.createNode(p, this.length);

dist_esm/index.js

@@ -10,3 +10,3 @@ export { Stack } from './stack.js';
 export { order };
-export { Fifo, Lru } from './store.js';
+export { Fifo, Lfu, Lru } from './store.js';
 //# sourceMappingURL=index.js.map

dist_esm/queue.js

@@ -1,17 +0,7 @@
-class Queue {
-    constructor(...p) {
-        this.items = p;
+// 可以抽象出BaseQueue
+class BaseQueue {
+    constructor() {
+        this.items = [];
     }
-    enqueue(...p) {
-        this.items.push(...p);
-        return this.size();
-    }
-    dequeue() {
-        return this.items.shift();
-    }
-    toArray() {
-        return this.items;
-    }
     getHead() {
-        // 有可能是undefined
         return this.items[0];
@@ -29,4 +19,21 @@ }
     clear() {
+        // return
         this.items = [];
     }
+}
+class Queue extends BaseQueue {
+    constructor(...p) {
+        super();
+        this.enqueue(...p);
+    }
+    enqueue(...p) {
+        this.items.push(...p);
+        return this.size();
+    }
+    dequeue() {
+        return this.items.shift();
+    }
+    toArray() {
+        return this.items;
+    }
     reverse() {
@@ -38,5 +45,6 @@ this.items.reverse();
 // 优先队列
-class PriorityQueue {
+class PriorityQueue extends BaseQueue {
     constructor(defaultPriority = 0) {
-        this.items = [];
+        super();
+        // this.items = []
         this.defaultPriority = defaultPriority;
@@ -66,33 +74,43 @@ }
     }
-    createElement(p, t) {
+    createNode(v, p = this.defaultPriority, position = -1) {
         return {
-            value: p,
-            priority: t ?? this.lowestPriority(),
+            value: v,
+            position: position,
+            priority: p,
         };
     }
     // 使一个元素入队列
-    enqueue(element, priority = this.defaultPriority) {
+    // 优先级高在前面
+    // positionFlag 是否放在同优先级的后面
+    // 考虑把参数处理为options
+    enqueue(element, priority = this.defaultPriority, positionFlag = true, needSetPosition = true) {
         let len = this.size();
-        let node = this.createElement(element, priority);
+        let node = this.createNode(element, priority);
         if (!len) {
             this.items.push(node);
-            return;
+            needSetPosition && this.setPosition();
         }
-        if (this._getHead().priority < node.priority) {
-            this.items.unshift(node);
-        }
-        else if (this._getTail().priority >= node.priority) {
-            this.items.push(node);
-        }
         else {
-            let index = 0;
-            while (index < len - 1) {
-                if (this.items[index].priority >= node.priority &&
-                    this.items[index + 1].priority < node.priority) {
-                    this.items.splice(index + 1, 0, node);
-                    break;
+            let positionPriority = positionFlag ? node.priority : node.priority + 1;
+            if (this._getHead().priority < positionPriority) {
+                this.items.unshift(node);
+                needSetPosition && this.setPosition();
+            }
+            else if (this._getTail().priority >= positionPriority) {
+                this.items.push(node);
+                needSetPosition && this.setPosition(this.size() - 1);
+            }
+            else {
+                let index = 0;
+                while (index < len - 1) {
+                    if (this.items[index].priority >= positionPriority &&
+                        this.items[index + 1].priority < positionPriority) {
+                        this.items.splice(index + 1, 0, node);
+                        break;
+                    }
+                    else {
+                        index++;
+                    }
                 }
-                else {
-                    index++;
-                }
+                needSetPosition && this.setPosition(index + 1);
             }
@@ -129,2 +147,30 @@ }
     }
+    setPosition(from = 0) {
+        let index = 0;
+        let size = this.size();
+        while (index < size) {
+            if (index >= from) {
+                this.items[index].position = index;
+            }
+            index++;
+        }
+    }
+    isValidRange(p) {
+        return 0 <= p && p < this.items.length;
+    }
+    updatePriorityAt(p, priority, positionFlag = false) {
+        let res = false;
+        if (this.isValidRange(p)) {
+            let [node] = this.items.splice(p, 1);
+            this.enqueue(node.value, node.priority + priority, positionFlag, false);
+            this.setPosition();
+            res = true;
+        }
+        return res;
+    }
+    updateDimension(v) {
+        this.items.forEach((item) => {
+            item.priority += v;
+        });
+    }
 }
@@ -131,0 +177,0 @@

dist_esm/store.js

@@ -110,4 +110,110 @@ import { SingleChain, DoublyChain } from './chain.js';
 }
+// 最近多频使用
+// 如果数据过去被访问多次，那么将来被访问的频率也更高
+class Lfu {
+    constructor(capacity) {
+        this.capacity = capacity;
+        this.chain = new DoublyChain();
+    }
+    _createNode(k, v, count = 0) {
+        return {
+            key: k,
+            value: v,
+            count,
+        };
+    }
+    _get(k) {
+        let res = undefined;
+        let cur = this.chain.head;
+        if (cur) {
+            while (cur) {
+                if (cur.value.key === k) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            res = cur;
+        }
+        return res;
+    }
+    get(k) {
+        let node = this._get(k);
+        let res = undefined;
+        if (node) {
+            res = node.value.value;
+            // 整理结构
+            this.chain.removeAt(node.position);
+            let newCount = node.value.count + 1;
+            let newNode = this._createNode(node.value.key, node.value.value, newCount);
+            if (this.chain.length) {
+                if (this.chain.tail.value.count > newCount) {
+                    this.chain.append(newCount);
+                }
+                else {
+                    let cur = this.chain.head;
+                    while (cur) {
+                        if (cur.value.count <= newCount) {
+                            break;
+                        }
+                        cur = cur.next;
+                    }
+                    this.chain.insert(newNode, cur.position);
+                }
+            }
+            else {
+                this.chain.append(newNode);
+            }
+        }
+        return res;
+    }
+    put(k, v) {
+        let node = this._get(k);
+        if (node) {
+            // 有
+            this.chain.removeAt(node.position);
+            node.value.count++;
+            node.value.value = v;
+            let cur = this.chain.head;
+            while (cur) {
+                if (cur.value.count <= node.value.count) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            this.chain.insert(node, cur.position);
+        }
+        else {
+            // 没有
+            while (this.chain.length >= this.capacity) {
+                this.chain.removeAt(this.chain.length - 1);
+            }
+            let newNode = this._createNode(k, v, 1);
+            this.chain.append(newNode);
+        }
+        return this.size();
+    }
+    size() {
+        return this.chain.length;
+    }
+    keys() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.key);
+            cur = cur.next;
+        }
+        return res;
+    }
+    values() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.value);
+            cur = cur.next;
+        }
+        return res;
+    }
+}
 
-export { Fifo, Lru };
+export { Fifo, Lfu, Lru };
 //# sourceMappingURL=store.js.map

package.json

 {
   "name": "data-footstone",
-  "version": "0.1.5",
+  "version": "0.1.6",
   "description": "data structure",
@@ -75,3 +75,3 @@ "author": "feigebaobei <[e-mail]>",
   },
-  "gitHead": "cadedc5eac625073a17f9e6809da2f2789ec75bb"
+  "gitHead": "47e74dbdff2145571f6e3938d9515d800cf07a3d"
 }

tscDist/src/chain.js

@@ -0,1 +1,3 @@
+// 考虑添加exchange功能
+// 可以使用removeAt() + insert()实现
 class BaseChain {
@@ -92,2 +94,3 @@ constructor() {
     }
+    // 对外不暴露数据结构。所心不提供appendNode方法。
     append(p) {
@@ -94,0 +97,0 @@ let node = this.createNode(p, this.length);

tscDist/src/index.js

@@ -9,3 +9,3 @@ import { Stack } from './stack';
 import * as order from './order';
-import { Lru, Fifo } from './store';
-export { Stack, Queue, PriorityQueue, SingleChain, DoublyChain, SingleCircleChain, DoublyCircleChain, PSet, PMap, HashMap, djb2HashFn, loseloseHashFn, BaseTree, BinarySearchTree, AVLTree, RedBackTree, order, Lru, Fifo, };
+import { Lru, Fifo, Lfu } from './store';
+export { Stack, Queue, PriorityQueue, SingleChain, DoublyChain, SingleCircleChain, DoublyCircleChain, PSet, PMap, HashMap, djb2HashFn, loseloseHashFn, BaseTree, BinarySearchTree, AVLTree, RedBackTree, order, Lru, Fifo, Lfu, };

tscDist/src/queue.js

@@ -1,17 +0,7 @@
-class Queue {
-    constructor(...p) {
-        this.items = p;
+// 可以抽象出BaseQueue
+class BaseQueue {
+    constructor() {
+        this.items = [];
     }
-    enqueue(...p) {
-        this.items.push(...p);
-        return this.size();
-    }
-    dequeue() {
-        return this.items.shift();
-    }
-    toArray() {
-        return this.items;
-    }
     getHead() {
-        // 有可能是undefined
         return this.items[0];
@@ -29,4 +19,21 @@ }
     clear() {
+        // return
         this.items = [];
     }
+}
+class Queue extends BaseQueue {
+    constructor(...p) {
+        super();
+        this.enqueue(...p);
+    }
+    enqueue(...p) {
+        this.items.push(...p);
+        return this.size();
+    }
+    dequeue() {
+        return this.items.shift();
+    }
+    toArray() {
+        return this.items;
+    }
     reverse() {
@@ -38,5 +45,6 @@ this.items.reverse();
 // 优先队列
-class PriorityQueue {
+class PriorityQueue extends BaseQueue {
     constructor(defaultPriority = 0) {
-        this.items = [];
+        super();
+        // this.items = []
         this.defaultPriority = defaultPriority;
@@ -66,33 +74,43 @@ }
     }
-    createElement(p, t) {
+    createNode(v, p = this.defaultPriority, position = -1) {
         return {
-            value: p,
-            priority: t ?? this.lowestPriority(),
+            value: v,
+            position: position,
+            priority: p,
         };
     }
     // 使一个元素入队列
-    enqueue(element, priority = this.defaultPriority) {
+    // 优先级高在前面
+    // positionFlag 是否放在同优先级的后面
+    // 考虑把参数处理为options
+    enqueue(element, priority = this.defaultPriority, positionFlag = true, needSetPosition = true) {
         let len = this.size();
-        let node = this.createElement(element, priority);
+        let node = this.createNode(element, priority);
         if (!len) {
             this.items.push(node);
-            return;
+            needSetPosition && this.setPosition();
         }
-        if (this._getHead().priority < node.priority) {
-            this.items.unshift(node);
-        }
-        else if (this._getTail().priority >= node.priority) {
-            this.items.push(node);
-        }
         else {
-            let index = 0;
-            while (index < len - 1) {
-                if (this.items[index].priority >= node.priority &&
-                    this.items[index + 1].priority < node.priority) {
-                    this.items.splice(index + 1, 0, node);
-                    break;
+            let positionPriority = positionFlag ? node.priority : node.priority + 1;
+            if (this._getHead().priority < positionPriority) {
+                this.items.unshift(node);
+                needSetPosition && this.setPosition();
+            }
+            else if (this._getTail().priority >= positionPriority) {
+                this.items.push(node);
+                needSetPosition && this.setPosition(this.size() - 1);
+            }
+            else {
+                let index = 0;
+                while (index < len - 1) {
+                    if (this.items[index].priority >= positionPriority &&
+                        this.items[index + 1].priority < positionPriority) {
+                        this.items.splice(index + 1, 0, node);
+                        break;
+                    }
+                    else {
+                        index++;
+                    }
                 }
-                else {
-                    index++;
-                }
+                needSetPosition && this.setPosition(index + 1);
             }
@@ -129,4 +147,32 @@ }
     }
+    setPosition(from = 0) {
+        let index = 0;
+        let size = this.size();
+        while (index < size) {
+            if (index >= from) {
+                this.items[index].position = index;
+            }
+            index++;
+        }
+    }
+    isValidRange(p) {
+        return 0 <= p && p < this.items.length;
+    }
+    updatePriorityAt(p, priority, positionFlag = false) {
+        let res = false;
+        if (this.isValidRange(p)) {
+            let [node] = this.items.splice(p, 1);
+            this.enqueue(node.value, node.priority + priority, positionFlag, false);
+            this.setPosition();
+            res = true;
+        }
+        return res;
+    }
+    updateDimension(v) {
+        this.items.forEach((item) => {
+            item.priority += v;
+        });
+    }
 }
 // 不写循环队列。它应该写在循环链表。
 export { Queue, PriorityQueue };

tscDist/src/store.js

 // 存储
 import { SingleChain, DoublyChain } from './chain';
-// import { Queue } from './queue'
 // 未测试完
@@ -151,11 +150,110 @@ class Cache {
 }
-// 待测试
+// 最近多频使用
 // 如果数据过去被访问多次，那么将来被访问的频率也更高
 class Lfu {
-    constructor() { }
+    constructor(capacity) {
+        this.capacity = capacity;
+        this.chain = new DoublyChain();
+    }
+    _createNode(k, v, count = 0) {
+        return {
+            key: k,
+            value: v,
+            count,
+        };
+    }
+    _get(k) {
+        let res = undefined;
+        let cur = this.chain.head;
+        if (cur) {
+            while (cur) {
+                if (cur.value.key === k) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            res = cur;
+        }
+        return res;
+    }
+    get(k) {
+        let node = this._get(k);
+        let res = undefined;
+        if (node) {
+            res = node.value.value;
+            // 整理结构
+            this.chain.removeAt(node.position);
+            let newCount = node.value.count + 1;
+            let newNode = this._createNode(node.value.key, node.value.value, newCount);
+            if (this.chain.length) {
+                if (this.chain.tail.value.count > newCount) {
+                    this.chain.append(newCount);
+                }
+                else {
+                    let cur = this.chain.head;
+                    while (cur) {
+                        if (cur.value.count <= newCount) {
+                            break;
+                        }
+                        cur = cur.next;
+                    }
+                    this.chain.insert(newNode, cur.position);
+                }
+            }
+            else {
+                this.chain.append(newNode);
+            }
+        }
+        return res;
+    }
+    put(k, v) {
+        let node = this._get(k);
+        if (node) {
+            // 有
+            this.chain.removeAt(node.position);
+            node.value.count++;
+            node.value.value = v;
+            let cur = this.chain.head;
+            while (cur) {
+                if (cur.value.count <= node.value.count) {
+                    break;
+                }
+                cur = cur.next;
+            }
+            this.chain.insert(node, cur.position);
+        }
+        else {
+            // 没有
+            while (this.chain.length >= this.capacity) {
+                this.chain.removeAt(this.chain.length - 1);
+            }
+            let newNode = this._createNode(k, v, 1);
+            this.chain.append(newNode);
+        }
+        return this.size();
+    }
+    size() {
+        return this.chain.length;
+    }
+    keys() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.key);
+            cur = cur.next;
+        }
+        return res;
+    }
+    values() {
+        let cur = this.chain.head;
+        let res = [];
+        while (cur) {
+            res.push(cur.value.value);
+            cur = cur.next;
+        }
+        return res;
+    }
 }
 export { 
 // Cache,
-Fifo, Lru,
-//  Lfu
- };
+Fifo, Lru, Lfu, };

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

340292

increased by10.84%

Lines of code

5396

increased by9.3%

No dependency changes