Radix tree, or trie's

.gitignore

node_modules

README.md

package.json

{
  "name": "radixtree",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "devDependencies": {
    "@types/jest": "^24.0.9",
    "@types/node": "^11.9.5",
    "jest": "^24.1.0",
    "ts-jest": "^24.0.0",
    "typescript": "^3.3.3333"
  },
  "scripts": {
    "test": "jest"
  },
  "author": "",
  "license": "ISC",
  "jest": {
    "moduleFileExtensions": [
      "ts",
      "js"
    ],
    "transform": {
      "\\.ts$": "ts-jest"
    }
  }
}

reference.cpp

/**
 * Reference implementation
 * @see http://yuanyuanzhangcs.blogspot.com/2017/02/trie-serialization.html
 *
 * Definition of TrieNode:
 * class TrieNode {
 * public:
 *     TrieNode() {}
 *     map<char, TrieNode*> children;
 * };
 */

class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm
     * to serialize a trie which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */

    string serialize(TrieNode* root) {
        string result;
        if(!root)
            return result;
        result += "<";
        for(char c = 'a'; c <= 'z'; c++){
            if(root->children.find(c) != root->children.end()){
                result += string(1, c);
                result += serialize(root->children[c]);
            }
        }
        result += ">";
        return result;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    TrieNode* deserialize(string data) {
        if(data.empty())
            return NULL;
        TrieNode* root = new TrieNode();
        TrieNode* current = root;
        stack<TrieNode*> stk;
        for(char c: data){
            switch(c){
                case '<':
                    stk.push(current);
                    break;
               
                case '>':
                    stk.pop();
                    break;
                default:
                    current = new TrieNode();
                    stk.top()->children[c] = current;
            }
        }
        return root;
   }
};

trie.spec.ts

import { put, TrieNode, lookup, serialize, deserialize } from "./trie";
import { randomBytes } from "crypto";

describe("Trie", () => {
	describe("put", () => {
		it("creates a leaf node", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			expect(node).toMatchSnapshot()
		})
		it("splits nodes", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0123456789abcdee", 2)
			expect(node.children).toHaveProperty("0123456789abcd.children.ef.value", 1)
			expect(node.children).toHaveProperty("0123456789abcd.children.ee.value", 2)
			expect(node).toMatchSnapshot()
		})
		it("splits nodes twice", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0123456789abcdee", 2)
			put(node, "0123455789abcdee", 3)
			expect(node.children).toHaveProperty("012345.children.5789abcdee.value", 3)
			expect(node.children).toHaveProperty("012345.children.6789abcd.children.ef.value", 1)
			expect(node.children).toHaveProperty("012345.children.6789abcd.children.ee.value", 2)
			expect(node).toMatchSnapshot()
		})
		it("splits deeply", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0124456789abcdef", 2)
			put(node, "0124466789abcdef", 3)
			expect(node.children).toHaveProperty("01.children.23456789abcdef.value", 1)
			expect(node.children).toHaveProperty("01.children.24.children.456789abcdef.value", 2)
			expect(node.children).toHaveProperty("01.children.24.children.466789abcdef.value", 3)
			expect(node).toMatchSnapshot()
		})
		it("overwrites values", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0123456789abcdee", 2)
			put(node, "0123456789abcdee", 3)
			expect(node.children).toHaveProperty("0123456789abcd.children.ef.value", 1)
			expect(node.children).toHaveProperty("0123456789abcd.children.ee.value", 3)
			expect(node).toMatchSnapshot()
		})
	})
	describe("lookup", () => {
		it("looks up a leaf node", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			expect(lookup(node, "0123456789abcdef").value).toEqual(1)
		})
		it("looks up a leaf node", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0123456789abcdee", 2)
			put(node, "0123455789abcdee", 3)
			expect(lookup(node, "0123456789abcdee").value).toEqual(2)
		})
	})
	describe("remove", () => {
	
	})

	describe("serialization", () => {
		it("reads back what it writes", () => {
			const node = new TrieNode()
			put(node, "0123456789abcdef", 1)
			put(node, "0124456789abcdef", 2)
			put(node, "0124466789abcdef", 3)
			expect(node).toMatchSnapshot("before")
			let buffer = Buffer.alloc(0);
			serialize(node, (...bytes) => buffer = Buffer.concat([buffer, new Uint8Array(bytes)]))
			expect(buffer.toString("hex")).toMatchSnapshot()
			const [result] = deserialize([...buffer.values()])
			expect(result).toMatchSnapshot("after")
			expect(result).toEqual(node)
		})
	})

	describe("random data", () => {
		it("writes", () => {
			let comparison = Buffer.alloc(0)
			const node = new TrieNode()
			for (let i = 0; i < 3000; i++) {
				const bridgeId = "001788ff"+randomBytes(4).toString("hex");
				comparison = Buffer.concat([comparison, Buffer.from(bridgeId, "hex"), Buffer.from([i % 255])]);
				put(node, bridgeId, i)
			}
			let buffer = Buffer.alloc(0);
			serialize(node, (...bytes) => buffer = Buffer.concat([buffer, new Uint8Array(bytes)]))
			console.log({
				comparison: comparison.length,
				buffer: buffer.length,
			})
			expect(comparison.length).toBeGreaterThan(buffer.length);
			// expect(buffer.toString("hex")).toMatchSnapshot()
		})
	})

})

trie.spec.ts.snap

// Jest Snapshot v1, https://goo.gl/fbAQLP

exports[`Trie put creates a leaf node 1`] = `
TrieNode {
  "children": Object {
    "0123456789abcdef": TrieNode {
      "children": Object {},
      "value": 1,
    },
  },
  "value": undefined,
}
`;

exports[`Trie put overwrites values 1`] = `
TrieNode {
  "children": Object {
    "0123456789abcd": TrieNode {
      "children": Object {
        "ee": TrieNode {
          "children": Object {},
          "value": 3,
        },
        "ef": TrieNode {
          "children": Object {},
          "value": 1,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

exports[`Trie put splits deeply 1`] = `
TrieNode {
  "children": Object {
    "01": TrieNode {
      "children": Object {
        "23456789abcdef": TrieNode {
          "children": Object {},
          "value": 1,
        },
        "24": TrieNode {
          "children": Object {
            "456789abcdef": TrieNode {
              "children": Object {},
              "value": 2,
            },
            "466789abcdef": TrieNode {
              "children": Object {},
              "value": 3,
            },
          },
          "value": undefined,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

exports[`Trie put splits nodes 1`] = `
TrieNode {
  "children": Object {
    "0123456789abcd": TrieNode {
      "children": Object {
        "ee": TrieNode {
          "children": Object {},
          "value": 2,
        },
        "ef": TrieNode {
          "children": Object {},
          "value": 1,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

exports[`Trie put splits nodes twice 1`] = `
TrieNode {
  "children": Object {
    "012345": TrieNode {
      "children": Object {
        "5789abcdee": TrieNode {
          "children": Object {},
          "value": 3,
        },
        "6789abcd": TrieNode {
          "children": Object {
            "ee": TrieNode {
              "children": Object {},
              "value": 2,
            },
            "ef": TrieNode {
              "children": Object {},
              "value": 1,
            },
          },
          "value": undefined,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

exports[`Trie serialization reads back what it writes 1`] = `"0101010201240206466789abcdef01000306456789abcdef0100020723456789abcdef010001"`;

exports[`Trie serialization reads back what it writes: after 1`] = `
TrieNode {
  "children": Object {
    "01": TrieNode {
      "children": Object {
        "23456789abcdef": TrieNode {
          "children": Object {},
          "value": 1,
        },
        "24": TrieNode {
          "children": Object {
            "456789abcdef": TrieNode {
              "children": Object {},
              "value": 2,
            },
            "466789abcdef": TrieNode {
              "children": Object {},
              "value": 3,
            },
          },
          "value": undefined,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

exports[`Trie serialization reads back what it writes: before 1`] = `
TrieNode {
  "children": Object {
    "01": TrieNode {
      "children": Object {
        "23456789abcdef": TrieNode {
          "children": Object {},
          "value": 1,
        },
        "24": TrieNode {
          "children": Object {
            "456789abcdef": TrieNode {
              "children": Object {},
              "value": 2,
            },
            "466789abcdef": TrieNode {
              "children": Object {},
              "value": 3,
            },
          },
          "value": undefined,
        },
      },
      "value": undefined,
    },
  },
  "value": undefined,
}
`;

trie.ts

const SIZE = 16;

export class TrieNode {
	constructor(value?: number) {
		this.value = value;
	}
	// Either children...
	public children: { [edge: string]: TrieNode } = {};
	// ... or value
	public value?: number;
}

export function put(node: TrieNode, key: string, value: TrieNode | number) {
	// console.log("put", node, key, value);
	if (key.length === 0) {
		if (typeof value === "number") {
			node.value = value;
		} else {
			node.value = value.value;
			node.children = value.children;
		}
		return;
	}
	if (typeof value === "number") {
		value = new TrieNode(value);
	}
	for (const edge in node.children) {
		// Descend
		if (edge.length > 0 && key.length >= edge.length) {
			if (key.startsWith(edge)) {
				const suffix = key.substr(edge.length);
				// console.log("dive", edge, suffix);
				return put(node.children[edge], suffix, value);
			}
			let same = 0;
			while (key.substr(same, 2) === edge.substr(same, 2)) { same+=2; }
			// Split
			if (same > 0) {
				const common = edge.substr(0, same);
				const partA = key.substr(same);
				const partB = edge.substr(same);
				// console.log("split", common, partA, partB);
				const rest = node.children[edge];
				delete node.children[edge];
				node.children[common] = new TrieNode();
				put(node.children[common], partA, value);
				put(node.children[common], partB, rest);
				return;
			}
		}
	}
	// Set leaf
	node.children[key] = value;
}

export function remove(node: TrieNode, key: string): number {
	if (key.length === 0) {
		delete node.value;
		return Object.keys(this.children).length;
	}
	let hasRemoved = 0;
	for (const edge in node.children) {
		const child = node.children[edge];
		if (key.startsWith(edge)) {
			const suffix = key.substr(edge.length);
			hasRemoved = remove(child, suffix);
			if (hasRemoved === 1 && typeof child.value === "undefined") {
				// Collapse
				node.children[edge + suffix] = lookup(child, suffix);
				delete node.children[edge];
			}
			if (hasRemoved === 0) {
				// Collapse
				delete node.children[edge];
			}
		}
	}
	return Object.keys(node.children).length;
}

export function lookup(node: TrieNode, key: string): TrieNode | undefined {
	if (key.length === 0) {
		return node;
	}
	for (const edge in node.children) {
		if (key.startsWith(edge)) {
			const suffix = key.substr(edge.length);
			return lookup(node.children[edge], suffix);
		}
	}
}

export function serialize(root: TrieNode, out: (...bytes: number[]) => void) {
	const keys = Object.keys(root.children);
	if (typeof root.value !== "undefined") {
		out(keys.length + 1);
		out(0, root.value);
	} else {
		out(keys.length);
	}

	keys.forEach((edge) => {
		const child = root.children[edge];
		const bytes = Buffer.from(edge, "hex");
		out(bytes.length, ...bytes);
		serialize(child, out);
	});
}

export function deserialize(data: number[]): [TrieNode, number] {
	const current = new TrieNode();
	let cursor = 0;

	const keysLength = data[cursor++];
	for (let k = 0; k < keysLength; k++) {
		const edgeLength = data[cursor++];
		if (edgeLength === 0) {
			current.value = data[cursor++];
			continue;
		}
		const edge = data.slice(cursor, cursor + edgeLength);
		cursor += edgeLength;
		const  [child, cursorIncrement] = deserialize(data.slice(cursor));
		cursor += cursorIncrement;
		current.children[Buffer.from(edge).toString("hex")] = child;
	}

	return [current, cursor];
}

tsconfig.json

{
	"compilerOptions": {
		"target": "es6",
		"moduleResolution": "node",
		"lib": ["scripthost", "es2015"],
	}
}