/**
 * @auther zhangxufeng@uworks.cc 2016/06/03
 */
public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {
  public BinaryHeap() {
    enlargeArray(DEFAULT_CAPACITY);
  }

  public BinaryHeap(int capacity) {
    int tmp = capacity;
    if (capacity < DEFAULT_CAPACITY) {
      tmp = DEFAULT_CAPACITY;
    }

    enlargeArray(tmp);
  }

  public BinaryHeap(AnyType[] items) {
    currentSize = items.length;
    enlargeArray(enlargeTimes());

    int i = 0;
    for (AnyType item : items) {
      array[++i] = item;
    }
    buildHeap();
  }

  public void insert(AnyType x) {
    if (currentSize == array.length - 1) {
      enlargeArray(array.length * 2 + 1);
    }

    int hole = ++currentSize;
    while (hole > 1 && x.compareTo(array[hole / 2]) < 0) {
      array[hole] = array[hole / 2];
      hole /= 2;
    }
    array[hole] = x;
  }

  public void insertFromTop(AnyType x) {
    if (currentSize == array.length - 1) {
      enlargeArray(array.length * 2 + 1);
    }

    AnyType item = x;

    // 获取要交换的路径
    int index = (currentSize + 1) / 2;
    int[] path = new int[height(1) + 1];
    for (int i = 0; i < path.length; i++) {
      path[i] = index;
      index /= 2;
    }

    for (int i = path.length - 1; i >= 0; i--) {
      if (path[i] <= 0) {
        continue;
      }
      item = compare(item, path[i]);
    }
    array[++currentSize] = item;
  }

  private AnyType compare(AnyType item, int index) {
    if (item.compareTo(array[index]) < 0) {
      AnyType tmp = item;
      item = array[index];
      array[index] = tmp;
    }
    return item;
  }

  private int height(int index) {
    int tmp = 1, i = 0;
    while (tmp * 2 <= index) {
      tmp *= 2;
    }

    while (tmp * 2 <= currentSize) {
      tmp *= 2;
      i++;
    }

    return i;
  }

  public AnyType findMin() {
    return null;
  }

  public int size() {
    return currentSize;
  }

  private int[] path(int root) {
    int[] result = new int[height(root) + 1];
    for (int i = currentSize, j = result.length - 1; i >= 1; i /= 2) {
      result[j--] = i;
    }
    return result;
  }

  public AnyType deleteMin() throws UnderflowException {
    if (isEmpty()) {
      throw new UnderflowException();
    }

    AnyType minItem = findMin();
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
  }

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

  public void makeEmpty() {
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  private static final int DEFAULT_CAPACITY = 10;

  private int currentSize;
  private AnyType[] array;

  private void percolateDown(int hole) {
    int child;
    AnyType tmp = array[hole];

    while ((child = hole * 2) <= currentSize) {
      if (child < currentSize && array[child + 1].compareTo(array[child]) < 0) {
        child++;
      }
      System.out.println("hole:" + hole + " child:" + child);

      if (array[child].compareTo(tmp) < 0) {
        array[hole] = array[child];
      } else {
        break;
      }
      hole = child;
    }
    array[hole] = tmp;
  }

  private void buildHeap() {
    for (int i = currentSize / 2; i > 0; i--) {
      percolateDown(i);
    }
  }

  private void enlargeArray(int newSize) {
    if (newSize <= currentSize) {
      newSize = enlargeTimes();
    }

    AnyType[] old = array;
    array = ((AnyType[]) new Comparable[newSize]);
    if (null != old) {
      for (int i = 0; i < old.length; i++) {
        array[i] = old[i];
      }
    }
  }

  private int enlargeTimes() {
    return (currentSize + 2) * 11 / 10;
  }

  public void print() {
    for (int i = 1; i <= currentSize; i++) {
      System.out.print(array[i] + "\t");
    }
  }
}

class UnderflowException extends Exception {}

/**
 * Created by Administrator on 2016/6/2.
 */
public class BinomialQueue<AnyType extends Comparable<? super AnyType>> {
  public BinomialQueue() {

  }

  public BinomialQueue(AnyType item) {

  }

  public void merge(BinomialQueue<AnyType> rhs) {
    if (this == rhs) {
      return;
    }

    currentSize += rhs.currentSize;

    if (currentSize > capacity()) {
      int maxLength = Math.max(theTrees.length, rhs.theTrees.length);
      expandTheTrees(maxLength + 1);
    }

    Node<AnyType> carry = null;
    for (int i = 0, j = 1; j < currentSize; i++, j*= 2) {
      Node<AnyType> t1 = theTrees[i];
      Node<AnyType> t2 = i < rhs.theTrees.length ? rhs.theTrees[i] : null;

      int whichCase = t1 == null ? 0 : 1;
      whichCase += t2 == null ? 0 : 1;
      whichCase += carry == null ? 0 : 4;

      switch (whichCase) {
        case 0:
        case 1:
          break;
        case 2:
          theTrees[i] = t2;
          rhs.theTrees[i] = null;
          break;
        case 4:
          theTrees[i] = carry;
          carry = null;
          break;
        case 3:
          carry = combineTrees(t1, t2);
          theTrees[i] = rhs.theTrees[i] = null;
          break;
        case 5:
          carry = combineTrees(t1, carry);
          theTrees[i] = null;
          break;
        case 6:
          carry = combineTrees(t2, carry);
          rhs.theTrees[i] = null;
          break;
        case 7:
          theTrees[i] = carry;
          carry = combineTrees(t1, t2);
          rhs.theTrees[i] = null;
          break;
        default:
      }
    }

    for (int k = 0; k < rhs.theTrees.length; k++) {
      rhs.theTrees[k] = null;
    }
    rhs.currentSize = 0;
  }

  public void insert(AnyType x) {
    merge(new BinomialQueue<>(x));
  }

  public AnyType findMin() {

  }

  public AnyType deleteMin() throws UnderflowException {
    if (isEmpty()) {
      throw new UnderflowException();
    }

    int minIndex = findMinIndex();
    AnyType minItem = theTrees[minIndex].element;

    Node<AnyType> deletedTree = theTrees[minIndex].leftChild;

    BinomialQueue<AnyType> deletedQueue = new BinomialQueue<>();
    deletedQueue.expandTheTrees(minIndex + 1);

    deletedQueue.currentSize = (1 << minIndex) - 1;
    for (int j = minIndex - 1; j >= 0; j--) {
      deletedQueue.theTrees[j] = deletedTree;
      deletedTree = deletedTree.nextSibling;
      deletedQueue.theTrees[j].nextSibling = null;
    }

    theTrees[minIndex] = null;
    currentSize -= deletedQueue.currentSize + 1;
    merge(deletedQueue);

    return minItem;
  }

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

  public void makeEmpty(){

  }

  private static class Node<AnyType> {
    Node(AnyType theElement) {
      this(theElement, null, null);
    }

    Node(AnyType theElement, Node<AnyType> lt, Node<AnyType> nt) {
      element = theElement;
      leftChild = lt;
      nextSibling = nt;
    }

    AnyType element;
    Node<AnyType> leftChild;
    Node<AnyType> nextSibling;
  }

  private static final int DEFAULT_TREES = 1;

  private int currentSize;
  private Node<AnyType>[] theTrees;

  private void expandTheTrees(int newNumTrees) {

  }

  private Node<AnyType> combineTrees(Node<AnyType> t1, Node<AnyType> t2) {
    if (t1.element.compareTo(t2.element) > 0) {
      return combineTrees(t2, t1);
    }
    t2.nextSibling = t1.leftChild;
    t1.leftChild = t2;
    return t1;
  }

  private int capacity() {
    return (1 << theTrees.length) - 1;
  }

  private int findMinIndex() {

  }
}

class UnderflowException extends Exception {}

/**
 * Created by Administrator on 2016/6/1.
 */
public class LeftistHeap<AnyType extends Comparable<? super AnyType>> {
  public LeftistHeap() {
    root = null;
  }

  public void merge(LeftistHeap<AnyType> rhs) {
    if (this == rhs) {
      return;
    }

    root = merge(root, rhs.root);
    rhs.root = null;
  }

  public void insert(AnyType x) {
    root = merge(new Node<>(x), root);
  }

  public AnyType findMin() {
    return root.element;
  }

  public AnyType deleteMin() {
    AnyType element = root.element;
    root = merge(root.left, root.right);
    return element;
  }

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

  public void makeEmpty() {
    root = null;
  }

  private static class Node<AnyType> {
    Node(AnyType theElement) {
      this(theElement, null, null);
    }

    Node(AnyType theElement, Node<AnyType> lt, Node<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
      npl = 0;
    }

    AnyType element;
    Node<AnyType> left;
    Node<AnyType> right;
    int npl;
  }

  private Node<AnyType> root;

  private Node<AnyType> merge(Node<AnyType> h1, Node<AnyType> h2) {
    if (null == h1) {
      return h2;
    }
    if (null == h2) {
      return h1;
    }
    if (h1.element.compareTo(h2.element) < 0) {
      return merge1(h1, h2);
    } else {
      return merge1(h2, h1);
    } 
  }

  private Node<AnyType> merge1(Node<AnyType> h1, Node<AnyType> h2) {
    if (h1.left == null) {
      h1.left = h2;
    } else {
      h1.right = merge(h1.right, h2);
      if (h1.left.npl < h1.right.npl) {
        swapChildren(h1);
      }
      h1.npl = h1.right.npl + 1;
    }

    return h1;
  }

  private void swapChildren(Node<AnyType> t) {
    
  }
}

//1.新旧字符串起始位置相同，终了位置相差1
  /**
   * 如果已知字符串excel的hashCode值，那么就可以求解excels的hashCode值
   * 计算公式为hash(new) = 31 * hash(old) + word.charAt(word.length() - 1);
   * @param word  新字符串，如excels
   * @param hash  就字符串的hash值，即excel的hash值
   * @return  新字符串的hash值
   */
  public int computeHashCode(String word, int hash) {
    if (word.length() == 1) {
      return word.hashCode();
    }
    return 31 * hash + word.charAt(word.length() - 1);
  }

// 2.新旧字符串起始和终了位置都向右相差长度为1的偏移量
  /**
   * 新旧字符串都是字符串goal的子串，并且新旧字符串起始和终了位置都向右相差长度为1的偏移量
   * 计算公式为 31 * oldHashCode + goal.charAt(index - 1 + k) - ((int) Math.pow(31, k)) * goal.charAt(index - 1);
   * @param goal  目标字符串
   * @param index 旧字符串的起始位置
   * @param k 新旧字符串的长度
   * @param oldHashCode 旧字符串的hashCode值
   * @return  新字符串的hashCode值
   */
  private int computeHashCode(String goal, int index, int k, int oldHashCode) {
    if (index > 0) {
      return 31 * oldHashCode + goal.charAt(index - 1 + k) - ((int) Math.pow(31, k)) * goal.charAt(index - 1);
    } else if (index == 0) {
      return goal.substring(0, k).hashCode();
    } else {
      return 0;
    }
  }

public class Solution {
  private char[][] table = new char[][]{{'t', 'h', 'i', 's'}, {'w', 'a', 't', 's'}, {'o', 'a', 'h', 'g'}, {'f', 'g', 'd', 't'}};
  private ArrayList<String> words = new ArrayList<>(4);
  private ArrayList<Integer> hashs = new ArrayList<>(4);

  public List<Vector> getMatchedWords() {
    initWords();
    initHashs();
    LinkedList<Vector> result = new LinkedList<>();
    for (int i = 0; i < table.length; i++) {
      for (int j = 0; j < table[0].length; j++) {
        computeResult(i, j, result);
      }
    }

    return result;
  }

  private void initWords() {
    words.add("this");
    words.add("two");
    words.add("fat");
    words.add("that");
  }

  private void initHashs() {
    words.forEach(word -> hashs.add(word.hashCode()));
  }

  private void computeResult(final int i, final int j, LinkedList<Vector> result) {
    Direction[] directions = Direction.values();
    for (int m = 0; m < directions.length; m++) {
      switch (directions[m]) {
        case UP:
          getLinearResult(i, -1, j, 0, result);
          break;
        case UPLEFT:
          getLinearResult(i, -1, j, -1, result);
          break;
        case LEFT:
          getLinearResult(i, 0, j, -1, result);
          break;
        case LEFTDOWN:
          getLinearResult(i, 1, j, -1, result);
          break;
        case DOWN:
          getLinearResult(i, 1, j, 0, result);
          break;
        case RIGHTDOWN:
          getLinearResult(i, 1, j, 1, result);
          break;
        case RIGHT:
          getLinearResult(i, 0, j, 1, result);
          break;
        case UPRIGHT:
          getLinearResult(i, -1, j, 1, result);
          break;
        default:
      }
    }
  }

  private void getLinearResult(final int i, final int yOffset, final int j, final int xOffset, LinkedList<Vector> result) {
    int iEnd = i; // 记录终点的横坐标
    int jEnd = j; // 记录终点的纵坐标
    String wordTmp = "";

    while (iEnd >= 0 && jEnd >= 0 && iEnd < table.length && jEnd < table[0].length) {
      wordTmp += table[iEnd][jEnd];
      if (isHashCodeExist(wordTmp.hashCode()) && words.contains(wordTmp)) {
        Vector vector = new Vector(i, j, iEnd, jEnd);
        result.add(vector);
      }
      iEnd += yOffset;
      jEnd += xOffset;
    }
  }

  private boolean isHashCodeExist(int hash) {
    return hashs.contains(hash);
  }

  private enum Direction {
    UP(1), UPLEFT(2), LEFT(3), LEFTDOWN(4), DOWN(5), RIGHTDOWN(6), RIGHT(7), UPRIGHT(8);

    private int code;

    Direction(int code) {
      this.code = code;
    }

    public int code() {
      return code;
    }

    public static Direction resolve(Integer code) {
      if (null == code) {
        return null;
      }

      switch (code) {
        case 1:
          return UP;
        case 2:
          return UPLEFT;
        case 3:
          return LEFT;
        case 4:
          return LEFTDOWN;
        case 5:
          return DOWN;
        case 6:
          return RIGHTDOWN;
        case 7:
          return RIGHT;
        case 8:
          return UPRIGHT;
        default:
          return null;
      }
    }
  }

  protected class Vector {
    private int stX;
    private int stY;
    private int enX;
    private int enY;

    public Vector(int sX, int sY, int eX, int eY) {
      stX = sX;
      stY = sY;
      enX = eX;
      enY = eY;
    }

    @Override
    public String toString() {
      return "坐标点为：(" + stX + "," + stY + ")->(" + enX + "," + enY + ")";
    }
  }
}

/**
 * 由于模式字符串的长度是一定的，那么在进行匹配的时候可以在目标字符串中进行一次循环遍历
 * 当模式串的hash值和目标串中长度与模式串相同的子串的hash值相等时该子串就有可能是要求解
 * 的子串，然后进行一次全匹配即可判断出结果；另外在目标串中进行hash值的计算时，由于第
 * i+1个子串的hash值与第i个子串的hash值有一定的关系，因而可以迅速计算出结果
 */
public class Solution {
  public int getFirstMatchedString(String goal, String pattern) { // abcdef  def
    if (goal.length() < pattern.length()) {
      return -1;
    }

    int hashGoal = computeHashCode(goal.substring(0, pattern.length()));
    int hashPattern = computeHashCode(pattern);

    for (int i = 0; i <= goal.length() - pattern.length(); i++) {
      if (hashGoal == hashPattern && goal.substring(i, i + pattern.length()).equals(pattern)) {
        return i;
      }
      hashGoal = computeHashCode(goal, i + 1, pattern.length(), hashGoal);
    }

    return -1;
  }

  private int computeHashCode(String goal, int index, int k, int oldHashCode) {
    return 31 * oldHashCode + goal.charAt(index - 1 + k) - ((int) Math.pow(31, k)) * goal.charAt(index - 1);
  }

  private int computeHashCode(String str) {
    return str.hashCode();
  }
}

/**
 * 双散列散列表：解决了聚集的问题，但是要求表的大小一定是素数，并且在hash值的计算较复杂
 * 的时候（如串）效率相对线性和平方散列较慢
 */
public class DoubleHashProbingHashTable<AnyType> {
  public DoubleHashProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public DoubleHashProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);
    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {
      this(e, true);
    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }

  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;  // The array of elements
  private int currentSize;  // The number of occupied cells

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset++ * hash2(x);
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }

    return currentPos;
  }

  private int hash2(AnyType x) {
    return  7 - (x.hashCode() % 7);
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

/**
 * 平方探测散列表：解决了一次聚集，但是当散列到同一位置的元素二次散列的位置也是一样的，这叫二次聚集
 * （相对最优的算法）
 */
public class QuadraticProbingHashTable<AnyType> {
  public QuadraticProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public QuadraticProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);

    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {

    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }


  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;
  private int currentSize;

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset;
      offset += 2;
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }
    return currentPos;
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

/**
 * 线性探测法：缺点是产生冲突的元素会聚集在某一块位置，这叫一次聚集
 */
public class ChainingProbingHashTable<AnyType> {
  public ChainingProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public ChainingProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);
    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {
      this(e, true);
    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }

  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;  // The array of elements
  private int currentSize;  // The number of occupied cells

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset;
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }

    return currentPos;
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

import java.util.LinkedList;
import java.util.List;

/**
 * 分离链接散列法
 */
public class SeparateChainingHashTable<AnyType> {
  public SeparateChainingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public  SeparateChainingHashTable(int size) {
    theLists = new LinkedList[nextPrime(size)];
    for (int i = 0; i < theLists.length; i++) {
      theLists[i] = new LinkedList<>();
    }
  }

  public void insert(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    if (!whichList.contains(x)) {
      whichList.add(x);
      if (++theSize > theLists.length) {
        rehash();
      }
    }
  }

  public void remove(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    if (whichList.contains(x)) {
      whichList.remove(x);
      theSize--;
    }
  }

  public boolean contains(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    return whichList.contains(x);
  }

  public void makeEmpty() {
    for (int i = 0; i < theLists.length; i++) {
      theLists[i].clear();
    }
    theSize = 0;
  }

  private static final int DEFAULT_TABLE_SIZE = 101;
  private List<AnyType>[] theLists;
  private int theSize;

  private void rehash() {
    List<AnyType>[] oldLists = theLists;

    theLists = new List[nextPrime(2 * theLists.length)];
    for (int j = 0; j < theLists.length; j++) {
      theLists[j] = new LinkedList<>();
    }

    theSize = 0;
    for (int i = 0; i < oldLists.length; i++) {
      for (AnyType item : oldLists[i]) {
        insert(item);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= theLists.length;
    if (hashVal < 0) {
      hashVal += theLists.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }
    int sqrt = (int) Math.sqrt(n);
    for (int i = 0; i < sqrt; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

/**
 * @auther zhangxufeng@uworks.cc 2016/05/10
 */
public class Queue<AnyType> {
  private static class QueueNode<AnyType> {
    QueueNode() {}
    QueueNode(AnyType e, QueueNode<AnyType> p, QueueNode<AnyType> n) {
      element = e;
      prev = p;
      next = n;
    }

    AnyType element;
    QueueNode<AnyType> prev;
    QueueNode<AnyType> next;
  }

  private QueueNode<AnyType> front;
  private QueueNode<AnyType> rear;
  private int size;

  public Queue() {
    front = new QueueNode<>();
    rear = new QueueNode<>(null, front, null);
    front.next = rear;
    size = 0;
  }

  public int size() {
    return size;
  }

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

  public void clear() {
    front.next = rear;
    rear.prev = front;
  }

  public void enQueue(AnyType item) {
    rear.prev.next = new QueueNode<>(item, rear.prev, rear);
    rear.prev = rear.prev.next;
    size++;
  }

  public AnyType deQueue() {
    if (isEmpty()) {
      throw new IllegalStateException();
    }

    AnyType result = front.next.element;
    front.next.next.prev = front;
    front.next = front.next.next;
    size--;
    return result;
  }
}

import java.util.Stack;

/**
 * Created by Administrator on 2016/5/6.
 */
public class MyAvlTree<AnyType extends Comparable<? super AnyType>> {
  private static class AvlNode<AnyType> {
    AvlNode(AnyType theElement) {
      this(theElement, null, null);
    }

    AvlNode(AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
      height = 0;
    }

    AnyType element;
    AvlNode<AnyType> left;
    AvlNode<AnyType> right;
    int height;
  }

  private AvlNode<AnyType> root;
  private int modCount;

  public MyAvlTree() {
    root = null;
    modCount = 0;
  }

  public void insert(AnyType item) {
    root = insert(item, root);
  }

  private AvlNode<AnyType> insert(AnyType item, AvlNode<AnyType> tree) {
    if (null == tree) {
      modCount++;
      return new AvlNode<>(item);
    }

    int compareResult = compare(item, tree.element);

    if (compareResult > 0) {
      tree.right = insert(item, tree.right);
      if (height(tree.right) - height(tree.left) == 2) {
        if (compare(item, tree.right.element) > 0) {
          tree = rotateWithRightChild(tree);
        } else {
          tree = doubleWithRightChild(tree);
        }
      }
    } else if (compareResult < 0) {
      tree.left = insert(item, tree.left);
      if (height(tree.left) - height(tree.right) == 2) {
        if (compare(item, tree.left.element) < 0) {
          tree = rotateWithLeftChild(tree);
        } else {
          tree = doubleWithLeftChild(tree);
        }
      }
    }

    tree.height = max(height(tree.left), height(tree.right)) + 1;
    return tree;
  }

  private int max(int a, int b) {
    return a > b ? a : b;
  }

  private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> node) {
    AvlNode<AnyType> leftNode = node;
    node = node.right;
    leftNode.right = node.left;
    node.left = leftNode;
    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
    node.height = max(height(node.left), height(node.right)) + 1;
    return node;
  }

  private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> node) {
//    AvlNode<AnyType> leftNode = node;
//    node = node.right.left;
//    leftNode.right.left = node.right;
//    node.right = leftNode.right;
//    leftNode.right = node.left;
//    node.left = leftNode;
//
//    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
//    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
//    node.height = max(height(node.left), height(node.right)) + 1;
    node.right = rotateWithLeftChild(node.right);
    return rotateWithRightChild(node);
  }

  private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> node) {
    AvlNode<AnyType> rightNode = node;
    node = node.left;
    rightNode.left = node.right;
    node.right = rightNode;

    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
    node.height = max(height(node.left), height(node.right)) + 1;

    return node;
  }

  private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> node) {
//    AvlNode<AnyType> rightNode = node;
//    node = node.left.right;
//    rightNode.left.right = node.left;
//    node.left = rightNode.left;
//    rightNode.left = node.right;
//    node.right = rightNode;
//
//    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
//    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
//    node.height = max(height(node.left), height(node.right)) + 1;
    node.left = rotateWithRightChild(node.left);
    return rotateWithLeftChild(node);
  }

  private int height(AvlNode<AnyType> node) {
    return null == node ? -1 : node.height;
  }

  private int compare(AnyType a, AnyType b) {
    return a.compareTo(b);
  }

  public void makeEmpty() {
    root = null;
  }

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

  public int size() {
    return size(root.left) + size(root.right) + 1;
  }

  private int size(AvlNode<AnyType> tree) {
    if (null == tree) {
      return 0;
    }

    return size(tree.left) + size(tree.right) + 1;
  }

  public void remove(AnyType item) {
    root = remove(item, root);
  }

  private AvlNode<AnyType> remove(AnyType item, AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    }

    int compareResult = compare(item, tree.element);

    if (compareResult > 0) {
      tree.right = remove(item, tree.right);
      if (height(tree.left) - height(tree.right) == 2) {
        tree = rotateWithLeftChild(tree);
      }
    } else if (compareResult < 0) {
      tree.left = remove(item, tree.left);
      if (height(tree.right) - height(tree.left) == 2) {
        tree = rotateWithRightChild(tree);
      }
    } else {
      if (null != tree.left && null != tree.right) {
        tree.element = findMin(tree.right).element;
        tree.right = remove(tree.element, tree.right);
        tree.height = max(height(tree.left), height(tree.right)) + 1;
      } else {
        tree = null != tree.left ? tree.left : tree.right;
      }
    }

    return tree;
  }

  public AnyType findMin() {
    return findMin(root).element;
  }

  private AvlNode<AnyType> findMin(AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    } else if (null == tree.left) {
      return tree;
    }

    return findMin(tree.left);
  }

  public AnyType findMax() {
    return findMax(root).element;
  }

  private AvlNode<AnyType> findMax(AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    } else if (null == tree.right) {
      return tree;
    }

    return findMax(tree.right);
  }

  public boolean isAvlTree() {
    return isAvlTree(root);
  }

  private boolean isAvlTree(AvlNode<AnyType> tree) {
    if (null == tree) {
      return true;
    } else if (height(root) != max(height(root.left), height(root.right)) + 1) {
      return false;
    }

    return isAvlTree(tree.left) && isAvlTree(tree.right);
  }

  public void insertWithoutRecursion(AnyType item) {
    Stack<AvlNode<AnyType>> stack = new Stack<>();
    AvlNode<AnyType> pointer = root;
    while (null != pointer) {
      stack.push(pointer);

      int compareResult = compare(item, pointer.element);

      if (compareResult < 0) {
        pointer = pointer.left;
      } else if (compareResult > 0) {
        pointer = pointer.right;
      } else {
        return;
      }
    }

    pointer = new AvlNode<>(item);

    while (!stack.isEmpty()) {
      pointer = stack.pop();
      pointer.height = max(height(pointer.left), height(pointer.right)) + 1;
    }
  }
}

import java.util.Stack;

/**
 * 带有比当前节点小的最大子节点和比当前节点大的最小子节点的二叉树，该树可以从两个角度看：树或双向链表
 * 因为每个节点都保存有前一个节点和后一个几点的指针，因而可以看做是一个双向链表，并且该链表是经过排序的链表
 */
public class MyTreeSet<AnyType extends Comparable<? super AnyType>> implements Iterable<AnyType> {
  private static class BinaryNode<AnyType> {
    BinaryNode() {}

    BinaryNode(AnyType theElement) {
      this(theElement, null, null, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt, BinaryNode<AnyType> pv, BinaryNode<AnyType> nt) {
      element = theElement;
      left = lt;
      right = rt;
      prev = pv;
      next = nt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
    BinaryNode<AnyType> prev;
    BinaryNode<AnyType> next;
  }

  public MyTreeSet() {
    root = null;
    begin = new BinaryNode<>();
    end = new BinaryNode<>(null, null, null, begin, null);
    begin.next = end;
    modCount = 0;
  }

  public void makeEmpty() {
    modCount++;
    root = null;
    begin.next = end;
    end.prev = begin;
  }

  public boolean isEmpty() {
    return null == root && begin.next == end && end.prev == begin;
  }

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public AnyType findMin() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return begin.next.element;
    }
  }

  public AnyType findMax() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return end.prev.element;
    }
  }

  public void insert(AnyType x) {
    root = insert(x, root, begin);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public void printTree() {
    if (isEmpty()) {
      System.out.println("Empty Tree");
    } else {
      BinaryNode<AnyType> pointer = begin.next;
      while (pointer != end) {
        System.out.print(pointer.element + "\t");
        pointer = pointer.next;
      }
    }
  }

  private boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return false;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      return contains(x, t.left);
    } else if (compareResult > 0) {
      return contains(x, t.right);
    } else {
      return true;
    }
  }

  private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.left){
      return t;
    }

    return findMin(t.left);
  }

  private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.right) {
      return t;
    }

    return findMin(t.right);
  }

  /**
   * 插入一个节点
   * @param x 要插入的节点值
   * @param t 要插入的位置
   * @param pv 要插入位置之前的最大节点
   * @return 插入后的子树
   */
  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t, BinaryNode<AnyType> pv) {
    if (null == t) {
      modCount++;
      BinaryNode<AnyType> result = new BinaryNode<>(x, null, null, pv, pv.next);
      pv.next.prev = result;
      pv.next = result;
      return result;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = insert(x, t.left, t.prev);
    } else if (compareResult > 0) {
      t.right = insert(x, t.right, t);
    }

    return t;
  }

  private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return t;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = remove(x, t.left);
    } else if (compareResult > 0) {
      t.right = remove(x, t.right);
    } else if (t.left != null && t.right != null) {
      t.element = findMin(t.right).element;
      t.right = remove(t.element, t.right);
    } else {
      modCount++;
      t.prev.next = t.next;
      t.next.prev = t.prev;
      t = null != t.left ? t.left : t.right;
    }

    return t;
  }

  public int size() {
    int result = 0;
    BinaryNode<AnyType> pointer = begin.next;
    while (pointer != end) {
      pointer = pointer.next;
      result++;
    }
    return result;
  }

  public void inOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()){
        pointer = stack.pop();
        visit(pointer);
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void inOrder1() {
    BinaryNode<AnyType> pointer = begin.next;
    while (pointer != end) {
      visit(pointer);
      pointer = pointer.next;
    }
  }

  public void preOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        visit(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()) {
        pointer = stack.pop();
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void laterOrder1() {
    Stack<StackElement<AnyType>> stack = new Stack<>();
    StackElement<AnyType> pointer = new StackElement<>(root, Tag.LEFT);

    while (true) {
      if (null != pointer.node && pointer.tag == Tag.LEFT) {
        stack.push(pointer);
        pointer = new StackElement<>(pointer.node.left, Tag.LEFT);
      } else if (!stack.isEmpty()){
        pointer = stack.peek();
        if (Tag.LEFT == pointer.tag) {
          pointer.tag = Tag.RIGHT;
          pointer = new StackElement<>(pointer.node.right, Tag.LEFT);
        } else {
          pointer = stack.pop();
          visit(pointer.node);
        }
      } else {
        break;
      }
    }

  }

  public void laterOrder() {
    if (null == root) {
      return;
    }
    Stack<StackElement<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;
    StackElement<AnyType> element;

    while (true) {
      while (null != pointer) { // 找到最左节点
        element = new StackElement<>(pointer, Tag.LEFT);
        stack.push(element);
        pointer = pointer.left;
      }

      element = stack.pop();
      pointer = element.node;

      while (Tag.RIGHT == element.tag) {  // 如果是从右子树返回，则对其进行访问
        visit(pointer);
        if (stack.isEmpty()) {
          return;
        }
        element = stack.pop();
        pointer = element.node;
      }

      element.tag = Tag.RIGHT;  // 左边节点访问完则向右下滑一个节点开始访问右边节点
      stack.push(element);
      pointer = pointer.right;
    }
  }

  private void visit(BinaryNode<AnyType> node) {
    System.out.print(node.element.toString() + "\t");
  }

  private BinaryNode<AnyType> begin;
  private BinaryNode<AnyType> end;
  private BinaryNode<AnyType> root;
  private int modCount;

  public java.util.Iterator<AnyType> iterator() {
    return new MyTreeSetIterator();
  }

  private class MyTreeSetIterator implements java.util.Iterator<AnyType> {
    private BinaryNode<AnyType> current;
    private Stack<BinaryNode<AnyType>> stack;
    private int expectedModCount = modCount;
    private boolean okToRemove = false;

    public MyTreeSetIterator() {
      stack = new Stack<>();
      pushLeftMost(root);
    }

    public boolean hasNext() {
      return !stack.isEmpty();
    }

    public AnyType next() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!hasNext()) {
        throw new java.util.NoSuchElementException();
      }

      current = stack.pop();
      pushLeftMost(current.right);
      okToRemove = true;

      return current.element;
    }

    public void remove() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!okToRemove) {
        throw new IllegalStateException();
      }

      MyTreeSet.this.remove(current.element);
      expectedModCount++;
    }

    private void pushLeftMost(BinaryNode<AnyType> tree) {
      BinaryNode<AnyType> pointer = tree;
      while (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      }
    }
  }

  private class StackElement<AnyType> {
    Tag tag;
    BinaryNode<AnyType> node;

    public StackElement(BinaryNode<AnyType> n, Tag t) {
      node = n;
      tag = t;
    }
  }
  enum Tag{LEFT, RIGHT}
}

class UnderFlowException extends Exception {}

import java.util.Stack;

/**
 * @auther zhangxufeng@uworks.cc 2016/05/03
 */
public class MyTreeSet<AnyType extends Comparable<? super AnyType>> implements Iterable<AnyType> {
  private static class BinaryNode<AnyType> {
    BinaryNode(AnyType theElement) {
      this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
  }

  public MyTreeSet() {
    root = null;
    modCount = 0;
  }

  public void makeEmpty() {
    modCount++;
    root = null;
  }

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

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public AnyType findMin() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return findMin(root).element;
    }
  }

  public AnyType findMax() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return findMax(root).element;
    }
  }

  public void insert(AnyType x) {
    root = insert(x, root);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public void printTree() {
    if (isEmpty()) {
      System.out.println("Empty Tree");
    } else {
      printTree(root);
    }
  }

  private void printTree(BinaryNode<AnyType> t) {
    if (null != t) {
      printTree(t.left);
      System.out.println(t.element);
      printTree(t.right);
    }
  }

  private boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return false;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      return contains(x, t.left);
    } else if (compareResult > 0) {
      return contains(x, t.right);
    } else {
      return true;
    }
  }

  private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.left){
      return t;
    }

    return findMin(t.left);
  }

  private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.right) {
      return t;
    }

    return findMax(t.right);
  }

  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      modCount++;
      return new BinaryNode<AnyType>(x, null, null);
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = insert(x, t.left);
    } else if (compareResult > 0) {
      t.right = insert(x, t.right);
    } else {}

    return t;
  }

  private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return t;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = remove(x, t.left);
    } else if (compareResult > 0) {
      t.right = remove(x, t.right);
    } else if (t.left != null && t.right != null) {
      t.element = findMin(t.right).element;
      t.right = remove(t.element, t.right);
    } else {
      modCount++;
      t = null != t.left ? t.left : t.right;
    }

    return t;
  }

  public int size() {
    return size(root);
  }

  private int size(BinaryNode<AnyType> tree) {
    if (null == tree) {
      return 0;
    }

    return size(tree.left) + size(tree.right) + 1;
  }

  public void inOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()){
        pointer = stack.pop();
        visit(pointer);
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void preOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        visit(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()) {
        pointer = stack.pop();
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void laterOrder1() {
    Stack<StackElement<AnyType>> stack = new Stack<>();
    StackElement<AnyType> pointer = new StackElement<>(root, Tag.LEFT);

    while (true) {
      if (null != pointer.node && pointer.tag == Tag.LEFT) {
        stack.push(pointer);
        pointer = new StackElement<>(pointer.node.left, Tag.LEFT);
      } else if (!stack.isEmpty()){
        pointer = stack.peek();
        if (Tag.LEFT == pointer.tag) {
          pointer.tag = Tag.RIGHT;
          pointer = new StackElement<>(pointer.node.right, Tag.LEFT);
        } else {
          pointer = stack.pop();
          visit(pointer.node);
        }
      } else {
        break;
      }
    }

  }

  public void laterOrder() {
    if (null == root) {
      return;
    }
    Stack<StackElement<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;
    StackElement<AnyType> element;

    while (true) {
      while (null != pointer) { // 找到最左节点
        element = new StackElement<>(pointer, Tag.LEFT);
        stack.push(element);
        pointer = pointer.left;
      }

      element = stack.pop();
      pointer = element.node;

      while (Tag.RIGHT == element.tag) {  // 如果是从右子树返回，则对其进行访问
        visit(pointer);
        if (stack.isEmpty()) {
          return;
        }
        element = stack.pop();
        pointer = element.node;
      }

      element.tag = Tag.RIGHT;  // 左边节点访问完则向右下滑一个节点开始访问右边节点
      stack.push(element);
      pointer = pointer.right;
    }
  }

  public void breadthOrder() {
    Queue<BinaryNode<AnyType>> queue = new Queue<>();
    queue.enQueue(root);

    while (!queue.isEmpty()) {
      BinaryNode<AnyType> pointer = queue.deQueue();
      visit(pointer);
      if (null != pointer.left) {
        queue.enQueue(pointer.left);
      }
      if (null != pointer.right) {
        queue.enQueue(pointer.right);
      }
    }
  }

  private void visit(BinaryNode<AnyType> node) {
    System.out.print(node.element.toString() + "\t");
  }

  private BinaryNode<AnyType> root;
  private int modCount;

  public java.util.Iterator<AnyType> iterator() {
    return new MyTreeSetIterator();
  }

  private class MyTreeSetIterator implements java.util.Iterator<AnyType> {
    private BinaryNode<AnyType> current;
    private Stack<BinaryNode<AnyType>> stack;
    private int expectedModCount = modCount;
    private boolean okToRemove = false;

    public MyTreeSetIterator() {
      stack = new Stack<>();
      pushLeftMost(root);
    }

    public boolean hasNext() {
      return !stack.isEmpty();
    }

    public AnyType next() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!hasNext()) {
        throw new java.util.NoSuchElementException();
      }

      current = stack.pop();
      pushLeftMost(current.right);
      okToRemove = true;

      return current.element;
    }

    public void remove() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!okToRemove) {
        throw new IllegalStateException();
      }

      MyTreeSet.this.remove(current.element);
      expectedModCount++;
    }

    private void pushLeftMost(BinaryNode<AnyType> tree) {
      BinaryNode<AnyType> pointer = tree;
      while (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      }
    }
  }

  private class StackElement<AnyType> {
    Tag tag;
    BinaryNode<AnyType> node;

    StackElement(BinaryNode<AnyType> n, Tag t) {
      node = n;
      tag = t;
    }
  }
  enum Tag{LEFT, RIGHT};
}

class UnderFlowException extends Exception {}

import java.io.File;

/**
 * Created by Administrator on 2016/4/24.
 */
public class FileList {
  private void list(File file) {
    list(file, 0);
  }

  private void list(File file, int depth) {
    printName(file, depth);
    if (file.isDirectory()) {
      File[] files = file.listFiles();
      for (File f : files) {
        list(f, depth + 1);
      }
    }
  }

  private void printName(File file, int depth) {
    String name = file.getName();
    for (int i = 0; i < depth; i++) {
      System.out.print("   ");
    }
    if (file.isDirectory()) {
      System.out.println("Dir:" + name);
    } else {
      System.out.println(file.getName() + " " + file.length());
    }
  }

  public static void main(String[] args) {
    FileList fileList = new FileList();
    File file = new File("E:\\书籍");
    fileList.list(file);
  }
}

public class A<AnyType extends Comparable> {
  private AnyType[] arr = null;
  
  public A() {
    arr = (AnyType[])new Comparable[10];
  }
}

  private long pow(int x, int n) {
    if (n == 1) {
      return x;
    }
    if (n % 2 == 0) {
      return pow(x * x, n / 2);
    } else {
      return x * pow(x * x, (n - 1) / 2);
    }
  }

x = a + b;
if ((x^a) < 0 && (x^b) < 0)
{
    //overflow, do something
}

  /**
   * 求两个数的最大公约数
   * @param m
   * @param n
   * @return
   */
  private int gcd(int m, int n) {
    if (m == n) {
      return m;
    }
    if (m < n) {
      m ^= n;
      n ^= m;
      m ^= n;
    }
    if (isEven(m) && isEven(n)) {
      return 2 * gcd(m >> 1, n >> 1);
    } else if (isEven(m) && isOdd(n)) {
      return gcd(m >> 1, n);
    } else if (isOdd(m) && isEven(n)) {
      return gcd(m, n >> 1);
    } else {
      return gcd((m + n) >> 1, (m - n) >> 1);
    }
  }

  private boolean isEven(int m) {
    return m % 2 == 0;
  }

  private boolean isOdd(int m) {
    return m % 2 == 1;
  }

  /**
   * 求两个数的最大公约数
   * @param m
   * @param n
   * @return
   */
  private int gcd(int m, int n) {
    if (m < n) {
      m = m ^ n;
      n = n ^ m;
      m = m ^ n;
    }
    int r = 0;
    while ((r = m % n) != 0) {
      m = n;
      n = r;
    }
    return n;
  }

  /**
   * 查找数组中下标与元素值相同的元素的索引，没找到则返回-1
   * @param arr 需要查找的数组
   * @return 查找到的数组的索引
   */
  private int find(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (i <= j) {
      int mid = (i + j) / 2;
      if (arr[mid] == mid) {
        return mid;
      }
      if (arr[mid] > mid) {
        j = mid - 1;
      } else {
        i = mid + 1;
      }
    }
    return -1;
  }

  /**
   * 计算函数式f(x) = a[n]x^n + a[n-1]x^(n-1) + a[n-2]x^(n-2) + ...+ a[0]算法，
   * 这里params数组中保存的是函数式的参数，顺序为从左到右，函数最高幂次为params.length - 1
   * @param params 参数数组
   * @param x 计算的变量
   * @return 计算结果
   */
  private double compute(double[] params, double x) {
    double poly = 0;
    for (int i = 0; i < params.length; i++) {
      poly = x * poly + params[i];
    }
    return poly;
  }