1 | // Copyright (c) Jupyter Development Team.
|
2 | // Distributed under the terms of the Modified BSD License.
|
3 | /*-----------------------------------------------------------------------------
|
4 | | Copyright (c) 2014-2017, PhosphorJS Contributors
|
5 | |
|
6 | | Distributed under the terms of the BSD 3-Clause License.
|
7 | |
|
8 | | The full license is in the file LICENSE, distributed with this software.
|
9 | |----------------------------------------------------------------------------*/
|
10 |
|
11 | /**
|
12 | * An object which can produce an iterator over its values.
|
13 | */
|
14 | export interface IIterable<T> {
|
15 | /**
|
16 | * Get an iterator over the object's values.
|
17 | *
|
18 | * @returns An iterator which yields the object's values.
|
19 | *
|
20 | * #### Notes
|
21 | * Depending on the iterable, the returned iterator may or may not be
|
22 | * a new object. A collection or other container-like object should
|
23 | * typically return a new iterator, while an iterator itself should
|
24 | * normally return `this`.
|
25 | */
|
26 | iter(): IIterator<T>;
|
27 | }
|
28 |
|
29 | /**
|
30 | * An object which traverses a collection of values.
|
31 | *
|
32 | * #### Notes
|
33 | * An `IIterator` is itself an `IIterable`. Most implementations of
|
34 | * `IIterator` should simply return `this` from the `iter()` method.
|
35 | */
|
36 | export interface IIterator<T> extends IIterable<T> {
|
37 | /**
|
38 | * Create an independent clone of the iterator.
|
39 | *
|
40 | * @returns A new independent clone of the iterator.
|
41 | *
|
42 | * #### Notes
|
43 | * The cloned iterator can be consumed independently of the current
|
44 | * iterator. In essence, it is a copy of the iterator value stream
|
45 | * which starts at the current location.
|
46 | *
|
47 | * This can be useful for lookahead and stream duplication.
|
48 | */
|
49 | clone(): IIterator<T>;
|
50 |
|
51 | /**
|
52 | * Get the next value from the iterator.
|
53 | *
|
54 | * @returns The next value from the iterator, or `undefined`.
|
55 | *
|
56 | * #### Notes
|
57 | * The `undefined` value is used to signal the end of iteration and
|
58 | * should therefore not be used as a value in a collection.
|
59 | *
|
60 | * The use of the `undefined` sentinel is an explicit design choice
|
61 | * which favors performance over purity. The ES6 iterator design of
|
62 | * returning a `{ value, done }` pair is suboptimal, as it requires
|
63 | * an object allocation on each iteration; and an `isDone()` method
|
64 | * would increase implementation and runtime complexity.
|
65 | */
|
66 | next(): T | undefined;
|
67 | }
|
68 |
|
69 | /**
|
70 | * A type alias for an iterable or builtin array-like object.
|
71 | */
|
72 | export type IterableOrArrayLike<T> = IIterable<T> | ArrayLike<T>;
|
73 |
|
74 | /**
|
75 | * Create an iterator for an iterable object.
|
76 | *
|
77 | * @param object - The iterable or array-like object of interest.
|
78 | *
|
79 | * @returns A new iterator for the given object.
|
80 | *
|
81 | * #### Notes
|
82 | * This function allows iteration algorithms to operate on user-defined
|
83 | * iterable types and builtin array-like objects in a uniform fashion.
|
84 | */
|
85 | export function iter<T>(object: IterableOrArrayLike<T>): IIterator<T> {
|
86 | let it: IIterator<T>;
|
87 | if (typeof (object as any).iter === 'function') {
|
88 | it = (object as IIterable<T>).iter();
|
89 | } else {
|
90 | it = new ArrayIterator<T>(object as ArrayLike<T>);
|
91 | }
|
92 | return it;
|
93 | }
|
94 |
|
95 | /**
|
96 | * Create an iterator for the keys in an object.
|
97 | *
|
98 | * @param object - The object of interest.
|
99 | *
|
100 | * @returns A new iterator for the keys in the given object.
|
101 | *
|
102 | * #### Complexity
|
103 | * Linear.
|
104 | *
|
105 | * #### Example
|
106 | * ```typescript
|
107 | * import { each, keys } from '@lumino/algorithm';
|
108 | *
|
109 | * let data = { one: 1, two: 2, three: 3 };
|
110 | *
|
111 | * each(keys(data), key => { console.log(key); }); // 'one', 'two', 'three'
|
112 | * ```
|
113 | */
|
114 | export function iterKeys<T>(object: {
|
115 | readonly [key: string]: T;
|
116 | }): IIterator<string> {
|
117 | return new KeyIterator(object);
|
118 | }
|
119 |
|
120 | /**
|
121 | * Create an iterator for the values in an object.
|
122 | *
|
123 | * @param object - The object of interest.
|
124 | *
|
125 | * @returns A new iterator for the values in the given object.
|
126 | *
|
127 | * #### Complexity
|
128 | * Linear.
|
129 | *
|
130 | * #### Example
|
131 | * ```typescript
|
132 | * import { each, values } from '@lumino/algorithm';
|
133 | *
|
134 | * let data = { one: 1, two: 2, three: 3 };
|
135 | *
|
136 | * each(values(data), value => { console.log(value); }); // 1, 2, 3
|
137 | * ```
|
138 | */
|
139 | export function iterValues<T>(object: {
|
140 | readonly [key: string]: T;
|
141 | }): IIterator<T> {
|
142 | return new ValueIterator<T>(object);
|
143 | }
|
144 |
|
145 | /**
|
146 | * Create an iterator for the items in an object.
|
147 | *
|
148 | * @param object - The object of interest.
|
149 | *
|
150 | * @returns A new iterator for the items in the given object.
|
151 | *
|
152 | * #### Complexity
|
153 | * Linear.
|
154 | *
|
155 | * #### Example
|
156 | * ```typescript
|
157 | * import { each, items } from '@lumino/algorithm';
|
158 | *
|
159 | * let data = { one: 1, two: 2, three: 3 };
|
160 | *
|
161 | * each(items(data), value => { console.log(value); }); // ['one', 1], ['two', 2], ['three', 3]
|
162 | * ```
|
163 | */
|
164 | export function iterItems<T>(object: {
|
165 | readonly [key: string]: T;
|
166 | }): IIterator<[string, T]> {
|
167 | return new ItemIterator<T>(object);
|
168 | }
|
169 |
|
170 | /**
|
171 | * Create an iterator for an iterator-like function.
|
172 | *
|
173 | * @param fn - A function which behaves like an iterator `next` method.
|
174 | *
|
175 | * @returns A new iterator for the given function.
|
176 | *
|
177 | * #### Notes
|
178 | * The returned iterator **cannot** be cloned.
|
179 | *
|
180 | * #### Example
|
181 | * ```typescript
|
182 | * import { each, iterFn } from '@lumino/algorithm';
|
183 | *
|
184 | * let it = iterFn((() => {
|
185 | * let i = 0;
|
186 | * return () => i > 3 ? undefined : i++;
|
187 | * })());
|
188 | *
|
189 | * each(it, v => { console.log(v); }); // 0, 1, 2, 3
|
190 | * ```
|
191 | */
|
192 | export function iterFn<T>(fn: () => T | undefined): IIterator<T> {
|
193 | return new FnIterator<T>(fn);
|
194 | }
|
195 |
|
196 | /**
|
197 | * Invoke a function for each value in an iterable.
|
198 | *
|
199 | * @param object - The iterable or array-like object of interest.
|
200 | *
|
201 | * @param fn - The callback function to invoke for each value.
|
202 | *
|
203 | * #### Notes
|
204 | * Iteration can be terminated early by returning `false` from the
|
205 | * callback function.
|
206 | *
|
207 | * #### Complexity
|
208 | * Linear.
|
209 | *
|
210 | * #### Example
|
211 | * ```typescript
|
212 | * import { each } from '@lumino/algorithm';
|
213 | *
|
214 | * let data = [5, 7, 0, -2, 9];
|
215 | *
|
216 | * each(data, value => { console.log(value); });
|
217 | * ```
|
218 | */
|
219 | export function each<T>(
|
220 | object: IterableOrArrayLike<T>,
|
221 | fn: (value: T, index: number) => boolean | void
|
222 | ): void {
|
223 | let index = 0;
|
224 | let it = iter(object);
|
225 | let value: T | undefined;
|
226 | while ((value = it.next()) !== undefined) {
|
227 | if (fn(value, index++) === false) {
|
228 | return;
|
229 | }
|
230 | }
|
231 | }
|
232 |
|
233 | /**
|
234 | * Test whether all values in an iterable satisfy a predicate.
|
235 | *
|
236 | * @param object - The iterable or array-like object of interest.
|
237 | *
|
238 | * @param fn - The predicate function to invoke for each value.
|
239 | *
|
240 | * @returns `true` if all values pass the test, `false` otherwise.
|
241 | *
|
242 | * #### Notes
|
243 | * Iteration terminates on the first `false` predicate result.
|
244 | *
|
245 | * #### Complexity
|
246 | * Linear.
|
247 | *
|
248 | * #### Example
|
249 | * ```typescript
|
250 | * import { every } from '@lumino/algorithm';
|
251 | *
|
252 | * let data = [5, 7, 1];
|
253 | *
|
254 | * every(data, value => value % 2 === 0); // false
|
255 | * every(data, value => value % 2 === 1); // true
|
256 | * ```
|
257 | */
|
258 | export function every<T>(
|
259 | object: IterableOrArrayLike<T>,
|
260 | fn: (value: T, index: number) => boolean
|
261 | ): boolean {
|
262 | let index = 0;
|
263 | let it = iter(object);
|
264 | let value: T | undefined;
|
265 | while ((value = it.next()) !== undefined) {
|
266 | if (!fn(value, index++)) {
|
267 | return false;
|
268 | }
|
269 | }
|
270 | return true;
|
271 | }
|
272 |
|
273 | /**
|
274 | * Test whether any value in an iterable satisfies a predicate.
|
275 | *
|
276 | * @param object - The iterable or array-like object of interest.
|
277 | *
|
278 | * @param fn - The predicate function to invoke for each value.
|
279 | *
|
280 | * @returns `true` if any value passes the test, `false` otherwise.
|
281 | *
|
282 | * #### Notes
|
283 | * Iteration terminates on the first `true` predicate result.
|
284 | *
|
285 | * #### Complexity
|
286 | * Linear.
|
287 | *
|
288 | * #### Example
|
289 | * ```typescript
|
290 | * import { some } from '@lumino/algorithm';
|
291 | *
|
292 | * let data = [5, 7, 1];
|
293 | *
|
294 | * some(data, value => value === 7); // true
|
295 | * some(data, value => value === 3); // false
|
296 | * ```
|
297 | */
|
298 | export function some<T>(
|
299 | object: IterableOrArrayLike<T>,
|
300 | fn: (value: T, index: number) => boolean
|
301 | ): boolean {
|
302 | let index = 0;
|
303 | let it = iter(object);
|
304 | let value: T | undefined;
|
305 | while ((value = it.next()) !== undefined) {
|
306 | if (fn(value, index++)) {
|
307 | return true;
|
308 | }
|
309 | }
|
310 | return false;
|
311 | }
|
312 |
|
313 | /**
|
314 | * Create an array from an iterable of values.
|
315 | *
|
316 | * @param object - The iterable or array-like object of interest.
|
317 | *
|
318 | * @returns A new array of values from the given object.
|
319 | *
|
320 | * #### Example
|
321 | * ```typescript
|
322 | * import { iter, toArray } from '@lumino/algorithm';
|
323 | *
|
324 | * let data = [1, 2, 3, 4, 5, 6];
|
325 | *
|
326 | * let stream = iter(data);
|
327 | *
|
328 | * toArray(stream); // [1, 2, 3, 4, 5, 6];
|
329 | * ```
|
330 | */
|
331 | export function toArray<T>(object: IterableOrArrayLike<T>): T[] {
|
332 | let index = 0;
|
333 | let result: T[] = [];
|
334 | let it = iter(object);
|
335 | let value: T | undefined;
|
336 | while ((value = it.next()) !== undefined) {
|
337 | result[index++] = value;
|
338 | }
|
339 | return result;
|
340 | }
|
341 |
|
342 | /**
|
343 | * Create an object from an iterable of key/value pairs.
|
344 | *
|
345 | * @param object - The iterable or array-like object of interest.
|
346 | *
|
347 | * @returns A new object mapping keys to values.
|
348 | *
|
349 | * #### Example
|
350 | * ```typescript
|
351 | * import { toObject } from '@lumino/algorithm';
|
352 | *
|
353 | * let data = [['one', 1], ['two', 2], ['three', 3]];
|
354 | *
|
355 | * toObject(data); // { one: 1, two: 2, three: 3 }
|
356 | * ```
|
357 | */
|
358 | export function toObject<T>(
|
359 | object: IterableOrArrayLike<[string, T]>
|
360 | ): { [key: string]: T } {
|
361 | let it = iter(object);
|
362 | let pair: [string, T] | undefined;
|
363 | let result: { [key: string]: T } = {};
|
364 | while ((pair = it.next()) !== undefined) {
|
365 | result[pair[0]] = pair[1];
|
366 | }
|
367 | return result;
|
368 | }
|
369 |
|
370 | /**
|
371 | * An iterator for an array-like object.
|
372 | *
|
373 | * #### Notes
|
374 | * This iterator can be used for any builtin JS array-like object.
|
375 | */
|
376 | export class ArrayIterator<T> implements IIterator<T> {
|
377 | /**
|
378 | * Construct a new array iterator.
|
379 | *
|
380 | * @param source - The array-like object of interest.
|
381 | */
|
382 | constructor(source: ArrayLike<T>) {
|
383 | this._source = source;
|
384 | }
|
385 |
|
386 | /**
|
387 | * Get an iterator over the object's values.
|
388 | *
|
389 | * @returns An iterator which yields the object's values.
|
390 | */
|
391 | iter(): IIterator<T> {
|
392 | return this;
|
393 | }
|
394 |
|
395 | /**
|
396 | * Create an independent clone of the iterator.
|
397 | *
|
398 | * @returns A new independent clone of the iterator.
|
399 | */
|
400 | clone(): IIterator<T> {
|
401 | let result = new ArrayIterator<T>(this._source);
|
402 | result._index = this._index;
|
403 | return result;
|
404 | }
|
405 |
|
406 | /**
|
407 | * Get the next value from the iterator.
|
408 | *
|
409 | * @returns The next value from the iterator, or `undefined`.
|
410 | */
|
411 | next(): T | undefined {
|
412 | if (this._index >= this._source.length) {
|
413 | return undefined;
|
414 | }
|
415 | return this._source[this._index++];
|
416 | }
|
417 |
|
418 | private _index = 0;
|
419 | private _source: ArrayLike<T>;
|
420 | }
|
421 |
|
422 | /**
|
423 | * An iterator for the keys in an object.
|
424 | *
|
425 | * #### Notes
|
426 | * This iterator can be used for any JS object.
|
427 | */
|
428 | export class KeyIterator implements IIterator<string> {
|
429 | /**
|
430 | * Construct a new key iterator.
|
431 | *
|
432 | * @param source - The object of interest.
|
433 | *
|
434 | * @param keys - The keys to iterate, if known.
|
435 | */
|
436 | constructor(
|
437 | source: { readonly [key: string]: any },
|
438 | keys = Object.keys(source)
|
439 | ) {
|
440 | this._source = source;
|
441 | this._keys = keys;
|
442 | }
|
443 |
|
444 | /**
|
445 | * Get an iterator over the object's values.
|
446 | *
|
447 | * @returns An iterator which yields the object's values.
|
448 | */
|
449 | iter(): IIterator<string> {
|
450 | return this;
|
451 | }
|
452 |
|
453 | /**
|
454 | * Create an independent clone of the iterator.
|
455 | *
|
456 | * @returns A new independent clone of the iterator.
|
457 | */
|
458 | clone(): IIterator<string> {
|
459 | let result = new KeyIterator(this._source, this._keys);
|
460 | result._index = this._index;
|
461 | return result;
|
462 | }
|
463 |
|
464 | /**
|
465 | * Get the next value from the iterator.
|
466 | *
|
467 | * @returns The next value from the iterator, or `undefined`.
|
468 | */
|
469 | next(): string | undefined {
|
470 | if (this._index >= this._keys.length) {
|
471 | return undefined;
|
472 | }
|
473 | let key = this._keys[this._index++];
|
474 | if (key in this._source) {
|
475 | return key;
|
476 | }
|
477 | return this.next();
|
478 | }
|
479 |
|
480 | private _index = 0;
|
481 | private _keys: string[];
|
482 | private _source: { readonly [key: string]: any };
|
483 | }
|
484 |
|
485 | /**
|
486 | * An iterator for the values in an object.
|
487 | *
|
488 | * #### Notes
|
489 | * This iterator can be used for any JS object.
|
490 | */
|
491 | export class ValueIterator<T> implements IIterator<T> {
|
492 | /**
|
493 | * Construct a new value iterator.
|
494 | *
|
495 | * @param source - The object of interest.
|
496 | *
|
497 | * @param keys - The keys to iterate, if known.
|
498 | */
|
499 | constructor(
|
500 | source: { readonly [key: string]: T },
|
501 | keys = Object.keys(source)
|
502 | ) {
|
503 | this._source = source;
|
504 | this._keys = keys;
|
505 | }
|
506 |
|
507 | /**
|
508 | * Get an iterator over the object's values.
|
509 | *
|
510 | * @returns An iterator which yields the object's values.
|
511 | */
|
512 | iter(): IIterator<T> {
|
513 | return this;
|
514 | }
|
515 |
|
516 | /**
|
517 | * Create an independent clone of the iterator.
|
518 | *
|
519 | * @returns A new independent clone of the iterator.
|
520 | */
|
521 | clone(): IIterator<T> {
|
522 | let result = new ValueIterator<T>(this._source, this._keys);
|
523 | result._index = this._index;
|
524 | return result;
|
525 | }
|
526 |
|
527 | /**
|
528 | * Get the next value from the iterator.
|
529 | *
|
530 | * @returns The next value from the iterator, or `undefined`.
|
531 | */
|
532 | next(): T | undefined {
|
533 | if (this._index >= this._keys.length) {
|
534 | return undefined;
|
535 | }
|
536 | let key = this._keys[this._index++];
|
537 | if (key in this._source) {
|
538 | return this._source[key];
|
539 | }
|
540 | return this.next();
|
541 | }
|
542 |
|
543 | private _index = 0;
|
544 | private _keys: string[];
|
545 | private _source: { readonly [key: string]: T };
|
546 | }
|
547 |
|
548 | /**
|
549 | * An iterator for the items in an object.
|
550 | *
|
551 | * #### Notes
|
552 | * This iterator can be used for any JS object.
|
553 | */
|
554 | export class ItemIterator<T> implements IIterator<[string, T]> {
|
555 | /**
|
556 | * Construct a new item iterator.
|
557 | *
|
558 | * @param source - The object of interest.
|
559 | *
|
560 | * @param keys - The keys to iterate, if known.
|
561 | */
|
562 | constructor(
|
563 | source: { readonly [key: string]: T },
|
564 | keys = Object.keys(source)
|
565 | ) {
|
566 | this._source = source;
|
567 | this._keys = keys;
|
568 | }
|
569 |
|
570 | /**
|
571 | * Get an iterator over the object's values.
|
572 | *
|
573 | * @returns An iterator which yields the object's values.
|
574 | */
|
575 | iter(): IIterator<[string, T]> {
|
576 | return this;
|
577 | }
|
578 |
|
579 | /**
|
580 | * Create an independent clone of the iterator.
|
581 | *
|
582 | * @returns A new independent clone of the iterator.
|
583 | */
|
584 | clone(): IIterator<[string, T]> {
|
585 | let result = new ItemIterator<T>(this._source, this._keys);
|
586 | result._index = this._index;
|
587 | return result;
|
588 | }
|
589 |
|
590 | /**
|
591 | * Get the next value from the iterator.
|
592 | *
|
593 | * @returns The next value from the iterator, or `undefined`.
|
594 | */
|
595 | next(): [string, T] | undefined {
|
596 | if (this._index >= this._keys.length) {
|
597 | return undefined;
|
598 | }
|
599 | let key = this._keys[this._index++];
|
600 | if (key in this._source) {
|
601 | return [key, this._source[key]];
|
602 | }
|
603 | return this.next();
|
604 | }
|
605 |
|
606 | private _index = 0;
|
607 | private _keys: string[];
|
608 | private _source: { readonly [key: string]: T };
|
609 | }
|
610 |
|
611 | /**
|
612 | * An iterator for an iterator-like function.
|
613 | */
|
614 | export class FnIterator<T> implements IIterator<T> {
|
615 | /**
|
616 | * Construct a new function iterator.
|
617 | *
|
618 | * @param fn - The iterator-like function of interest.
|
619 | */
|
620 | constructor(fn: () => T | undefined) {
|
621 | this._fn = fn;
|
622 | }
|
623 |
|
624 | /**
|
625 | * Get an iterator over the object's values.
|
626 | *
|
627 | * @returns An iterator which yields the object's values.
|
628 | */
|
629 | iter(): IIterator<T> {
|
630 | return this;
|
631 | }
|
632 |
|
633 | /**
|
634 | * Create an independent clone of the iterator.
|
635 | *
|
636 | * @returns A new independent clone of the iterator.
|
637 | */
|
638 | clone(): IIterator<T> {
|
639 | throw new Error('An `FnIterator` cannot be cloned.');
|
640 | }
|
641 |
|
642 | /**
|
643 | * Get the next value from the iterator.
|
644 | *
|
645 | * @returns The next value from the iterator, or `undefined`.
|
646 | */
|
647 | next(): T | undefined {
|
648 | return this._fn.call(undefined);
|
649 | }
|
650 |
|
651 | private _fn: () => T | undefined;
|
652 | }
|