# COMP 2540 - Midterm

// LinkedList
package Assignment2;

public class LinkedList {

  private Node head;
  private Node tail;
  private int count;

  // constructor
  public LinkedList() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  // addFirst
  public void addFirst(Object data) {
    Node n = new Node(data);

    // if Head and Tail point to null
    // Both head and tail point to the new node
    // and the new node points to null
    if (tail == null && head == null) {
      head = n;
      tail = n;
    } else {
      // link the new node to its successor
      // link head to the new node
      n.setNext(head);
      head = n;
    }

    count++;
  }

  // removeFirst
  public Node removeFirst() {
    if (head == null) {
      System.out.println("Error: the list is empty!");
      return null;
    }

    Node n = head;
    // head points to next node
    head = n.getNext();
    // Allow garbage collector to reclaim the former first node
    n.setNext(null);
    count--;
    return n;
  }

  // addLast
  public void addLast(Object data) {
    Node n = new Node(data);

    // if Head and Tail point to null
    // Both head and tail point to the new node
    // and the new node points to null
    if (tail == null && head == null) {
      head = n;
      tail = n;
    } else {
      // the old last node point to new node
      tail.setNext(n);
      // update tail to point to the new node
      tail = n;
    }

    count++;
  }

  // removeLast
  public Node removeLast() {
    if (head == null) {
      System.out.println("Error: the list is empty!");
      return null;
    }

    Node current = head;
    Node previous = null;

    // find the last node, and the node before it;
    while (current.getNext() != null) {
      previous = current;
      current = current.getNext();
    }

    // set the previous node to point to null
    previous.setNext(null);

    count--;
    return current;
  }

  // getFirst
  public Node getFirst() {
    return head;
  }

  // getLast
  public Node getLast() {
    return tail;
  }

  // size
  public int size() {
    return count;
  }

}

// LinkedStack

package Assignment2;

public class LinkedStack {
  private LinkedList list = null;

  public LinkedStack() {
    this.list = new LinkedList();
  }

  public void push(Object data) {
    list.addFirst(data);
  }

  public Node pop() {
    return list.removeFirst();
  }

  public Node top() {
    return list.getFirst();
  }

  public int size() {
    return list.size();
  }

  public Boolean isEmpty() {
    if (list.size() == 0) {
      return true;
    } else {
      return false;
    }
  }
}

// LinkedQueue

package Assignment2;

public class LinkedQueue {

  private LinkedList list = null;

  public LinkedQueue() {
    this.list = new LinkedList();
  }

  public void enqueue(Object data) {
    list.addLast(data);
  }

  public Node dequeue() {
    return list.removeFirst();
  }

  public Node front() {
    return list.getFirst();
  }

  public int size() {
    return list.size();
  }

  public Boolean isEmpty() {
    if (list.size() == 0) {
      return true;
    } else {
      return false;
    }
  }
}

void select_sort(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    int minIndex = i;
    // 找到最小元素
    for (int j = i + 1; j < n; j++) {
      if(a[j] < a[minIndex]) minIndex = j;
    }
    // 交换最小元素与第一个未排序元素
    int temp = a[i];
    a[i] = a[minIndex];
    a[minIndex] = temp;
  }
}

public static void insertionSort(int[] arr, int n) {
  int i, j;
  for (i = 1; i < n; i++) {
    int value = arr[i];

    // find the position to insert item
    for (j = i - 1; j >= 0; j--) {
      if (value < arr[j])
        arr[j + 1] = arr[j];
      else
        break;
    }
    arr[j + 1] = value; // insert item
  }
}

// quick sort
public static void quickSort(int[] a, int left, int right) {
  if (left >= right)
    return;

  // The Pivot is the last element
  int pivot = a[right];
  int i = left;
  int j = right - 1;

  while (i <= j) {
    // Find an element that is greater then Pivot (from left to right)
    while (i <= j && a[i] <= pivot) {
      i++;
    }
    // Find an element that is less then Pivot (from right to left)
    while (i <= j && a[j] >= pivot) {
      j--;
    }
    // if left index is less than right index
    // then, swap elements at indices left and right;
    if (i < j) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }

  // relocate pivot
  // swap element at index i with the previous pivot
  int temp = a[i];
  a[i] = a[right];
  a[right] = temp;

  // use recursion to seperate the array to two part
  // the first is the array that is less than pivot
  // the second is the array that is greater than pivot
  quickSort(a, left, i - 1);
  quickSort(a, i + 1, right);
}

public static void merge_sort(int[] a, int n) {
  divide(a, 0, n - 1);
}

// 切分
public static void divide(int[] a, int low, int high) {
  int mid = (low + high) / 2;

  if (low < high) {
    // 左边
    divide(a, low, mid);
    // 右边
    divide(a, mid + 1, high);
    // 左右归并
    merge(a, low, mid, high);
  }
}

// 合并
public static void merge(int[] a, int low, int mid, int high) {
  int[] temp = new int[high - low + 1];

  int i = low;
  int j = mid + 1;
  int k = 0;

  // 按照从小到大排列
  while (i <= mid && j <= high) {
    if (a[i] <= a[j]) {
      temp[k] = a[i];
      k++;
      i++;
    } else {
      temp[k] = a[j];
      k++;
      j++;
    }
  }

  // 把左边剩余的数移入数组
  while (i <= mid) {
    temp[k] = a[i];
    k++;
    i++;
  }
  // 把右边边剩余的数移入数组
  while (j <= high) {
    temp[k] = a[j];
    k++;
    j++;
  }
  // 把新数组中的数覆盖原数组
  for (k = 0; k < temp.length; k++) {
    a[k + low] = temp[k];
  }
}

void preOrder(Node* root) {
  if (root == null) return;
  System.out.print(root->value);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  System.out.print(root->value);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  System.out.print(root->value);
}