/**
* Advanced Data Structures for Performance Optimization
* [ENH: ALGO] High-performance data structures
*/
// =============================================================================
// Deque (Double-ended Queue) - O(1) push/pop from both ends
// =============================================================================
/**
* Efficient Deque implementation using circular buffer
* Used for BFS operations to replace O(n) Array.shift() with O(1) operation
*/
export class Deque<T> {
private buffer: (T | undefined)[];
private head: number;
private tail: number;
private _size: number;
private capacity: number;
constructor(initialCapacity: number = 16) {
this.capacity = initialCapacity;
this.buffer = new Array(initialCapacity);
this.head = 0;
this.tail = 0;
this._size = 0;
}
get size(): number {
return this._size;
}
isEmpty(): boolean {
return this._size === 0;
}
/**
* Add element to back - O(1) amortized
*/
pushBack(item: T): void {
if (this._size === this.capacity) {
this.resize();
}
this.buffer[this.tail] = item;
this.tail = (this.tail + 1) % this.capacity;
this._size++;
}
/**
* Add element to front - O(1) amortized
*/
pushFront(item: T): void {
if (this._size === this.capacity) {
this.resize();
}
this.head = (this.head - 1 + this.capacity) % this.capacity;
this.buffer[this.head] = item;
this._size++;
}
/**
* Remove element from front - O(1)
*/
popFront(): T | undefined {
if (this._size === 0) return undefined;
const item = this.buffer[this.head];
this.buffer[this.head] = undefined;
this.head = (this.head + 1) % this.capacity;
this._size--;
return item;
}
/**
* Remove element from back - O(1)
*/
popBack(): T | undefined {
if (this._size === 0) return undefined;
this.tail = (this.tail - 1 + this.capacity) % this.capacity;
const item = this.buffer[this.tail];
this.buffer[this.tail] = undefined;
this._size--;
return item;
}
/**
* Peek front element - O(1)
*/
peekFront(): T | undefined {
if (this._size === 0) return undefined;
return this.buffer[this.head];
}
/**
* Peek back element - O(1)
*/
peekBack(): T | undefined {
if (this._size === 0) return undefined;
return this.buffer[(this.tail - 1 + this.capacity) % this.capacity];
}
private resize(): void {
const newCapacity = this.capacity * 2;
const newBuffer = new Array(newCapacity);
for (let i = 0; i < this._size; i++) {
newBuffer[i] = this.buffer[(this.head + i) % this.capacity];
}
this.buffer = newBuffer;
this.head = 0;
this.tail = this._size;
this.capacity = newCapacity;
}
/**
* Convert to array - O(n)
*/
toArray(): T[] {
const result: T[] = [];
for (let i = 0; i < this._size; i++) {
result.push(this.buffer[(this.head + i) % this.capacity]!);
}
return result;
}
/**
* Clear deque - O(1)
*/
clear(): void {
this.buffer = new Array(this.capacity);
this.head = 0;
this.tail = 0;
this._size = 0;
}
}
// =============================================================================
// LRU Cache - O(1) get/put with automatic eviction
// =============================================================================
interface LRUNode<K, V> {
key: K;
value: V;
prev: LRUNode<K, V> | null;
next: LRUNode<K, V> | null;
timestamp: number;
}
/**
* LRU Cache with O(1) operations and TTL support
* Used for file content caching to reduce disk I/O
*/
export class LRUCache<K, V> {
private capacity: number;
private cache: Map<K, LRUNode<K, V>>;
private head: LRUNode<K, V> | null;
private tail: LRUNode<K, V> | null;
private ttlMs: number;
constructor(capacity: number, ttlMs: number = 5 * 60 * 1000) {
this.capacity = capacity;
this.cache = new Map();
this.head = null;
this.tail = null;
this.ttlMs = ttlMs;
}
get size(): number {
return this.cache.size;
}
/**
* Get value by key - O(1)
*/
get(key: K): V | undefined {
const node = this.cache.get(key);
if (!node) return undefined;
// Check TTL
if (Date.now() - node.timestamp > this.ttlMs) {
this.delete(key);
return undefined;
}
// Move to front (most recently used)
this.moveToFront(node);
return node.value;
}
/**
* Check if key exists - O(1)
*/
has(key: K): boolean {
const node = this.cache.get(key);
if (!node) return false;
// Check TTL
if (Date.now() - node.timestamp > this.ttlMs) {
this.delete(key);
return false;
}
return true;
}
/**
* Put value - O(1)
*/
set(key: K, value: V): void {
let node = this.cache.get(key);
if (node) {
// Update existing
node.value = value;
node.timestamp = Date.now();
this.moveToFront(node);
} else {
// Create new node
node = {
key,
value,
prev: null,
next: this.head,
timestamp: Date.now()
};
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node;
}
this.cache.set(key, node);
// Evict if over capacity
if (this.cache.size > this.capacity) {
this.evictLRU();
}
}
}
/**
* Delete key - O(1)
*/
delete(key: K): boolean {
const node = this.cache.get(key);
if (!node) return false;
this.removeNode(node);
this.cache.delete(key);
return true;
}
/**
* Clear cache - O(1)
*/
clear(): void {
this.cache.clear();
this.head = null;
this.tail = null;
}
/**
* Get all keys - O(n)
*/
keys(): K[] {
return Array.from(this.cache.keys());
}
private moveToFront(node: LRUNode<K, V>): void {
if (node === this.head) return;
this.removeNode(node);
node.prev = null;
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node;
}
}
private removeNode(node: LRUNode<K, V>): void {
if (node.prev) {
node.prev.next = node.next;
} else {
this.head = node.next;
}
if (node.next) {
node.next.prev = node.prev;
} else {
this.tail = node.prev;
}
}
private evictLRU(): void {
if (!this.tail) return;
const key = this.tail.key;
this.removeNode(this.tail);
this.cache.delete(key);
}
}
// =============================================================================
// Multi-Index Store - O(1) lookups by multiple keys
// =============================================================================
/**
* Multi-index data structure for efficient lookups by multiple keys
* Used for Issue tracking with O(1) lookups by ID, status, severity, category
*/
export class MultiIndexStore<T, K extends string = string> {
private primaryIndex: Map<K, T>;
private secondaryIndexes: Map<string, Map<unknown, Set<K>>>;
private keyExtractor: (item: T) => K;
constructor(keyExtractor: (item: T) => K) {
this.primaryIndex = new Map();
this.secondaryIndexes = new Map();
this.keyExtractor = keyExtractor;
}
get size(): number {
return this.primaryIndex.size;
}
/**
* Add secondary index - O(n) for initial setup, then O(1) per update
*/
addIndex<V>(name: string, valueExtractor: (item: T) => V): void {
const index = new Map<V, Set<K>>();
// Build index for existing items
for (const [key, item] of this.primaryIndex) {
const value = valueExtractor(item);
if (!index.has(value)) {
index.set(value, new Set());
}
index.get(value)!.add(key);
}
this.secondaryIndexes.set(name, index as Map<unknown, Set<K>>);
}
/**
* Get by primary key - O(1)
*/
get(key: K): T | undefined {
return this.primaryIndex.get(key);
}
/**
* Check if key exists - O(1)
*/
has(key: K): boolean {
return this.primaryIndex.has(key);
}
/**
* Get all items by secondary index value - O(1) lookup + O(k) to collect items
*/
getByIndex<V>(indexName: string, value: V): T[] {
const index = this.secondaryIndexes.get(indexName);
if (!index) return [];
const keys = index.get(value as unknown);
if (!keys) return [];
return Array.from(keys).map(k => this.primaryIndex.get(k)!);
}
/**
* Get count by secondary index value - O(1)
*/
countByIndex<V>(indexName: string, value: V): number {
const index = this.secondaryIndexes.get(indexName);
if (!index) return 0;
const keys = index.get(value as unknown);
return keys ? keys.size : 0;
}
/**
* Get all values for an index - O(1)
*/
getIndexValues(indexName: string): unknown[] {
const index = this.secondaryIndexes.get(indexName);
if (!index) return [];
return Array.from(index.keys());
}
/**
* Add or update item - O(k) where k is number of indexes
*/
set(item: T, oldItem?: T): void {
const key = this.keyExtractor(item);
// Remove old item from secondary indexes
if (oldItem) {
this.removeFromSecondaryIndexes(key, oldItem);
} else if (this.primaryIndex.has(key)) {
this.removeFromSecondaryIndexes(key, this.primaryIndex.get(key)!);
}
// Add to primary index
this.primaryIndex.set(key, item);
// Add to secondary indexes
this.addToSecondaryIndexes(key, item);
}
/**
* Delete item - O(k) where k is number of indexes
*/
delete(key: K): boolean {
const item = this.primaryIndex.get(key);
if (!item) return false;
this.removeFromSecondaryIndexes(key, item);
this.primaryIndex.delete(key);
return true;
}
/**
* Get all items - O(n)
*/
values(): T[] {
return Array.from(this.primaryIndex.values());
}
/**
* Clear all - O(1)
*/
clear(): void {
this.primaryIndex.clear();
for (const index of this.secondaryIndexes.values()) {
index.clear();
}
}
private addToSecondaryIndexes(_key: K, _item: T): void {
// This would require storing value extractors - simplified version
// In practice, you'd call addIndex with extractors that get stored
}
private removeFromSecondaryIndexes(key: K, _item: T): void {
for (const index of this.secondaryIndexes.values()) {
for (const keys of index.values()) {
keys.delete(key);
}
}
}
}
// =============================================================================
// Union-Find (Disjoint Set Union) - Nearly O(1) operations with path compression
// =============================================================================
/**
* Union-Find data structure for efficient relationship tracking
* Used for Issue merge/split tracking with near O(1) union and find operations
*/
export class UnionFind<T extends string = string> {
private parent: Map<T, T>;
private rank: Map<T, number>;
private _size: number;
constructor() {
this.parent = new Map();
this.rank = new Map();
this._size = 0;
}
get size(): number {
return this._size;
}
/**
* Make a new set with single element - O(1)
*/
makeSet(x: T): void {
if (this.parent.has(x)) return;
this.parent.set(x, x);
this.rank.set(x, 0);
this._size++;
}
/**
* Find root with path compression - O(α(n)) ≈ O(1)
*/
find(x: T): T {
if (!this.parent.has(x)) {
this.makeSet(x);
}
if (this.parent.get(x) !== x) {
// Path compression
this.parent.set(x, this.find(this.parent.get(x)!));
}
return this.parent.get(x)!;
}
/**
* Union by rank - O(α(n)) ≈ O(1)
*/
union(x: T, y: T): void {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return;
const rankX = this.rank.get(rootX)!;
const rankY = this.rank.get(rootY)!;
// Union by rank
if (rankX < rankY) {
this.parent.set(rootX, rootY);
} else if (rankX > rankY) {
this.parent.set(rootY, rootX);
} else {
this.parent.set(rootY, rootX);
this.rank.set(rootX, rankX + 1);
}
}
/**
* Check if two elements are in same set - O(α(n)) ≈ O(1)
*/
connected(x: T, y: T): boolean {
return this.find(x) === this.find(y);
}
/**
* Get all elements in same set as x - O(n)
*/
getSet(x: T): T[] {
const root = this.find(x);
const result: T[] = [];
for (const [element] of this.parent) {
if (this.find(element) === root) {
result.push(element);
}
}
return result;
}
/**
* Get number of distinct sets - O(n)
*/
getSetCount(): number {
const roots = new Set<T>();
for (const [element] of this.parent) {
roots.add(this.find(element));
}
return roots.size;
}
}
// =============================================================================
// Sliding Window Counter - O(1) operations for time-based counting
// =============================================================================
/**
* Sliding window counter for tracking events in recent N units
* Used for tracking recent issue transitions for stability detection
*/
export class SlidingWindowCounter {
private windowSize: number;
private counts: Map<number, number>;
private total: number;
constructor(windowSize: number) {
this.windowSize = windowSize;
this.counts = new Map();
this.total = 0;
}
/**
* Add event at position - O(1)
*/
add(position: number, count: number = 1): void {
const existing = this.counts.get(position) || 0;
this.counts.set(position, existing + count);
this.total += count;
}
/**
* Get count in window ending at position - O(windowSize) worst case
*/
getCount(currentPosition: number): number {
let count = 0;
const start = currentPosition - this.windowSize + 1;
for (let pos = start; pos <= currentPosition; pos++) {
count += this.counts.get(pos) || 0;
}
return count;
}
/**
* Clean up old entries - O(n)
*/
cleanup(currentPosition: number): void {
const cutoff = currentPosition - this.windowSize;
for (const [pos, count] of this.counts) {
if (pos <= cutoff) {
this.total -= count;
this.counts.delete(pos);
}
}
}
/**
* Get total count - O(1)
*/
getTotal(): number {
return this.total;
}
/**
* Clear all - O(1)
*/
clear(): void {
this.counts.clear();
this.total = 0;
}
}
// =============================================================================
// Issue Index - Specialized multi-index for Issue tracking
// =============================================================================
import type { Issue, IssueStatus, IssueCategory, Severity } from '../types/index.js';
/**
* Specialized index for Issue tracking with O(1) lookups
*/
export class IssueIndex {
// Primary index by ID (case-insensitive)
private byId: Map<string, Issue>;
// Secondary indexes
private byStatus: Map<IssueStatus, Set<string>>;
private bySeverity: Map<Severity, Set<string>>;
private byCategory: Map<IssueCategory, Set<string>>;
// Pre-computed counts
private statusCounts: Record<IssueStatus, number>;
private severityCounts: Record<Severity, number>;
private categoryCounts: Record<IssueCategory, number>;
// Transition tracking with sliding window
private transitionCounter: SlidingWindowCounter;
constructor() {
this.byId = new Map();
this.byStatus = new Map();
this.bySeverity = new Map();
this.byCategory = new Map();
this.statusCounts = {
RAISED: 0, CHALLENGED: 0, RESOLVED: 0, UNRESOLVED: 0,
DISMISSED: 0, MERGED: 0, SPLIT: 0
};
this.severityCounts = { CRITICAL: 0, HIGH: 0, MEDIUM: 0, LOW: 0 };
this.categoryCounts = {
SECURITY: 0, CORRECTNESS: 0, RELIABILITY: 0,
MAINTAINABILITY: 0, PERFORMANCE: 0
};
this.transitionCounter = new SlidingWindowCounter(2); // Track last 2 rounds
}
/**
* Get issue by ID - O(1)
*/
get(id: string): Issue | undefined {
return this.byId.get(id.toUpperCase());
}
/**
* Check if issue exists - O(1)
*/
has(id: string): boolean {
return this.byId.has(id.toUpperCase());
}
/**
* Add or update issue - O(1)
*/
upsert(issue: Issue): void {
const normalizedId = issue.id.toUpperCase();
const existing = this.byId.get(normalizedId);
if (existing) {
// Remove from old indexes
this.removeFromIndexes(existing);
}
// Add to primary index
this.byId.set(normalizedId, issue);
// Add to secondary indexes
this.addToIndexes(issue);
}
/**
* Delete issue - O(1)
*/
delete(id: string): boolean {
const normalizedId = id.toUpperCase();
const issue = this.byId.get(normalizedId);
if (!issue) return false;
this.removeFromIndexes(issue);
this.byId.delete(normalizedId);
return true;
}
/**
* Get issues by status - O(k) where k is result size
*/
getByStatus(status: IssueStatus): Issue[] {
const ids = this.byStatus.get(status);
if (!ids) return [];
return Array.from(ids).map(id => this.byId.get(id)!);
}
/**
* Get issues by severity - O(k) where k is result size
*/
getBySeverity(severity: Severity): Issue[] {
const ids = this.bySeverity.get(severity);
if (!ids) return [];
return Array.from(ids).map(id => this.byId.get(id)!);
}
/**
* Get issues by category - O(k) where k is result size
*/
getByCategory(category: IssueCategory): Issue[] {
const ids = this.byCategory.get(category);
if (!ids) return [];
return Array.from(ids).map(id => this.byId.get(id)!);
}
/**
* Get count by status - O(1)
*/
countByStatus(status: IssueStatus): number {
return this.statusCounts[status];
}
/**
* Get count by severity - O(1)
*/
countBySeverity(severity: Severity): number {
return this.severityCounts[severity];
}
/**
* Get count by category - O(1)
*/
countByCategory(category: IssueCategory): number {
return this.categoryCounts[category];
}
/**
* Get active issues (not RESOLVED, DISMISSED, MERGED) - O(k)
*/
getActiveIssues(): Issue[] {
const result: Issue[] = [];
const inactiveStatuses: IssueStatus[] = ['RESOLVED', 'DISMISSED', 'MERGED'];
for (const issue of this.byId.values()) {
if (!inactiveStatuses.includes(issue.status)) {
result.push(issue);
}
}
return result;
}
/**
* Get active count - O(1)
*/
getActiveCount(): number {
return this.size -
this.statusCounts.RESOLVED -
this.statusCounts.DISMISSED -
this.statusCounts.MERGED;
}
/**
* Get all issues - O(n)
*/
getAll(): Issue[] {
return Array.from(this.byId.values());
}
/**
* Get all status counts - O(1)
*/
getStatusCounts(): Record<IssueStatus, number> {
return { ...this.statusCounts };
}
/**
* Get all severity counts - O(1)
*/
getSeverityCounts(): Record<Severity, number> {
return { ...this.severityCounts };
}
/**
* Get all category counts - O(1)
*/
getCategoryCounts(): Record<IssueCategory, number> {
return { ...this.categoryCounts };
}
/**
* Record transition for stability tracking
*/
recordTransition(round: number): void {
this.transitionCounter.add(round);
}
/**
* Get recent transition count - O(1)
*/
getRecentTransitions(currentRound: number): number {
return this.transitionCounter.getCount(currentRound);
}
/**
* Check if issues are stabilized (no recent transitions)
*/
isStabilized(currentRound: number): boolean {
return this.transitionCounter.getCount(currentRound) === 0;
}
get size(): number {
return this.byId.size;
}
/**
* Clear all - O(1)
*/
clear(): void {
this.byId.clear();
this.byStatus.clear();
this.bySeverity.clear();
this.byCategory.clear();
for (const status of Object.keys(this.statusCounts) as IssueStatus[]) {
this.statusCounts[status] = 0;
}
for (const severity of Object.keys(this.severityCounts) as Severity[]) {
this.severityCounts[severity] = 0;
}
for (const category of Object.keys(this.categoryCounts) as IssueCategory[]) {
this.categoryCounts[category] = 0;
}
this.transitionCounter.clear();
}
/**
* Build from existing issues array - O(n)
*/
static fromArray(issues: Issue[]): IssueIndex {
const index = new IssueIndex();
for (const issue of issues) {
index.upsert(issue);
}
return index;
}
private addToIndexes(issue: Issue): void {
const normalizedId = issue.id.toUpperCase();
// Status index
if (!this.byStatus.has(issue.status)) {
this.byStatus.set(issue.status, new Set());
}
this.byStatus.get(issue.status)!.add(normalizedId);
this.statusCounts[issue.status]++;
// Severity index
if (!this.bySeverity.has(issue.severity)) {
this.bySeverity.set(issue.severity, new Set());
}
this.bySeverity.get(issue.severity)!.add(normalizedId);
this.severityCounts[issue.severity]++;
// Category index
if (!this.byCategory.has(issue.category)) {
this.byCategory.set(issue.category, new Set());
}
this.byCategory.get(issue.category)!.add(normalizedId);
this.categoryCounts[issue.category]++;
}
private removeFromIndexes(issue: Issue): void {
const normalizedId = issue.id.toUpperCase();
// Status index
this.byStatus.get(issue.status)?.delete(normalizedId);
this.statusCounts[issue.status]--;
// Severity index
this.bySeverity.get(issue.severity)?.delete(normalizedId);
this.severityCounts[issue.severity]--;
// Category index
this.byCategory.get(issue.category)?.delete(normalizedId);
this.categoryCounts[issue.category]--;
}
}
