jstreemap - npm Package Compare versions

Comparing version 1.7.1 to 1.8.1

esdoc.json

 {
   "source": "./src",
-  "destination": "./build/docs",
+  "destination": "./docs",
   "plugins": [
@@ -15,8 +15,7 @@ {
         "brand": {
-          "title": "setmap Library",
-          "description": "this is awesome library",
-          "repository": "https://github.com/foo/bar",
-          "site": "http://my-library.org",
-          "author": "https://twitter.com/foo",
-          "image": "http://my-library.org/logo.png"
+          "title": "jstreemap Library",
+          "description": "Associative containers (sets, maps) library for JavaScript, using red-black trees.",
+          "repository": "https://github.com/Kirusi/jstreemap",
+          "site": "https://github.com/Kirusi/jstreemap",
+          "author": "https://github.com/Kirusi"
         }
@@ -23,0 +22,0 @@ }

package.json

 {
   "name": "jstreemap",
-  "version": "1.7.1",
+  "version": "1.8.1",
   "description": "Library of associative containers.",
-  "main": "index.js",
+  "main": "jstreemap.js",
   "scripts": {
@@ -25,2 +25,4 @@ "build": "webpack --config ./config/webpack.config.js",
     "map",
+    "multimap",
+    "multiset",
     "red",
@@ -27,0 +29,0 @@ "black",

README.md

@@ -1,2 +0,57 @@
-# setmap
-Associative containers (sets, maps) library for JavaScript, using red-black trees.
+# jstreemap
+
+A JavaScript (ES6) library of tree-based associative containers.
+* [**TreeSet**](https://kirusi.github.io/jstreemap/class/src/public/tree-set.js~TreeSet.html) - is a container that stores unique elements following a specific order. In a TreeSet, the value of an element also identifies it (the value is itself the key),and each value must be unique. The value of the elements in a TreeSet cannot be modified once in the container (the elements are immutable), but they can be inserted or removed from the container.
+* [**TreeMap**](https://kirusi.github.io/jstreemap/class/src/public/tree-map.js~TreeMap.html) - is an associative container that stores elements formed
+by a combination of a key value and a mapped value, following a specific order.
+In a TreeMap, the key values are generally used to sort and uniquely identify
+the elements, while the mapped values store the content associated to this key.
+The types of key and mapped value may differ.
+* [**TreeMultiSet**](https://kirusi.github.io/jstreemap/class/src/public/tree-multiset.js~TreeMultiSet.html) - is a container that stores elements following a specific order, and where multiple elements can have equivalent values. In a TreeMultiSet, the value of an element also identifies it (the value is itself the key). The value of the elements in a multiset cannot be modified once in the container (the elements are always immutable), but they can be inserted or removed from the container.
+* [**TreeMultiMap**](https://kirusi.github.io/jstreemap/class/src/public/tree-multimap.js~TreeMultiMap.html) - is an associative container that stores elements formed by a combination of a key value and a mapped value, following a specific order, and where multiple elements can have equivalent keys. In a TreeMultiMap, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ.
+
+All container implementations are using  red-black trees. Detailed library documentation is [here.](https://kirusi.github.io/jstreemap)
+
+## Installation
+
+Using npm:
+```shell
+$ npm i --save jstreemap
+```
+
+In Node.js:
+```js
+// Load library.
+const {TreeSet, TreeMap, TreeMultiSet, TreeMultiMap} = require('jstreemap');
+
+// Create and initialize map.
+let map = new TreeMap([[2, 'B'], [1, 'A'], [3, 'C']]);
+// Iterate through all key-value pairs
+// Note that entries are stored in the ascending order of the keys,
+// not in the insertion order as in standard ES6 map
+for(let [k,v] of map) {
+    console.log(`key: ${k}, value: ${v}`);
+}
+// Expected output:
+// key: 1, value: A
+// key: 2, value: B
+// key: 3, value: C
+
+// Iterate elements in reverse order
+for(let [k,v] of map.backward()) {
+    console.log(`key: ${k}, value: ${v}`);
+}
+
+// find all elements with keys between 10 and 20 inclusive
+for (let it = map.lowerBound(10); !it.equals(map.upperBound(20); it.next()) {
+    console.log(`key: ${it.key}, value: ${it.value}`);
+}
+```
+## Why jstreemap?
+Ordered associative containers are not provided by default with JavaScript. This library provides an efficient implementation where performance of insert, delete and search operations is O(log(n)).
+
+Unlike standard sets and maps in ES6, this library provides  ordered containers. Iteration through container contents will be done in sorted order without any additional performance load.
+
+[Container API](https://kirusi.github.io/jstreemap) implements features of default ES6 maps and sets as well as parts of STL (C++ library) interface.
+
+The library showcases 100% test coverage and 100% documentation coverage.

src/internal/tree.js

@@ -11,2 +11,4 @@ 'use strict';
 const {KeyOnlyPolicy, ValueOnlyPolicy, KeyValuePolicy} = require('./policies');
+/** @ignore */
+const {InsertionResult} = require('../public/insertion-result');
 
@@ -215,5 +217,6 @@ /** insertion mode of a multimap, nodes with the same keys can be added */
      * @param {*} node
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      */
     insertMulti(node) {
-        this.insertNode(node, INSERT_MULTI);
+        return this.insertNode(node, INSERT_MULTI);
     }
@@ -224,5 +227,6 @@
      * @param {*} node
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      */
     insertUnique(node) {
-        this.insertNode(node, INSERT_UNIQUE);
+        return this.insertNode(node, INSERT_UNIQUE);
     }
@@ -233,5 +237,6 @@
      * @param {*} node
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      */
     insertOrReplace(node) {
-        this.insertNode(node, INSERT_REPLACE);
+        return this.insertNode(node, INSERT_REPLACE);
     }
@@ -244,23 +249,27 @@
      * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      */
     insertNode(n, mode = INSERT_MULTI) {
-        this.insertNodeInternal(this.head.root, n, mode);
-        if (this.head.size === 0) {
-            this.head.root = n;
-            this.head.leftmost = n;
-            this.head.rightmost = n;
+        let res = this.insertNodeInternal(this.head.root, n, mode);
+        if (res.wasAdded) {
+            if (this.head.size === 0) {
+                this.head.root = n;
+                this.head.leftmost = n;
+                this.head.rightmost = n;
 
-            n.left = this.head;
-            n.right = this.head;
+                n.left = this.head;
+                n.right = this.head;
+            }
+            else if (this.head.leftmost.left === n) {
+                this.head.leftmost = n;
+                n.left = this.head;
+            }
+            else if (this.head.rightmost.right === n) {
+                this.head.rightmost = n;
+                n.right = this.head;
+            }
+            this.insertRepairTree(n);
+            this.head.size = this.head.size + 1;
         }
-        else if (this.head.leftmost.left === n) {
-            this.head.leftmost = n;
-            n.left = this.head;
-        }
-        else if (this.head.rightmost.right === n) {
-            this.head.rightmost = n;
-            n.right = this.head;
-        }
-        this.insertRepairTree(n);
-        this.head.size = this.head.size + 1;
+        return res;
     }
@@ -274,2 +283,3 @@
      * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      */
@@ -296,6 +306,6 @@ insertNodeInternal(root, n, mode) {
                         // it's a duplicate
-                        return;
+                        return new InsertionResult(false, false, undefined);
                     case INSERT_REPLACE:
                         this.valuePolicy.copy(y, n);
-                        return;
+                        return new InsertionResult(false, true, new Iterator(y, this));
                     default:
@@ -321,2 +331,3 @@ // INSERT_MULTI
         }
+        return new InsertionResult(true, false, new Iterator(n, this));
     }
@@ -323,0 +334,0 @@

src/public/tree-map.js

@@ -9,3 +9,18 @@ /** An implementation of red-black tree */
 /**
- * This is an associative container class storing key-value pairs in ascending order
+ * TreeMap is an associative container that stores elements formed
+ * by a combination of a key value and a mapped value, following a specific order.
+ *
+ * In a TreeMap, the key values are generally used to sort and uniquely identify
+ * the elements, while the mapped values store the content associated to this key.
+ * The types of key and mapped value may differ.
+ *
+ * ## Container properties
+ * * **Associative** - Elements in associative containers are referenced by their key
+ * and not by their absolute position in the container.
+ * * **Ordered** - The elements in the container follow a strict order at all times.
+ * All inserted elements are given a position in this order.
+ * * **Map** - Each element associates a key to a mapped value. Keys are meant
+ * to identify the elements whose main content is the mapped value.
+ * * **Unique keys** - No two elements in the container can have equivalent keys.
+ *
  * @example
@@ -257,2 +272,14 @@ * let map = new TreeMap();
 
+    /**
+     * Sets custom comparison function if key values are not of primitive types.
+     * Callback is a 3-way comparison function accepts two key values (lhs, rhs). It is expected to return
+     *      +1 if the value of rhs is greater than lhs
+     *      -1 if the value of rhs is less than lhs
+     *       0 if values are the same
+     */
+    set compareFunc(func) {
+        this.clear();
+        this.__t.compare = func;
+    }
+
     /*======================================================
@@ -310,7 +337,13 @@ * STL-like methods
      * @param {*} value
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      * @example
      * let m = new TreeMap();
-     * m.insertUnique(1, 'A');
-     * m.insertUnique(1, 'B'); // this step has no effect on the map
-     * let v = m.get(1); // 'A'
+     * let res = m.insertUnique(1, 'A');
+     * if (res.wasInserted) {
+     *   console.log(`Inserted ${res.iterator.value}`); // prints A
+     * }
+     * res = m.insertUnique(1, 'B') // this step has no effect on the map
+     * if (res.wasInserted) {
+     *   console.log(`Inserted ${res.iterator.key}`); // not executed
+     * }
      */
@@ -328,7 +361,13 @@ insertUnique(key, value) {
      * @param {*} value
+     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
      * @example
      * let m = new TreeMap();
-     * m.insertOrReplace(1, 'A');
-     * m.insertOrReplace(1, 'B'); // replaces the value for key 1
-     * let v = m.get(1); // 'B'
+     * let res = m.insertOrReplace(1, 'A');
+     * if (res.wasInserted) {
+     *   console.log(`Inserted ${res.iterator.value}`); // prints A
+     * }
+     * res = m.insertOrReplace(1, 'B') // replaces value on the existing node
+     * if (res.wasInserted) {
+     *   console.log(`Inserted ${res.iterator.key}`); // prints B
+     * }
      */
@@ -350,4 +389,4 @@ insertOrReplace(key, value) {
      * // iterate through all key-value pairs with keys between 0 and 50 inclusive
-     * let from = t.lowerBound(0);
-     * let to = t.upperBound(50);
+     * let from = m.lowerBound(0);
+     * let to = m.upperBound(50);
      * let it = from;
@@ -362,4 +401,4 @@ * while (!it.equals(to)) {
      * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order
-     * let from = new ReverseIterator(t.upperBound(50));
-     * let to = new ReverseIterator(t.lowerBound(0));
+     * let from = new ReverseIterator(m.upperBound(50));
+     * let to = new ReverseIterator(m.lowerBound(0));
      * let it = from;
@@ -411,4 +450,4 @@ * while (!it.equals(to)) {
      * // iterate through all key-value pairs with keys between 0 and 50 inclusive
-     * let from = t.lowerBound(0);
-     * let to = t.upperBound(50);
+     * let from = m.lowerBound(0);
+     * let to = m.upperBound(50);
      * let it = from;
@@ -423,4 +462,4 @@ * while (!it.equals(to)) {
      * // iterate through all key-value pairs with keys between 0 and 50 inclusive in reverse order
-     * let from = new ReverseIterator(t.upperBound(50));
-     * let to = new ReverseIterator(t.lowerBound(0));
+     * let from = new ReverseIterator(m.upperBound(50));
+     * let to = new ReverseIterator(m.lowerBound(0));
      * let it = from;
@@ -427,0 +466,0 @@ * while (!it.equals(to)) {

test/test-tree-map.js

@@ -32,2 +32,90 @@ 'use strict';
 
+    it('constructor; ES6 map', function(done) {
+        let jsMap = new Map([[2, 'B'], [1, 'A'], [3, 'C']]);
+        let m = new TreeMap(jsMap);
+        should.equal(3, m.size);
+
+        let actual = [];
+        for (let [k, v] of m) {
+            actual.push([k, v]);
+        }
+
+        let expected = [[1, 'A'], [2, 'B'], [3, 'C']];
+        should.deepEqual(expected, actual);
+
+        done();
+    });
+
+    it('constructor; generator function', function(done) {
+        let gen = function*() {
+            for (let i = 1; i < 4; ++i) {
+                yield [i, `N${i * 2}`];
+            }
+        };
+        let m = new TreeMap(gen());
+        should.equal(3, m.size);
+
+        let actual = [];
+        for (let [k, v] of m) {
+            actual.push([k, v]);
+        }
+
+        let expected = [[1, 'N2'], [2, 'N4'], [3, 'N6']];
+        should.deepEqual(expected, actual);
+
+        done();
+    });
+
+    it('compareFunc', function(done) {
+        /* Test ability to compare alphanumeric structures like ['A',123]
+           First string portion is compared. If string portions of two objects are equal then numeric portions are compared */
+        class Id {
+            constructor(a, n) {
+                this.alpha = a;
+                this.num = n;
+            }
+        }
+
+        function compareIds(idLhs, idRhs) {
+            if (idLhs.alpha < idRhs.alpha) {
+                return -1;
+            }
+            else if (idLhs.alpha > idRhs.alpha) {
+                return 1;
+            }
+            else {
+                if (idLhs.num < idRhs.num) {
+                    return -1;
+                }
+                else if (idLhs.num > idRhs.num) {
+                    return 1;
+                }
+                else {
+                    return 0;
+                }
+            }
+        }
+
+        let m = new TreeMap();
+        m.compareFunc = compareIds;
+        m.set(new Id('B', 8), 'Book with id B8');
+        m.set(new Id('A', 340), 'Book with id A340');
+        m.set(new Id('A', 12), 'Book with id A12');
+        m.set({alpha: 'AA', num: 147}, 'Book with id AA147'); // create an ad-hoc object
+
+        let actual = [];
+        for (let [k, v] of m) {
+            actual.push([k.alpha, k.num, v]);
+        }
+        let expected = [
+            ['A', 12, 'Book with id A12'],
+            ['A', 340, 'Book with id A340'],
+            ['AA', 147, 'Book with id AA147'],
+            ['B', 8, 'Book with id B8']
+        ];
+        should.deepEqual(expected, actual);
+
+        done();
+    });
+
     it('constructor; invalid literal', function(done) {
@@ -235,6 +323,17 @@ try {
     it('insertUnique', function(done) {
-        let map = new TreeMap();
-        map.insertUnique(1, 'A');
-        map.insertUnique(1, 'B');
-        should.equal('A', map.get(1));
+        let m = new TreeMap();
+        for (let i = 1; i < 4; ++i) {
+            let res = m.insertUnique(1, `N${i}`);
+            if (i === 1) {
+                should.ok(res.wasAdded);
+                should.ok(!res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual('N1', res.iterator.value);
+            }
+            else {
+                should.ok(!res.wasAdded);
+                should.ok(!res.wasReplaced);
+            }
+        }
+        should.equal(1, m.size);
 
@@ -244,7 +343,20 @@ done();
 
-    it('insertOrReplace', function(done) {
-        let map = new TreeMap();
-        map.insertOrReplace(1, 'A');
-        map.insertOrReplace(1, 'B');
-        should.equal('B', map.get(1));
+    it('insertOrUpdate', function(done) {
+        let m = new TreeMap();
+        for (let i = 1; i < 4; ++i) {
+            let res = m.insertOrReplace(1, `N${i}`);
+            if (i === 1) {
+                should.ok(res.wasAdded);
+                should.ok(!res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual(`N${i}`, res.iterator.value);
+            }
+            else {
+                should.ok(!res.wasAdded);
+                should.ok(res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual(`N${i}`, res.iterator.value);
+            }
+        }
+        should.equal(1, m.size);
 
@@ -251,0 +363,0 @@ done();

test/test-tree.js

@@ -1336,2 +1336,70 @@ 'use strict';
 
+    it('insertUnique', function(done) {
+        let t = new Tree();
+        t.valuePolicy = new KeyValuePolicy();
+        for (let i = 1; i < 4; ++i) {
+            let n = new TreeNode();
+            n.key = 1;
+            n.value = `N${i}`;
+            let res = t.insertUnique(n);
+            if (i === 1) {
+                should.ok(res.wasAdded);
+                should.ok(!res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual('N1', res.iterator.value);
+            }
+            else {
+                should.ok(!res.wasAdded);
+                should.ok(!res.wasReplaced);
+            }
+        }
+        should.equal(1, t.size());
+
+        done();
+    });
+
+    it('insertOrUpdate', function(done) {
+        let t = new Tree();
+        t.valuePolicy = new KeyValuePolicy();
+        for (let i = 1; i < 4; ++i) {
+            let n = new TreeNode();
+            n.key = 1;
+            n.value = `N${i}`;
+            let res = t.insertOrReplace(n);
+            if (i === 1) {
+                should.ok(res.wasAdded);
+                should.ok(!res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual(`N${i}`, res.iterator.value);
+            }
+            else {
+                should.ok(!res.wasAdded);
+                should.ok(res.wasReplaced);
+                should.strictEqual(1, res.iterator.key);
+                should.strictEqual(`N${i}`, res.iterator.value);
+            }
+        }
+        should.equal(1, t.size());
+
+        done();
+    });
+
+    it('insertMulti', function(done) {
+        let t = new Tree();
+        t.valuePolicy = new KeyValuePolicy();
+        for (let i = 1; i < 4; ++i) {
+            let n = new TreeNode();
+            n.key = 1;
+            n.value = `N${i}`;
+            let res = t.insertMulti(n);
+            should.ok(res.wasAdded);
+            should.ok(!res.wasReplaced);
+            should.strictEqual(1, res.iterator.key);
+            should.strictEqual(`N${i}`, res.iterator.value);
+        }
+        should.equal(3, t.size());
+
+        done();
+    });
+
     it('insertMulti; lowerBound/upperBound range; same values', function(done) {
@@ -1359,3 +1427,3 @@ let t = new Tree();
 
-    it('insertUnique; lowerBound/upperBound range; same values', function(done) {
+    it('insertMulti; lowerBound/upperBound range; same values', function(done) {
         let t = new Tree();
@@ -1379,2 +1447,3 @@ t.valuePolicy = new KeyValuePolicy();
         should.deepEqual(expected, actual);
+        should.equal(1, t.size());
 
@@ -1403,2 +1472,3 @@ done();
         should.deepEqual(expected, actual);
+        should.equal(1, t.size());
 
@@ -1405,0 +1475,0 @@ done();

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Mixed license

License

(Experimental) Package contains multiple licenses.

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

Mixed license

License

(Experimental) Package contains multiple licenses.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

12174334

increased by8593.1%

Number of package files

90

increased by350%

Lines of code

234034

increased by5688.62%

Number of lines in readme file

57

increased by1800%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes