Could you please add it?
diff -r 00ef87ea4591 src/sys/js/fan/List.js --- a/src/sys/js/fan/List.js Mon Apr 25 15:51:45 2011 -0400 +++ b/src/sys/js/fan/List.js Tue May 17 19:01:54 2011 +0700 @@ -720,11 +720,7 @@ fan.sys.List.prototype.sort = function(f) { this.modify(); - if (f === undefined) f = null; - if (f != null) - this.m_values.sort(function(a,b) { return f.call(a,b) }); - else - this.m_values.sort(function(a,b) { return fan.sys.ObjUtil.compare(a,b,false) }); + this.m_values.sort(fan.sys.List.comparator(f)); return this; } @@ -739,6 +735,28 @@ return this; } +fan.sys.List.prototype.binarySearch = function(key, f) +{ + var c = fan.sys.List.comparator(f); + var low = 0; + var high = this.m_size - 1; + while (low <= high) + { + var mid = (low + high) / 2 + var cmp = c(this.m_values[mid], key); + if (cmp < 0) low = mid + 1; + else if (cmp > 0) high = mid - 1; + else return mid; + } + return -(low + 1); +} + +fan.sys.List.comparator = function(f) +{ + if (f) return function(a,b) { return f.call(a,b) }; + return function(a,b) { return fan.sys.ObjUtil.compare(a,b,false) }; +} + fan.sys.List.prototype.reverse = function() { this.modify();
Great - thanks Yuri! Pushed with a tweak to truncate the division:
var mid = Math.floor((low + high) / 2);
And looks good:
$ fan compilerJs::TestRunner testSys::ListTest.testBinarySearch -- Run: testSys::ListTest.testBinarySearch... Pass: testSys::ListTest.testBinarySearch [159] Time: 179ms *** *** All tests passed! [1 tests, 1 methods, 159 verifies] ***
Thanks a lot!
Login or Signup to reply.
Yuri Strot Tue 17 May 2011
Could you please add it?
andy Tue 17 May 2011
Great - thanks Yuri! Pushed with a tweak to truncate the division:
And looks good:
Yuri Strot Tue 17 May 2011
Thanks a lot!