summaryrefslogtreecommitdiffstats
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, 0 insertions, 372 deletions
diff --git a/trunk/infrastructure/ace/www/bbtree.js b/trunk/infrastructure/ace/www/bbtree.js
deleted file mode 100644
index 70cb8c0..0000000
--- a/trunk/infrastructure/ace/www/bbtree.js
+++ /dev/null
@@ -1,372 +0,0 @@
-/**
- * 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-1-g7c22 (git 2.25.1) at 2024-06-27 21:14:13 +0000