Debian Codegraph @

packages/datagrid/src/sectionlist.ts

raw
1 // Copyright (c) Jupyter Development Team.
2 // Distributed under the terms of the Modified BSD License.
3 /*-----------------------------------------------------------------------------
4 | Copyright (c) 2014-2019, 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 import { ArrayExt } from '@lumino/algorithm';
11
12 /**
13 * An object which manages a collection of variable sized sections.
14 *
15 * #### Notes
16 * This class is an implementation detail. It is designed to manage
17 * the variable row and column sizes for a data grid. User code will
18 * not interact with this class directly.
19 */
20 export class SectionList {
21 /**
22 * Construct a new section list.
23 *
24 * @param options - The options for initializing the list.
25 */
26 constructor(options: SectionList.IOptions) {
27 this._minimumSize = options.minimumSize || 2;
28 this._defaultSize = Math.max(
29 this._minimumSize,
30 Math.floor(options.defaultSize)
31 );
32 }
33
34 /**
35 * The total size of all sections in the list.
36 *
37 * #### Complexity
38 * Constant.
39 */
40 get length(): number {
41 return this._length;
42 }
43
44 /**
45 * The total number of sections in the list.
46 *
47 * #### Complexity
48 * Constant.
49 */
50 get count(): number {
51 return this._count;
52 }
53
54 /**
55 * Get the minimum size of sections in the list.
56 *
57 * #### Complexity
58 * Constant.
59 */
60 get minimumSize(): number {
61 return this._minimumSize;
62 }
63
64 /**
65 * Set the minimum size of sections in the list.
66 *
67 * #### Complexity
68 * Linear on the number of resized sections.
69 */
70 set minimumSize(value: number) {
71 // Normalize the value.
72 value = Math.max(2, Math.floor(value));
73
74 // Bail early if the value does not change.
75 if (this._minimumSize === value) {
76 return;
77 }
78
79 // Update the internal minimum size.
80 this._minimumSize = value;
81
82 // Update default size if larger than minimum size
83 if (value > this._defaultSize) {
84 this.defaultSize = value;
85 }
86 }
87
88 /**
89 * Get the default size of sections in the list.
90 *
91 * #### Complexity
92 * Constant.
93 */
94 get defaultSize(): number {
95 return this._defaultSize;
96 }
97
98 /**
99 * Set the default size of sections in the list.
100 *
101 * #### Complexity
102 * Linear on the number of resized sections.
103 */
104 set defaultSize(value: number) {
105 // Normalize the value.
106 value = Math.max(this._minimumSize, Math.floor(value));
107
108 // Bail early if the value does not change.
109 if (this._defaultSize === value) {
110 return;
111 }
112
113 // Compute the delta default size.
114 let delta = value - this._defaultSize;
115
116 // Update the internal default size.
117 this._defaultSize = value;
118
119 // Update the length.
120 this._length += delta * (this._count - this._sections.length);
121
122 // Bail early if there are no modified sections.
123 if (this._sections.length === 0) {
124 return;
125 }
126
127 // Recompute the offsets of the modified sections.
128 for (let i = 0, n = this._sections.length; i < n; ++i) {
129 // Look up the previous and current modified sections.
130 let prev = this._sections[i - 1];
131 let curr = this._sections[i];
132
133 // Adjust the offset for the current section.
134 if (prev) {
135 let count = curr.index - prev.index - 1;
136 curr.offset = prev.offset + prev.size + count * value;
137 } else {
138 curr.offset = curr.index * value;
139 }
140 }
141 }
142
143 /**
144 * Clamp a size to the minimum section size
145 *
146 * @param size - The size to clamp.
147 *
148 * @returns The size or the section minimum size, whichever is larger
149 */
150 clampSize(size: number): number {
151 return Math.max(this._minimumSize, Math.floor(size));
152 }
153
154 /**
155 * Find the index of the section which covers the given offset.
156 *
157 * @param offset - The offset of the section of interest.
158 *
159 * @returns The index of the section which covers the given offset,
160 * or `-1` if the offset is out of range.
161 *
162 * #### Complexity
163 * Logarithmic on the number of resized sections.
164 */
165 indexOf(offset: number): number {
166 // Bail early if the offset is out of range.
167 if (offset < 0 || offset >= this._length || this._count === 0) {
168 return -1;
169 }
170
171 // Handle the simple case of no modified sections.
172 if (this._sections.length === 0) {
173 return Math.floor(offset / this._defaultSize);
174 }
175
176 // Find the modified section for the given offset.
177 let i = ArrayExt.lowerBound(this._sections, offset, Private.offsetCmp);
178
179 // Return the index of an exact match.
180 if (i < this._sections.length && this._sections[i].offset <= offset) {
181 return this._sections[i].index;
182 }
183
184 // Handle the case of no modified sections before the offset.
185 if (i === 0) {
186 return Math.floor(offset / this._defaultSize);
187 }
188
189 // Compute the index from the previous modified section.
190 let section = this._sections[i - 1];
191 let span = offset - (section.offset + section.size);
192 return section.index + Math.floor(span / this._defaultSize) + 1;
193 }
194
195 /**
196 * Find the offset of the section at the given index.
197 *
198 * @param index - The index of the section of interest.
199 *
200 * @returns The offset of the section at the given index, or `-1`
201 * if the index is out of range.
202 *
203 * #### Undefined Behavior
204 * An `index` which is non-integral.
205 *
206 * #### Complexity
207 * Logarithmic on the number of resized sections.
208 */
209 offsetOf(index: number): number {
210 // Bail early if the index is out of range.
211 if (index < 0 || index >= this._count) {
212 return -1;
213 }
214
215 // Handle the simple case of no modified sections.
216 if (this._sections.length === 0) {
217 return index * this._defaultSize;
218 }
219
220 // Find the modified section for the given index.
221 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
222
223 // Return the offset of an exact match.
224 if (i < this._sections.length && this._sections[i].index === index) {
225 return this._sections[i].offset;
226 }
227
228 // Handle the case of no modified sections before the index.
229 if (i === 0) {
230 return index * this._defaultSize;
231 }
232
233 // Compute the offset from the previous modified section.
234 let section = this._sections[i - 1];
235 let span = index - section.index - 1;
236 return section.offset + section.size + span * this._defaultSize;
237 }
238
239 /**
240 * Find the extent of the section at the given index.
241 *
242 * @param index - The index of the section of interest.
243 *
244 * @returns The extent of the section at the given index, or `-1`
245 * if the index is out of range.
246 *
247 * #### Undefined Behavior
248 * An `index` which is non-integral.
249 *
250 * #### Complexity
251 * Logarithmic on the number of resized sections.
252 */
253 extentOf(index: number): number {
254 // Bail early if the index is out of range.
255 if (index < 0 || index >= this._count) {
256 return -1;
257 }
258
259 // Handle the simple case of no modified sections.
260 if (this._sections.length === 0) {
261 return (index + 1) * this._defaultSize - 1;
262 }
263
264 // Find the modified section for the given index.
265 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
266
267 // Return the offset of an exact match.
268 if (i < this._sections.length && this._sections[i].index === index) {
269 return this._sections[i].offset + this._sections[i].size - 1;
270 }
271
272 // Handle the case of no modified sections before the index.
273 if (i === 0) {
274 return (index + 1) * this._defaultSize - 1;
275 }
276
277 // Compute the offset from the previous modified section.
278 let section = this._sections[i - 1];
279 let span = index - section.index;
280 return section.offset + section.size + span * this._defaultSize - 1;
281 }
282
283 /**
284 * Find the size of the section at the given index.
285 *
286 * @param index - The index of the section of interest.
287 *
288 * @returns The size of the section at the given index, or `-1`
289 * if the index is out of range.
290 *
291 * #### Undefined Behavior
292 * An `index` which is non-integral.
293 *
294 * #### Complexity
295 * Logarithmic on the number of resized sections.
296 */
297 sizeOf(index: number): number {
298 // Bail early if the index is out of range.
299 if (index < 0 || index >= this._count) {
300 return -1;
301 }
302
303 // Handle the simple case of no modified sections.
304 if (this._sections.length === 0) {
305 return this._defaultSize;
306 }
307
308 // Find the modified section for the given index.
309 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
310
311 // Return the size of an exact match.
312 if (i < this._sections.length && this._sections[i].index === index) {
313 return this._sections[i].size;
314 }
315
316 // Return the default size for all other cases.
317 return this._defaultSize;
318 }
319
320 /**
321 * Resize a section in the list.
322 *
323 * @param index - The index of the section to resize. This method
324 * is a no-op if this value is out of range.
325 *
326 * @param size - The new size of the section. This value will be
327 * clamped to an integer `>= 0`.
328 *
329 * #### Undefined Behavior
330 * An `index` which is non-integral.
331 *
332 * #### Complexity
333 * Linear on the number of resized sections.
334 */
335 resize(index: number, size: number): void {
336 // Bail early if the index is out of range.
337 if (index < 0 || index >= this._count) {
338 return;
339 }
340
341 // Clamp the size to an integer >= minimum size.
342 size = Math.max(this._minimumSize, Math.floor(size));
343
344 // Find the modified section for the given index.
345 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
346
347 // Update or create the modified section as needed.
348 let delta: number;
349 if (i < this._sections.length && this._sections[i].index === index) {
350 let section = this._sections[i];
351 delta = size - section.size;
352 section.size = size;
353 } else if (i === 0) {
354 let offset = index * this._defaultSize;
355 ArrayExt.insert(this._sections, i, { index, offset, size });
356 delta = size - this._defaultSize;
357 } else {
358 let section = this._sections[i - 1];
359 let span = index - section.index - 1;
360 let offset = section.offset + section.size + span * this._defaultSize;
361 ArrayExt.insert(this._sections, i, { index, offset, size });
362 delta = size - this._defaultSize;
363 }
364
365 // Adjust the length.
366 this._length += delta;
367
368 // Update all modified sections after the resized section.
369 for (let j = i + 1, n = this._sections.length; j < n; ++j) {
370 this._sections[j].offset += delta;
371 }
372 }
373
374 /**
375 * Insert sections into the list.
376 *
377 * @param index - The index at which to insert the sections. This
378 * value will be clamped to the bounds of the list.
379 *
380 * @param count - The number of sections to insert. This method
381 * is a no-op if this value is `<= 0`.
382 *
383 * #### Undefined Behavior
384 * An `index` or `count` which is non-integral.
385 *
386 * #### Complexity
387 * Linear on the number of resized sections.
388 */
389 insert(index: number, count: number): void {
390 // Bail early if there are no sections to insert.
391 if (count <= 0) {
392 return;
393 }
394
395 // Clamp the index to the bounds of the list.
396 index = Math.max(0, Math.min(index, this._count));
397
398 // Add the new sections to the totals.
399 let span = count * this._defaultSize;
400 this._count += count;
401 this._length += span;
402
403 // Bail early if there are no modified sections to update.
404 if (this._sections.length === 0) {
405 return;
406 }
407
408 // Find the modified section for the given index.
409 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
410
411 // Update all modified sections after the insert location.
412 for (let n = this._sections.length; i < n; ++i) {
413 let section = this._sections[i];
414 section.index += count;
415 section.offset += span;
416 }
417 }
418
419 /**
420 * Remove sections from the list.
421 *
422 * @param index - The index of the first section to remove. This
423 * method is a no-op if this value is out of range.
424 *
425 * @param count - The number of sections to remove. This method
426 * is a no-op if this value is `<= 0`.
427 *
428 * #### Undefined Behavior
429 * An `index` or `count` which is non-integral.
430 *
431 * #### Complexity
432 * Linear on the number of resized sections.
433 */
434 remove(index: number, count: number): void {
435 // Bail early if there is nothing to remove.
436 if (index < 0 || index >= this._count || count <= 0) {
437 return;
438 }
439
440 // Clamp the count to the bounds of the list.
441 count = Math.min(this._count - index, count);
442
443 // Handle the simple case of no modified sections to update.
444 if (this._sections.length === 0) {
445 this._count -= count;
446 this._length -= count * this._defaultSize;
447 return;
448 }
449
450 // Handle the simple case of removing all sections.
451 if (count === this._count) {
452 this._length = 0;
453 this._count = 0;
454 this._sections.length = 0;
455 return;
456 }
457
458 // Find the modified section for the start index.
459 let i = ArrayExt.lowerBound(this._sections, index, Private.indexCmp);
460
461 // Find the modified section for the end index.
462 let j = ArrayExt.lowerBound(
463 this._sections,
464 index + count,
465 Private.indexCmp
466 );
467
468 // Remove the relevant modified sections.
469 let removed = this._sections.splice(i, j - i);
470
471 // Compute the total removed span.
472 let span = (count - removed.length) * this._defaultSize;
473 for (let k = 0, n = removed.length; k < n; ++k) {
474 span += removed[k].size;
475 }
476
477 // Adjust the totals.
478 this._count -= count;
479 this._length -= span;
480
481 // Update all modified sections after the removed span.
482 for (let k = i, n = this._sections.length; k < n; ++k) {
483 let section = this._sections[k];
484 section.index -= count;
485 section.offset -= span;
486 }
487 }
488
489 /**
490 * Move sections within the list.
491 *
492 * @param index - The index of the first section to move. This method
493 * is a no-op if this value is out of range.
494 *
495 * @param count - The number of sections to move. This method is a
496 * no-op if this value is `<= 0`.
497 *
498 * @param destination - The destination index for the first section.
499 * This value will be clamped to the allowable range.
500 *
501 * #### Undefined Behavior
502 * An `index`, `count`, or `destination` which is non-integral.
503 *
504 * #### Complexity
505 * Linear on the number of moved resized sections.
506 */
507 move(index: number, count: number, destination: number): void {
508 // Bail early if there is nothing to move.
509 if (index < 0 || index >= this._count || count <= 0) {
510 return;
511 }
512
513 // Handle the simple case of no modified sections.
514 if (this._sections.length === 0) {
515 return;
516 }
517
518 // Clamp the move count to the limit.
519 count = Math.min(count, this._count - index);
520
521 // Clamp the destination index to the limit.
522 destination = Math.min(Math.max(0, destination), this._count - count);
523
524 // Bail early if there is no effective move.
525 if (index === destination) {
526 return;
527 }
528
529 // Compute the first affected index.
530 let i1 = Math.min(index, destination);
531
532 // Look up the first affected modified section.
533 let k1 = ArrayExt.lowerBound(this._sections, i1, Private.indexCmp);
534
535 // Bail early if there are no affected modified sections.
536 if (k1 === this._sections.length) {
537 return;
538 }
539
540 // Compute the last affected index.
541 let i2 = Math.max(index + count - 1, destination + count - 1);
542
543 // Look up the last affected modified section.
544 let k2 = ArrayExt.upperBound(this._sections, i2, Private.indexCmp) - 1;
545
546 // Bail early if there are no affected modified sections.
547 if (k2 < k1) {
548 return;
549 }
550
551 // Compute the pivot index.
552 let pivot = destination < index ? index : index + count;
553
554 // Compute the count for each side of the pivot.
555 let count1 = pivot - i1;
556 let count2 = i2 - pivot + 1;
557
558 // Compute the span for each side of the pivot.
559 let span1 = count1 * this._defaultSize;
560 let span2 = count2 * this._defaultSize;
561
562 // Adjust the spans for the modified sections.
563 for (let j = k1; j <= k2; ++j) {
564 let section = this._sections[j];
565 if (section.index < pivot) {
566 span1 += section.size - this._defaultSize;
567 } else {
568 span2 += section.size - this._defaultSize;
569 }
570 }
571
572 // Look up the pivot section.
573 let k3 = ArrayExt.lowerBound(this._sections, pivot, Private.indexCmp);
574
575 // Rotate the modified sections if needed.
576 if (k1 <= k3 && k3 <= k2) {
577 ArrayExt.rotate(this._sections, k3 - k1, k1, k2);
578 }
579
580 // Adjust the modified section indices and offsets.
581 for (let j = k1; j <= k2; ++j) {
582 let section = this._sections[j];
583 if (section.index < pivot) {
584 section.index += count2;
585 section.offset += span2;
586 } else {
587 section.index -= count1;
588 section.offset -= span1;
589 }
590 }
591 }
592
593 /**
594 * Reset all modified sections to the default size.
595 *
596 * #### Complexity
597 * Constant.
598 */
599 reset(): void {
600 this._sections.length = 0;
601 this._length = this._count * this._defaultSize;
602 }
603
604 /**
605 * Remove all sections from the list.
606 *
607 * #### Complexity
608 * Constant.
609 */
610 clear(): void {
611 this._count = 0;
612 this._length = 0;
613 this._sections.length = 0;
614 }
615
616 private _count = 0;
617 private _length = 0;
618 private _minimumSize: number;
619 private _defaultSize: number;
620 private _sections: Private.Section[] = [];
621 }
622
623 /**
624 * The namespace for the `SectionList` class statics.
625 */
626 export namespace SectionList {
627 /**
628 * An options object for initializing a section list.
629 */
630 export interface IOptions {
631 /**
632 * The size of new sections added to the list.
633 */
634 defaultSize: number;
635
636 /**
637 * The minimum size of the section list.
638 */
639 minimumSize?: number;
640 }
641 }
642
643 /**
644 * The namespace for the module implementation details.
645 */
646 namespace Private {
647 /**
648 * An object which represents a modified section.
649 */
650 export type Section = {
651 /**
652 * The index of the section.
653 *
654 * This is always `>= 0`.
655 */
656 index: number;
657
658 /**
659 * The offset of the section.
660 */
661 offset: number;
662
663 /**
664 * The size of the section.
665 *
666 * This is always `>= 0`.
667 */
668 size: number;
669 };
670
671 /**
672 * A comparison function for searching by offset.
673 */
674 export function offsetCmp(section: Section, offset: number): number {
675 if (offset < section.offset) {
676 return 1;
677 }
678 if (section.offset + section.size <= offset) {
679 return -1;
680 }
681 return 0;
682 }
683
684 /**
685 * A comparison function for searching by index.
686 */
687 export function indexCmp(section: Section, index: number): number {
688 return section.index - index;
689 }
690 }