Примеры Структур Данных Web TypeScript

// Web TypeScript Array Operations Examples
// Comprehensive array manipulation and processing

// 1. Basic Array Operations
class ArrayOperations<T> {
  // Create array
  static create<T>(...items: T[]): T[] {
    return [...items];
  }

  // Add element to end
  static push<T>(array: T[], item: T): number {
    return array.push(item);
  }

  // Add element to beginning
  static unshift<T>(array: T[], item: T): number {
    return array.unshift(item);
  }

  // Remove last element
  static pop<T>(array: T[]): T | undefined {
    return array.pop();
  }

  // Remove first element
  static shift<T>(array: T[]): T | undefined {
    return array.shift();
  }

  // Get element at index
  static get<T>(array: T[], index: number): T | undefined {
    return array[index];
  }

  // Set element at index
  static set<T>(array: T[], index: number, item: T): void {
    array[index] = item;
  }

  // Get array length
  static length<T>(array: T[]): number {
    return array.length;
  }

  // Check if array is empty
  static isEmpty<T>(array: T[]): boolean {
    return array.length === 0;
  }

  // Clear array
  static clear<T>(array: T[]): void {
    array.length = 0;
  }

  // Clone array
  static clone<T>(array: T[]): T[] {
    return [...array];
  }

  // Merge arrays
  static merge<T>(...arrays: T[][]): T[] {
    return arrays.flat();
  }

  // Slice array
  static slice<T>(array: T[], start: number, end?: number): T[] {
    return array.slice(start, end);
  }

  // Splice array (remove and insert)
  static splice<T>(array: T[], start: number, deleteCount: number, ...items: T[]): T[] {
    return array.splice(start, deleteCount, ...items);
  }
}

// 2. Array Searching
class ArraySearching<T> {
  // Linear search
  static linearSearch<T>(array: T[], target: T): number {
    for (let i = 0; i < array.length; i++) {
      if (array[i] === target) {
        return i;
      }
    }
    return -1;
  }

  // Binary search (requires sorted array)
  static binarySearch(array: number[], target: number): number {
    let left = 0;
    let right = array.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (array[mid] === target) {
        return mid;
      } else if (array[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  // Find element by predicate
  static find<T>(array: T[], predicate: (item: T) => boolean): T | undefined {
    return array.find(predicate);
  }

  // Find index by predicate
  static findIndex<T>(array: T[], predicate: (item: T) => boolean): number {
    return array.findIndex(predicate);
  }

  // Find all matching elements
  static findAll<T>(array: T[], predicate: (item: T) => boolean): T[] {
    return array.filter(predicate);
  }

  // Find last occurrence
  static findLast<T>(array: T[], predicate: (item: T) => boolean): T | undefined {
    for (let i = array.length - 1; i >= 0; i--) {
      if (predicate(array[i])) {
        return array[i];
      }
    }
    return undefined;
  }

  // Find last index
  static findLastIndex<T>(array: T[], predicate: (item: T) => boolean): number {
    for (let i = array.length - 1; i >= 0; i--) {
      if (predicate(array[i])) {
        return i;
      }
    }
    return -1;
  }

  // Check if element exists
  static contains<T>(array: T[], element: T): boolean {
    return array.includes(element);
  }

  // Count occurrences
  static countOccurrences<T>(array: T[], element: T): number {
    return array.filter(item => item === element).length;
  }
}

// 3. Array Sorting
class ArraySorting<T> {
  // Bubble sort
  static bubbleSort(array: number[]): number[] {
    const result = [...array];
    const n = result.length;

    for (let i = 0; i < n - 1; i++) {
      for (let j = 0; j < n - i - 1; j++) {
        if (result[j] > result[j + 1]) {
          [result[j], result[j + 1]] = [result[j + 1], result[j]];
        }
      }
    }

    return result;
  }

  // Selection sort
  static selectionSort(array: number[]): number[] {
    const result = [...array];
    const n = result.length;

    for (let i = 0; i < n - 1; i++) {
      let minIndex = i;

      for (let j = i + 1; j < n; j++) {
        if (result[j] < result[minIndex]) {
          minIndex = j;
        }
      }

      [result[i], result[minIndex]] = [result[minIndex], result[i]];
    }

    return result;
  }

  // Insertion sort
  static insertionSort(array: number[]): number[] {
    const result = [...array];

    for (let i = 1; i < result.length; i++) {
      const key = result[i];
      let j = i - 1;

      while (j >= 0 && result[j] > key) {
        result[j + 1] = result[j];
        j--;
      }

      result[j + 1] = key;
    }

    return result;
  }

  // Merge sort
  static mergeSort(array: number[]): number[] {
    if (array.length <= 1) {
      return array;
    }

    const mid = Math.floor(array.length / 2);
    const left = this.mergeSort(array.slice(0, mid));
    const right = this.mergeSort(array.slice(mid));

    return this.merge(left, right);
  }

  private static merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] <= right[rightIndex]) {
        result.push(left[leftIndex++]);
      } else {
        result.push(right[rightIndex++]);
      }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
  }

  // Quick sort
  static quickSort(array: number[]): number[] {
    if (array.length <= 1) {
      return array;
    }

    const pivot = array[Math.floor(array.length / 2)];
    const left = array.filter(x => x < pivot);
    const middle = array.filter(x => x === pivot);
    const right = array.filter(x => x > pivot);

    return [...this.quickSort(left), ...middle, ...this.quickSort(right)];
  }

  // Sort with custom comparator
  static sortBy<T>(array: T[], comparator: (a: T, b: T) => number): T[] {
    return [...array].sort(comparator);
  }

  // Sort numbers ascending
  static sortAscending(array: number[]): number[] {
    return [...array].sort((a, b) => a - b);
  }

  // Sort numbers descending
  static sortDescending(array: number[]): number[] {
    return [...array].sort((a, b) => b - a);
  }

  // Sort by property
  static sortByProperty<T>(array: T[], property: keyof T): T[] {
    return [...array].sort((a, b) => {
      const aValue = a[property];
      const bValue = b[property];

      if (aValue < bValue) return -1;
      if (aValue > bValue) return 1;
      return 0;
    });
  }
}

// 4. Array Filtering
class ArrayFiltering<T> {
  // Filter by predicate
  static filter<T>(array: T[], predicate: (item: T) => boolean): T[] {
    return array.filter(predicate);
  }

  // Filter unique elements
  static unique<T>(array: T[]): T[] {
    return Array.from(new Set(array));
  }

  // Filter out null/undefined
  static filterNotNull<T>(array: (T | null | undefined)[]): T[] {
    return array.filter((item): item is T => item !== null && item !== undefined);
  }

  // Filter by type
  static filterByType<T, U extends T>(array: T[], typeGuard: (item: T) => item is U): U[] {
    return array.filter(typeGuard);
  }

  // Partition array
  static partition<T>(array: T[], predicate: (item: T) => boolean): [T[], T[]] {
    const truthy: T[] = [];
    const falsy: T[] = [];

    for (const item of array) {
      if (predicate(item)) {
        truthy.push(item);
      } else {
        falsy.push(item);
      }
    }

    return [truthy, falsy];
  }

  // Remove elements
  static remove<T>(array: T[], elementsToRemove: T[]): T[] {
    const removeSet = new Set(elementsToRemove);
    return array.filter(item => !removeSet.has(item));
  }

  // Remove at indices
  static removeAt<T>(array: T[], indices: number[]): T[] {
    const indexSet = new Set(indices);
    return array.filter((_, index) => !indexSet.has(index));
  }
}

// 5. Array Transformation
class ArrayTransformation<T> {
  // Map array
  static map<T, U>(array: T[], mapper: (item: T, index: number) => U): U[] {
    return array.map(mapper);
  }

  // Flat map
  static flatMap<T, U>(array: T[], mapper: (item: T) => U[]): U[] {
    return array.flatMap(mapper);
  }

  // Reduce array
  static reduce<T, U>(array: T[], reducer: (acc: U, item: T, index: number) => U, initialValue: U): U {
    return array.reduce(reducer, initialValue);
  }

  // Reverse array
  static reverse<T>(array: T[]): T[] {
    return [...array].reverse();
  }

  // Shuffle array
  static shuffle<T>(array: T[]): T[] {
    const result = [...array];

    for (let i = result.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [result[i], result[j]] = [result[j], result[i]];
    }

    return result;
  }

  // Flatten nested array
  static flatten<T>(array: T[][]): T[] {
    return array.flat();
  }

  // Group by key
  static groupBy<T>(array: T[], keyGetter: (item: T) => string): Record<string, T[]> {
    return array.reduce((groups, item) => {
      const key = keyGetter(item);
      if (!groups[key]) {
        groups[key] = [];
      }
      groups[key].push(item);
      return groups;
    }, {} as Record<string, T[]>);
  }

  // Chunk array
  static chunk<T>(array: T[], size: number): T[][] {
    const chunks: T[][] = [];

    for (let i = 0; i < array.length; i += size) {
      chunks.push(array.slice(i, i + size));
    }

    return chunks;
  }

  // Zip arrays
  static zip<T, U>(array1: T[], array2: U[]): [T, U][] {
    const length = Math.min(array1.length, array2.length);
    const result: [T, U][] = [];

    for (let i = 0; i < length; i++) {
      result.push([array1[i], array2[i]]);
    }

    return result;
  }

  // Rotate array
  static rotate<T>(array: T[], positions: number): T[] {
    const normalizedPositions = positions % array.length;
    return [
      ...array.slice(normalizedPositions),
      ...array.slice(0, normalizedPositions)
    ];
  }
}

// 6. Array Aggregation
class ArrayAggregation<T> {
  // Sum numbers
  static sum(array: number[]): number {
    return array.reduce((sum, num) => sum + num, 0);
  }

  // Average
  static average(array: number[]): number {
    if (array.length === 0) return 0;
    return this.sum(array) / array.length;
  }

  // Min value
  static min(array: number[]): number | undefined {
    return array.reduce((min, current) => current < min ? current : min, array[0]);
  }

  // Max value
  static max(array: number[]): number | undefined {
    return array.reduce((max, current) => current > max ? current : max, array[0]);
  }

  // Min and max
  static minMax(array: number[]): { min: number; max: number } | undefined {
    if (array.length === 0) return undefined;

    let min = array[0];
    let max = array[0];

    for (const num of array) {
      if (num < min) min = num;
      if (num > max) max = num;
    }

    return { min, max };
  }

  // Product
  static product(array: number[]): number {
    return array.reduce((prod, num) => prod * num, 1);
  }

  // Count by predicate
  static count<T>(array: T[], predicate: (item: T) => boolean): number {
    return array.filter(predicate).length;
  }

  // Frequency map
  static frequency<T>(array: T[]): Map<T, number> {
    const freq = new Map<T, number>();

    for (const item of array) {
      freq.set(item, (freq.get(item) || 0) + 1);
    }

    return freq;
  }

  // Most frequent
  static mostFrequent<T>(array: T[]): T | undefined {
    const freq = this.frequency(array);
    let maxCount = 0;
    let mostFrequent: T | undefined;

    for (const [item, count] of freq.entries()) {
      if (count > maxCount) {
        maxCount = count;
        mostFrequent = item;
      }
    }

    return mostFrequent;
  }
}

// 7. Array Set Operations
class ArraySetOperations<T> {
  // Union
  static union(array1: T[], array2: T[]): T[] {
    return Array.from(new Set([...array1, ...array2]));
  }

  // Intersection
  static intersection(array1: T[], array2: T[]): T[] {
    const set2 = new Set(array2);
    return array1.filter(item => set2.has(item));
  }

  // Difference
  static difference(array1: T[], array2: T[]): T[] {
    const set2 = new Set(array2);
    return array1.filter(item => !set2.has(item));
  }

  // Symmetric difference
  static symmetricDifference(array1: T[], array2: T[]): T[] {
    const set1 = new Set(array1);
    const set2 = new Set(array2);

    return [
      ...array1.filter(item => !set2.has(item)),
      ...array2.filter(item => !set1.has(item))
    ];
  }

  // Is subset
  static isSubset(array1: T[], array2: T[]): boolean {
    const set2 = new Set(array2);
    return array1.every(item => set2.has(item));
  }

  // Is superset
  static isSuperset(array1: T[], array2: T[]): boolean {
    return this.isSubset(array2, array1);
  }
}

// Usage Examples
async function demonstrateArrayOperations() {
  console.log('=== Web TypeScript Array Operations Examples ===\n');

  // 1. Basic operations
  console.log('--- 1. Basic Operations ---');
  const arr = [1, 2, 3];
  ArrayOperations.push(arr, 4);
  console.log(`After push: ${arr}`);

  ArrayOperations.unshift(arr, 0);
  console.log(`After unshift: ${arr}`);

  console.log(`Pop: ${ArrayOperations.pop(arr)}`);
  console.log(`Shift: ${ArrayOperations.shift(arr)}`);

  const merged = ArrayOperations.merge([1, 2], [3, 4], [5]);
  console.log(`Merged: ${merged}`);

  // 2. Searching
  console.log('\n--- 2. Searching ---');
  const numbers = [5, 3, 8, 1, 9, 2];
  console.log(`Array: ${numbers}`);
  console.log(`Linear search 8: index ${ArraySearching.linearSearch(numbers, 8)}`);

  const sorted = [1, 3, 5, 7, 9, 11];
  console.log(`Binary search 7: index ${ArraySearching.binarySearch(sorted, 7)}`);
  console.log(`Contains 5: ${ArraySearching.contains(numbers, 5)}`);
  console.log(`Count of 3: ${ArraySearching.countOccurrences([...numbers, 3], 3)}`);

  // 3. Sorting
  console.log('\n--- 3. Sorting ---');
  const unsorted = [64, 34, 25, 12, 22, 11, 90];
  console.log(`Original: ${unsorted}`);
  console.log(`Bubble sort: ${ArraySorting.bubbleSort(unsorted)}`);
  console.log(`Quick sort: ${ArraySorting.quickSort(unsorted)}`);
  console.log(`Ascending: ${ArraySorting.sortAscending(unsorted)}`);
  console.log(`Descending: ${ArraySorting.sortDescending(unsorted)}`);

  // 4. Filtering
  console.log('\n--- 4. Filtering ---');
  const mixed = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4];
  console.log(`Original: ${mixed}`);
  console.log(`Unique: ${ArrayFiltering.unique(mixed)}`);

  const [even, odd] = ArrayFiltering.partition(mixed, n => n % 2 === 0);
  console.log(`Even: ${even}`);
  console.log(`Odd: ${odd}`);

  // 5. Transformation
  console.log('\n--- 5. Transformation ---');
  const nums = [1, 2, 3, 4, 5];
  console.log(`Original: ${nums}`);
  console.log(`Doubled: ${ArrayTransformation.map(nums, n => n * 2)}`);
  console.log(`Reversed: ${ArrayTransformation.reverse(nums)}`);
  console.log(`Shuffled: ${ArrayTransformation.shuffle(nums)}`);
  console.log(`Chunked (2): ${ArrayTransformation.chunk(nums, 2).map(c => `[${c}]`).join(', ')}`);

  // 6. Aggregation
  console.log('\n--- 6. Aggregation ---');
  const values = [10, 20, 30, 40, 50];
  console.log(`Array: ${values}`);
  console.log(`Sum: ${ArrayAggregation.sum(values)}`);
  console.log(`Average: ${ArrayAggregation.average(values)}`);
  console.log(`Min: ${ArrayAggregation.min(values)}`);
  console.log(`Max: ${ArrayAggregation.max(values)}`);
  console.log(`Min/Max: ${JSON.stringify(ArrayAggregation.minMax(values))}`);

  // 7. Set operations
  console.log('\n--- 7. Set Operations ---');
  const set1 = [1, 2, 3, 4];
  const set2 = [3, 4, 5, 6];
  console.log(`Set 1: ${set1}`);
  console.log(`Set 2: ${set2}`);
  console.log(`Union: ${ArraySetOperations.union(set1, set2)}`);
  console.log(`Intersection: ${ArraySetOperations.intersection(set1, set2)}`);
  console.log(`Difference: ${ArraySetOperations.difference(set1, set2)}`);
  console.log(`Symmetric diff: ${ArraySetOperations.symmetricDifference(set1, set2)}`);

  // 8. Group by
  console.log('\n--- 8. Group By ---');
  const people = [
    { name: 'Alice', age: 25 },
    { name: 'Bob', age: 30 },
    { name: 'Charlie', age: 25 }
  ];

  const grouped = ArrayTransformation.groupBy(people, p => String(p.age));
  console.log('Grouped by age:', Object.entries(grouped).map(([k, v]) => `${k}: [${v.map(p => p.name).join(', ')}]`).join(', '));

  console.log('\n=== All Array Operations Examples Completed ===');
}

// Export classes
export { ArrayOperations, ArraySearching, ArraySorting, ArrayFiltering, ArrayTransformation, ArrayAggregation, ArraySetOperations };
export { demonstrateArrayOperations };

// Web TypeScript Hash Map Examples
// Custom hash map implementation with collision handling

// 1. Basic Hash Map Entry
class HashMapEntry<K, V> {
  key: K;
  value: V;
  next: HashMapEntry<K, V> | null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

// 2. Hash Map Implementation
class HashMap<K, V> {
  private buckets: Array<HashMapEntry<K, V> | null>;
  private size: number;
  private capacity: number;
  private loadFactor: number;

  constructor(initialCapacity: number = 16, loadFactor: number = 0.75) {
    this.capacity = initialCapacity;
    this.loadFactor = loadFactor;
    this.size = 0;
    this.buckets = new Array(this.capacity).fill(null);
  }

  // Hash function
  private hash(key: K): number {
    const keyString = String(key);
    let hash = 0;

    for (let i = 0; i < keyString.length; i++) {
      hash = (hash << 5) - hash + keyString.charCodeAt(i);
      hash = hash | 0; // Convert to 32-bit integer
    }

    return Math.abs(hash) % this.capacity;
  }

  // Put key-value pair
  put(key: K, value: V): void {
    const index = this.hash(key);
    let entry = this.buckets[index];

    // Check if key already exists
    while (entry !== null) {
      if (entry.key === key) {
        entry.value = value;
        return;
      }
      entry = entry.next;
    }

    // Add new entry at the beginning
    const newEntry = new HashMapEntry(key, value);
    newEntry.next = this.buckets[index];
    this.buckets[index] = newEntry;
    this.size++;

    // Resize if needed
    if (this.size / this.capacity >= this.loadFactor) {
      this.resize();
    }
  }

  // Get value by key
  get(key: K): V | undefined {
    const index = this.hash(key);
    let entry = this.buckets[index];

    while (entry !== null) {
      if (entry.key === key) {
        return entry.value;
      }
      entry = entry.next;
    }

    return undefined;
  }

  // Remove key-value pair
  remove(key: K): boolean {
    const index = this.hash(key);
    let entry = this.buckets[index];
    let prev: HashMapEntry<K, V> | null = null;

    while (entry !== null) {
      if (entry.key === key) {
        if (prev === null) {
          this.buckets[index] = entry.next;
        } else {
          prev.next = entry.next;
        }
        this.size--;
        return true;
      }
      prev = entry;
      entry = entry.next;
    }

    return false;
  }

  // Check if key exists
  containsKey(key: K): boolean {
    return this.get(key) !== undefined;
  }

  // Check if value exists
  containsValue(value: V): boolean {
    for (const bucket of this.buckets) {
      let entry = bucket;
      while (entry !== null) {
        if (entry.value === value) {
          return true;
        }
        entry = entry.next;
      }
    }
    return false;
  }

  // Get all keys
  keys(): K[] {
    const keys: K[] = [];

    for (const bucket of this.buckets) {
      let entry = bucket;
      while (entry !== null) {
        keys.push(entry.key);
        entry = entry.next;
      }
    }

    return keys;
  }

  // Get all values
  values(): V[] {
    const values: V[] = [];

    for (const bucket of this.buckets) {
      let entry = bucket;
      while (entry !== null) {
        values.push(entry.value);
        entry = entry.next;
      }
    }

    return values;
  }

  // Get all entries
  entries(): Array<[K, V]> {
    const entries: Array<[K, V]> = [];

    for (const bucket of this.buckets) {
      let entry = bucket;
      while (entry !== null) {
        entries.push([entry.key, entry.value]);
        entry = entry.next;
      }
    }

    return entries;
  }

  // Get size
  getSize(): number {
    return this.size;
  }

  // Check if empty
  isEmpty(): boolean {
    return this.size === 0;
  }

  // Clear hash map
  clear(): void {
    this.buckets = new Array(this.capacity).fill(null);
    this.size = 0;
  }

  // Resize buckets
  private resize(): void {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null);
    this.size = 0;

    for (const bucket of oldBuckets) {
      let entry = bucket;
      while (entry !== null) {
        this.put(entry.key, entry.value);
        entry = entry.next;
      }
    }
  }

  // Print hash map (for debugging)
  print(): void {
    console.log('\n=== Hash Map Contents ===');
    console.log(`Size: ${this.size}, Capacity: ${this.capacity}`);

    for (let i = 0; i < this.buckets.length; i++) {
      const bucket = this.buckets[i];
      if (bucket !== null) {
        console.log(`Bucket ${i}:`);

        let entry = bucket;
        while (entry !== null) {
          console.log(`  ${entry.key} => ${entry.value}`);
          entry = entry.next;
        }
      }
    }
  }
}

// 3. Multi-Value Map (one key, multiple values)
class MultiValueMap<K, V> {
  private map = new Map<K, V[]>();

  // Add value for key
  put(key: K, value: V): void {
    if (!this.map.has(key)) {
      this.map.set(key, []);
    }
    this.map.get(key)!.push(value);
  }

  // Get all values for key
  get(key: K): V[] {
    return this.map.get(key) || [];
  }

  // Remove specific value for key
  remove(key: K, value: V): boolean {
    const values = this.map.get(key);
    if (!values) return false;

    const index = values.indexOf(value);
    if (index > -1) {
      values.splice(index, 1);

      if (values.length === 0) {
        this.map.delete(key);
      }

      return true;
    }

    return false;
  }

  // Remove all values for key
  removeAll(key: K): V[] {
    const values = this.map.get(key);
    this.map.delete(key);
    return values || [];
  }

  // Get all keys
  keys(): K[] {
    return Array.from(this.map.keys());
  }

  // Get all values
  values(): V[] {
    const allValues: V[] = [];
    for (const values of this.map.values()) {
      allValues.push(...values);
    }
    return allValues;
  }

  // Check if key exists
  containsKey(key: K): boolean {
    return this.map.has(key);
  }

  // Get size (number of keys)
  size(): number {
    return this.map.size;
  }

  // Clear map
  clear(): void {
    this.map.clear();
  }
}

// 4. LRU Cache (Least Recently Used)
class LRUCache<K, V> {
  private capacity: number;
  private cache = new Map<K, V>();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  // Get value and move to end (most recently used)
  get(key: K): V | undefined {
    if (!this.cache.has(key)) {
      return undefined;
    }

    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  // Put value and evict least recently used if at capacity
  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }

    this.cache.set(key, value);
  }

  // Check if key exists
  has(key: K): boolean {
    return this.cache.has(key);
  }

  // Get size
  size(): number {
    return this.cache.size;
  }

  // Clear cache
  clear(): void {
    this.cache.clear();
  }

  // Get all keys (in order of least to most recently used)
  keys(): K[] {
    return Array.from(this.cache.keys());
  }
}

// 5. Hash Map Utilities
class HashMapUtilities {
  // Merge two hash maps
  static merge<K, V>(map1: Map<K, V>, map2: Map<K, V>): Map<K, V> {
    return new Map([...map1, ...map2]);
  }

  // Clone hash map
  static clone<K, V>(map: Map<K, V>): Map<K, V> {
    return new Map(map);
  }

  // Invert hash map (swap keys and values)
  static invert<K, V>(map: Map<K, V>): Map<V, K> {
    const inverted = new Map<V, K>();

    for (const [key, value] of map.entries()) {
      inverted.set(value, key);
    }

    return inverted;
  }

  // Filter hash map by predicate
  static filter<K, V>(map: Map<K, V>, predicate: (key: K, value: V) => boolean): Map<K, V> {
    const filtered = new Map<K, V>();

    for (const [key, value] of map.entries()) {
      if (predicate(key, value)) {
        filtered.set(key, value);
      }
    }

    return filtered;
  }

  // Map values
  static mapValues<K, V, U>(map: Map<K, V>, mapper: (key: K, value: V) => U): Map<K, U> {
    const result = new Map<K, U>();

    for (const [key, value] of map.entries()) {
      result.set(key, mapper(key, value));
    }

    return result;
  }

  // Group array by key function
  static groupBy<T, K>(array: T[], keyGetter: (item: T) => K): Map<K, T[]> {
    const grouped = new Map<K, T[]>();

    for (const item of array) {
      const key = keyGetter(item);

      if (!grouped.has(key)) {
        grouped.set(key, []);
      }

      grouped.get(key)!.push(item);
    }

    return grouped;
  }

  // Count occurrences
  static countOccurrences<T>(array: T[]): Map<T, number> {
    const counts = new Map<T, number>();

    for (const item of array) {
      counts.set(item, (counts.get(item) || 0) + 1);
    }

    return counts;
  }
}

// 6. Hash Map Comparison
class HashMapComparison {
  // Check if two maps are equal
  static equal<K, V>(map1: Map<K, V>, map2: Map<K, V>): boolean {
    if (map1.size !== map2.size) {
      return false;
    }

    for (const [key, value] of map1.entries()) {
      if (!map2.has(key) || map2.get(key) !== value) {
        return false;
      }
    }

    return true;
  }

  // Get keys present in map1 but not in map2
  static keyDifference<K, V>(map1: Map<K, V>, map2: Map<K, V>): Set<K> {
    const diff = new Set<K>();

    for (const key of map1.keys()) {
      if (!map2.has(key)) {
        diff.add(key);
      }
    }

    return diff;
  }

  // Get common keys
  static keyIntersection<K, V>(map1: Map<K, V>, map2: Map<K, V>): Set<K> {
    const intersection = new Set<K>();

    for (const key of map1.keys()) {
      if (map2.has(key)) {
        intersection.add(key);
      }
    }

    return intersection;
  }
}

// Usage Examples
async function demonstrateHashMap() {
  console.log('=== Web TypeScript Hash Map Examples ===\n');

  // 1. Basic hash map operations
  console.log('--- 1. Basic Hash Map ---');
  const hashMap = new HashMap<string, number>();

  hashMap.put('one', 1);
  hashMap.put('two', 2);
  hashMap.put('three', 3);

  console.log(`Get 'two': ${hashMap.get('two')}`);
  console.log(`Contains 'three': ${hashMap.containsKey('three')}`);
  console.log(`Keys: ${hashMap.keys().join(', ')}`);
  console.log(`Values: ${hashMap.values().join(', ')}`);
  console.log(`Size: ${hashMap.getSize()}`);

  hashMap.remove('two');
  console.log(`After remove 'two', size: ${hashMap.getSize()}`);

  // 2. Collision handling
  console.log('\n--- 2. Collision Handling ---');
  const smallMap = new HashMap<number, string>(4);

  // These might hash to same bucket
  smallMap.put(1, 'one');
  smallMap.put(5, 'five');
  smallMap.put(9, 'nine');

  console.log(`Get 1: ${smallMap.get(1)}`);
  console.log(`Get 5: ${smallMap.get(5)}`);
  console.log(`Get 9: ${smallMap.get(9)}`);

  smallMap.print();

  // 3. Multi-value map
  console.log('\n--- 3. Multi-Value Map ---');
  const multiMap = new MultiValueMap<string, number>();

  multiMap.put('fruits', 1);
  multiMap.put('fruits', 2);
  multiMap.put('fruits', 3);
  multiMap.put('vegetables', 10);

  console.log(`Fruits: ${multiMap.get('fruits').join(', ')}`);
  console.log(`Vegetables: ${multiMap.get('vegetables').join(', ')}`);

  multiMap.remove('fruits', 2);
  console.log(`After removing 2 from fruits: ${multiMap.get('fruits').join(', ')}`);

  // 4. LRU Cache
  console.log('\n--- 4. LRU Cache ---');
  const lru = new LRUCache<string, number>(3);

  lru.put('a', 1);
  lru.put('b', 2);
  lru.put('c', 3);
  console.log(`Cache keys: ${lru.keys().join(', ')}`);

  lru.put('d', 4); // 'a' should be evicted
  console.log(`After adding 'd': ${lru.keys().join(', ')}`);
  console.log(`Has 'a': ${lru.has('a')}`);
  console.log(`Get 'b': ${lru.get('b')}`);
  console.log(`After getting 'b': ${lru.keys().join(', ')}`);

  // 5. Hash map utilities
  console.log('\n--- 5. Hash Map Utilities ---');
  const map1 = new Map([['a', 1], ['b', 2], ['c', 3]]);
  const map2 = new Map([['c', 30], ['d', 4]]);

  const merged = HashMapUtilities.merge(map1, map2);
  console.log(`Merged: ${Array.from(merged.entries()).map(([k, v]) => `${k}:${v}`).join(', ')}`);

  const filtered = HashMapUtilities.filter(map1, (k, v) => v > 1);
  console.log(`Filtered (> 1): ${Array.from(filtered.entries()).map(([k, v]) => `${k}:${v}`).join(', ')}`);

  const numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4];
  const counts = HashMapUtilities.countOccurrences(numbers);
  console.log(`Occurrences: ${Array.from(counts.entries()).map(([k, v]) => `${k}:${v}`).join(', ')}`);

  // 6. Group by
  console.log('\n--- 6. Group By ---');
  const people = [
    { name: 'Alice', age: 25 },
    { name: 'Bob', age: 30 },
    { name: 'Charlie', age: 25 },
    { name: 'David', age: 30 }
  ];

  const grouped = HashMapUtilities.groupBy(people, p => p.age);
  console.log('Grouped by age:');
  for (const [age, persons] of grouped.entries()) {
    console.log(`  ${age}: ${persons.map(p => p.name).join(', ')}`);
  }

  // 7. Hash map comparison
  console.log('\n--- 7. Hash Map Comparison ---');
  const mapA = new Map([['x', 1], ['y', 2]]);
  const mapB = new Map([['x', 1], ['y', 2]]);
  const mapC = new Map([['x', 1], ['z', 2]]);

  console.log(`A equals B: ${HashMapComparison.equal(mapA, mapB)}`);
  console.log(`A equals C: ${HashMapComparison.equal(mapA, mapC)}`);

  const diff = HashMapComparison.keyDifference(mapA, mapC);
  console.log(`A - C keys: ${Array.from(diff).join(', ')}`);

  const intersection = HashMapComparison.keyIntersection(mapA, mapC);
  console.log(`A ∩ C keys: ${Array.from(intersection).join(', ')}`);

  console.log('\n=== All Hash Map Examples Completed ===');
}

// Export classes
export { HashMap, HashMapEntry, MultiValueMap, LRUCache, HashMapUtilities, HashMapComparison };
export { demonstrateHashMap };

// Web TypeScript Linked List Examples
// Singly and doubly linked list implementations

// 1. Singly Linked List Node
class ListNode<T> {
  value: T;
  next: ListNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
  }
}

// 2. Singly Linked List
class LinkedList<T> {
  private head: ListNode<T> | null = null;
  private tail: ListNode<T> | null = null;
  private length: number = 0;

  // Add to end
  append(value: T): void {
    const newNode = new ListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  // Add to beginning
  prepend(value: T): void {
    const newNode = new ListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
  }

  // Insert at index
  insert(index: number, value: T): boolean {
    if (index < 0 || index > this.length) {
      return false;
    }

    if (index === 0) {
      this.prepend(value);
      return true;
    }

    if (index === this.length) {
      this.append(value);
      return true;
    }

    const newNode = new ListNode(value);
    const current = this.getNodeAt(index - 1);

    if (current) {
      newNode.next = current.next;
      current.next = newNode;
      this.length++;
      return true;
    }

    return false;
  }

  // Remove at index
  removeAt(index: number): T | null {
    if (index < 0 || index >= this.length) {
      return null;
    }

    if (index === 0) {
      const value = this.head!.value;
      this.head = this.head!.next;

      if (!this.head) {
        this.tail = null;
      }

      this.length--;
      return value;
    }

    const prev = this.getNodeAt(index - 1);
    if (prev && prev.next) {
      const value = prev.next.value;
      prev.next = prev.next.next;

      if (!prev.next) {
        this.tail = prev;
      }

      this.length--;
      return value;
    }

    return null;
  }

  // Remove first occurrence of value
  remove(value: T): boolean {
    if (!this.head) {
      return false;
    }

    if (this.head.value === value) {
      this.head = this.head.next;

      if (!this.head) {
        this.tail = null;
      }

      this.length--;
      return true;
    }

    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;

        if (!current.next) {
          this.tail = current;
        }

        this.length--;
        return true;
      }
      current = current.next;
    }

    return false;
  }

  // Get value at index
  get(index: number): T | null {
    if (index < 0 || index >= this.length) {
      return null;
    }

    const node = this.getNodeAt(index);
    return node ? node.value : null;
  }

  // Find index of value
  indexOf(value: T): number {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  // Check if contains value
  contains(value: T): boolean {
    return this.indexOf(value) !== -1;
  }

  // Get size
  size(): number {
    return this.length;
  }

  // Check if empty
  isEmpty(): boolean {
    return this.length === 0;
  }

  // Clear list
  clear(): void {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Convert to array
  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  // Reverse list
  reverse(): void {
    let prev: ListNode<T> | null = null;
    let current = this.head;
    this.tail = this.head;

    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    this.head = prev;
  }

  // Get node at index (private helper)
  private getNodeAt(index: number): ListNode<T> | null {
    let current = this.head;
    let count = 0;

    while (current && count < index) {
      current = current.next;
      count++;
    }

    return current;
  }

  // Print list
  print(): void {
    const values = this.toArray();
    console.log(`[${values.join(' -> ')}]`);
  }
}

// 3. Doubly Linked List Node
class DoublyListNode<T> {
  value: T;
  next: DoublyListNode<T> | null;
  prev: DoublyListNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// 4. Doubly Linked List
class DoublyLinkedList<T> {
  private head: DoublyListNode<T> | null = null;
  private tail: DoublyListNode<T> | null = null;
  private length: number = 0;

  // Add to end
  append(value: T): void {
    const newNode = new DoublyListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  // Add to beginning
  prepend(value: T): void {
    const newNode = new DoublyListNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length++;
  }

  // Insert at index
  insert(index: number, value: T): boolean {
    if (index < 0 || index > this.length) {
      return false;
    }

    if (index === 0) {
      this.prepend(value);
      return true;
    }

    if (index === this.length) {
      this.append(value);
      return true;
    }

    const newNode = new DoublyListNode(value);
    const current = this.getNodeAt(index);

    if (current) {
      newNode.prev = current.prev;
      newNode.next = current;
      current.prev!.next = newNode;
      current.prev = newNode;
      this.length++;
      return true;
    }

    return false;
  }

  // Remove at index
  removeAt(index: number): T | null {
    if (index < 0 || index >= this.length) {
      return null;
    }

    const node = this.getNodeAt(index);
    if (!node) {
      return null;
    }

    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;
    }

    this.length--;
    return node.value;
  }

  // Get value at index
  get(index: number): T | null {
    if (index < 0 || index >= this.length) {
      return null;
    }

    const node = this.getNodeAt(index);
    return node ? node.value : null;
  }

  // Find index of value
  indexOf(value: T): number {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  // Get size
  size(): number {
    return this.length;
  }

  // Check if empty
  isEmpty(): boolean {
    return this.length === 0;
  }

  // Clear list
  clear(): void {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Convert to array
  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  // Convert to reversed array
  toArrayReverse(): T[] {
    const result: T[] = [];
    let current = this.tail;

    while (current) {
      result.push(current.value);
      current = current.prev;
    }

    return result;
  }

  // Get node at index (private helper)
  private getNodeAt(index: number): DoublyListNode<T> | null {
    // Optimize by starting from closest end
    if (index < this.length / 2) {
      let current = this.head;
      let count = 0;

      while (current && count < index) {
        current = current.next;
        count++;
      }

      return current;
    } else {
      let current = this.tail;
      let count = this.length - 1;

      while (current && count > index) {
        current = current.prev;
        count--;
      }

      return current;
    }
  }

  // Print list forward
  printForward(): void {
    const values = this.toArray();
    console.log(`Forward: [${values.join(' <-> ')}]`);
  }

  // Print list backward
  printBackward(): void {
    const values = this.toArrayReverse();
    console.log(`Backward: [${values.join(' <-> ')}]`);
  }
}

// 5. Linked List Utilities
class LinkedListUtilities {
  // Detect cycle in linked list
  static hasCycle<T>(head: ListNode<T> | null): boolean {
    if (!head) {
      return false;
    }

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
      slow = slow.next!;
      fast = fast.next.next;

      if (slow === fast) {
        return true;
      }
    }

    return false;
  }

  // Find middle node
  static findMiddle<T>(head: ListNode<T> | null): ListNode<T> | null {
    if (!head) {
      return null;
    }

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
      slow = slow.next!;
      fast = fast.next.next;
    }

    return slow;
  }

  // Reverse linked list
  static reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
    let prev: ListNode<T> | null = null;
    let current = head;

    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    return prev;
  }

  // Merge two sorted lists
  static mergeSortedLists<T>(
    list1: ListNode<T> | null,
    list2: ListNode<T> | null,
    compare: (a: T, b: T) => number
  ): ListNode<T> | null {
    const dummy = new ListNode<T>(null as T);
    let current = dummy;

    while (list1 && list2) {
      if (compare(list1.value, list2.value) <= 0) {
        current.next = list1;
        list1 = list1.next;
      } else {
        current.next = list2;
        list2 = list2.next;
      }
      current = current.next;
    }

    current.next = list1 || list2;
    return dummy.next;
  }

  // Create linked list from array
  static fromArray<T>(values: T[]): LinkedList<T> {
    const list = new LinkedList<T>();
    for (const value of values) {
      list.append(value);
    }
    return list;
  }
}

// 6. Linked List Algorithms
class LinkedListAlgorithms {
  // Check if palindrome
  static isPalindrome<T>(list: LinkedList<T>): boolean {
    const values = list.toArray();
    const reversed = [...values].reverse();

    return JSON.stringify(values) === JSON.stringify(reversed);
  }

  // Remove nth node from end
  static removeNthFromEnd<T>(list: LinkedList<T>, n: number): boolean {
    const index = list.size() - n;

    if (index < 0) {
      return false;
    }

    return list.removeAt(index) !== null;
  }

  // Swap nodes in pairs
  static swapPairs<T>(list: LinkedList<T>): void {
    for (let i = 0; i < list.size() - 1; i += 2) {
      const first = list.get(i);
      const second = list.get(i + 1);

      if (first !== null && second !== null) {
        list.removeAt(i);
        list.removeAt(i);
        list.insert(i, second);
        list.insert(i + 1, first);
      }
    }
  }

  // Rotate list to the right by k places
  static rotateRight<T>(list: LinkedList<T>, k: number): void {
    if (list.isEmpty() || k === 0) {
      return;
    }

    const size = list.size();
    k = k % size;

    if (k === 0) {
      return;
    }

    // Get the split point
    const splitIndex = size - k;

    // Create new list with rotated elements
    const values = list.toArray();
    const rotated = [
      ...values.slice(splitIndex),
      ...values.slice(0, splitIndex)
    ];

    list.clear();
    for (const value of rotated) {
      list.append(value);
    }
  }
}

// Usage Examples
async function demonstrateLinkedList() {
  console.log('=== Web TypeScript Linked List Examples ===\n');

  // 1. Singly linked list basics
  console.log('--- 1. Singly Linked List ---');
  const list = new LinkedList<number>();

  list.append(1);
  list.append(2);
  list.append(3);
  list.prepend(0);

  console.log('After adding elements:');
  list.print();

  console.log(`Get index 2: ${list.get(2)}`);
  console.log(`Index of 2: ${list.indexOf(2)}`);
  console.log(`Contains 3: ${list.contains(3)}`);
  console.log(`Size: ${list.size()}`);

  list.insert(2, 100);
  console.log('After inserting 100 at index 2:');
  list.print();

  list.removeAt(2);
  console.log('After removing index 2:');
  list.print();

  list.reverse();
  console.log('After reversing:');
  list.print();

  // 2. Doubly linked list
  console.log('\n--- 2. Doubly Linked List ---');
  const doublyList = new DoublyLinkedList<string>();

  doublyList.append('first');
  doublyList.append('second');
  doublyList.append('third');
  doublyList.prepend('zero');

  console.log('Forward:');
  doublyList.printForward();

  console.log('Backward:');
  doublyList.printBackward();

  doublyList.insert(2, 'middle');
  console.log('After inserting at index 2:');
  doublyList.printForward();

  console.log(`Removed at index 2: ${doublyList.removeAt(2)}`);
  doublyList.printForward();

  // 3. Linked list utilities
  console.log('\n--- 3. Linked List Utilities ---');

  // Create a list for utilities
  const utilList = LinkedListUtilities.fromArray([1, 2, 3, 4, 5]);
  console.log('Created from array [1,2,3,4,5]:');
  utilList.print();

  // Find middle
  const middle = LinkedListUtilities.findMiddle(utilList['head'] || null);
  console.log(`Middle node value: ${middle?.value}`);

  // Reverse
  const reversed = LinkedListUtilities.reverse(utilList['head'] || null);
  console.log('Reversed:');
  let current = reversed;
  while (current) {
    console.log(current.value + ' -> ');
    current = current.next;
  }

  // 4. Linked list algorithms
  console.log('\n--- 4. Linked List Algorithms ---');

  // Palindrome check
  const palindromeList = LinkedListUtilities.fromArray([1, 2, 3, 2, 1]);
  console.log(`Is [1,2,3,2,1] palindrome: ${LinkedListAlgorithms.isPalindrome(palindromeList)}`);

  const nonPalindromeList = LinkedListUtilities.fromArray([1, 2, 3, 4, 5]);
  console.log(`Is [1,2,3,4,5] palindrome: ${LinkedListAlgorithms.isPalindrome(nonPalindromeList)}`);

  // Remove nth from end
  const removeList = LinkedListUtilities.fromArray([1, 2, 3, 4, 5]);
  console.log('Before removing 2nd from end:');
  removeList.print();
  LinkedListAlgorithms.removeNthFromEnd(removeList, 2);
  console.log('After removing 2nd from end:');
  removeList.print();

  // Rotate right
  const rotateList = LinkedListUtilities.fromArray([1, 2, 3, 4, 5]);
  console.log('Before rotating right by 2:');
  rotateList.print();
  LinkedListAlgorithms.rotateRight(rotateList, 2);
  console.log('After rotating right by 2:');
  rotateList.print();

  // Swap pairs
  const swapList = LinkedListUtilities.fromArray([1, 2, 3, 4, 5]);
  console.log('Before swapping pairs:');
  swapList.print();
  LinkedListAlgorithms.swapPairs(swapList);
  console.log('After swapping pairs:');
  swapList.print();

  // 5. Conversion
  console.log('\n--- 5. Conversion ---');
  const arr = [10, 20, 30, 40, 50];
  const listFromArray = LinkedListUtilities.fromArray(arr);
  console.log(`Array: [${arr.join(', ')}]`);
  console.log('Linked list:');
  listFromArray.print();

  const backToArray = listFromArray.toArray();
  console.log(`Back to array: [${backToArray.join(', ')}]`);

  console.log('\n=== All Linked List Examples Completed ===');
}

// Export classes
export { ListNode, LinkedList, DoublyListNode, DoublyLinkedList, LinkedListUtilities, LinkedListAlgorithms };
export { demonstrateLinkedList };