1const chai = require("chai");
  2
  3const bigInt = require("big-integer");
  4
  5const smt = require("../src/smt.js");
  6
  7const assert = chai.assert;
  8
  9
 10function stringifyBigInts(o) {
 11    if ((typeof(o) == "bigint") || (o instanceof bigInt))  {
 12        return o.toString(10);
 13    } else if (Array.isArray(o)) {
 14        return o.map(stringifyBigInts);
 15    } else if (typeof o == "object") {
 16        const res = {};
 17        for (let k in o) {
 18            res[k] = stringifyBigInts(o[k]);
 19        }
 20        return res;
 21    } else {
 22        return o;
 23    }
 24}
 25
 26describe("SMT Javascript test", function () {
 27    this.timeout(100000);
 28    before( async () => {
 29    });
 30
 31    it("Should insert 2 elements and empty them", async () => {
 32        const tree = await smt.newMemEmptyTrie();
 33        const key1 = bigInt(111);
 34        const value1 = bigInt(222);
 35        const key2 = bigInt(333);
 36        const value2 = bigInt(444);
 37
 38        await tree.insert(key1,value1);
 39        await tree.insert(key2,value2);
 40        await tree.delete(key2);
 41        await tree.delete(key1);
 42
 43        assert(tree.root.isZero());
 44    });
 45
 46    it("Should insert 3 elements in dferent order and should be the same", async () => {
 47        const keys = [bigInt(8), bigInt(9), bigInt(32)];
 48        const values = [bigInt(88), bigInt(99), bigInt(3232)];
 49        const tree1 = await smt.newMemEmptyTrie();
 50        const tree2 = await smt.newMemEmptyTrie();
 51        const tree3 = await smt.newMemEmptyTrie();
 52        const tree4 = await smt.newMemEmptyTrie();
 53        const tree5 = await smt.newMemEmptyTrie();
 54        const tree6 = await smt.newMemEmptyTrie();
 55
 56        await tree1.insert(keys[0],values[0]);
 57        await tree1.insert(keys[1],values[1]);
 58        await tree1.insert(keys[2],values[2]);
 59
 60        await tree2.insert(keys[0],values[0]);
 61        await tree2.insert(keys[2],values[2]);
 62        await tree2.insert(keys[1],values[1]);
 63
 64        await tree3.insert(keys[1],values[1]);
 65        await tree3.insert(keys[0],values[0]);
 66        await tree3.insert(keys[2],values[2]);
 67
 68        await tree4.insert(keys[1],values[1]);
 69        await tree4.insert(keys[2],values[2]);
 70        await tree4.insert(keys[0],values[0]);
 71
 72        await tree5.insert(keys[2],values[2]);
 73        await tree5.insert(keys[0],values[0]);
 74        await tree5.insert(keys[1],values[1]);
 75
 76        await tree6.insert(keys[2],values[2]);
 77        await tree6.insert(keys[1],values[1]);
 78        await tree6.insert(keys[0],values[0]);
 79
 80        assert(tree1.root.equals(tree2.root));
 81        assert(tree2.root.equals(tree3.root));
 82        assert(tree3.root.equals(tree4.root));
 83        assert(tree4.root.equals(tree5.root));
 84        assert(tree5.root.equals(tree6.root));
 85
 86        assert.equal(Object.keys(tree1.db.nodes).length,  Object.keys(tree2.db.nodes).length);
 87        assert.equal(Object.keys(tree2.db.nodes).length,  Object.keys(tree3.db.nodes).length);
 88        assert.equal(Object.keys(tree3.db.nodes).length,  Object.keys(tree4.db.nodes).length);
 89        assert.equal(Object.keys(tree4.db.nodes).length,  Object.keys(tree5.db.nodes).length);
 90        assert.equal(Object.keys(tree5.db.nodes).length,  Object.keys(tree6.db.nodes).length);
 91
 92        await tree1.delete(keys[0]);
 93        await tree1.delete(keys[1]);
 94        await tree2.delete(keys[1]);
 95        await tree2.delete(keys[0]);
 96        assert(tree1.root.equals(tree2.root));
 97
 98        await tree3.delete(keys[0]);
 99        await tree3.delete(keys[2]);
100        await tree4.delete(keys[2]);
101        await tree4.delete(keys[0]);
102        assert(tree3.root.equals(tree4.root));
103
104        await tree5.delete(keys[1]);
105        await tree5.delete(keys[2]);
106        await tree6.delete(keys[2]);
107        await tree6.delete(keys[1]);
108        assert(tree5.root.equals(tree6.root));
109
110        await tree1.delete(keys[2]);
111        await tree2.delete(keys[2]);
112        await tree3.delete(keys[1]);
113        await tree4.delete(keys[1]);
114        await tree5.delete(keys[0]);
115        await tree6.delete(keys[0]);
116
117        assert(tree1.root.isZero());
118        assert(tree2.root.isZero());
119        assert(tree3.root.isZero());
120        assert(tree4.root.isZero());
121        assert(tree5.root.isZero());
122        assert(tree6.root.isZero());
123
124        assert.equal(Object.keys(tree1.db.nodes).length, 0);
125        assert.equal(Object.keys(tree2.db.nodes).length, 0);
126        assert.equal(Object.keys(tree3.db.nodes).length, 0);
127        assert.equal(Object.keys(tree4.db.nodes).length, 0);
128        assert.equal(Object.keys(tree5.db.nodes).length, 0);
129        assert.equal(Object.keys(tree6.db.nodes).length, 0);
130    });
131
132    it("Insert and remove 100 numbers randomly", async () => {
133        function perm(a) {
134            const arr = a.slice();
135            const rArr = [];
136            for (let i=0; i<arr.length; i++) {
137                let rIdx = Math.floor(Math.random() * (arr.length - i));
138                rArr.push(arr[rIdx]);
139                arr[rIdx] = arr[arr.length - i - 1];
140            }
141            return rArr;
142        }
143        const tree = await smt.newMemEmptyTrie();
144        const arr = [];
145        const N = 100;
146        for (let i=0; i<N; i++) {
147            arr.push(bigInt(i));
148        }
149        const insArr = perm(arr);
150        for (let i=0; i<N; i++) {
151            await tree.insert(insArr[i], i);
152        }
153        const delArr = perm(insArr);
154        for (let i=0; i<N; i++) {
155            await tree.delete(delArr[i]);
156        }
157
158        assert(tree.root.isZero());
159        assert.equal(Object.keys(tree.db.nodes).length, 0);
160    });
161
162    it("Should test update", async () => {
163        const tree1 = await smt.newMemEmptyTrie();
164        const tree2 = await smt.newMemEmptyTrie();
165
166        await tree1.insert(8,88);
167        await tree1.insert(9,99,);
168        await tree1.insert(32,3232);
169
170        await tree2.insert(8,888);
171        await tree2.insert(9,999);
172        await tree2.insert(32,323232);
173
174        await tree1.update(8, 888);
175        await tree1.update(9, 999);
176        await tree1.update(32, 323232);
177
178        assert(tree1.root.equals(tree2.root));
179    });
180
181});