aboutsummaryrefslogtreecommitdiffstats
path: root/trunk/infrastructure/ace/www/bbtree.js
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/infrastructure/ace/www/bbtree.js')
-rw-r--r--trunk/infrastructure/ace/www/bbtree.js372
1 files changed, 372 insertions, 0 deletions
diff --git a/trunk/infrastructure/ace/www/bbtree.js b/trunk/infrastructure/ace/www/bbtree.js
new file mode 100644
index 0000000..70cb8c0
--- /dev/null
+++ b/trunk/infrastructure/ace/www/bbtree.js
@@ -0,0 +1,372 @@
+/**
+ * Copyright 2009 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS-IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+function makeBBTree(transferContents, augment) {
+
+ var nil = [];
+ nil.push(nil,nil);
+ nil.level = 0;
+ var root = nil;
+ augment = (augment || (function(n) {}));
+
+ function skew(t) {
+ if (t != nil && t[0].level == t.level) {
+ // rotate right
+ var tmp = t;
+ t = t[0];
+ tmp[0] = t[1];
+ t[1] = tmp;
+ reaugment(tmp);
+ reaugment(t);
+ }
+ return t;
+ }
+
+ function split(t) {
+ if (t != nil && t[1][1].level == t.level) {
+ // rotate left
+ var tmp = t;
+ t = t[1];
+ tmp[1] = t[0];
+ t[0] = tmp;
+ t.level++;
+ reaugment(tmp);
+ reaugment(t);
+ }
+ return t;
+ }
+
+ function reaugment(n) {
+ if (n != nil) augment(n);
+ }
+
+ var self = {};
+
+ self.insert = function(compare) {
+ var n;
+ function recurse(t) {
+ if (t == nil) {
+ t = [nil,nil];
+ t.level = 1;
+ n = t;
+ }
+ else {
+ var cmp = compare(t);
+ if (cmp < 0) {
+ t[0] = recurse(t[0]);
+ }
+ else if (cmp > 0) {
+ t[1] = recurse(t[1]);
+ }
+ t = skew(t);
+ t = split(t);
+ }
+ reaugment(t);
+ return t;
+ }
+ root = recurse(root);
+ return n;
+ }
+
+ self.remove = function(compare) {
+ var deleted = nil;
+ var last;
+ var deletedEqual = false;
+ function recurse(t) {
+ if (t != nil) {
+ last = t;
+ var cmp = compare(t);
+ if (cmp < 0) {
+ t[0] = recurse(t[0]);
+ }
+ else {
+ deleted = t;
+ // whether the node called "deleted" is actually a
+ // match for deletion
+ deletedEqual = (cmp == 0);
+ t[1] = recurse(t[1]);
+ }
+ if (t == last && deleted != nil && deletedEqual) {
+ // t may be same node as deleted
+ transferContents(t, deleted);
+ t = t[1];
+ reaugment(deleted);
+ deleted = nil;
+ }
+ else {
+ reaugment(t);
+ if (t[0].level < t.level-1 ||
+ t[1].level < t.level-1) {
+ t.level--;
+ if (t[1].level > t.level)
+ t[1].level = t.level;
+ t = skew(t);
+ t[1] = skew(t[1]);
+ t[1][1] = skew(t[1][1]);
+ t = split(t);
+ t[1] = split(t[1]);
+ }
+ }
+ }
+ return t;
+ }
+ root = recurse(root);
+ }
+
+ self.find = function(compare) {
+ function recurse(t) {
+ if (t == nil) return t;
+ var cmp = compare(t);
+ if (cmp < 0) {
+ return recurse(t[0]);
+ }
+ else if (cmp > 0) {
+ return recurse(t[1]);
+ }
+ else {
+ return t;
+ }
+ }
+ var result = recurse(root);
+ return (result != nil && result) || null;
+ }
+
+ self.root = function() { return root; }
+
+ self.forEach = function(func) {
+ function recurse(t) {
+ if (t != nil) {
+ recurse(t[0]);
+ func(t);
+ recurse(t[1]);
+ }
+ }
+ recurse(root);
+ }
+
+ return self;
+}
+
+function makeBBList() {
+ var length = 0;
+ var totalWidth = 0;
+
+ function _treeSize(n) { return n.size || 0; }
+ function _treeWidth(n) { return n.width || 0; }
+ function _width(n) { return (n && n.entry && n.entry.width) || 0; }
+
+ function _transferContents(a, b) {
+ b.key = a.key;
+ b.entry = a.entry;
+ }
+ function _augment(n) {
+ n.size = _treeSize(n[0]) + _treeSize(n[1]) + 1;
+ n.width = _treeWidth(n[0]) + _treeWidth(n[1]) + _width(n);
+ }
+
+ var keyToEntry = {};
+
+ var bb = makeBBTree(transferContents, augment);
+
+ function makeIndexComparator(indexFunc) {
+ var curIndex = _treeSize(bb.root()[0]);
+ return function (n) {
+ var dir = indexFunc(curIndex, n);
+ if (dir < 0) {
+ curIndex -= _treeSize(n[0][1]) + 1;
+ }
+ else if (dir >= 0) {
+ curIndex += _treeSize(n[1][0]) + 1;
+ }
+ return dir;
+ }
+ }
+
+ function makeWidthComparator(widthFunc) {
+ var curIndex = _treeWidth(bb.root()[0]);
+ return function (n) {
+ var dir = indexFunc(curIndex, n);
+ if (dir < 0) {
+ curIndex -= _treeWidth(n[0][1]) + _width(n[0]);
+ }
+ else if (dir >= 0) {
+ curIndex += _treeWidth(n[1][0]) + _width(n);
+ }
+ return dir;
+ }
+ }
+
+ function numcomp(a,b) { if (a < b) return -1; if (a > b) return 1; return 0; }
+
+ function removeByIndex(idx) {
+ var entry;
+ bb.remove(makeComparator(function (curIndex, n) {
+ var cmp = numcomp(idx, curIndex);
+ if (cmp == 0) entry = n.entry;
+ return cmp;
+ }));
+ return entry;
+ }
+
+ function insertAtIndex(idx, entry) {
+ var newNode = bb.insert(makeComparator(function (curIndex) {
+ if (idx <= curIndex) return -1;
+ return 1;
+ }));
+ newNode.entry = entry;
+ return newNode;
+ }
+
+ var entriesByKey = {};
+
+ var self = {
+ splice: function (start, deleteCount, newEntryArray) {
+ for(var i=0;i<deleteCount;i++) {
+ var oldEntry = removeByIndex(start);
+ length--;
+ totalWidth -= (entry.width || 0);
+ delete entriesByKey[oldEntry.key];
+ }
+ for(var i=0;i<newEntryArray.length;i++) {
+ var entry = newEntryArray[i];
+ var newNode = insertAtIndex(start+i, entry);
+ length++;
+ totalWidth += (entry.width || 0);
+ entriesByKey[entry.key] = entry;
+ }
+ },
+ next: function (entry) {
+
+ }
+ };
+
+ return self;
+}
+
+/*function size(n) {
+ return n.size || 0;
+}
+
+var a = makeBBTree(function (a,b) {
+ b.data = a.data;
+},
+ function (n) {
+ n.size = size(n[0]) + size(n[1]) + 1;
+ });
+
+var arrayRep = [];
+
+function makeComparator(indexFunc) {
+ var curIndex = size(a.root()[0]);
+ return function (n) {
+ var dir = indexFunc(curIndex);
+ if (dir < 0) {
+ curIndex -= size(n[0][1]) + 1;
+ }
+ else if (dir >= 0) {
+ curIndex += size(n[1][0]) + 1;
+ }
+ return dir;
+ }
+}
+
+function insert(idx, data) {
+ arrayRep.splice(idx, 0, data);
+ var newNode = a.insert(makeComparator(function (curIndex) {
+ if (idx <= curIndex) return -1;
+ return 1;
+ }));
+ newNode.data = data;
+ checkRep();
+}
+
+function remove(idx) {
+ arrayRep.splice(idx, 1);
+ a.remove(makeComparator(function (curIndex) {
+ return numcomp(idx, curIndex);
+ }));
+ checkRep();
+}
+
+function genArray() {
+ var array = [];
+ a.forEach(function (n) { array.push(n.data); });
+ return array;
+}
+
+function checkRep() {
+ var array2 = genArray();
+ var str1 = array2.join(',');
+ var str2 = arrayRep.join(',');
+ if (str1 != str2) console.error(str1+" != "+str2);
+
+ a.forEach(function(n) {
+ if (size(n) != size(n[0]) + size(n[1]) + 1) {
+ console.error("size of "+n.data+" is wrong");
+ }
+ });
+}
+
+function print() {
+ console.log(genArray().join(','));
+}
+
+insert(0,1);
+insert(0,2);
+insert(0,3);
+insert(1,4);
+insert(4,5);
+insert(0,6);
+print();
+
+function numcomp(a,b) { if (a < b) return -1; if (a > b) return 1; return 0; }
+*/
+/*var tree = makeBBTree(function(a, b) { b.key = a.key; });
+function insert(x) { tree.insert(function(n) { return numcomp(x, n.key) }).key = x; }
+function remove(x) { tree.remove(function (n) { return numcomp(x, n.key); }); }
+function contains(x) { return !! tree.find(function (n) { return numcomp(x, n.key); }); }
+
+function print() {
+ function recurse(t) {
+ if (! ('key' in t)) return '';
+ return '('+recurse(t[0])+','+t.key+','+recurse(t[1])+')';
+ }
+ return recurse(tree.root());
+}
+
+
+insert(2);
+insert(1);
+insert(8);
+insert(7);
+console.log(print());
+insert(6);
+insert(3);
+insert(5);
+insert(4);
+console.log(print());
+remove(2);
+remove(1);
+remove(8);
+remove(7);
+console.log(print());
+//remove(6);
+//remove(3);
+//remove(5);
+//remove(4);
+//console.log(print());
+*/ \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-18 09:36:38 +0000