private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)

      newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

      newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

  }

 private static class Node<E> {

    E item;

    Node<E> next;

    Node<E> prev;

 

    Node(Node<E> prev, E element, Node<E> next) {

      this.item = element;

      this.next = next;

      this.prev = prev;

    }

  }

/**

   * Pointer to first node.

   * Invariant: (first == null && last == null) ||

   *      (first.prev == null && first.item != null)

   */

  transient Node<E> first;

 

  /**

   * Pointer to last node.

   * Invariant: (first == null && last == null) ||

   *      (last.next == null && last.item != null)

   */

  transient Node<E> last;

/**

   * Links e as last element.

   */

  void linkLast(E e) {

    final Node<E> l = last;

    final Node<E> newNode = new Node<>(l, e, null);

    last = newNode;

    if (l == null)

      first = newNode;

    else

      l.next = newNode;

    size++;

    modCount++;

  }

public V put(K key, V value) {

    Entry<K,V> t = root;

    if (t == null) {

      compare(key, key); // type (and possibly null) check

 

      root = new Entry<>(key, value, null);

      size = 1;

      modCount++;

      return null;

    }

    int cmp;

    Entry<K,V> parent;

    // split comparator and comparable paths

    Comparator<? super K> cpr = comparator;

    if (cpr != null) {

      do {

        parent = t;

        cmp = cpr.compare(key, t.key);

        if (cmp < 0)

          t = t.left;

        else if (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    else {

      if (key == null)

        throw new NullPointerException();

      @SuppressWarnings("unchecked")

        Comparable<? super K> k = (Comparable<? super K>) key;

      do {

        parent = t;

        cmp = k.compareTo(t.key);

        if (cmp < 0)

          t = t.left;

        else if (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    Entry<K,V> e = new Entry<>(key, value, parent);

    if (cmp < 0)

      parent.left = e;

    else

      parent.right = e;

    fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

  }

public boolean add(E e) {

    return map.put(e, PRESENT)==null;

  }

private transient HashMap<E,Object> map;

public TreeSet() {

    this(new TreeMap<E,Object>());

  }

public boolean add(E e) {

    return m.put(e, PRESENT)==null;

  }