class HashLinkedNode {
  value: any;
  key: string;
  next: HashLinkedNode | null;

  constructor(key: string, value: any) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

class HashTableForCityNumber {

  buckets: HashLinkedNode[];

  private bucketSize: number = 1000;

  constructor() {
    this.buckets = [];
  }

  // Treat the number as a 6-digit int.
  private hash(key: number): number {
    let bucketNum = Math.floor(key / this.bucketSize);
    return bucketNum;
  }

  // Loop the link list to find the node.
  private findNodeByKeyInBucket(head: HashLinkedNode, key: string): any {
    let current = head;
    let prev = null;
    let node: HashLinkedNode = null;

    while (current !== null) {
      if (current.key === key) {
        node = current;
        break;
      }
      prev = current;
      current = current.next;
    }
    return {
      current: node,
      prev: prev
    };
  }

  put(key: string, value: any): void {
    const bucketNum: number = this.hash(parseInt(key));
    const bucketHead: HashLinkedNode = this.buckets[bucketNum];

    // First node
    if (typeof bucketHead === 'undefined') {
      this.buckets[bucketNum] = new HashLinkedNode(key, value);
    }
    else {
      const targetNode = this.findNodeByKeyInBucket(bucketHead, key);
      // Insert the new node to head
      if (targetNode.current === null) {
        const insertNode = new HashLinkedNode(key, value);
        insertNode.next = bucketHead;
        this.buckets[bucketNum] = insertNode;
      }
      // Replace current value
      else {
        targetNode.current.value = value;
      }
    }
  }
  get(key: string): HashLinkedNode {
    const bucketNum: number = this.hash(parseInt(key));
    const bucketHead: HashLinkedNode = this.buckets[bucketNum];
    const targetNode = this.findNodeByKeyInBucket(bucketHead, key).current;
    return targetNode ? targetNode.value : null;
  }
  remove(key: string): HashLinkedNode {
    const bucketNum: number = this.hash(parseInt(key));
    const bucketHead: HashLinkedNode = this.buckets[bucketNum];
    const targetNode = this.findNodeByKeyInBucket(bucketHead, key);

    if (targetNode.current === null) {
      throw new TypeError(`Can't remove a node which doesn't exist.`);
    }
    // Remove the head
    else if (targetNode.prev === null) {
      this.buckets[bucketNum] = targetNode.current.next;
    }
    // Remove node in the middle
    else {
      targetNode.prev.next = targetNode.current.next;
    }
    return targetNode.current;
  }
}

const cityHashTable = new HashTableForCityNumber();
cityHashTable.put('110011', 'hello');
cityHashTable.put('123116', 'world');
console.log(cityHashTable.get('110011'));
cityHashTable.remove('123116');
cityHashTable.put('110011', 'hello2');
console.log(cityHashTable.get('110011'));

/**
 * Use an `object` as a hash table.
 **/

const findCommonArray = (nums1: number[], nums2: number[]): number[] => {
  const map: object = {}
  const res: number[] = []
  nums1.forEach((num, index) => {
    map[num] = 1
  })
  nums2.forEach((num, index) => {
    if (map[num] === 1) {
      res.push(num)
      // This number is consumed.
      map[num] = 0
    }
  })
  return res
}

const nums1 = [1, 1, 1, 5, 2, 4, 9]
const nums2 = [5, 8, 5, 9, 1, 1]
console.log(findCommonArray(nums1, nums2)) // [5,9,1]

/**
 * Here is an prerequisite:
 * Each number in `nums` are unique.
 */
const findTwoNumbersByTarget = (nums: number[], target: number): number[] => {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    map.set(num, i)
    const d = target - num
    if (map.has(d)) {
      return [i, map.get(d)]
    }
  }
  return null
}

const nums = [1, 6, 9, 5]
const target = 14
console.log(findTwoNumbersByTarget(nums, target)) // [3,2]

const findThreeNumbersByTarget = (
  nums: number[],
  target: number,
): number[][] => {
  const res: number[][] = []
  const map = new Map()
  const len = nums.length
  let left = 0
  let mid = 1

  // Sort the numbers from min to max
  nums.sort((a, b) => a - b)

  // Put all nums into a set
  // Time complexity is O(n)
  for (let i = 0; i < len; i++) {
    const num = nums[i]
    if (typeof map.get(num) === 'undefined') {
      map.set(num, [i])
    } else {
      const indexs = map.get(num)
      indexs.push(i)
      map.set(num, indexs)
    }
  }

  // Find the matched number by moving the two pointers,
  // three numbers' sum can be seen as finding the match number
  // equals target - num1 - num2.
  while (left < len - 2) {
    // Minimum number is still bigger than target
    if (nums[left] > target) {
      break
    }
    // mid number reach the end
    if (mid === len - 2) {
      left++
      mid = left + 1
      continue
    }

    let lastNum = target - nums[left] - nums[mid]
    const matchedNums: number[] = map.get(lastNum)
    // Can't find the match number,
    // move the pointer.
    if (typeof matchedNums === 'undefined') {
      mid++
    }
    // find the matched number
    else {
      matchedNums.forEach((matchNum: number) => {
        // Don't add repeated combination
        if (
          left !== matchNum &&
          mid !== matchNum &&
          nums[left] !== nums[left - 1] &&
          nums[mid] !== nums[mid - 1]
        ) {
          const combination = [nums[left], nums[mid], nums[matchNum]]
          res.push(combination)
        }
      })
      mid++
    }
  }
  return res
}

const nums: number[] = [1, 0, -1, 5, 9, 7, 7, 6, 0, -1]
console.log(findThreeNumbersByTarget(nums, 15)) // [ [ -1, 7, 9 ], [ 0, 6, 9 ], [ 1, 5, 9 ], [ 1, 7, 7 ] ]