-
-
Save binarymax/1451190 to your computer and use it in GitHub Desktop.
SortedSet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function( | |
| s, //the array (set) | |
| o, //the item you want to add to the set | |
| r, //placeholder, lower bound for binary search | |
| t, //placeholder, upper bound for binary search | |
| y //placeholder, middle bound index for binary search | |
| ){ | |
| for(r=0,t=s.length;r<=t;) //binary search loop | |
| if(o>s[y=parseInt((r+t)/2)]) //item greater than middle item? | |
| r=y+1; //make lower bound middle+1 | |
| else t=o==s[y]?-2:y-1; //if match found, make middle -2, otherwise make upper bound middle-1 | |
| if(t>-2) //match not found, splice it into the set at the correct position: | |
| s.splice(r,0,o) | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function(s,o,r,t,y){for(r=0,t=s.length;r<=t;)if(o>s[y=parseInt((r+t)/2)])r=y+1;else t=o==s[y]?-2:y-1;if(t>-2)s.splice(r,0,o)} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 Max Irwin http://www.binarymax.com | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "SortedSet", | |
| "description": "Function to maintain a sorted array. When an item is added to the array, it puts it in the right place, and removes duplicates.", | |
| "keywords": [ | |
| "set", | |
| "sort", | |
| "array" | |
| ] | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <title>Foo</title> | |
| <div>Expected value: <b>apples,bananas,grapes,kiwis,oranges,strawberries</b></div> | |
| <div>Actual value: <b id="ret"></b></div> | |
| <script> | |
| var f = function(s,o,r,t,y){for(r=0,t=s.length;r<=t;)if(o>s[y=parseInt((r+t)/2)])r=y+1;else t=o==s[y]?-2:y-1;if(t>-2)s.splice(r,0,o)} | |
| var S = []; | |
| var a = ["apples","oranges","bananas","grapes","strawberries"]; | |
| var b = ["strawberries","bananas"]; | |
| var c = ["strawberries","kiwis"]; | |
| var d = []; | |
| f(S,a[0]); | |
| f(S,a[1]); | |
| f(S,a[2]); | |
| f(S,a[3]); | |
| f(S,a[4]); | |
| f(S,b[0]); | |
| f(S,b[1]); | |
| f(S,c[0]); | |
| f(S,c[1]); | |
| document.getElementById( "ret" ).innerHTML = S.join(','); | |
| </script> |
What about
function(s,o,r,t,y){for(r=0,t=s.length;r<=t;)o>s[y=r+t>>1]?r=y+1:t=o==s[y]?-2:y-1;t>-2&&s.splice(r,0,o)}
?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This can be shortened using Array.indexOf - but it would be much slower. Also the version as it is above is supported by browsers missing native Array.indexOf.