From d7c5ad7d6263fd1baf9bfdbaa4c50b70ef2fbdb2 Mon Sep 17 00:00:00 2001 From: Alexander Sulfrian Date: Tue, 8 Jun 2010 08:22:05 +0200 Subject: reverted folder structure change for better mergeing with upstream --- trunk/infrastructure/ace/www/bbtree.js | 372 +++++++++++++++++++++++++++++++++ 1 file changed, 372 insertions(+) create mode 100644 trunk/infrastructure/ace/www/bbtree.js (limited to 'trunk/infrastructure/ace/www/bbtree.js') 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= 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 -- cgit v1.2.3-1-g7c22