binarysearch - npm Package Compare versions

Comparing version 0.1.4 to 0.1.5

index.js

@@ -28,3 +28,2 @@
 
-
   opts = opts||{};
@@ -35,2 +34,3 @@ if(!comparitor) comparitor = module.exports._defaultComparitor();
 
+
   if(closest > arr.length-1) closest = arr.length-1;
@@ -42,2 +42,40 @@ else if(closest < 0) closest = 0;
 
+// inserts element into the correct sorted spot into the array
+module.exports.insert = function(arr,search,opts,comparitor){ 
+
+  if(typeof opts === 'function') {
+    comparitor = opts;
+    opts = {};
+  }
+
+  opts = opts||{};
+  if(!comparitor) comparitor = module.exports._defaultComparitor();
+  if(!arr.length) {
+    arr[0] = search;
+    return 0;
+  }
+
+  var closest = module.exports.closest(arr,search,comparitor);
+
+  var cmp = comparitor(arr[closest],search);
+  if(cmp  === -1) {//less
+    arr.splice(++closest,0,search);
+  } else if(cmp === 1){ 
+    arr.splice(closest,0,search);
+  } else {
+    if(opts.unique){
+      arr[closest] = search;
+    } else {
+      // im equal. this value should be appended to the list of existing same sorted values.
+      while(comparitor(arr[closest],search) === 0){
+        if(closest >= arr.length-1) break;
+        closest++;
+      }
+
+      arr.splice(closest,0,search);
+    }
+  }
+  return closest;
+}
+
 // this is inconsistent because it gives values.
@@ -52,3 +90,2 @@ // i should breaking change this soon.
 
-
   // this is a hack. 
@@ -62,2 +99,3 @@ // i should be able to fix the algorithm and generate a correct range.
   }
+
   while(range.length){
@@ -68,2 +106,3 @@ if(comparitor(range[range.length-1],to) < 1) break;
   return range;
+
 }
@@ -86,3 +125,3 @@
 module.exports._defaultComparitor = function() {
-  var indexMode;
+  var indexMode,indexModeSearch;
   return function(v,search){
@@ -93,6 +132,8 @@ // support the object format of generated indexes
       indexMode = false;
+      if(typeof search === 'object' && search.hasOwnProperty('v')) indexModeSearch = true
     }
 
     if(indexMode) v = v.v;
-    
+    if(indexModeSearch) search = search.v;
+
     if(v > search) return 1;
@@ -158,6 +199,13 @@ else if(v < search) return -1;
   
-  if (max == min && arr[min] == search) {
+  if (max == min && comparitor(arr[min],search) === 0) {
     return min;
   } else {
-    return closest?(invert?min+1:min-1):-1;
+    if(closest) {
+      var match = comparitor(arr[min],search);
+      if(min == arr.length-1 && match === -1) return min;
+      if(min == 0 && match === 1) return 0;
+
+      return closest?(invert?min+1:min-1):-1;
+    } 
+    return -1;
   }
@@ -164,0 +212,0 @@ }

package.json

 {
   "name": "binarysearch",
   "description": "pure js binary search for sorted javascript arrays||array like objects. returns any || last || first || closest matched key for value, or slice between 2 values where values need not exist.",
-  "version": "0.1.4",
+  "version": "0.1.5",
   "repository": {
@@ -6,0 +6,0 @@ "url": "git://github.com/soldair/node-binarysearch.git"

README.md

@@ -77,2 +77,27 @@
 
+insert a value into a sorted array.
+
+```js
+var arr = [1,3,4];
+bs.insert(arr,2) === 1
+// returns the key it inserted into 
+
+arr[1] === 2
+// true
+ 
+```
+when you insert values and there are duplicates the default behavior is to insert the new value after the other same values.
+if you pass option.unique = true the key's value is replaced with the new value
+
+```js
+var arr = [1,2,3];
+bs.insert(arr,2)
+// arr is [1,2,2,3]
+
+var arr = [1,2,3];
+bs.insert(arr,2,{unique:true});
+// arr is [1,2,3]
+ 
+```
+
 create an object index
@@ -79,0 +104,0 @@

test/closest.js

@@ -28,2 +28,8 @@ var test = require('tap').test;
 
+test("can get closest at end",function(t){
+  var key = bs.closest([1,2,4,5,6],7);
+  t.equals(key,4,key+' should have got 4 as key because it is the last');
+  t.end();
+});
+
 // end sorted
@@ -39,3 +45,3 @@
   var key = bs.closest([1,2,4,5,6],7,{end:true});
-  t.equals(key,4,key+' should have got 2 as key because it is the last closest to 3');
+  t.equals(key,4,key+' should have got 4 as key because it is the last');
   t.end();
@@ -42,0 +48,0 @@ });

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

13253

increased by28.61%

Number of package files

11

increased by10%

Lines of code

308

increased by32.76%

Number of lines in readme file

135

increased by22.73%

No dependency changes