Advanced Algorithms

// Bellman-Ford Algorithm for shortest paths with negative weights
class BellmanFord {
    findShortestPaths(edges: [number, number, number][], vertices: number, source: number): 
        { distances: number[], hasNegativeCycle: boolean } {
        const distances = new Array(vertices).fill(Infinity);
        distances[source] = 0;
        
        // Relax edges V-1 times
        for (let i = 0; i < vertices - 1; i++) {
            for (const [u, v, weight] of edges) {
                if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }
        
        // Check for negative cycles
        let hasNegativeCycle = false;
        for (const [u, v, weight] of edges) {
            if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
                hasNegativeCycle = true;
                break;
            }
        }
        
        return { distances, hasNegativeCycle };
    }
}

// Floyd-Warshall Algorithm for all-pairs shortest paths
class FloydWarshall {
    allPairsShortestPaths(matrix: number[][]): number[][] {
        const n = matrix.length;
        const dist = matrix.map(row => [...row]);
        
        // Initialize with infinity for no direct path
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (i !== j && dist[i][j] === 0) {
                    dist[i][j] = Infinity;
                }
            }
        }
        
        // Try all intermediate vertices
        for (let k = 0; k < n; k++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        return dist;
    }
}

// Topological Sort using DFS
class TopologicalSort {
    private visited: Set = new Set();
    private stack: number[] = [];
    
    topologicalSort(graph: Map): number[] {
        this.visited.clear();
        this.stack = [];
        
        for (const vertex of graph.keys()) {
            if (!this.visited.has(vertex)) {
                this.dfs(vertex, graph);
            }
        }
        
        return this.stack.reverse();
    }
    
    private dfs(vertex: number, graph: Map): void {
        this.visited.add(vertex);
        
        const neighbors = graph.get(vertex) || [];
        for (const neighbor of neighbors) {
            if (!this.visited.has(neighbor)) {
                this.dfs(neighbor, graph);
            }
        }
        
        this.stack.push(vertex);
    }
}
                                

// KMP (Knuth-Morris-Pratt) Algorithm
class KMPMatcher {
    // Build failure function (longest proper prefix which is also suffix)
    private buildFailureFunction(pattern: string): number[] {
        const m = pattern.length;
        const failure = new Array(m).fill(0);
        let j = 0;
        
        for (let i = 1; i < m; i++) {
            while (j > 0 && pattern[i] !== pattern[j]) {
                j = failure[j - 1];
            }
            
            if (pattern[i] === pattern[j]) {
                j++;
            }
            
            failure[i] = j;
        }
        
        return failure;
    }
    
    // Find all occurrences of pattern in text
    search(text: string, pattern: string): number[] {
        if (pattern.length === 0) return [];
        
        const n = text.length;
        const m = pattern.length;
        const failure = this.buildFailureFunction(pattern);
        const matches: number[] = [];
        let j = 0;
        
        for (let i = 0; i < n; i++) {
            while (j > 0 && text[i] !== pattern[j]) {
                j = failure[j - 1];
            }
            
            if (text[i] === pattern[j]) {
                j++;
            }
            
            if (j === m) {
                matches.push(i - m + 1);
                j = failure[j - 1];
            }
        }
        
        return matches;
    }
}

// Rabin-Karp Algorithm
class RabinKarpMatcher {
    private readonly prime = 101;
    private readonly base = 256;
    
    search(text: string, pattern: string): number[] {
        const n = text.length;
        const m = pattern.length;
        const matches: number[] = [];
        
        if (m > n) return matches;
        
        // Calculate hash values
        let patternHash = 0;
        let textHash = 0;
        let h = 1;
        
        // Calculate h = base^(m-1) % prime
        for (let i = 0; i < m - 1; i++) {
            h = (h * this.base) % this.prime;
        }
        
        // Calculate initial hash values
        for (let i = 0; i < m; i++) {
            patternHash = (this.base * patternHash + pattern.charCodeAt(i)) % this.prime;
            textHash = (this.base * textHash + text.charCodeAt(i)) % this.prime;
        }
        
        // Slide the pattern over text
        for (let i = 0; i <= n - m; i++) {
            // Check if hash values match
            if (patternHash === textHash) {
                // Verify character by character
                let j;
                for (j = 0; j < m; j++) {
                    if (text[i + j] !== pattern[j]) break;
                }
                if (j === m) matches.push(i);
            }
            
            // Calculate hash for next window
            if (i < n - m) {
                textHash = (this.base * (textHash - text.charCodeAt(i) * h) + 
                           text.charCodeAt(i + m)) % this.prime;
                
                // Handle negative hash value
                if (textHash < 0) textHash += this.prime;
            }
        }
        
        return matches;
    }
}

// Example: Find repeated DNA sequences
function findRepeatedDnaSequences(s: string): string[] {
    const seen = new Set();
    const repeated = new Set();
    
    for (let i = 0; i <= s.length - 10; i++) {
        const sequence = s.substring(i, i + 10);
        if (seen.has(sequence)) {
            repeated.add(sequence);
        }
        seen.add(sequence);
    }
    
    return Array.from(repeated);
}
                                

// Counting Sort
function countingSort(arr: number[], maxValue: number): number[] {
    const count = new Array(maxValue + 1).fill(0);
    const output = new Array(arr.length);
    
    // Count occurrences
    for (const num of arr) {
        count[num]++;
    }
    
    // Transform to cumulative count
    for (let i = 1; i <= maxValue; i++) {
        count[i] += count[i - 1];
    }
    
    // Build output array (stable sort)
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    
    return output;
}

// Radix Sort
function radixSort(arr: number[]): number[] {
    if (arr.length === 0) return arr;
    
    const getMax = (arr: number[]) => Math.max(...arr);
    const getDigit = (num: number, place: number) => 
        Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
    
    const maxNum = getMax(arr);
    const maxDigits = Math.floor(Math.log10(maxNum)) + 1;
    
    let result = [...arr];
    
    for (let k = 0; k < maxDigits; k++) {
        const buckets: number[][] = Array.from({ length: 10 }, () => []);
        
        for (const num of result) {
            const digit = getDigit(num, k);
            buckets[digit].push(num);
        }
        
        result = buckets.flat();
    }
    
    return result;
}

// Bucket Sort
function bucketSort(arr: number[]): number[] {
    if (arr.length === 0) return arr;
    
    const n = arr.length;
    const buckets: number[][] = Array.from({ length: n }, () => []);
    
    // Find range
    const minVal = Math.min(...arr);
    const maxVal = Math.max(...arr);
    const range = maxVal - minVal;
    
    // Distribute to buckets
    for (const num of arr) {
        const index = Math.floor(((num - minVal) / range) * (n - 1));
        buckets[index].push(num);
    }
    
    // Sort individual buckets and concatenate
    const result: number[] = [];
    for (const bucket of buckets) {
        bucket.sort((a, b) => a - b);
        result.push(...bucket);
    }
    
    return result;
}

// External Merge Sort for large datasets
class ExternalSort {
    private chunkSize: number;
    
    constructor(chunkSize: number = 1000000) {
        this.chunkSize = chunkSize;
    }
    
    // Simulate sorting large file
    sort(data: number[]): number[] {
        const chunks: number[][] = [];
        
        // Step 1: Sort chunks that fit in memory
        for (let i = 0; i < data.length; i += this.chunkSize) {
            const chunk = data.slice(i, i + this.chunkSize);
            chunk.sort((a, b) => a - b);
            chunks.push(chunk);
        }
        
        // Step 2: K-way merge
        return this.kWayMerge(chunks);
    }
    
    private kWayMerge(chunks: number[][]): number[] {
        const result: number[] = [];
        const indices = new Array(chunks.length).fill(0);
        
        // Min heap for efficient minimum finding
        const heap: [number, number][] = []; // [value, chunk index]
        
        // Initialize heap with first element from each chunk
        for (let i = 0; i < chunks.length; i++) {
            if (chunks[i].length > 0) {
                heap.push([chunks[i][0], i]);
            }
        }
        
        // Min heapify
        heap.sort((a, b) => a[0] - b[0]);
        
        while (heap.length > 0) {
            const [value, chunkIndex] = heap.shift()!;
            result.push(value);
            indices[chunkIndex]++;
            
            if (indices[chunkIndex] < chunks[chunkIndex].length) {
                heap.push([chunks[chunkIndex][indices[chunkIndex]], chunkIndex]);
                heap.sort((a, b) => a[0] - b[0]);
            }
        }
        
        return result;
    }
}
                                

// Closest Pair of Points
interface Point {
    x: number;
    y: number;
}

class ClosestPair {
    private distance(p1: Point, p2: Point): number {
        return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
    }
    
    private bruteForce(points: Point[]): number {
        let minDist = Infinity;
        for (let i = 0; i < points.length; i++) {
            for (let j = i + 1; j < points.length; j++) {
                minDist = Math.min(minDist, this.distance(points[i], points[j]));
            }
        }
        return minDist;
    }
    
    private stripClosest(strip: Point[], d: number): number {
        let minDist = d;
        strip.sort((a, b) => a.y - b.y);
        
        for (let i = 0; i < strip.length; i++) {
            for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < minDist; j++) {
                minDist = Math.min(minDist, this.distance(strip[i], strip[j]));
            }
        }
        
        return minDist;
    }
    
    private closestPairRec(px: Point[], py: Point[]): number {
        const n = px.length;
        
        if (n <= 3) {
            return this.bruteForce(px);
        }
        
        const mid = Math.floor(n / 2);
        const midpoint = px[mid];
        
        const pyl = py.filter(point => point.x <= midpoint.x);
        const pyr = py.filter(point => point.x > midpoint.x);
        
        const dl = this.closestPairRec(px.slice(0, mid), pyl);
        const dr = this.closestPairRec(px.slice(mid), pyr);
        
        const d = Math.min(dl, dr);
        
        const strip = py.filter(point => Math.abs(point.x - midpoint.x) < d);
        
        return Math.min(d, this.stripClosest(strip, d));
    }
    
    findClosestPair(points: Point[]): number {
        const px = [...points].sort((a, b) => a.x - b.x);
        const py = [...points].sort((a, b) => a.y - b.y);
        
        return this.closestPairRec(px, py);
    }
}

// Karatsuba Multiplication
class KaratsubaMultiplication {
    multiply(x: bigint, y: bigint): bigint {
        if (x < 10n || y < 10n) {
            return x * y;
        }
        
        const xStr = x.toString();
        const yStr = y.toString();
        const n = Math.max(xStr.length, yStr.length);
        const half = Math.floor(n / 2);
        
        const multiplier = 10n ** BigInt(half);
        
        const high1 = x / multiplier;
        const low1 = x % multiplier;
        const high2 = y / multiplier;
        const low2 = y % multiplier;
        
        const z0 = this.multiply(low1, low2);
        const z1 = this.multiply(low1 + high1, low2 + high2);
        const z2 = this.multiply(high1, high2);
        
        return z2 * (multiplier ** 2n) + (z1 - z2 - z0) * multiplier + z0;
    }
}

// Matrix Multiplication (Strassen's Algorithm)
class StrassenMatrix {
    multiply(A: number[][], B: number[][]): number[][] {
        const n = A.length;
        
        if (n <= 2) {
            return this.standardMultiply(A, B);
        }
        
        const half = Math.floor(n / 2);
        
        // Divide matrices into quadrants
        const A11 = this.getSubMatrix(A, 0, 0, half);
        const A12 = this.getSubMatrix(A, 0, half, half);
        const A21 = this.getSubMatrix(A, half, 0, half);
        const A22 = this.getSubMatrix(A, half, half, half);
        
        const B11 = this.getSubMatrix(B, 0, 0, half);
        const B12 = this.getSubMatrix(B, 0, half, half);
        const B21 = this.getSubMatrix(B, half, 0, half);
        const B22 = this.getSubMatrix(B, half, half, half);
        
        // Calculate 7 products (Strassen's method)
        const M1 = this.multiply(this.add(A11, A22), this.add(B11, B22));
        const M2 = this.multiply(this.add(A21, A22), B11);
        const M3 = this.multiply(A11, this.subtract(B12, B22));
        const M4 = this.multiply(A22, this.subtract(B21, B11));
        const M5 = this.multiply(this.add(A11, A12), B22);
        const M6 = this.multiply(this.subtract(A21, A11), this.add(B11, B12));
        const M7 = this.multiply(this.subtract(A12, A22), this.add(B21, B22));
        
        // Calculate result quadrants
        const C11 = this.add(this.subtract(this.add(M1, M4), M5), M7);
        const C12 = this.add(M3, M5);
        const C21 = this.add(M2, M4);
        const C22 = this.add(this.subtract(this.add(M1, M3), M2), M6);
        
        // Combine quadrants
        return this.combineMatrices(C11, C12, C21, C22);
    }
    
    private standardMultiply(A: number[][], B: number[][]): number[][] {
        const n = A.length;
        const result = Array(n).fill(0).map(() => Array(n).fill(0));
        
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                for (let k = 0; k < n; k++) {
                    result[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return result;
    }
    
    private getSubMatrix(matrix: number[][], startRow: number, startCol: number, size: number): number[][] {
        const result = Array(size).fill(0).map(() => Array(size).fill(0));
        for (let i = 0; i < size; i++) {
            for (let j = 0; j < size; j++) {
                result[i][j] = matrix[startRow + i][startCol + j];
            }
        }
        return result;
    }
    
    private add(A: number[][], B: number[][]): number[][] {
        const n = A.length;
        const result = Array(n).fill(0).map(() => Array(n).fill(0));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                result[i][j] = A[i][j] + B[i][j];
            }
        }
        return result;
    }
    
    private subtract(A: number[][], B: number[][]): number[][] {
        const n = A.length;
        const result = Array(n).fill(0).map(() => Array(n).fill(0));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                result[i][j] = A[i][j] - B[i][j];
            }
        }
        return result;
    }
    
    private combineMatrices(C11: number[][], C12: number[][], C21: number[][], C22: number[][]): number[][] {
        const half = C11.length;
        const n = half * 2;
        const result = Array(n).fill(0).map(() => Array(n).fill(0));
        
        for (let i = 0; i < half; i++) {
            for (let j = 0; j < half; j++) {
                result[i][j] = C11[i][j];
                result[i][j + half] = C12[i][j];
                result[i + half][j] = C21[i][j];
                result[i + half][j + half] = C22[i][j];
            }
        }
        
        return result;
    }
}