← Back to branch summary

~mrooney/etherpad/ubuntu

« back to all changes in this revision

Viewing changes to trunk/trunk/infrastructure/ace/www/bbtree.js

  • Committer: Aaron Iba
  • Date: 2009-12-18 07:40:23 UTC
  • Revision ID: hg-v1:a9f8774a2e00cc15b35857471fecea17f649e3c9
initial code push

Show diffs side-by-side

added added

removed removed

Lines of Context:
trunk/trunk/infrastructure/ace/www/bbtree.js
 
1
/**
 
2
 * Copyright 2009 Google Inc.
 
3
 * 
 
4
 * Licensed under the Apache License, Version 2.0 (the "License");
 
5
 * you may not use this file except in compliance with the License.
 
6
 * You may obtain a copy of the License at
 
7
 * 
 
8
 *      http://www.apache.org/licenses/LICENSE-2.0
 
9
 * 
 
10
 * Unless required by applicable law or agreed to in writing, software
 
11
 * distributed under the License is distributed on an "AS-IS" BASIS,
 
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
13
 * See the License for the specific language governing permissions and
 
14
 * limitations under the License.
 
15
 */
 
16
 
 
17
 
 
18
function makeBBTree(transferContents, augment) {
 
19
 
 
20
  var nil = [];
 
21
  nil.push(nil,nil);
 
22
  nil.level = 0;
 
23
  var root = nil;
 
24
  augment = (augment || (function(n) {}));
 
25
  
 
26
  function skew(t) {
 
27
    if (t != nil && t[0].level == t.level) {
 
28
      // rotate right
 
29
      var tmp = t;
 
30
      t = t[0];
 
31
      tmp[0] = t[1];
 
32
      t[1] = tmp;
 
33
      reaugment(tmp);
 
34
      reaugment(t);
 
35
    }
 
36
    return t;
 
37
  }
 
38
 
 
39
  function split(t) {
 
40
    if (t != nil && t[1][1].level == t.level) {
 
41
      // rotate left
 
42
      var tmp = t;
 
43
      t = t[1];
 
44
      tmp[1] = t[0];
 
45
      t[0] = tmp;
 
46
      t.level++;
 
47
      reaugment(tmp);
 
48
      reaugment(t);
 
49
    }
 
50
    return t;
 
51
  }
 
52
 
 
53
  function reaugment(n) {
 
54
    if (n != nil) augment(n);
 
55
  }
 
56
  
 
57
  var self = {};
 
58
  
 
59
  self.insert = function(compare) {
 
60
    var n;
 
61
    function recurse(t) {
 
62
      if (t == nil) {
 
63
        t = [nil,nil];
 
64
        t.level = 1;
 
65
        n = t;
 
66
      }
 
67
      else {
 
68
        var cmp = compare(t);
 
69
        if (cmp < 0) {
 
70
          t[0] = recurse(t[0]);
 
71
        }
 
72
        else if (cmp > 0) {
 
73
          t[1] = recurse(t[1]);
 
74
        }
 
75
        t = skew(t);
 
76
        t = split(t);
 
77
      }
 
78
      reaugment(t);
 
79
      return t;
 
80
    }
 
81
    root = recurse(root);
 
82
    return n;
 
83
  }
 
84
  
 
85
  self.remove = function(compare) {
 
86
    var deleted = nil;
 
87
    var last;
 
88
    var deletedEqual = false;
 
89
    function recurse(t) {
 
90
      if (t != nil) {
 
91
        last = t;
 
92
        var cmp = compare(t);
 
93
        if (cmp < 0) {
 
94
          t[0] = recurse(t[0]);
 
95
        }
 
96
        else {
 
97
          deleted = t;
 
98
          // whether the node called "deleted" is actually a
 
99
          // match for deletion
 
100
          deletedEqual = (cmp == 0);
 
101
          t[1] = recurse(t[1]);
 
102
        }
 
103
        if (t == last && deleted != nil && deletedEqual) {
 
104
          // t may be same node as deleted
 
105
          transferContents(t, deleted);
 
106
          t = t[1];
 
107
          reaugment(deleted);
 
108
          deleted = nil;
 
109
        }
 
110
        else {
 
111
          reaugment(t);
 
112
          if (t[0].level < t.level-1 ||
 
113
              t[1].level < t.level-1) {
 
114
            t.level--;
 
115
            if (t[1].level > t.level)
 
116
              t[1].level = t.level;
 
117
            t = skew(t);
 
118
            t[1] = skew(t[1]);
 
119
            t[1][1] = skew(t[1][1]);
 
120
            t = split(t);
 
121
            t[1] = split(t[1]);
 
122
          }
 
123
        }
 
124
      }
 
125
      return t;
 
126
    }
 
127
    root = recurse(root);
 
128
  }
 
129
 
 
130
  self.find = function(compare) {
 
131
    function recurse(t) {
 
132
      if (t == nil) return t;
 
133
      var cmp = compare(t);
 
134
      if (cmp < 0) {
 
135
        return recurse(t[0]);
 
136
      }
 
137
      else if (cmp > 0) {
 
138
        return recurse(t[1]);
 
139
      }
 
140
      else {
 
141
        return t;
 
142
      }
 
143
    }
 
144
    var result = recurse(root);
 
145
    return (result != nil && result) || null;
 
146
  }
 
147
 
 
148
  self.root = function() { return root; }
 
149
 
 
150
  self.forEach = function(func) {
 
151
    function recurse(t) {
 
152
      if (t != nil) {
 
153
        recurse(t[0]);
 
154
        func(t);
 
155
        recurse(t[1]);
 
156
      }
 
157
    }
 
158
    recurse(root);
 
159
  }
 
160
  
 
161
  return self;
 
162
}
 
163
 
 
164
function makeBBList() {
 
165
  var length = 0;
 
166
  var totalWidth = 0;
 
167
 
 
168
  function _treeSize(n) { return n.size || 0; }
 
169
  function _treeWidth(n) { return n.width || 0; }
 
170
  function _width(n) { return (n && n.entry && n.entry.width) || 0; }
 
171
  
 
172
  function _transferContents(a, b) {
 
173
    b.key = a.key;
 
174
    b.entry = a.entry;
 
175
  }
 
176
  function _augment(n) {
 
177
    n.size = _treeSize(n[0]) + _treeSize(n[1]) + 1;
 
178
    n.width = _treeWidth(n[0]) + _treeWidth(n[1]) + _width(n);
 
179
  }
 
180
 
 
181
  var keyToEntry = {};
 
182
  
 
183
  var bb = makeBBTree(transferContents, augment);
 
184
 
 
185
  function makeIndexComparator(indexFunc) {
 
186
    var curIndex = _treeSize(bb.root()[0]);
 
187
    return function (n) {
 
188
      var dir = indexFunc(curIndex, n);
 
189
      if (dir < 0) {
 
190
        curIndex -= _treeSize(n[0][1]) + 1;
 
191
      }
 
192
      else if (dir >= 0) {
 
193
        curIndex += _treeSize(n[1][0]) + 1;      
 
194
      }
 
195
      return dir;
 
196
    }
 
197
  }
 
198
 
 
199
  function makeWidthComparator(widthFunc) {
 
200
    var curIndex = _treeWidth(bb.root()[0]);
 
201
    return function (n) {
 
202
      var dir = indexFunc(curIndex, n);
 
203
      if (dir < 0) {
 
204
        curIndex -= _treeWidth(n[0][1]) + _width(n[0]);
 
205
      }
 
206
      else if (dir >= 0) {
 
207
        curIndex += _treeWidth(n[1][0]) + _width(n);
 
208
      }
 
209
      return dir;
 
210
    }
 
211
  }
 
212
 
 
213
  function numcomp(a,b) { if (a < b) return -1; if (a > b) return 1; return 0; }
 
214
  
 
215
  function removeByIndex(idx) {
 
216
    var entry;
 
217
    bb.remove(makeComparator(function (curIndex, n) {
 
218
      var cmp = numcomp(idx, curIndex);
 
219
      if (cmp == 0) entry = n.entry;
 
220
      return cmp;
 
221
    }));
 
222
    return entry;
 
223
  }
 
224
 
 
225
  function insertAtIndex(idx, entry) {
 
226
    var newNode = bb.insert(makeComparator(function (curIndex) {
 
227
      if (idx <= curIndex) return -1;
 
228
      return 1;
 
229
    }));
 
230
    newNode.entry = entry;
 
231
    return newNode;
 
232
  }
 
233
 
 
234
  var entriesByKey = {};
 
235
  
 
236
  var self = {
 
237
    splice: function (start, deleteCount, newEntryArray) {
 
238
      for(var i=0;i<deleteCount;i++) {
 
239
        var oldEntry = removeByIndex(start);
 
240
        length--;
 
241
        totalWidth -= (entry.width || 0);
 
242
        delete entriesByKey[oldEntry.key];
 
243
      }
 
244
      for(var i=0;i<newEntryArray.length;i++) {
 
245
        var entry = newEntryArray[i];
 
246
        var newNode = insertAtIndex(start+i, entry);
 
247
        length++;
 
248
        totalWidth += (entry.width || 0);
 
249
        entriesByKey[entry.key] = entry;
 
250
      }
 
251
    },
 
252
    next: function (entry) {
 
253
      
 
254
    }
 
255
  };
 
256
 
 
257
  return self;
 
258
}
 
259
 
 
260
/*function size(n) {
 
261
  return n.size || 0;
 
262
}
 
263
 
 
264
var a = makeBBTree(function (a,b) {
 
265
  b.data = a.data;
 
266
},
 
267
                   function (n) {
 
268
                     n.size = size(n[0]) + size(n[1]) + 1;
 
269
                   });
 
270
 
 
271
var arrayRep = [];
 
272
 
 
273
function makeComparator(indexFunc) {
 
274
  var curIndex = size(a.root()[0]);
 
275
  return function (n) {
 
276
    var dir = indexFunc(curIndex);
 
277
    if (dir < 0) {
 
278
      curIndex -= size(n[0][1]) + 1;
 
279
    }
 
280
    else if (dir >= 0) {
 
281
      curIndex += size(n[1][0]) + 1;      
 
282
    }
 
283
    return dir;
 
284
  }
 
285
}
 
286
 
 
287
function insert(idx, data) {
 
288
  arrayRep.splice(idx, 0, data);
 
289
  var newNode = a.insert(makeComparator(function (curIndex) {
 
290
    if (idx <= curIndex) return -1;
 
291
    return 1;
 
292
  }));
 
293
  newNode.data = data;
 
294
  checkRep();
 
295
}
 
296
 
 
297
function remove(idx) {
 
298
  arrayRep.splice(idx, 1);
 
299
  a.remove(makeComparator(function (curIndex) {
 
300
    return numcomp(idx, curIndex);
 
301
  }));
 
302
  checkRep();
 
303
}
 
304
 
 
305
function genArray() {
 
306
  var array = [];
 
307
  a.forEach(function (n) { array.push(n.data); });
 
308
  return array;
 
309
}
 
310
 
 
311
function checkRep() {
 
312
  var array2 = genArray();
 
313
  var str1 = array2.join(',');
 
314
  var str2 = arrayRep.join(',');
 
315
  if (str1 != str2) console.error(str1+" != "+str2);
 
316
 
 
317
  a.forEach(function(n) {
 
318
    if (size(n) != size(n[0]) + size(n[1]) + 1) {
 
319
      console.error("size of "+n.data+" is wrong");
 
320
    }
 
321
  });
 
322
}
 
323
 
 
324
function print() {
 
325
  console.log(genArray().join(','));
 
326
}
 
327
 
 
328
insert(0,1);
 
329
insert(0,2);
 
330
insert(0,3);
 
331
insert(1,4);
 
332
insert(4,5);
 
333
insert(0,6);
 
334
print();
 
335
 
 
336
function numcomp(a,b) { if (a < b) return -1; if (a > b) return 1; return 0; }
 
337
*/
 
338
/*var tree = makeBBTree(function(a, b) { b.key = a.key; });
 
339
function insert(x) { tree.insert(function(n) { return numcomp(x, n.key) }).key = x; }
 
340
function remove(x) { tree.remove(function (n) { return numcomp(x, n.key); }); }
 
341
function contains(x) { return !! tree.find(function (n) { return numcomp(x, n.key); }); }
 
342
 
 
343
function print() {
 
344
  function recurse(t) {
 
345
    if (! ('key' in t)) return '';
 
346
    return '('+recurse(t[0])+','+t.key+','+recurse(t[1])+')';
 
347
  }
 
348
  return recurse(tree.root());
 
349
}
 
350
 
 
351
 
 
352
insert(2);
 
353
insert(1);
 
354
insert(8);
 
355
insert(7);
 
356
console.log(print());
 
357
insert(6);
 
358
insert(3);
 
359
insert(5);
 
360
insert(4);
 
361
console.log(print());
 
362
remove(2);
 
363
remove(1);
 
364
remove(8);
 
365
remove(7);
 
366
console.log(print());
 
367
//remove(6);
 
368
//remove(3);
 
369
//remove(5);
 
370
//remove(4);
 
371
//console.log(print());
 
372
*/
 
 
b'\\ No newline at end of file'