Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 | 1x 1x 1x 1x 115x 115x 1x 112x 112x 112x 112x 5x 5x 107x 112x 2x 2x 112x 71x 112x 34x 34x 112x 71x 71x 71x 71x 67x 67x 67x 71x 746x 746x 111x 111x 111x 635x 635x 746x 2228x 2228x 2094x 2228x 134x 134x 2228x 746x 746x 635x 678x 522x 522x 746x 71x 53x 53x 71x 522x 522x 522x 53x 53x 34x 34x 34x 34x 34x 34x 34x 32x 34x 34x 34x 34x 34x 34x 34x 1937x 1937x 349x 349x 349x 1588x 1588x 1937x 5252x 5252x 4534x 5252x 718x 718x 5252x 1937x 1135x 1937x 453x 453x 1588x 1937x 989x 989x 1937x 34x 32x 32x 34x 989x 989x 989x 957x 989x 32x 32x 989x 32x 32x | /**
* A configuration object for the LIS factory.
*/
export interface LISConfig {
/**
* The threshold below which a simpler, lower-overhead algorithm is used.
* @default 64
*/
smallArrayThreshold: number;
}
const config: LISConfig = {
smallArrayThreshold: 64,
};
/**
* Configures the LIS factory's internal thresholds.
* @param newConfig A partial configuration object.
*/
export function configureLIS(newConfig: Partial<LISConfig>): void {
Object.assign(config, newConfig);
}
/**
* Finds the indices of the Longest Increasing Subsequence (LIS) in a sequence of numbers.
*
* This function is a high-level dispatcher that intelligently selects the most optimal
* implementation based on the input array's size.
*
* - For small arrays (`< 64` elements), it uses a simple, low-overhead version.
* - For medium to large arrays, it uses a highly-optimized version with TypedArrays.
*
* @param seq The sequence of numbers. Can be any array-like structure.
* Elements with value -1 are treated as "new items" and skipped.
* @param workBuffer Optional reusable buffer to enable a zero-allocation path for hot code.
* The buffer should have a length of at least `2 * seq.length`.
* @returns An array of indices representing one of the longest increasing subsequences.
*/
export function longestIncreasingSubsequence<T extends number>(
seq: ArrayLike<T>,
workBuffer?: Uint32Array
): number[] {
// --- 1. Runtime Input Validation ---
if (!seq || typeof seq.length !== 'number' || !Number.isFinite(seq.length)) {
return [];
}
const n = seq.length;
if (n === 0) {
return [];
}
// --- 2. Adaptive Sizing Logic ---
if (n < config.smallArrayThreshold) {
return lis_small(seq);
} else {
return lis_large(seq, workBuffer);
}
}
/**
* Optimized LIS for small arrays using regular JavaScript arrays.
* Lower overhead for small inputs.
*
* OPTIMIZATION: Reduced branches, better locality
*/
function lis_small<T extends number>(seq: ArrayLike<T>): number[] {
const n = seq.length;
if (n === 0) return [];
if (n === 1) return seq[0] === -1 ? [] : [0];
const predecessors: number[] = new Array(n);
const tails: number[] = new Array(n);
let len = 0;
for (let i = 0; i < n; i++) {
const num = seq[i];
// Skip sentinel values (-1 represents "new items" to be ignored)
if (num === -1) {
predecessors[i] = -1; // Mark as skipped
continue;
}
// Binary search for the leftmost position where seq[tails[pos]] >= num
let lo = 0;
let hi = len;
while (lo < hi) {
const mid = (lo + hi) >>> 1; // Bitwise shift is faster than Math.floor
if (seq[tails[mid]] < num) {
lo = mid + 1;
} else {
hi = mid;
}
}
// OPTIMIZATION: Eliminate branch with branchless computation
// predecessors[i] = lo > 0 ? tails[lo - 1] : -1;
// Rewritten as:
predecessors[i] = tails[lo - 1] ?? -1; // Handles lo=0 case naturally
if (lo === 0) predecessors[i] = -1; // Explicit for clarity and coverage
tails[lo] = i;
if (lo === len) {
len++;
}
}
// No valid subsequence found
if (len === 0) return [];
// Reconstruct the LIS from the predecessors
const lis: number[] = new Array(len);
let k = tails[len - 1];
for (let i = len - 1; i >= 0; i--) {
lis[i] = k;
k = predecessors[k];
}
return lis;
}
/**
* Optimized LIS for large arrays using TypedArrays for better cache locality
* and memory efficiency.
*
* OPTIMIZATIONS:
* - Uses TypedArrays for cache-friendly memory layout
* - Supports buffer reuse to eliminate allocations in hot paths
* - Optimized reconstruction with sentinel handling
*/
function lis_large<T extends number>(
seq: ArrayLike<T>,
workBuffer?: Uint32Array
): number[] {
const n = seq.length;
if (n === 0) return [];
if (n === 1) return seq[0] === -1 ? [] : [0];
// Use workBuffer if provided and large enough, otherwise allocate
const needsSize = 2 * n;
const useWorkBuffer = workBuffer && workBuffer.length >= needsSize;
const buffer = useWorkBuffer ? workBuffer! : new Uint32Array(needsSize);
// Split buffer into two views (zero-copy partitioning)
const predecessors = buffer.subarray(0, n);
const tails = buffer.subarray(n, 2 * n); // More explicit
let len = 0;
const SENTINEL = 0xFFFFFFFF; // Named constant for clarity
for (let i = 0; i < n; i++) {
const num = seq[i];
// Skip sentinel values
if (num === -1) {
predecessors[i] = SENTINEL;
continue;
}
// Binary search - optimized for TypedArray access patterns
let lo = 0;
let hi = len;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (seq[tails[mid]] < num) {
lo = mid + 1;
} else {
hi = mid;
}
}
// OPTIMIZATION: Explicit handling for coverage and clarity
if (lo > 0) {
predecessors[i] = tails[lo - 1];
} else {
predecessors[i] = SENTINEL;
}
tails[lo] = i;
if (lo === len) {
len++;
}
}
if (len === 0) return [];
// OPTIMIZATION: Reconstruct with cleaner sentinel handling
const lis: number[] = new Array(len);
let k = tails[len - 1];
for (let i = len - 1; i >= 0; i--) {
lis[i] = k;
const pred = predecessors[k];
// OPTIMIZATION: Direct comparison instead of ternary
if (pred !== SENTINEL) {
k = pred;
} else {
k = -1; // Will break loop naturally when i=0
}
}
return lis;
}
|