diff options
author | Egil Moeller <egil.moller@freecode.no> | 2010-03-22 00:16:53 +0100 |
---|---|---|
committer | Egil Moeller <egil.moller@freecode.no> | 2010-03-22 00:16:53 +0100 |
commit | fc00cfedd6c25d1634a1e0d28a7b7bc5f42e1cd7 (patch) | |
tree | 928419d6bfe794865e4b8f0634bd792f795c4b8a /trunk/infrastructure/ace/www/bbtree.js | |
parent | 0fdab3db005c4fa31fb8306b573c0b35073d3e56 (diff) | |
parent | d56b9b3b82cdebcaeb00eec0fcb4326ad21adaa8 (diff) | |
download | etherpad-fc00cfedd6c25d1634a1e0d28a7b7bc5f42e1cd7.tar.gz etherpad-fc00cfedd6c25d1634a1e0d28a7b7bc5f42e1cd7.tar.xz etherpad-fc00cfedd6c25d1634a1e0d28a7b7bc5f42e1cd7.zip |
Merge branch 'master' into plugin-framework
Diffstat (limited to 'trunk/infrastructure/ace/www/bbtree.js')
-rw-r--r-- | trunk/infrastructure/ace/www/bbtree.js | 372 |
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 |