Skip to content

Instantly share code, notes, and snippets.

@a-s-o
Last active August 29, 2015 14:11
Show Gist options
  • Save a-s-o/6abd25978ca86d335dfe to your computer and use it in GitHub Desktop.
Save a-s-o/6abd25978ca86d335dfe to your computer and use it in GitHub Desktop.
Unique Sorted Set with binary search
class Collection {
constructor (opts = {}) {
this.list = [];
this.length = 0;
var isFn = $.is.function;
if (opts.key) {
var keyType = $.object.type(opts.key);
if (keyType === 'function') {
this.isHashed = true;
this.map = {};
this.key = opts.key;
}
else if (keyType === 'string') {
this.isHashed = true;
this.map = {};
this.key = function (elem) {
return $.object.result(elem, opts.key);
};
}
}
this.equals = isFn(opts.equals) ? opts.equals : function (a, b) {
return a === b;
};
this.comparator = isFn(opts.comparator) ? opts.comparator : function (a, b) {
if (b && b.localeCompare) return b.localeCompare(a);
else return this.equals(a, b) ? 0 : a > b ? 1 : -1;
};
}
get ( input ) {
if (this.isHashed) {
if (this.map[ input ]) return this.map[ input ];
var key = this.key( input );
if (key && this.map[ key ]) return this.map[ key ];
key = this.list[ input ];
if (key && this.map[ key ]) return this.map[ key ];
} else {
return this.input[ input ];
}
}
indexOf ( element ) {
var i, low = 0, high = this.length;
while (low < high) {
i = (low + high) / 2 | 0;
var cursor = this.comparator(this.get( i ), element);
if (cursor > 0) low = i + 1;
else if (cursor < 0) high = i;
else return i;
}
return high < 0 ? high : ~high;
}
insert ( element ) {
var key = this.isHashed ? this.key( element ) : element;
var index = this.indexOf( key );
if (index < 0) {
var array = this.list;
array.splice(~index, 0, key);
if (this.isHashed) this.map[key] = element;
this.length = array.length;
}
return this;
}
remove ( key ) {
var index = this.indexOf( this.isHashed ? this.get( key ) : key );
console.log(index, key);
if (index >= 0) {
var removal = this.list.splice( ~index, 1 );
this.length = this.list.length;
if (this.isHashed) {
this.map = $.object.omit(this.map, removal[0]);
}
}
return this;
}
}
function randid () {
var id = ('' + Math.pow(10, $.utils.random(1, 10))).replace(/1|0/g, function () {
return (0 | Math.random() * 16).toString(16);
});
return id;
}
export default {
controller () {
var set = new Collection({ key: 'id' });
console.time('timeTaken');
for (var i = 5; i >= 1; i--) {
set.insert({ id: i, name: randid() });
}
set.remove(2);
set.remove(3);
console.timeEnd('timeTaken');
console.log( set.length, set.list, set.get(2) );
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment