source: trip-planner-front/node_modules/hdr-histogram-js/src/packedarray/PackedArrayContext.ts@ 8d391a1

Last change on this file since 8d391a1 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 23.5 KB
Line 
1/*
2 * This is a TypeScript port of the original Java version, which was written by
3 * Gil Tene as described in
4 * https://github.com/HdrHistogram/HdrHistogram
5 * and released to the public domain, as explained at
6 * http://creativecommons.org/publicdomain/zero/1.0/
7 */
8
9/**
10 * A packed-value, sparse array context used for storing 64 bit signed values.
11 *
12 * An array context is optimised for tracking sparsely set (as in mostly zeros) values that tend to not make
13 * use pof the full 64 bit value range even when they are non-zero. The array context's internal representation
14 * is such that the packed value at each virtual array index may be represented by 0-8 bytes of actual storage.
15 *
16 * An array context encodes the packed values in 8 "set trees" with each set tree representing one byte of the
17 * packed value at the virtual index in question. The {@link #getPackedIndex(int, int, boolean)} method is used
18 * to look up the byte-index corresponding to the given (set tree) value byte of the given virtual index, and can
19 * be used to add entries to represent that byte as needed. As a succesful {@link #getPackedIndex(int, int, boolean)}
20 * may require a resizing of the array, it can throw a {@link ResizeException} to indicate that the requested
21 * packed index cannot be found or added without a resize of the physical storage.
22 *
23 */
24export const MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY = 16;
25const MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH = Math.pow(2, 13) - 1; //(Short.MAX_VALUE / 4); TODO ALEX why ???
26const SET_0_START_INDEX = 0;
27const NUMBER_OF_SETS = 8;
28const LEAF_LEVEL_SHIFT = 3;
29const NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET = 0;
30const NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS = 1;
31const PACKED_ARRAY_GROWTH_INCREMENT = 16;
32const PACKED_ARRAY_GROWTH_FRACTION_POW2 = 4;
33
34const { pow, ceil, log2, max } = Math;
35
36const bitCount = (n: number) => {
37 var bits = 0;
38 while (n !== 0) {
39 bits += bitCount32(n | 0);
40 n /= 0x100000000;
41 }
42 return bits;
43};
44
45const bitCount32 = (n: number) => {
46 n = n - ((n >> 1) & 0x55555555);
47 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
48 return (((n + (n >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
49};
50
51export class PackedArrayContext {
52 public readonly isPacked: boolean;
53 physicalLength: number;
54
55 private array: ArrayBuffer;
56 private byteArray: Uint8Array;
57 private shortArray: Uint16Array;
58 private longArray: Float64Array;
59 private populatedShortLength: number = 0;
60 private virtualLength: number;
61 private topLevelShift: number = Number.MAX_VALUE; // Make it non-sensical until properly initialized.
62
63 constructor(virtualLength: number, initialPhysicalLength: number) {
64 this.physicalLength = Math.max(
65 initialPhysicalLength,
66 MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
67 );
68 this.isPacked =
69 this.physicalLength <= MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH;
70 if (!this.isPacked) {
71 this.physicalLength = virtualLength;
72 }
73 this.array = new ArrayBuffer(this.physicalLength * 8);
74 this.initArrayViews(this.array);
75 this.init(virtualLength);
76 }
77
78 private initArrayViews(array: ArrayBuffer) {
79 this.byteArray = new Uint8Array(array);
80 this.shortArray = new Uint16Array(array);
81 this.longArray = new Float64Array(array);
82 }
83
84 private init(virtualLength: number) {
85 if (!this.isPacked) {
86 // Deal with non-packed context init:
87 this.virtualLength = virtualLength;
88 return;
89 }
90
91 this.populatedShortLength = SET_0_START_INDEX + 8;
92
93 // Populate empty root entries, and point to them from the root indexes:
94 for (let i = 0; i < NUMBER_OF_SETS; i++) {
95 this.setAtShortIndex(SET_0_START_INDEX + i, 0);
96 }
97
98 this.setVirtualLength(virtualLength);
99 }
100
101 public clear() {
102 this.byteArray.fill(0);
103 this.init(this.virtualLength);
104 }
105
106 public copyAndIncreaseSize(
107 newPhysicalArrayLength: number,
108 newVirtualArrayLength: number
109 ) {
110 const ctx = new PackedArrayContext(
111 newVirtualArrayLength,
112 newPhysicalArrayLength
113 );
114 if (this.isPacked) {
115 ctx.populateEquivalentEntriesWithEntriesFromOther(this);
116 }
117 return ctx;
118 }
119
120 public getPopulatedShortLength() {
121 return this.populatedShortLength;
122 }
123
124 public getPopulatedLongLength() {
125 return (this.getPopulatedShortLength() + 3) >> 2; // round up
126 }
127
128 public setAtByteIndex(byteIndex: number, value: number) {
129 this.byteArray[byteIndex] = value;
130 }
131
132 public getAtByteIndex(byteIndex: number) {
133 return this.byteArray[byteIndex];
134 }
135
136 /**
137 * add a byte value to a current byte value in the array
138 * @param byteIndex index of byte value to add to
139 * @param valueToAdd byte value to add
140 * @return the afterAddValue. ((afterAddValue & 0x100) != 0) indicates a carry.
141 */
142 public addAtByteIndex(byteIndex: number, valueToAdd: number) {
143 const newValue = this.byteArray[byteIndex] + valueToAdd;
144 this.byteArray[byteIndex] = newValue;
145 return newValue;
146 }
147
148 setPopulatedLongLength(newPopulatedLongLength: number) {
149 this.populatedShortLength = newPopulatedLongLength << 2;
150 }
151
152 public getVirtualLength() {
153 return this.virtualLength;
154 }
155 public length() {
156 return this.physicalLength;
157 }
158
159 setAtShortIndex(shortIndex: number, value: number) {
160 this.shortArray[shortIndex] = value;
161 }
162
163 setAtLongIndex(longIndex: number, value: number) {
164 this.longArray[longIndex] = value;
165 }
166
167 getAtShortIndex(shortIndex: number) {
168 return this.shortArray[shortIndex];
169 }
170
171 getIndexAtShortIndex(shortIndex: number) {
172 return this.shortArray[shortIndex];
173 }
174
175 setPackedSlotIndicators(entryIndex: number, newPackedSlotIndicators: number) {
176 this.setAtShortIndex(
177 entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET,
178 newPackedSlotIndicators
179 );
180 }
181
182 getPackedSlotIndicators(entryIndex: number) {
183 return (
184 this.shortArray[entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET] &
185 0xffff
186 );
187 }
188
189 private getIndexAtEntrySlot(entryIndex: number, slot: number) {
190 return this.getAtShortIndex(
191 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot
192 );
193 }
194
195 setIndexAtEntrySlot(entryIndex: number, slot: number, newIndexValue: number) {
196 this.setAtShortIndex(
197 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot,
198 newIndexValue
199 );
200 }
201
202 private expandArrayIfNeeded(entryLengthInLongs: number) {
203 const currentLength = this.length();
204 if (currentLength < this.getPopulatedLongLength() + entryLengthInLongs) {
205 const growthIncrement = max(
206 entryLengthInLongs,
207 PACKED_ARRAY_GROWTH_INCREMENT,
208 this.getPopulatedLongLength() >> PACKED_ARRAY_GROWTH_FRACTION_POW2
209 );
210 this.resizeArray(currentLength + growthIncrement);
211 }
212 }
213
214 private newEntry(entryLengthInShorts: number) {
215 // Add entry at the end of the array:
216
217 const newEntryIndex = this.populatedShortLength;
218 this.expandArrayIfNeeded((entryLengthInShorts >> 2) + 1);
219 this.populatedShortLength = newEntryIndex + entryLengthInShorts;
220
221 for (let i = 0; i < entryLengthInShorts; i++) {
222 this.setAtShortIndex(newEntryIndex + i, -1); // Poison value -1. Must be overriden before reads
223 }
224 return newEntryIndex;
225 }
226
227 private newLeafEntry() {
228 // Add entry at the end of the array:
229 let newEntryIndex;
230
231 newEntryIndex = this.getPopulatedLongLength();
232 this.expandArrayIfNeeded(1);
233
234 this.setPopulatedLongLength(newEntryIndex + 1);
235
236 this.setAtLongIndex(newEntryIndex, 0);
237
238 return newEntryIndex;
239 }
240
241 /**
242 * Consolidate entry with previous entry verison if one exists
243 *
244 * @param entryIndex The shortIndex of the entry to be consolidated
245 * @param previousVersionIndex the index of the previous version of the entry
246 */
247 private consolidateEntry(entryIndex: number, previousVersionIndex: number) {
248 const previousVersionPackedSlotsIndicators = this.getPackedSlotIndicators(
249 previousVersionIndex
250 );
251 // Previous version exists, needs consolidation
252
253 const packedSlotsIndicators = this.getPackedSlotIndicators(entryIndex);
254
255 const insertedSlotMask =
256 packedSlotsIndicators ^ previousVersionPackedSlotsIndicators; // the only bit that differs
257 const slotsBelowBitNumber = packedSlotsIndicators & (insertedSlotMask - 1);
258 const insertedSlotIndex = bitCount(slotsBelowBitNumber);
259 const numberOfSlotsInEntry = bitCount(packedSlotsIndicators);
260
261 // Copy the entry slots from previous version, skipping the newly inserted slot in the target:
262 let sourceSlot = 0;
263 for (let targetSlot = 0; targetSlot < numberOfSlotsInEntry; targetSlot++) {
264 if (targetSlot !== insertedSlotIndex) {
265 const indexAtSlot = this.getIndexAtEntrySlot(
266 previousVersionIndex,
267 sourceSlot
268 );
269 if (indexAtSlot !== 0) {
270 this.setIndexAtEntrySlot(entryIndex, targetSlot, indexAtSlot);
271 }
272 sourceSlot++;
273 }
274 }
275 }
276
277 /**
278 * Expand entry as indicated.
279 *
280 * @param existingEntryIndex the index of the entry
281 * @param entryPointerIndex index to the slot pointing to the entry (needs to be fixed up)
282 * @param insertedSlotIndex realtive [packed] index of slot being inserted into entry
283 * @param insertedSlotMask mask value fo slot being inserted
284 * @param nextLevelIsLeaf the level below this one is a leaf level
285 * @return the updated index of the entry (-1 if epansion failed due to conflict)
286 * @throws RetryException if expansion fails due to concurrent conflict, and caller should try again.
287 */
288 expandEntry(
289 existingEntryIndex: number,
290 entryPointerIndex: number,
291 insertedSlotIndex: number,
292 insertedSlotMask: number,
293 nextLevelIsLeaf: boolean
294 ): number {
295 let packedSlotIndicators =
296 this.getAtShortIndex(existingEntryIndex) & 0xffff;
297 packedSlotIndicators |= insertedSlotMask;
298 const numberOfslotsInExpandedEntry = bitCount(packedSlotIndicators);
299
300 if (insertedSlotIndex >= numberOfslotsInExpandedEntry) {
301 throw new Error(
302 "inserted slot index is out of range given provided masks"
303 );
304 }
305
306 const expandedEntryLength =
307 numberOfslotsInExpandedEntry + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS;
308
309 // Create new next-level entry to refer to from slot at this level:
310 let indexOfNewNextLevelEntry = 0;
311 if (nextLevelIsLeaf) {
312 indexOfNewNextLevelEntry = this.newLeafEntry(); // Establish long-index to new leaf entry
313 } else {
314 // TODO: Optimize this by creating the whole sub-tree here, rather than a step that will immediaterly expand
315
316 // Create a new 1 word (empty, no slots set) entry for the next level:
317 indexOfNewNextLevelEntry = this.newEntry(
318 NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
319 ); // Establish short-index to new leaf entry
320
321 this.setPackedSlotIndicators(indexOfNewNextLevelEntry, 0);
322 }
323
324 const insertedSlotValue = indexOfNewNextLevelEntry;
325
326 const expandedEntryIndex = this.newEntry(expandedEntryLength);
327
328 // populate the packed indicators word:
329 this.setPackedSlotIndicators(expandedEntryIndex, packedSlotIndicators);
330
331 // Populate the inserted slot with the index of the new next level entry:
332 this.setIndexAtEntrySlot(
333 expandedEntryIndex,
334 insertedSlotIndex,
335 insertedSlotValue
336 );
337
338 this.setAtShortIndex(entryPointerIndex, expandedEntryIndex);
339 this.consolidateEntry(expandedEntryIndex, existingEntryIndex);
340
341 return expandedEntryIndex;
342 }
343
344 //
345 // ###### ######## ######## ## ## ### ## ## #### ## ## ######## ######## ## ##
346 // ## ## ## ## ## ## ## ## ## ## ## ### ## ## ## ## ## ##
347 // ## ## ## ## ## ## ## ## ## ## #### ## ## ## ## ## ##
348 // ## #### ###### ## ## ## ## ## ## ## ## ## ## ## ## ## ###### ###
349 // ## ## ## ## ## ## ######### ## ## ## ## #### ## ## ## ## ##
350 // ## ## ## ## ## ## ## ## ## ## ## ## ### ## ## ## ## ##
351 // ###### ######## ## ### ## ## ######## ## #### ## ## ######## ######## ## ##
352 //
353
354 getRootEntry(setNumber: number, insertAsNeeded: boolean = false) {
355 const entryPointerIndex = SET_0_START_INDEX + setNumber;
356 let entryIndex = this.getIndexAtShortIndex(entryPointerIndex);
357
358 if (entryIndex == 0) {
359 if (!insertAsNeeded) {
360 return 0; // Index does not currently exist in packed array;
361 }
362
363 entryIndex = this.newEntry(NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS);
364 // Create a new empty (no slots set) entry for the next level:
365 this.setPackedSlotIndicators(entryIndex, 0);
366
367 this.setAtShortIndex(entryPointerIndex, entryIndex);
368 }
369 return entryIndex;
370 }
371
372 /**
373 * Get the byte-index (into the packed array) corresponding to a given (set tree) value byte of given virtual index.
374 * Inserts new set tree nodes as needed if indicated.
375 *
376 * @param setNumber The set tree number (0-7, 0 corresponding with the LSByte set tree)
377 * @param virtualIndex The virtual index into the PackedArray
378 * @param insertAsNeeded If true, will insert new set tree nodes as needed if they do not already exist
379 * @return the byte-index corresponding to the given (set tree) value byte of the given virtual index
380 */
381 getPackedIndex(
382 setNumber: number,
383 virtualIndex: number,
384 insertAsNeeded: boolean
385 ) {
386 if (virtualIndex >= this.virtualLength) {
387 throw new Error(
388 `Attempting access at index ${virtualIndex}, beyond virtualLength ${this.virtualLength}`
389 );
390 }
391
392 let entryPointerIndex = SET_0_START_INDEX + setNumber; // TODO init needed ?
393 let entryIndex = this.getRootEntry(setNumber, insertAsNeeded);
394 if (entryIndex == 0) {
395 return -1; // Index does not currently exist in packed array;
396 }
397
398 // Work down the levels of non-leaf entries:
399 for (
400 let indexShift = this.topLevelShift;
401 indexShift >= LEAF_LEVEL_SHIFT;
402 indexShift -= 4
403 ) {
404 const nextLevelIsLeaf = indexShift === LEAF_LEVEL_SHIFT;
405 // Target is a packedSlotIndicators entry
406 const packedSlotIndicators = this.getPackedSlotIndicators(entryIndex);
407 const slotBitNumber = (virtualIndex / pow(2, indexShift)) & 0xf; //(virtualIndex >>> indexShift) & 0xf;
408 const slotMask = 1 << slotBitNumber;
409 const slotsBelowBitNumber = packedSlotIndicators & (slotMask - 1);
410 const slotNumber = bitCount(slotsBelowBitNumber);
411
412 if ((packedSlotIndicators & slotMask) === 0) {
413 // The entryIndex slot does not have the contents we want
414 if (!insertAsNeeded) {
415 return -1; // Index does not currently exist in packed array;
416 }
417
418 // Expand the entry, adding the index to new entry at the proper slot:
419 entryIndex = this.expandEntry(
420 entryIndex,
421 entryPointerIndex,
422 slotNumber,
423 slotMask,
424 nextLevelIsLeaf
425 );
426 }
427
428 // Next level's entry pointer index is in the appropriate slot in in the entries array in this entry:
429 entryPointerIndex =
430 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slotNumber;
431
432 entryIndex = this.getIndexAtShortIndex(entryPointerIndex);
433 }
434
435 // entryIndex is the long-index of a leaf entry that contains the value byte for the given set
436
437 const byteIndex = (entryIndex << 3) + (virtualIndex & 0x7); // Determine byte index offset within leaf entry
438 return byteIndex;
439 }
440
441 determineTopLevelShiftForVirtualLength(virtualLength: number) {
442 const sizeMagnitude = ceil(log2(virtualLength));
443 const eightsSizeMagnitude = sizeMagnitude - 3;
444 let multipleOfFourSizeMagnitude = ceil(eightsSizeMagnitude / 4) * 4;
445 multipleOfFourSizeMagnitude = max(multipleOfFourSizeMagnitude, 8);
446 const topLevelShiftNeeded = multipleOfFourSizeMagnitude - 4 + 3;
447 return topLevelShiftNeeded;
448 }
449
450 setVirtualLength(virtualLength: number) {
451 if (!this.isPacked) {
452 throw new Error(
453 "Should never be adjusting the virtual size of a non-packed context"
454 );
455 }
456 this.topLevelShift = this.determineTopLevelShiftForVirtualLength(
457 virtualLength
458 );
459 this.virtualLength = virtualLength;
460 }
461
462 getTopLevelShift() {
463 return this.topLevelShift;
464 }
465
466 //
467 // ## ## ######## ####### ######## ## ## ## ### ######## ########
468 // ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
469 // ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
470 // ### ####### ######## ## ## ######## ## ## ## ## ## ## ######
471 // ## ## ## ## ## ## ## ## ## ######### ## ##
472 // ## ## ## ## ## ## ## ## ## ## ## ## ##
473 // ## ## ## ####### ## ####### ######## ## ## ## ########
474 //
475
476 public resizeArray(newLength: number) {
477 const tmp = new Uint8Array(newLength * 8);
478 tmp.set(this.byteArray);
479 this.array = tmp.buffer;
480 this.initArrayViews(this.array);
481 this.physicalLength = newLength;
482 }
483
484 private populateEquivalentEntriesWithEntriesFromOther(
485 other: PackedArrayContext
486 ) {
487 if (this.virtualLength < other.getVirtualLength()) {
488 throw new Error("Cannot populate array of smaller virtual length");
489 }
490
491 for (let i = 0; i < NUMBER_OF_SETS; i++) {
492 const otherEntryIndex = other.getAtShortIndex(SET_0_START_INDEX + i);
493 if (otherEntryIndex == 0) continue; // No tree to duplicate
494 let entryIndexPointer = SET_0_START_INDEX + i;
495 for (let i = this.topLevelShift; i > other.topLevelShift; i -= 4) {
496 // for each inserted level:
497 // Allocate entry in other:
498 const sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + 1;
499 const newEntryIndex = this.newEntry(sizeOfEntry);
500
501 // Link new level in.
502 this.setAtShortIndex(entryIndexPointer, newEntryIndex);
503 // Populate new level entry, use pointer to slot 0 as place to populate under:
504 this.setPackedSlotIndicators(newEntryIndex, 0x1); // Slot 0 populated
505 entryIndexPointer =
506 newEntryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS; // Where the slot 0 index goes.
507 }
508 this.copyEntriesAtLevelFromOther(
509 other,
510 otherEntryIndex,
511 entryIndexPointer,
512 other.topLevelShift
513 );
514 }
515 }
516
517 private copyEntriesAtLevelFromOther(
518 other: PackedArrayContext,
519 otherLevelEntryIndex: number,
520 levelEntryIndexPointer: number,
521 otherIndexShift: number
522 ) {
523 const nextLevelIsLeaf = otherIndexShift == LEAF_LEVEL_SHIFT;
524 const packedSlotIndicators = other.getPackedSlotIndicators(
525 otherLevelEntryIndex
526 );
527 const numberOfSlots = bitCount(packedSlotIndicators);
528 const sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + numberOfSlots;
529 const entryIndex = this.newEntry(sizeOfEntry);
530
531 this.setAtShortIndex(levelEntryIndexPointer, entryIndex);
532 this.setAtShortIndex(
533 entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET,
534 packedSlotIndicators
535 );
536
537 for (let i = 0; i < numberOfSlots; i++) {
538 if (nextLevelIsLeaf) {
539 // Make leaf in other:
540 const leafEntryIndex = this.newLeafEntry();
541
542 this.setIndexAtEntrySlot(entryIndex, i, leafEntryIndex);
543
544 // OPTIM
545 // avoid iteration on all the values of the source ctx
546 const otherNextLevelEntryIndex = other.getIndexAtEntrySlot(
547 otherLevelEntryIndex,
548 i
549 );
550 this.longArray[leafEntryIndex] =
551 other.longArray[otherNextLevelEntryIndex];
552 } else {
553 const otherNextLevelEntryIndex = other.getIndexAtEntrySlot(
554 otherLevelEntryIndex,
555 i
556 );
557 this.copyEntriesAtLevelFromOther(
558 other,
559 otherNextLevelEntryIndex,
560 entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + i,
561 otherIndexShift - 4
562 );
563 }
564 }
565 }
566
567 getAtUnpackedIndex(index: number) {
568 return this.longArray[index];
569 }
570
571 setAtUnpackedIndex(index: number, newValue: number) {
572 this.longArray[index] = newValue;
573 }
574
575 lazysetAtUnpackedIndex(index: number, newValue: number) {
576 this.longArray[index] = newValue;
577 }
578
579 incrementAndGetAtUnpackedIndex(index: number) {
580 this.longArray[index]++;
581 return this.longArray[index];
582 }
583
584 addAndGetAtUnpackedIndex(index: number, valueToAdd: number) {
585 this.longArray[index] += valueToAdd;
586 return this.longArray[index];
587 }
588
589 //
590 // ######## ####### ###### ######## ######## #### ## ## ######
591 // ## ## ## ## ## ## ## ## ## ### ## ## ##
592 // ## ## ## ## ## ## ## ## #### ## ##
593 // ## ## ## ####### ###### ## ######## ## ## ## ## ## ####
594 // ## ## ## ## ## ## ## ## ## #### ## ##
595 // ## ## ## ## ## ## ## ## ## ## ### ## ##
596 // ## ####### ###### ## ## ## #### ## ## ######
597 //
598
599 private nonLeafEntryToString(
600 entryIndex: number,
601 indexShift: number,
602 indentLevel: number
603 ) {
604 let output = "";
605 for (let i = 0; i < indentLevel; i++) {
606 output += " ";
607 }
608 try {
609 const packedSlotIndicators = this.getPackedSlotIndicators(entryIndex);
610 output += `slotIndiators: 0x${toHex(
611 packedSlotIndicators
612 )}, prevVersionIndex: 0: [ `;
613
614 const numberOfslotsInEntry = bitCount(packedSlotIndicators);
615 for (let i = 0; i < numberOfslotsInEntry; i++) {
616 output += this.getIndexAtEntrySlot(entryIndex, i);
617 if (i < numberOfslotsInEntry - 1) {
618 output += ", ";
619 }
620 }
621 output += ` ] (indexShift = ${indexShift})\n`;
622 const nextLevelIsLeaf = indexShift == LEAF_LEVEL_SHIFT;
623 for (let i = 0; i < numberOfslotsInEntry; i++) {
624 const nextLevelEntryIndex = this.getIndexAtEntrySlot(entryIndex, i);
625 if (nextLevelIsLeaf) {
626 output += this.leafEntryToString(
627 nextLevelEntryIndex,
628 indentLevel + 4
629 );
630 } else {
631 output += this.nonLeafEntryToString(
632 nextLevelEntryIndex,
633 indexShift - 4,
634 indentLevel + 4
635 );
636 }
637 }
638 } catch (ex) {
639 output += `Exception thrown at nonLeafEnty at index ${entryIndex} with indexShift ${indexShift}\n`;
640 }
641 return output;
642 }
643
644 private leafEntryToString(entryIndex: number, indentLevel: number) {
645 let output = "";
646 for (let i = 0; i < indentLevel; i++) {
647 output += " ";
648 }
649 try {
650 output += "Leaf bytes : ";
651 for (let i = 0; i < 8; i++) {
652 output += `0x${toHex(this.byteArray[entryIndex * 8 + i])} `;
653 }
654 output += "\n";
655 } catch (ex) {
656 output += `Exception thrown at leafEnty at index ${entryIndex}\n`;
657 }
658 return output;
659 }
660
661 public toString() {
662 let output = "PackedArrayContext:\n";
663 if (!this.isPacked) {
664 return output + "Context is unpacked:\n"; // unpackedToString();
665 }
666 for (let setNumber = 0; setNumber < NUMBER_OF_SETS; setNumber++) {
667 try {
668 const entryPointerIndex = SET_0_START_INDEX + setNumber;
669 const entryIndex = this.getIndexAtShortIndex(entryPointerIndex);
670 output += `Set ${setNumber}: root = ${entryIndex} \n`;
671 if (entryIndex == 0) continue;
672 output += this.nonLeafEntryToString(entryIndex, this.topLevelShift, 4);
673 } catch (ex) {
674 output += `Exception thrown in set ${setNumber}%d\n`;
675 }
676 }
677 //output += recordedValuesToString();
678 return output;
679 }
680}
681
682const toHex = (n: number) => {
683 return Number(n)
684 .toString(16)
685 .padStart(2, "0");
686};
Note: See TracBrowser for help on using the repository browser.