maxLen -> branchingFactor

tonsky · Jul 27, 2023 · a4ec73e · a4ec73e
1 parent 958c672
commit a4ec73e
Show file tree

Hide file tree

Showing 6 changed files with 52 additions and 51 deletions.
diff --git a/project.clj b/project.clj
@@ -14,7 +14,7 @@
   :java-source-paths ["src-java"]
   :test-paths        ["test-clojure"]
 
-  :javac-options ["-target" "8" "-source" "8" "-bootclasspath" ~(str (or (System/getenv "JAVA8_HOME") (throw (Exception. "Please set JAVA8_HOME"))) "/jre/lib/rt.jar")]
+  :javac-options ["-Xlint:unchecked" "-Xlint:-options" "-target" "8" "-source" "8" "-bootclasspath" ~(str (or (System/getenv "JAVA8_HOME") (throw (Exception. "Please set JAVA8_HOME"))) "/jre/lib/rt.jar")]
   :jvm-opts ["-ea"]
 
   :profiles

diff --git a/src-clojure/me/tonsky/persistent_sorted_set.clj b/src-clojure/me/tonsky/persistent_sorted_set.clj
@@ -82,19 +82,19 @@
 
 (defn- map->settings ^Settings [m]
   (Settings.
-    (int (or (:max-len m) 0))
+    (int (or (:branching-factor m) 0))
     (case (:ref-type m)
       :strong RefType/STRONG
       :soft   RefType/SOFT
       :weak   RefType/WEAK
       nil)))
 
 (defn- settings->map [^Settings s]
-  {:max-len  (.maxLen s)
-   :ref-type (condp identical? (.refType s)
-               RefType/STRONG :strong
-               RefType/SOFT   :soft
-               RefType/WEAK   :weak)})
+  {:branching-factor (.branchingFactor s)
+   :ref-type         (condp identical? (.refType s)
+                       RefType/STRONG :strong
+                       RefType/SOFT   :soft
+                       RefType/WEAK   :weak)})
 
 (defn from-sorted-array
   "Fast path to create a set if you already have a sorted array of elements on your hands."
@@ -103,26 +103,26 @@
   ([^Comparator cmp keys len]
    (from-sorted-array cmp keys len (Settings.)))
   ([^Comparator cmp keys len opts]
-   (let [settings  (map->settings opts)
-         max       (.maxLen settings)
-         avg       (-> (.minLen settings) (+ max) (quot 2))
-         storage   nil
-         ->Leaf    (fn [keys]
-                     (Leaf. (count keys) keys settings))
-         ->Branch  (fn [level ^objects children]
-                     (Branch.
-                       level
-                       (count children)
-                       ^objects (arrays/amap #(.maxKey ^ANode %) Object children)
-                       nil
-                       children
-                       settings))]
+   (let [settings             (map->settings opts)
+         max-branching-factor (.branchingFactor settings)
+         avg-branching-factor (-> (.minBranchingFactor settings) (+ max-branching-factor) (quot 2))
+         storage              nil
+         ->Leaf               (fn [keys]
+                                (Leaf. (count keys) keys settings))
+         ->Branch             (fn [level ^objects children]
+                                (Branch.
+                                  level
+                                  (count children)
+                                  ^objects (arrays/amap #(.maxKey ^ANode %) Object children)
+                                  nil
+                                  children
+                                  settings))]
      (loop [level 1
-            nodes (mapv ->Leaf (split keys len Object avg max))]
+            nodes (mapv ->Leaf (split keys len Object avg-branching-factor max-branching-factor))]
        (case (count nodes)
          0 (PersistentSortedSet. {} cmp settings)
          1 (PersistentSortedSet. {} cmp nil storage (first nodes) len settings 0)
-         (recur (inc level) (mapv #(->Branch level %) (split nodes (count nodes) Object avg max))))))))
+         (recur (inc level) (mapv #(->Branch level %) (split nodes (count nodes) Object avg-branching-factor max-branching-factor))))))))
 
 (defn from-sequential
   "Create a set with custom comparator and a collection of keys. Useful when you don’t want to call [[clojure.core/apply]] on [[sorted-set-by]]."

diff --git a/src-java/me/tonsky/persistent_sorted_set/ANode.java b/src-java/me/tonsky/persistent_sorted_set/ANode.java
@@ -123,7 +123,7 @@ public String toString() {
 
   protected static int newLen(int len, Settings settings) {
     if (settings.editable())
-        return Math.min(settings.maxLen(), len + settings.expandLen());
+        return Math.min(settings.branchingFactor(), len + settings.expandLen());
     else
         return len;
   }

diff --git a/src-java/me/tonsky/persistent_sorted_set/Branch.java b/src-java/me/tonsky/persistent_sorted_set/Branch.java
@@ -213,7 +213,7 @@ public ANode[] add(IStorage storage, Key key, Comparator<Key> cmp, Settings sett
     }
 
     // len + 1
-    if (_len < _settings.maxLen()) {
+    if (_len < _settings.branchingFactor()) {
       Branch n = new Branch(_level, _len + 1, settings);
       new Stitch(n._keys, 0)
         .copyAll(_keys, 0, ins)
@@ -367,7 +367,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
                  + (nodes[2] != null ? 1 : 0);
 
     // no rebalance needed
-    if (newLen >= _settings.minLen() || (left == null && right == null)) {
+    if (newLen >= _settings.minBranchingFactor() || (left == null && right == null)) {
       // can update in place
       if (editable() && idx < _len-2) {
         Stitch ks = new Stitch(_keys, Math.max(idx-1, 0));
@@ -428,7 +428,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
     }
 
     // can join with left
-    if (left != null && left._len + newLen <= _settings.maxLen()) {
+    if (left != null && left._len + newLen <= _settings.branchingFactor()) {
       Branch join = new Branch(_level, left._len + newLen, settings);
 
       Stitch ks = new Stitch(join._keys, 0);
@@ -462,7 +462,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
     }
 
     // can join with right
-    if (right != null && newLen + right._len <= _settings.maxLen()) {
+    if (right != null && newLen + right._len <= _settings.branchingFactor()) {
       Branch join = new Branch(_level, newLen + right._len, settings);
 
       Stitch ks = new Stitch(join._keys, 0);

diff --git a/src-java/me/tonsky/persistent_sorted_set/Leaf.java b/src-java/me/tonsky/persistent_sorted_set/Leaf.java
@@ -57,7 +57,7 @@ public ANode[] add(IStorage storage, Key key, Comparator<Key> cmp, Settings sett
     }
 
     // simply adding to array
-    if (_len < _settings.maxLen()) {
+    if (_len < _settings.branchingFactor()) {
       ANode n = new Leaf(_len + 1, settings);
       new Stitch(n._keys, 0)
         .copyAll(_keys, 0, ins)
@@ -105,7 +105,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
     int newLen = _len - 1;
 
     // nothing to merge
-    if (newLen >= _settings.minLen() || (left == null && right == null)) {
+    if (newLen >= _settings.minBranchingFactor() || (left == null && right == null)) {
 
       // transient, can edit in place
       if (editable()) {
@@ -125,7 +125,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
     }
 
     // can join with left
-    if (left != null && left._len + newLen <= _settings.maxLen()) {
+    if (left != null && left._len + newLen <= _settings.branchingFactor()) {
       Leaf join = new Leaf(left._len + newLen, settings);
       new Stitch(join._keys, 0)
         .copyAll(left._keys, 0,       left._len)
@@ -135,7 +135,7 @@ public ANode[] remove(IStorage storage, Key key, ANode _left, ANode _right, Comp
     }
 
     // can join with right
-    if (right != null && newLen + right.len() <= _settings.maxLen()) {
+    if (right != null && newLen + right.len() <= _settings.branchingFactor()) {
       Leaf join = new Leaf(newLen + right._len, settings);
       new Stitch(join._keys, 0)
         .copyAll(_keys,       0,       idx)

diff --git a/src-java/me/tonsky/persistent_sorted_set/Settings.java b/src-java/me/tonsky/persistent_sorted_set/Settings.java
@@ -4,46 +4,46 @@
 import java.util.concurrent.atomic.*;
 
 public class Settings {
-  public final int _maxLen;
+  public final int _branchingFactor;
   public final RefType _refType;
   public final AtomicBoolean _edit;
 
-  public Settings(int maxLen, RefType refType, AtomicBoolean edit) {
-    _maxLen = maxLen;
+  public Settings(int branchingFactor, RefType refType, AtomicBoolean edit) {
+    _branchingFactor = branchingFactor;
     _refType = refType;
     _edit = edit;
   }
 
   public Settings() {
-    _maxLen = 64;
+    _branchingFactor = 64;
     _refType = RefType.SOFT;
     _edit = null;
   }
 
-  public Settings(int maxLen) {
-    _maxLen = maxLen;
+  public Settings(int branchingFactor) {
+    _branchingFactor = branchingFactor;
     _refType = RefType.SOFT;
     _edit = null;
   }
 
-  public Settings(int maxLen, RefType refType) {
-    if (maxLen <= 0) {
-      maxLen = 64;
+  public Settings(int branchingFactor, RefType refType) {
+    if (branchingFactor <= 0) {
+      branchingFactor = 64;
     }
     if (null == refType) {
       refType = RefType.SOFT;
     }
-    _maxLen = maxLen;
+    _branchingFactor = branchingFactor;
     _refType = refType;
     _edit = null;
   }
 
-  public int minLen() {
-    return _maxLen >>> 1;
+  public int minBranchingFactor() {
+    return _branchingFactor >>> 1;
   }
 
-  public int maxLen() {
-    return _maxLen;
+  public int branchingFactor() {
+    return _branchingFactor;
   }
 
   public int expandLen() {
@@ -61,24 +61,25 @@ public boolean editable() {
   public Settings editable(boolean value) {
     assert !editable();
     assert value == true;
-    return new Settings(_maxLen, _refType, new AtomicBoolean(value));
+    return new Settings(_branchingFactor, _refType, new AtomicBoolean(value));
   }
 
   public void persistent() {
     assert _edit != null;
     _edit.set(false);
   }
 
-  public Object makeReference(Object value) {
+  public <T> Object makeReference(T value) {
     switch (_refType) {
     case STRONG:
       return value;
     case SOFT:
-      return new SoftReference(value);
+      return new SoftReference<T>(value);
     case WEAK:
-      return new WeakReference(value);
+      return new WeakReference<T>(value);
+    default:
+      throw new RuntimeException("Unexpected _refType: " + _refType);
     }
-    throw new RuntimeException("Unexpected _refType: " + _refType);
   }
 
   public Object readReference(Object ref) {