fix(associative): #375 major update/rewrite SortedMap impl

- update Node impl to use 4-way linkage - simplify .set()/.delete() impls - remove obsolete SortedMapOpts.capacity - add SortedMapOpts.rnd to customize IRandom impl (e.g. for reproducible behavior/branching) - update tests - update deps (add thi.ng/random)
thi-ng · Feb 4, 2023 · d5f793a · d5f793a
1 parent 80ec39b
commit d5f793a
Show file tree

Hide file tree

Showing 6 changed files with 179 additions and 161 deletions.
diff --git a/packages/associative/package.json b/packages/associative/package.json
@@ -42,6 +42,7 @@
 		"@thi.ng/dcons": "^3.2.30",
 		"@thi.ng/equiv": "^2.1.17",
 		"@thi.ng/errors": "^2.2.8",
+		"@thi.ng/random": "^3.3.21",
 		"@thi.ng/transducers": "^8.3.30",
 		"tslib": "^2.5.0"
 	},

diff --git a/packages/associative/src/api.ts b/packages/associative/src/api.ts
@@ -9,6 +9,7 @@ import type {
 	IInto,
 	Predicate2,
 } from "@thi.ng/api";
+import type { IRandom } from "@thi.ng/random";
 
 export interface IEquivSet<T>
 	extends Set<T>,
@@ -105,20 +106,20 @@ export interface SortedMapOpts<K> {
 	 * [`compare()`](https://docs.thi.ng/umbrella/compare/functions/compare.html)
 	 */
 	compare: Comparator<K>;
-	/**
-	 * Initial capacity before resizing (doubling) occurs.
-	 * This value will be rounded up to next pow2.
-	 *
-	 * @defaultValue 8
-	 */
-	capacity: number;
 	/**
 	 * Probability for a value to exist in any express lane of the
 	 * underlying Skip List implementation.
 	 *
 	 * @defaultValue `1 / Math.E`
 	 */
 	probability: number;
+	/**
+	 * Random number generator for choosing new insertion levels. By default
+	 * uses
+	 * [`SYSTEM`](https://docs.thi.ng/umbrella/random/variables/SYSTEM.html)
+	 * from thi.ng/random pkg.
+	 */
+	rnd: IRandom;
 }
 
 export type SortedSetOpts<T> = SortedMapOpts<T>;