From 49b3a5cf1ea2d7ed3f1bf9c1262ee92d66a83a7d Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Wed, 25 May 2022 00:32:15 -0500
Subject: begin KDTree implementation

---
 modules/KDTree.js      | 33 +++++++++++++++++++++++++++++++++
 modules/KDTree.test.js | 12 ++++++++++++
 2 files changed, 45 insertions(+)
 create mode 100644 modules/KDTree.js
 create mode 100644 modules/KDTree.test.js

(limited to 'modules')

diff --git a/modules/KDTree.js b/modules/KDTree.js
new file mode 100644
index 0000000..d9133d1
--- /dev/null
+++ b/modules/KDTree.js
@@ -0,0 +1,33 @@
+'use strict';
+
+class NodeType {
+	static Leaf = new NodeType('Leaf');
+	static Branch = new NodeType('Branch');
+
+	constructor(name) { this.name = name; }
+	toString() { return `NodeType.${this.name}`; }
+}
+
+
+class LeafNode {
+	constructor(point) {
+		this.type = NodeType.Leaf;
+		this.point = point;
+	}
+}
+class BranchNode {
+}
+
+
+class KDTree {
+	constructor() {
+		this.root = null;
+	}
+
+	insert(point) {
+		this.root = new LeafNode(point);
+	}
+}
+
+export { KDTree, NodeType, LeafNode, BranchNode };
+export default KDTree;
diff --git a/modules/KDTree.test.js b/modules/KDTree.test.js
new file mode 100644
index 0000000..4e2657b
--- /dev/null
+++ b/modules/KDTree.test.js
@@ -0,0 +1,12 @@
+import { test, assert } from './test-assert.js';
+
+import { KDTree, NodeType } from './KDTree.js';
+
+test('single point does not split tree', () => {
+	let tree = new KDTree();
+	tree.insert({x: 0.5, y: 0.5 });
+	assert.deepEqual(tree.root.type, NodeType.Leaf);
+	assert.ok(tree.root.point);
+	assert(tree.root.point.x = 0.5);
+	assert(tree.root.point.y = 0.5);
+});
-- 
cgit v1.2.1