https://zerowaste.org/assets/rope-sequence-540056b7.js

1// [email protected] downloaded from https://cdn.jsdelivr.net/npm/[email protected]/dist/index.js
2
3var GOOD_LEAF_SIZE = 200;
4
5// :: class<T> A rope sequence is a persistent sequence data structure
6// that supports appending, prepending, and slicing without doing a
7// full copy. It is represented as a mostly-balanced tree.
8var RopeSequence = function RopeSequence () {};
9
10RopeSequence.prototype.append = function append (other) {
11  if (!other.length) { return this }
12  other = RopeSequence.from(other);
13
14  return (!this.length && other) ||
15    (other.length < GOOD_LEAF_SIZE && this.leafAppend(other)) ||
16    (this.length < GOOD_LEAF_SIZE && other.leafPrepend(this)) ||
17    this.appendInner(other)
18};
19
20// :: (union<[T], RopeSequence<T>>) → RopeSequence<T>
21// Prepend an array or other rope to this one, returning a new rope.
22RopeSequence.prototype.prepend = function prepend (other) {
23  if (!other.length) { return this }
24  return RopeSequence.from(other).append(this)
25};
26
27RopeSequence.prototype.appendInner = function appendInner (other) {
28  return new Append(this, other)
29};
30
31// :: (?number, ?number) → RopeSequence<T>
32// Create a rope repesenting a sub-sequence of this rope.
33RopeSequence.prototype.slice = function slice (from, to) {
34    if ( from === void 0 ) from = 0;
35    if ( to === void 0 ) to = this.length;
36
37  if (from >= to) { return RopeSequence.empty }
38  return this.sliceInner(Math.max(0, from), Math.min(this.length, to))
39};
40
41// :: (number) → T
42// Retrieve the element at the given position from this rope.
43RopeSequence.prototype.get = function get (i) {
44  if (i < 0 || i >= this.length) { return undefined }
45  return this.getInner(i)
46};
47
48// :: ((element: T, index: number) → ?bool, ?number, ?number)
49// Call the given function for each element between the given
50// indices. This tends to be more efficient than looping over the
51// indices and calling `get`, because it doesn't have to descend the
52// tree for every element.
53RopeSequence.prototype.forEach = function forEach (f, from, to) {
54    if ( from === void 0 ) from = 0;
55    if ( to === void 0 ) to = this.length;
56
57  if (from <= to)
58    { this.forEachInner(f, from, to, 0); }
59  else
60    { this.forEachInvertedInner(f, from, to, 0); }
61};
62
63// :: ((element: T, index: number) → U, ?number, ?number) → [U]
64// Map the given functions over the elements of the rope, producing
65// a flat array.
66RopeSequence.prototype.map = function map (f, from, to) {
67    if ( from === void 0 ) from = 0;
68    if ( to === void 0 ) to = this.length;
69
70  var result = [];
71  this.forEach(function (elt, i) { return result.push(f(elt, i)); }, from, to);
72  return result
73};
74
75// :: (?union<[T], RopeSequence<T>>) → RopeSequence<T>
76// Create a rope representing the given array, or return the rope
77// itself if a rope was given.
78RopeSequence.from = function from (values) {
79  if (values instanceof RopeSequence) { return values }
80  return values && values.length ? new Leaf(values) : RopeSequence.empty
81};
82
83var Leaf = /*@__PURE__*/(function (RopeSequence) {
84  function Leaf(values) {
85    RopeSequence.call(this);
86    this.values = values;
87  }
88
89  if ( RopeSequence ) Leaf.__proto__ = RopeSequence;
90  Leaf.prototype = Object.create( RopeSequence && RopeSequence.prototype );
91  Leaf.prototype.constructor = Leaf;
92
93  var prototypeAccessors = { length: { configurable: true },depth: { configurable: true } };
94
95  Leaf.prototype.flatten = function flatten () {
96    return this.values
97  };
98
99  Leaf.prototype.sliceInner = function sliceInner (from, to) {
100    if (from == 0 && to == this.length) { return this }
101    return new Leaf(this.values.slice(from, to))
102  };
103
104  Leaf.prototype.getInner = function getInner (i) {
105    return this.values[i]
106  };
107
108  Leaf.prototype.forEachInner = function forEachInner (f, from, to, start) {
109    for (var i = from; i < to; i++)
110      { if (f(this.values[i], start + i) === false) { return false } }
111  };
112
113  Leaf.prototype.forEachInvertedInner = function forEachInvertedInner (f, from, to, start) {
114    for (var i = from - 1; i >= to; i--)
115      { if (f(this.values[i], start + i) === false) { return false } }
116  };
117
118  Leaf.prototype.leafAppend = function leafAppend (other) {
119    if (this.length + other.length <= GOOD_LEAF_SIZE)
120      { return new Leaf(this.values.concat(other.flatten())) }
121  };
122
123  Leaf.prototype.leafPrepend = function leafPrepend (other) {
124    if (this.length + other.length <= GOOD_LEAF_SIZE)
125      { return new Leaf(other.flatten().concat(this.values)) }
126  };
127
128  prototypeAccessors.length.get = function () { return this.values.length };
129
130  prototypeAccessors.depth.get = function () { return 0 };
131
132  Object.defineProperties( Leaf.prototype, prototypeAccessors );
133
134  return Leaf;
135}(RopeSequence));
136
137// :: RopeSequence
138// The empty rope sequence.
139RopeSequence.empty = new Leaf([]);
140
141var Append = /*@__PURE__*/(function (RopeSequence) {
142  function Append(left, right) {
143    RopeSequence.call(this);
144    this.left = left;
145    this.right = right;
146    this.length = left.length + right.length;
147    this.depth = Math.max(left.depth, right.depth) + 1;
148  }
149
150  if ( RopeSequence ) Append.__proto__ = RopeSequence;
151  Append.prototype = Object.create( RopeSequence && RopeSequence.prototype );
152  Append.prototype.constructor = Append;
153
154  Append.prototype.flatten = function flatten () {
155    return this.left.flatten().concat(this.right.flatten())
156  };
157
158  Append.prototype.getInner = function getInner (i) {
159    return i < this.left.length ? this.left.get(i) : this.right.get(i - this.left.length)
160  };
161
162  Append.prototype.forEachInner = function forEachInner (f, from, to, start) {
163    var leftLen = this.left.length;
164    if (from < leftLen &&
165        this.left.forEachInner(f, from, Math.min(to, leftLen), start) === false)
166      { return false }
167    if (to > leftLen &&
168        this.right.forEachInner(f, Math.max(from - leftLen, 0), Math.min(this.length, to) - leftLen, start + leftLen) === false)
169      { return false }
170  };
171
172  Append.prototype.forEachInvertedInner = function forEachInvertedInner (f, from, to, start) {
173    var leftLen = this.left.length;
174    if (from > leftLen &&
175        this.right.forEachInvertedInner(f, from - leftLen, Math.max(to, leftLen) - leftLen, start + leftLen) === false)
176      { return false }
177    if (to < leftLen &&
178        this.left.forEachInvertedInner(f, Math.min(from, leftLen), to, start) === false)
179      { return false }
180  };
181
182  Append.prototype.sliceInner = function sliceInner (from, to) {
183    if (from == 0 && to == this.length) { return this }
184    var leftLen = this.left.length;
185    if (to <= leftLen) { return this.left.slice(from, to) }
186    if (from >= leftLen) { return this.right.slice(from - leftLen, to - leftLen) }
187    return this.left.slice(from, leftLen).append(this.right.slice(0, to - leftLen))
188  };
189
190  Append.prototype.leafAppend = function leafAppend (other) {
191    var inner = this.right.leafAppend(other);
192    if (inner) { return new Append(this.left, inner) }
193  };
194
195  Append.prototype.leafPrepend = function leafPrepend (other) {
196    var inner = this.left.leafPrepend(other);
197    if (inner) { return new Append(inner, this.right) }
198  };
199
200  Append.prototype.appendInner = function appendInner (other) {
201    if (this.left.depth >= Math.max(this.right.depth, other.depth) + 1)
202      { return new Append(this.left, new Append(this.right, other)) }
203    return new Append(this, other)
204  };
205
206  return Append;
207}(RopeSequence));
208
209export default RopeSequence;