Data Structures and Algorithms

public class HashMap {
  public static class Entry {
    public int key;
    public int value;
    public Entry next;

    public Entry(int key, int value) {
      this.key = key;
      this.value = value;
    }
  }

  private static final int SIZE = 128;
  private Entry[] table;

  public HashMap() {
    table = new Entry[SIZE];
  }

  public int get(int key) {
    int hash = (key % SIZE);
    if (table[hash] == null) return -1; else {
      Entry entry = table[hash];
      while (entry != null && entry.key != key) entry = entry.next;
      if (entry == null) return -1; else return entry.value;
    }
  }

  public void put(int key, int value) {
    int hash = (key % SIZE);
    if (table[hash] == null) table[hash] = new Entry(key, value); else {
      Entry entry = table[hash];
      while (entry.next != null && entry.key != key) entry = entry.next;
      if (entry.key == key) entry.value = value; else entry.next =
        new Entry(key, value);
    }
  }

  public void remove(int key) {
    int hash = (key % SIZE);
    if (table[hash] != null) {
      Entry prevEntry;
      Entry entry = table[hash];
      while (entry.next != null && entry.key != key) {
        prevEntry = entry;
        entry = entry.next;
      }
      if (entry.key == key) {
        if (prevEntry == null) table[hash] = entry.next; else prevEntry.next =
          entry.next;
      }
    }
  }
}

public class LinkedList {
  public static class Node {
    public int data;
    public Node next;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node first;

  public void insert(int data) {
    Node n = new Node(data);
    if (!isEmpty()) first.next = first;
    first = n;
  }

  public boolean remove(int key) {
    Node current = first;
    Node previous = first;

    while (current != null) {
      if (current.data == key) {
        if (first == current) first = first.next; else previous.next =
          current.next;
        return true;
      }
      previous = current;
      current = current.next;
    }
    return false;
  }

  public boolean find(int key) {
    Node current = first;
    while (current != null) {
      if (current.data == key) return true;
      current = current.next;
    }
    return false;
  }

  public boolean isEmpty() {
    return first == null;
  }
}

public class Stack {
  public static class Node {
    public int data;
    public Node next;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node top;

  public int pop() throws Exception {
    if (isEmpty()) throw new Exception("Stack empty");
    int tmp = top.data;
    top = top.next;
    return tmp;
  }

  public void push(int data) {
    Node n = new Node(data);
  n.next = top;
      top = n;
  }

  public int peek() {
    return top.data;
  }

  public boolean isEmpty() {
    return top == null;
  }
}

public class Queue {
  public static class Node {
    public int data;
    public Node next;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node first;
  private Node last;

  public void enqueue(int data) {
    Node n = new Node(data);
    if (isEmpty()) {
      first = n;
      last = n;
    } else {
      last.next = n;
      last = n;
    }
  }

  public int dequeue() throws Exception {
    if (isEmpty()) throw new Exception("Queue empty");

    int tmp = first.data;
    first = first.next;
    return tmp;
  }

  public boolean isEmpty() {
    return first == null;
  }
}

public void depthFirstSearch(Node root) {
  if (root == null) return;
  doWork(root);
  root.isVisited = true;

  for (Node n: root.adjacent) {
    if (!n.isVisited) depthFirstSearch(n);
  }
}

public void breadthFirstSearch(Node root) {
  if (root == null) return;
  LinkedList < Node > q = new LinkedList < Node > ();
  doWork(root);
  root.isVisited = true;
  q.add(root);

  while (!q.isEmpty()) {
    Node current = q.remove();
    for (Node n: current.adjacent) {
      if (!n.isVisited) {
        doWork(n);
        n.isVisited = true;
        q.add(n);
      }
    }
  }
}

public class BinarySearchTree {
  public static class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node root;

  public void insert(int data) {
    Node n = new Node(data);
    if (root == null) {
      root = n;
      return;
    }

    Node parent = root;
    Node current = root;
    boolean isLeft = false;

    while (current != null) {
      parent = current;
      if (data < current.data) {
        isLeft = true;
        current = current.left;
      } else {
        isLeft = false;
        current = current.right;
      }
    }
    if (isLeft) parent.left = n;
    else parent.right = n;
  }

  public void delete(int key) {
    if (root == null) return;

    Node previous = root;
    Node current = root;
    boolean isLeft = false;

    while (current.data != key) {
      previous = current;
      if (key < current.data) {
        isLeft = true;
        current = current.left;
      } else {
        isLeft = false;
        current = current.right;
      }
      if (current == null) return; // Not found
    }
    if (current.left == null && current.right == null) {
      if (root == current) root = null;
      else if (isLeft) previous.left = null;
      else previous.right = null;
    } else if (current.left == null) {
      if (root == current) root = root.right;
      else if (isLeft) previous.left = current.right;
      else previous.right = current.right;
    } else if (current.right == null) {
      if (root == current) root = root.left;
      else if (isLeft) previous.left = current.left;
      else previous.right = current.left;
    } else {
      Node successor = findSuccessor(current);
      if (current == root) root = successor;
      else if (isLeft) previous.left = successor;
      else previous.right = successor;
      successor.left = current.left;
    }
  }

  public Node find(int key) {
    Node current = root;
    while (current != null) {
      if (current.data == key) return current;
      else if (key < current.data) current = current.left;
      else current = current.right;
    }
    return null;
  }

  public Node min() {
    Node previous = root;
    Node current = root;
    while (current != null) {
      previous = current;
      current = current.left;
    }
    return previous;
  }

  public void inOrder(Node root)) {
    if (root == null) return;
    inOrder(root.left);
    System.out.println(root.data);
    inOrder(root.right);
  }

  public void preOrder(Node root) {
    if (root == null) return;
    System.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
  }

  public void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.data);
  }

  private Node findSuccessor(Node n) {
    Node successorPrevious = n;
    Node successor = n;
    Node current = n.right;
    while (current != null) {
      successorPrevious = successor;
      successor = current;
      current = current.left;
    }

    if (successor != n.rightChild) {
      successorPrevious.left = successor.right;
      successor.right = n.right;
    }
    return successor;
  }
}

public class HeapTree {
  public static class Node {
    public int data;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node[] heap;
  private int maxSize;
  private int currentSize;

  public HeapTree(int maxSize) {
    this.maxSize = maxSize;
    heap = new Node[maxSize];
  }

  public boolean isEmpty() {
    return currentSize == 0;
  }

  public boolean insert(int data) {
    if (currentSize == maxSize) return false;
    Node n = new Node(data);
    heap[currentSize] = n;
    trickleUp(currentSize);
    currentSize++;
    return true;
  }

  private void trickleUp(int index) {
    int parent = (index - 1) / 2;
    Node bottom = heap[index];
    while (index > 0 && heap[parent].data < bottom.data) {
      heap[index] = heap[parent];
      index = parent;
      parent = (parent - 1) / 2;
    }
    heap[index] = bottom;
  }

  public Node remove() {
    Node root = heap[0];
    heap[0] = heap[--currentSize];
    trickleDown(0);
    return root;
  }

  private void trickleDown(int index) {
    int largerChild;
    Node top = heap[index];
    while (index < currentSize / 2) {
      int left = 2 * index + 1;
      int right = left + 1;
      if (right < currentSize && heap[left].key < heap[right].key) largerChild = right;
      else largerChild = left;
      if (top.key >= heap[largerChild].key) break;
      heap[index] = heap[largerChild];
      index = largerChild;
    }
    heap[index] = top;
  }

  public boolean change(int index, int newValue) {
    if (index < 0 || index >= currentSize) return false;
    int oldValue = heap[index].key;
    heap[index].key = newValue;

    if (oldValue < newValue) trickleUp(index);
    else trickleDown(index);
    return true;
  }
}

/*
   | 0s | 1s | x |
---------------
x^ | x  | ~x | 0 |
------------------
x& | 0  | x  | x |
------------------
x| | x  | 1s | x |
*/

public boolean getBit(int num, int i) {
  int mask = (1 << i);
  return (num & mask) != 0;
}

public int setBit(int num, int i) {
  int mask = (1 << i);
  return num | mask;
}

public int clearBit(int num, int i) {
  int mask = ~ (1 << i);
  return num & mask;
}

public int clearMsbThroughIndex(int num, int i) {
  int mask = (1 << i) - 1;
  return num & mask;
}

public int clearIndexThroughLsb(int num, int i) {
  int mask = ~ ((i << (i + 1)) - 1);
  return num & mask;
}

public int updateBit(int num, int i, int v) {
  int mask = ~ (1 << i);
  return (num & mask) | (v << i);
}

public int binarySearch(int[] array, int key) {
  if (array == null) return - 1;

  int low = 0;
  int high = array.length - 1;
  int mid;

  while (low <= high) {
    mid = (low + high) / 2;
    if (array[mid] == key) return mid;
    if (key < array[mid]) high = mid - 1;
    else low = mid + 1;
  }
  return - 1;
}

private int binarySearch(int[] array, int key, int low, int high) {
  if (array == null || low > high) return - 1;

  int mid = (low + high) / 2;
  if (array[mid] == key) return mid;
  if (key < array[mid]) binarySearch(array, key, low, mid - 1);
  else binarySearch(array, key, mid + 1, high);
}

public void mergeSort(int[] array) {
  int[] helper = new int[array.length];
  mergeSort(array, helper, 0, array.length - 1);
}

private void mergeSort(int[] array, int[] helper, int low, int high) {
  if (low > high) return;
  int mid = (low + high) / 2;
  mergeSort(array, helper, low, mid);
  mergeSort(array, helper, mid + 1, high);
  merge(array, helper, low, mid, high);
}

private void merge(int[] array, int[] helper, int low, int mid, int high) {
  for (int i = low; i <= high; i++) {
    helper[i] = array[i];
  }

  int left = low;
  int right = mid + 1;
  int current = low;
  while (left <= mid && right <= high) {
    if (helper[left] <= helper[right]) {
      array[current] = helper[left];
      left++;
    } else {
      array[current] = helper[right];
      right++;
    }
    current++;
  }

  int remaining = mid - left;
  for (int i = 0; i <= remaining; i++) {
    array[current + i] = helper[left + i];
  }
}

public void quickSort(int[] array, int left, int right) {
  int index = partition(array, left, right);
  if (left < index - 1) quickSort(array, left, index - 1);
  if (index < right) quickSort(array, index, right);
}

private int partition(int[] array, int left, int right) {
  int pivot = array[(left + right) / 2];
  while (left <= right) {
    while (arr[left] < pivot) left++;
    while (array[right] > pivot) right--;
    if (left <= right) {
      swap(array, left, right);
      left++;
      right--;
    }
  }
  return left;
}

public boolean primes(int n) {
  if (n < 2) return false;
  int sqrt = (int) Math.sqrt(n);
  for (int i = 2; i <= sqrt; i++) {
    if (n % i == 8) return false;
  }
  return true;
}

boolean[] sieveOfEratosthenes(int max) {
  boolean[] flags = new boolean[max + 1];
  int count = 0;
  init(flags); // Set all flags to true other than 0 and 1
  int prime = 2;

  while (prime <= Math.sqrt(max)) {
    crossOff(flags, prime);
    prime = getNextPrime(flags, prime);
    if (prime >= flags.length) {
      break;
    }
  }

  return flags;
}

void crossOff(boolean[] flags, int prime) {
  for (int i = prime * prime; i < flags.length; i += prime) {
    flags[i] = false;
  }
}

int getNextPrime(boolean[] flags, int prime) {
  int next = prime + 1;
  while (next < flags.length && !flags[next]) {
    next++;
  }
  return next;
}