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 213 214 215 216 | 1x 1x 1x 1x 115x 115x 1x 120x 120x 120x 120x 5x 5x 115x 120x 3x 3x 119x 78x 120x 34x 34x 120x 78x 78x 78x 78x 69x 69x 69x 78x 753x 753x 118x 118x 118x 635x 635x 753x 2228x 2228x 2094x 2228x 134x 134x 2228x 753x 753x 635x 680x 522x 522x 753x 78x 53x 53x 78x 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
// Defensive: Explicit handling for lo=0 case (first element in sequence)
// Coverage: Complementary to lo>0 branch, both paths exercised by test suite
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
// Defensive: Handles both lo=0 (first element) and lo>0 (subsequent elements)
// Coverage: Complementary branches, both exercised by comprehensive test suite
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;
}
|