← Back to branch summary

~dpm/+junk/navigator

« back to all changes in this revision

Viewing changes to platforms/ubuntu/build/node_modules/q/node_modules/collections/sorted-set.js

  • Committer: David Planella
  • Date: 2015-05-28 07:14:31 UTC
  • Revision ID: david.planella@ubuntu.com-20150528071431-hlvqt5utpe6d1o6o
Added Ubuntu platform

Show diffs side-by-side

added added

removed removed

Lines of Context:
platforms/ubuntu/build/node_modules/q/node_modules/collections/sorted-set.js
 
1
"use strict";
 
2
 
 
3
module.exports = SortedSet;
 
4
 
 
5
var Shim = require("./shim");
 
6
var GenericCollection = require("./generic-collection");
 
7
var GenericSet = require("./generic-set");
 
8
var ObservableObject = require("./observable-object");
 
9
var ObservableRange = require("./observable-range");
 
10
var Iterator = require("./iterator");
 
11
var TreeLog = require("./tree-log");
 
12
 
 
13
function SortedSet(values, equals, compare, getDefault) {
 
14
    if (!(this instanceof SortedSet)) {
 
15
        return new SortedSet(values, equals, compare, getDefault);
 
16
    }
 
17
    this.contentEquals = equals || Object.equals;
 
18
    this.contentCompare = compare || Object.compare;
 
19
    this.getDefault = getDefault || Function.noop;
 
20
    this.root = null;
 
21
    this.length = 0;
 
22
    this.addEach(values);
 
23
}
 
24
 
 
25
// hack so require("sorted-set").SortedSet will work in MontageJS
 
26
SortedSet.SortedSet = SortedSet;
 
27
 
 
28
Object.addEach(SortedSet.prototype, GenericCollection.prototype);
 
29
Object.addEach(SortedSet.prototype, GenericSet.prototype);
 
30
Object.addEach(SortedSet.prototype, ObservableObject.prototype);
 
31
Object.addEach(SortedSet.prototype, ObservableRange.prototype);
 
32
 
 
33
SortedSet.prototype.isSorted = true;
 
34
 
 
35
SortedSet.prototype.constructClone = function (values) {
 
36
    return new this.constructor(
 
37
        values,
 
38
        this.contentEquals,
 
39
        this.contentCompare,
 
40
        this.getDefault
 
41
    );
 
42
};
 
43
 
 
44
SortedSet.prototype.has = function (value) {
 
45
    if (this.root) {
 
46
        this.splay(value);
 
47
        return this.contentEquals(value, this.root.value);
 
48
    } else {
 
49
        return false;
 
50
    }
 
51
};
 
52
 
 
53
SortedSet.prototype.get = function (value) {
 
54
    if (this.root) {
 
55
        this.splay(value);
 
56
        if (this.contentEquals(value, this.root.value)) {
 
57
            return this.root.value;
 
58
        }
 
59
    }
 
60
    return this.getDefault(value);
 
61
};
 
62
 
 
63
SortedSet.prototype.add = function (value) {
 
64
    var node = new this.Node(value);
 
65
    if (this.root) {
 
66
        this.splay(value);
 
67
        if (!this.contentEquals(value, this.root.value)) {
 
68
            var comparison = this.contentCompare(value, this.root.value);
 
69
            if (comparison === 0) {
 
70
                throw new Error("SortedSet cannot contain incomparable but inequal values: " + value + " and " + this.root.value);
 
71
            }
 
72
            if (this.dispatchesRangeChanges) {
 
73
                this.dispatchRangeWillChange([value], [], this.root.index);
 
74
            }
 
75
            if (comparison < 0) {
 
76
                // rotate right
 
77
                //   R        N
 
78
                //  / \  ->  / \
 
79
                // l   r    l   R
 
80
                // :   :    :    \
 
81
                //                r
 
82
                //                :
 
83
                node.right = this.root;
 
84
                node.left = this.root.left;
 
85
                this.root.left = null;
 
86
                this.root.touch();
 
87
            } else {
 
88
                // rotate left
 
89
                //   R        N
 
90
                //  / \  ->  / \
 
91
                // l   r    R   r
 
92
                // :   :   /    :
 
93
                //        l
 
94
                //        :
 
95
                node.left = this.root;
 
96
                node.right = this.root.right;
 
97
                this.root.right = null;
 
98
                this.root.touch();
 
99
            }
 
100
            node.touch();
 
101
            this.root = node;
 
102
            this.length++;
 
103
            if (this.dispatchesRangeChanges) {
 
104
                this.dispatchRangeChange([value], [], this.root.index);
 
105
            }
 
106
            return true;
 
107
        }
 
108
    } else {
 
109
        if (this.dispatchesRangeChanges) {
 
110
            this.dispatchRangeWillChange([value], [], 0);
 
111
        }
 
112
        this.root = node;
 
113
        this.length++;
 
114
        if (this.dispatchesRangeChanges) {
 
115
            this.dispatchRangeChange([value], [], 0);
 
116
        }
 
117
        return true;
 
118
    }
 
119
    return false;
 
120
};
 
121
 
 
122
SortedSet.prototype['delete'] = function (value) {
 
123
    if (this.root) {
 
124
        this.splay(value);
 
125
        if (this.contentEquals(value, this.root.value)) {
 
126
            var index = this.root.index;
 
127
            if (this.dispatchesRangeChanges) {
 
128
                this.dispatchRangeWillChange([], [value], index);
 
129
            }
 
130
            if (!this.root.left) {
 
131
                this.root = this.root.right;
 
132
            } else {
 
133
                // remove the right side of the tree,
 
134
                var right = this.root.right;
 
135
                this.root = this.root.left;
 
136
                // the tree now only contains the left side of the tree, so all
 
137
                // values are less than the value deleted.
 
138
                // splay so that the root has an empty right child
 
139
                this.splay(value);
 
140
                // put the right side of the tree back
 
141
                this.root.right = right;
 
142
            }
 
143
            this.length--;
 
144
            if (this.root) {
 
145
                this.root.touch();
 
146
            }
 
147
            if (this.dispatchesRangeChanges) {
 
148
                this.dispatchRangeChange([], [value], index);
 
149
            }
 
150
            return true;
 
151
        }
 
152
    }
 
153
    return false;
 
154
};
 
155
 
 
156
SortedSet.prototype.indexOf = function (value) {
 
157
    if (this.root) {
 
158
        this.splay(value);
 
159
        if (this.contentEquals(value, this.root.value)) {
 
160
            return this.root.index;
 
161
        }
 
162
    }
 
163
    return -1;
 
164
};
 
165
 
 
166
SortedSet.prototype.findValue = function (value) {
 
167
    if (this.root) {
 
168
        this.splay(value);
 
169
        if (this.contentEquals(value, this.root.value)) {
 
170
            return this.root;
 
171
        }
 
172
    }
 
173
};
 
174
 
 
175
SortedSet.prototype.findGreatest = function (at) {
 
176
    if (this.root) {
 
177
        at = at || this.root;
 
178
        while (at.right) {
 
179
            at = at.right;
 
180
        }
 
181
        return at;
 
182
    }
 
183
};
 
184
 
 
185
SortedSet.prototype.findLeast = function (at) {
 
186
    if (this.root) {
 
187
        at = at || this.root;
 
188
        while (at.left) {
 
189
            at = at.left;
 
190
        }
 
191
        return at;
 
192
    }
 
193
};
 
194
 
 
195
SortedSet.prototype.findGreatestLessThanOrEqual = function (value) {
 
196
    if (this.root) {
 
197
        this.splay(value);
 
198
        // assert root.value <= value
 
199
        return this.root;
 
200
    }
 
201
};
 
202
 
 
203
SortedSet.prototype.findGreatestLessThan = function (value) {
 
204
    if (this.root) {
 
205
        this.splay(value);
 
206
        // assert root.value <= value
 
207
        return this.root.getPrevious();
 
208
    }
 
209
};
 
210
 
 
211
SortedSet.prototype.findLeastGreaterThanOrEqual = function (value) {
 
212
    if (this.root) {
 
213
        this.splay(value);
 
214
        // assert root.value <= value
 
215
        var comparison = this.contentCompare(value, this.root.value);
 
216
        if (comparison === 0) {
 
217
            return this.root;
 
218
        } else {
 
219
            return this.root.getNext();
 
220
        }
 
221
    }
 
222
};
 
223
 
 
224
SortedSet.prototype.findLeastGreaterThan = function (value) {
 
225
    if (this.root) {
 
226
        this.splay(value);
 
227
        // assert root.value <= value
 
228
        var comparison = this.contentCompare(value, this.root.value);
 
229
        return this.root.getNext();
 
230
    }
 
231
};
 
232
 
 
233
SortedSet.prototype.pop = function () {
 
234
    if (this.root) {
 
235
        var found = this.findGreatest();
 
236
        this["delete"](found.value);
 
237
        return found.value;
 
238
    }
 
239
};
 
240
 
 
241
SortedSet.prototype.shift = function () {
 
242
    if (this.root) {
 
243
        var found = this.findLeast();
 
244
        this["delete"](found.value);
 
245
        return found.value;
 
246
    }
 
247
};
 
248
 
 
249
SortedSet.prototype.push = function () {
 
250
    this.addEach(arguments);
 
251
};
 
252
 
 
253
SortedSet.prototype.unshift = function () {
 
254
    this.addEach(arguments);
 
255
};
 
256
 
 
257
SortedSet.prototype.slice = function (start, end) {
 
258
    var temp;
 
259
    start = start || 0;
 
260
    end = end || this.length;
 
261
    if (start < 0) {
 
262
        start += this.length;
 
263
    }
 
264
    if (end < 0) {
 
265
        end += this.length;
 
266
    }
 
267
    var sliced = [];
 
268
    if (this.root) {
 
269
        this.splayIndex(start);
 
270
        while (this.root.index < end) {
 
271
            sliced.push(this.root.value);
 
272
            if (!this.root.right) {
 
273
                break;
 
274
            }
 
275
            this.splay(this.root.getNext().value);
 
276
        }
 
277
    }
 
278
    return sliced;
 
279
};
 
280
 
 
281
SortedSet.prototype.splice = function (at, length /*...plus*/) {
 
282
    return this.swap(at, length, Array.prototype.slice.call(arguments, 2));
 
283
};
 
284
 
 
285
SortedSet.prototype.swap = function (start, length, plus) {
 
286
    if (start === undefined && length === undefined) {
 
287
        return [];
 
288
    }
 
289
    start = start || 0;
 
290
    if (start < 0) {
 
291
        start += this.length;
 
292
    }
 
293
    if (length === undefined) {
 
294
        length = Infinity;
 
295
    }
 
296
    var swapped = [];
 
297
 
 
298
    if (this.root) {
 
299
 
 
300
        // start
 
301
        this.splayIndex(start);
 
302
 
 
303
        // minus length
 
304
        for (var i = 0; i < length; i++) {
 
305
            swapped.push(this.root.value);
 
306
            var next = this.root.getNext();
 
307
            this["delete"](this.root.value);
 
308
            if (!next) {
 
309
                break;
 
310
            }
 
311
            this.splay(next.value);
 
312
        }
 
313
    }
 
314
 
 
315
    // plus
 
316
    this.addEach(plus);
 
317
 
 
318
    return swapped;
 
319
};
 
320
 
 
321
// This is the simplified top-down splaying algorithm from: "Self-adjusting
 
322
// Binary Search Trees" by Sleator and Tarjan guarantees that the root.value <=
 
323
// value if root exists
 
324
// - as described in https://github.com/hij1nx/forest
 
325
SortedSet.prototype.splay = function (value) {
 
326
    var stub, left, right, temp, root, history;
 
327
 
 
328
    if (!this.root) {
 
329
        return;
 
330
    }
 
331
 
 
332
    // Create a stub node.  The use of the stub node is a bit
 
333
    // counter-intuitive: The right child of the stub node will hold the L tree
 
334
    // of the algorithm.  The left child of the stub node will hold the R tree
 
335
    // of the algorithm.  Using a stub node, left and right will always be
 
336
    // nodes and we avoid special cases.
 
337
    // - http://code.google.com/p/v8/source/browse/branches/bleeding_edge/src/splay-tree-inl.h
 
338
    stub = left = right = new this.Node();
 
339
    // The history is an upside down tree used to propagate new tree sizes back
 
340
    // up the left and right arms of a traversal.  The right children of the
 
341
    // transitive left side of the tree will be former roots while linking
 
342
    // left.  The left children of the transitive walk to the right side of the
 
343
    // history tree will all be previous roots from linking right.  The last
 
344
    // node of the left and right traversal will each become a child of the new
 
345
    // root.
 
346
    history = new this.Node();
 
347
    root = this.root;
 
348
 
 
349
    while (true) {
 
350
        var comparison = this.contentCompare(value, root.value);
 
351
        if (comparison < 0) {
 
352
            if (root.left) {
 
353
                if (this.contentCompare(value, root.left.value) < 0) {
 
354
                    // rotate right
 
355
                    //        Root         L(temp)
 
356
                    //      /     \       / \
 
357
                    //     L(temp) R    LL    Root
 
358
                    //    / \                /    \
 
359
                    //  LL   LR            LR      R
 
360
                    temp = root.left;
 
361
                    root.left = temp.right;
 
362
                    root.touch();
 
363
                    temp.right = root;
 
364
                    temp.touch();
 
365
                    root = temp;
 
366
                    if (!root.left) {
 
367
                        break;
 
368
                    }
 
369
                }
 
370
                // remember former root for repropagating length
 
371
                temp = new Node();
 
372
                temp.right = root;
 
373
                temp.left = history.left;
 
374
                history.left = temp;
 
375
                // link left
 
376
                right.left = root;
 
377
                right.touch();
 
378
                right = root;
 
379
                root = root.left;
 
380
            } else {
 
381
                break;
 
382
            }
 
383
        } else if (comparison > 0) {
 
384
            if (root.right) {
 
385
                if (this.contentCompare(value, root.right.value) > 0) {
 
386
                    // rotate left
 
387
                    //        Root         L(temp)
 
388
                    //      /     \       / \
 
389
                    //     L(temp) R    LL    Root
 
390
                    //    / \                /    \
 
391
                    //  LL   LR            LR      R
 
392
                    temp = root.right;
 
393
                    root.right = temp.left;
 
394
                    root.touch();
 
395
                    temp.left = root;
 
396
                    temp.touch();
 
397
                    root = temp;
 
398
                    if (!root.right) {
 
399
                        break;
 
400
                    }
 
401
                }
 
402
                // remember former root for repropagating length
 
403
                temp = new Node();
 
404
                temp.left = root;
 
405
                temp.right = history.right;
 
406
                history.right = temp;
 
407
                // link right
 
408
                left.right = root;
 
409
                left.touch();
 
410
                left = root;
 
411
                root = root.right;
 
412
            } else {
 
413
                break;
 
414
            }
 
415
        } else { // equal or incomparable
 
416
            break;
 
417
        }
 
418
    }
 
419
 
 
420
    // reassemble
 
421
    left.right = root.left;
 
422
    left.touch();
 
423
    right.left = root.right;
 
424
    right.touch();
 
425
    root.left = stub.right;
 
426
    root.right = stub.left;
 
427
 
 
428
    // propagate new lengths
 
429
    while (history.left) {
 
430
        history.left.right.touch();
 
431
        history.left = history.left.left;
 
432
    }
 
433
    while (history.right) {
 
434
        history.right.left.touch();
 
435
        history.right = history.right.right;
 
436
    }
 
437
    root.touch();
 
438
 
 
439
    this.root = root;
 
440
};
 
441
 
 
442
// an internal utility for splaying a node based on its index
 
443
SortedSet.prototype.splayIndex = function (index) {
 
444
    if (this.root) {
 
445
        var at = this.root;
 
446
        var atIndex = this.root.index;
 
447
 
 
448
        while (atIndex !== index) {
 
449
            if (atIndex > index && at.left) {
 
450
                at = at.left;
 
451
                atIndex -= 1 + (at.right ? at.right.length : 0);
 
452
            } else if (atIndex < index && at.right) {
 
453
                at = at.right;
 
454
                atIndex += 1 + (at.left ? at.left.length : 0);
 
455
            } else {
 
456
                break;
 
457
            }
 
458
        }
 
459
 
 
460
        this.splay(at.value);
 
461
 
 
462
        return this.root.index === index;
 
463
    }
 
464
    return false;
 
465
};
 
466
 
 
467
SortedSet.prototype.reduce = function (callback, basis, thisp) {
 
468
    if (this.root) {
 
469
        basis = this.root.reduce(callback, basis, 0, thisp, this);
 
470
    }
 
471
    return basis;
 
472
};
 
473
 
 
474
SortedSet.prototype.reduceRight = function (callback, basis, thisp) {
 
475
    if (this.root) {
 
476
        basis = this.root.reduceRight(callback, basis, this.length - 1, thisp, this);
 
477
    }
 
478
    return basis;
 
479
};
 
480
 
 
481
SortedSet.prototype.min = function (at) {
 
482
    var least = this.findLeast(at);
 
483
    if (least) {
 
484
        return least.value;
 
485
    }
 
486
};
 
487
 
 
488
SortedSet.prototype.max = function (at) {
 
489
    var greatest = this.findGreatest(at);
 
490
    if (greatest) {
 
491
        return greatest.value;
 
492
    }
 
493
};
 
494
 
 
495
SortedSet.prototype.one = function () {
 
496
    return this.min();
 
497
};
 
498
 
 
499
SortedSet.prototype.clear = function () {
 
500
    var minus;
 
501
    if (this.dispatchesRangeChanges) {
 
502
        minus = this.toArray();
 
503
        this.dispatchRangeWillChange([], minus, 0);
 
504
    }
 
505
    this.root = null;
 
506
    this.length = 0;
 
507
    if (this.dispatchesRangeChanges) {
 
508
        this.dispatchRangeChange([], minus, 0);
 
509
    }
 
510
};
 
511
 
 
512
SortedSet.prototype.iterate = function (start, end) {
 
513
    return new this.Iterator(this, start, end);
 
514
};
 
515
 
 
516
SortedSet.prototype.Iterator = SortedSetIterator;
 
517
 
 
518
SortedSet.prototype.summary = function () {
 
519
    if (this.root) {
 
520
        return this.root.summary();
 
521
    } else {
 
522
        return "()";
 
523
    }
 
524
};
 
525
 
 
526
SortedSet.prototype.log = function (charmap, logNode, callback, thisp) {
 
527
    charmap = charmap || TreeLog.unicodeRound;
 
528
    logNode = logNode || this.logNode;
 
529
    if (!callback) {
 
530
        callback = console.log;
 
531
        thisp = console;
 
532
    }
 
533
 
 
534
    // Bind is unavailable in PhantomJS, the only environment of consequence
 
535
    // that does not implement it yet.
 
536
    var originalCallback = callback;
 
537
    callback = function () {
 
538
        return originalCallback.apply(thisp, arguments);
 
539
    };
 
540
 
 
541
    if (this.root) {
 
542
        this.root.log(charmap, logNode, callback, callback);
 
543
    }
 
544
};
 
545
 
 
546
SortedSet.prototype.logNode = function (node, log, logBefore) {
 
547
    log(" " + node.value);
 
548
};
 
549
 
 
550
SortedSet.logCharsets = TreeLog;
 
551
 
 
552
SortedSet.prototype.Node = Node;
 
553
 
 
554
function Node(value) {
 
555
    this.value = value;
 
556
    this.left = null;
 
557
    this.right = null;
 
558
    this.length = 1;
 
559
}
 
560
 
 
561
// TODO case where no basis is provided for reduction
 
562
 
 
563
Node.prototype.reduce = function (callback, basis, index, thisp, tree, depth) {
 
564
    depth = depth || 0;
 
565
    if (this.left) {
 
566
        // prerecord length to be resistant to mutation
 
567
        var length = this.left.length;
 
568
        basis = this.left.reduce(callback, basis, index, thisp, tree, depth + 1);
 
569
        index += length;
 
570
    }
 
571
    basis = callback.call(thisp, basis, this.value, index, tree, this, depth);
 
572
    index += 1;
 
573
    if (this.right) {
 
574
        basis = this.right.reduce(callback, basis, index, thisp, tree, depth + 1);
 
575
    }
 
576
    return basis;
 
577
};
 
578
 
 
579
Node.prototype.reduceRight = function (callback, basis, index, thisp, tree, depth) {
 
580
    depth = depth || 0;
 
581
    if (this.right) {
 
582
        basis = this.right.reduce(callback, basis, index, thisp, tree, depth + 1);
 
583
        index -= this.right.length;
 
584
    }
 
585
    basis = callback.call(thisp, basis, this.value, this.value, tree, this, depth);
 
586
    index -= 1;
 
587
    if (this.left) {
 
588
        basis = this.left.reduce(callback, basis, index, thisp, tree, depth + 1);
 
589
    }
 
590
    return basis;
 
591
};
 
592
 
 
593
Node.prototype.touch = function () {
 
594
    this.length = 1 +
 
595
        (this.left ? this.left.length : 0) +
 
596
        (this.right ? this.right.length : 0);
 
597
    this.index = this.left ? this.left.length : 0;
 
598
};
 
599
 
 
600
Node.prototype.checkIntegrity = function () {
 
601
    var length = 1;
 
602
    length += this.left ? this.left.checkIntegrity() : 0;
 
603
    length += this.right ? this.right.checkIntegrity() : 0;
 
604
    if (this.length !== length)
 
605
        throw new Error("Integrity check failed: " + this.summary());
 
606
    return length;
 
607
}
 
608
 
 
609
// get the next node in this subtree
 
610
Node.prototype.getNext = function () {
 
611
    var node = this;
 
612
    if (node.right) {
 
613
        node = node.right;
 
614
        while (node.left) {
 
615
            node = node.left;
 
616
        }
 
617
        return node;
 
618
    }
 
619
};
 
620
 
 
621
// get the previous node in this subtree
 
622
Node.prototype.getPrevious = function () {
 
623
    var node = this;
 
624
    if (node.left) {
 
625
        node = node.left;
 
626
        while (node.right) {
 
627
            node = node.right;
 
628
        }
 
629
        return node;
 
630
    }
 
631
};
 
632
 
 
633
Node.prototype.summary = function () {
 
634
    var value = this.value || "-";
 
635
    value += " <" + this.length;
 
636
    if (!this.left && !this.right) {
 
637
        return "(" + value + ")";
 
638
    }
 
639
    return "(" + value + " " + (
 
640
        this.left ? this.left.summary() : "()"
 
641
    ) + ", " + (
 
642
        this.right ? this.right.summary() : "()"
 
643
    ) + ")";
 
644
};
 
645
 
 
646
Node.prototype.log = function (charmap, logNode, log, logAbove) {
 
647
    var self = this;
 
648
 
 
649
    var branch;
 
650
    if (this.left && this.right) {
 
651
        branch = charmap.intersection;
 
652
    } else if (this.left) {
 
653
        branch = charmap.branchUp;
 
654
    } else if (this.right) {
 
655
        branch = charmap.branchDown;
 
656
    } else {
 
657
        branch = charmap.through;
 
658
    }
 
659
 
 
660
    var loggedAbove;
 
661
    this.left && this.left.log(
 
662
        charmap,
 
663
        logNode,
 
664
        function innerWrite(line) {
 
665
            if (!loggedAbove) {
 
666
                loggedAbove = true;
 
667
                // leader
 
668
                logAbove(charmap.fromBelow + charmap.through + line);
 
669
            } else {
 
670
                // below
 
671
                logAbove(charmap.strafe + " " + line);
 
672
            }
 
673
        },
 
674
        function innerWriteAbove(line) {
 
675
            // above
 
676
            logAbove("  " + line);
 
677
        }
 
678
    );
 
679
 
 
680
    var loggedOn;
 
681
    logNode(
 
682
        this,
 
683
        function innerWrite(line) {
 
684
            if (!loggedOn) {
 
685
                loggedOn = true;
 
686
                log(branch + line);
 
687
            } else {
 
688
                log((self.right ? charmap.strafe : " ") + line);
 
689
            }
 
690
        },
 
691
        function innerWriteAbove(line) {
 
692
            logAbove((self.left ? charmap.strafe : " ") + line);
 
693
        }
 
694
    );
 
695
 
 
696
    var loggedBelow;
 
697
    this.right && this.right.log(
 
698
        charmap,
 
699
        logNode,
 
700
        function innerWrite(line) {
 
701
            if (!loggedBelow) {
 
702
                loggedBelow = true;
 
703
                log(charmap.fromAbove + charmap.through + line);
 
704
            } else {
 
705
                log("  " + line);
 
706
            }
 
707
        },
 
708
        function innerWriteAbove(line) {
 
709
            log(charmap.strafe + " " + line);
 
710
        }
 
711
    );
 
712
};
 
713
 
 
714
function SortedSetIterator(set, start, end) {
 
715
    this.set = set;
 
716
    this.prev = null;
 
717
    this.end = end;
 
718
    if (start) {
 
719
        var next = this.set.findLeastGreaterThanOrEqual(start);
 
720
        if (next) {
 
721
            this.set.splay(next.value);
 
722
            this.prev = next.getPrevious();
 
723
        }
 
724
    }
 
725
    this.index = 0;
 
726
}
 
727
 
 
728
SortedSetIterator.prototype = Object.create(SortedSetIterator.prototype);
 
729
SortedSetIterator.prototype.constructor = SortedSetIterator;
 
730
 
 
731
SortedSetIterator.prototype.next = function () {
 
732
    var next;
 
733
    if (this.prev) {
 
734
        next = this.set.findLeastGreaterThan(this.prev.value);
 
735
    } else {
 
736
        next = this.set.findLeast();
 
737
    }
 
738
    if (!next) {
 
739
        return Iterator.done;
 
740
    }
 
741
    if (
 
742
        this.end !== undefined &&
 
743
        this.set.contentCompare(next.value, this.end) >= 0
 
744
    ) {
 
745
        return Iterator.done;
 
746
    }
 
747
    this.prev = next;
 
748
    return new Iterator.Iteration(
 
749
        next.value,
 
750
        this.index++
 
751
    );
 
752
};
 
753