partial.lenses - npm Package Compare versions

Comparing version 1.3.0 to 1.3.1

package.json

 {
   "name": "partial.lenses",
-  "version": "1.3.0",
+  "version": "1.3.1",
   "description": "Ramda compatible partial lenses",
@@ -5,0 +5,0 @@ "main": "lib/partial.lenses.js",

README.md

@@ -265,4 +265,5 @@ [ [Tutorial](#tutorial) | [Reference](#reference) | [Background](#background) ]
 const binarySearch = key =>
-  L(L.default({key}),
-    L.normalize(node => {
+  L(L.normalize(node => {
+      if (!node)
+        return node
       if ("value" in node)
@@ -274,4 +275,6 @@ return node
         return node.greater
-      return node
-    }),
+      return L.set(binarySearch(node.smaller.key),
+                   node.smaller,
+                   node.greater)}),
+    L.default({key}),
     L.choose(node =>
@@ -288,7 +291,7 @@ key < node.key ? L("smaller", binarySearch(key)) :
 { greater: { value: 3, key: 'b' }, value: 2, key: 'a' }
-
 ```
 
 As an exercise you could improve the normalization to maintain some balance
-condition such as AVL.
+condition such as AVL.  Another worthy exercise would be to make it so that the
+empty binary tree is `null` rather than `undefined`.
 
@@ -295,0 +298,0 @@ ## Reference

test/tests.js

@@ -156,1 +156,63 @@ import R from "ramda"
 })
+
+const BST = {
+  search: key =>
+    L(L.normalize(node => {
+      if (!node)
+        return node
+      if ("value" in node)
+        return node
+      if (!("greater" in node) && "smaller" in node)
+        return node.smaller
+      if (!("smaller" in node) && "greater" in node)
+        return node.greater
+      return L.set(BST.search(node.smaller.key),
+                   node.smaller,
+                   node.greater)}),
+      L.default({key}),
+      L.choose(node =>
+               key < node.key ? L("smaller", BST.search(key)) :
+               node.key < key ? L("greater", BST.search(key)) :
+                                L.identity)),
+  valueOf: key => L(BST.search(key), "value"),
+  isValid: (node, keyPred = () => true) =>
+    undefined === node
+    || "key" in node
+    && "value" in node
+    && keyPred(node.key)
+    && BST.isValid(node.smaller, key => key < node.key)
+    && BST.isValid(node.greater, key => node.key < key)
+}
+
+describe("BST", () => {
+  const randomInt = (min, max) =>
+    Math.floor(Math.random() * (max - min)) + min
+  const randomPick = (...choices) =>
+    choices[randomInt(0, choices.length)]
+
+  it("maintains validity through operations", () => {
+    let t0
+    let t1
+    let op
+    let k
+
+    for (let i=0; i<1000; ++i) {
+      k = randomInt(0, 10)
+      op = randomPick("set", "delete")
+
+      switch (op) {
+        case "set":
+          t1 = L.set(BST.valueOf(k), k, t0)
+          break
+        case "delete":
+          t1 = L.delete(BST.valueOf(k), t0)
+          break
+      }
+
+      if (!BST.isValid(t1))
+        throw new Error("From " + show(t0) + " " + op + " with " + k + " gave " + t1)
+
+      t0 = t1
+    }
+  })
+})

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

78081

increased by7.97%

Lines of code

559

increased by10.91%

Number of lines in readme file

614

increased by0.49%

No dependency changes