/*
 * Copyright (C) 2010 The Android Open Source Project
 * Copyright (C) 2012 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.gson.internal;

import java.io.ObjectStreamException;
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.NoSuchElementException;
import java.util.Set;

A map of comparable keys to values. Unlike TreeMap, this class uses insertion order for iteration order. Comparison order is only used as an optimization for efficient insertion and removal. 
This implementation was derived from Android 4.1's TreeMap and
LinkedHashMap classes.
/**
 * A map of comparable keys to values. Unlike {@code TreeMap}, this class uses
 * insertion order for iteration order. Comparison order is only used as an
 * optimization for efficient insertion and removal.
 *
 * <p>This implementation was derived from Android 4.1's TreeMap and
 * LinkedHashMap classes.
 */
public final class LinkedHashTreeMap<K, V> extends AbstractMap<K, V> implements Serializable {
  @SuppressWarnings({ "unchecked", "rawtypes" }) // to avoid Comparable<Comparable<Comparable<...>>>
  private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() {
    public int compare(Comparable a, Comparable b) {
      return a.compareTo(b);
    }
  };

  Comparator<? super K> comparator;
  Node<K, V>[] table;
  final Node<K, V> header;
  int size = 0;
  int modCount = 0;
  int threshold;

  
Create a natural order, empty tree map whose keys must be mutually
comparable and non-null.
/**
   * Create a natural order, empty tree map whose keys must be mutually
   * comparable and non-null.
   */
  @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable
  public LinkedHashTreeMap() {
    this((Comparator<? super K>) NATURAL_ORDER);
  }

  
Create a tree map ordered by comparator. This map's keys may only be null if comparator permits. 
Params:
comparator – the comparator to order elements with, or null to use the natural ordering./**
   * Create a tree map ordered by {@code comparator}. This map's keys may only
   * be null if {@code comparator} permits.
   *
   * @param comparator the comparator to order elements with, or {@code null} to
   *     use the natural ordering.
   */
  @SuppressWarnings({ "unchecked", "rawtypes" }) // unsafe! if comparator is null, this assumes K is comparable
  public LinkedHashTreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator != null
        ? comparator
        : (Comparator) NATURAL_ORDER;
    this.header = new Node<K, V>();
    this.table = new Node[16]; // TODO: sizing/resizing policies
    this.threshold = (table.length / 2) + (table.length / 4); // 3/4 capacity
  }

  @Override public int size() {
    return size;
  }

  @Override public V get(Object key) {
    Node<K, V> node = findByObject(key);
    return node != null ? node.value : null;
  }

  @Override public boolean containsKey(Object key) {
    return findByObject(key) != null;
  }

  @Override public V put(K key, V value) {
    if (key == null) {
      throw new NullPointerException("key == null");
    }
    Node<K, V> created = find(key, true);
    V result = created.value;
    created.value = value;
    return result;
  }

  @Override public void clear() {
    Arrays.fill(table, null);
    size = 0;
    modCount++;

    // Clear all links to help GC
    Node<K, V> header = this.header;
    for (Node<K, V> e = header.next; e != header; ) {
      Node<K, V> next = e.next;
      e.next = e.prev = null;
      e = next;
    }

    header.next = header.prev = header;
  }

  @Override public V remove(Object key) {
    Node<K, V> node = removeInternalByKey(key);
    return node != null ? node.value : null;
  }

  
Returns the node at or adjacent to the given key, creating it if requested.
Throws:
ClassCastException – if key and the tree's keys aren't mutually comparable./**
   * Returns the node at or adjacent to the given key, creating it if requested.
   *
   * @throws ClassCastException if {@code key} and the tree's keys aren't
   *     mutually comparable.
   */
  Node<K, V> find(K key, boolean create) {
    Comparator<? super K> comparator = this.comparator;
    Node<K, V>[] table = this.table;
    int hash = secondaryHash(key.hashCode());
    int index = hash & (table.length - 1);
    Node<K, V> nearest = table[index];
    int comparison = 0;

    if (nearest != null) {
      // Micro-optimization: avoid polymorphic calls to Comparator.compare().
      @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble.
      Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
          ? (Comparable<Object>) key
          : null;

      while (true) {
        comparison = (comparableKey != null)
            ? comparableKey.compareTo(nearest.key)
            : comparator.compare(key, nearest.key);

        // We found the requested key.
        if (comparison == 0) {
          return nearest;
        }

        // If it exists, the key is in a subtree. Go deeper.
        Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
        if (child == null) {
          break;
        }

        nearest = child;
      }
    }

    // The key doesn't exist in this tree.
    if (!create) {
      return null;
    }

    // Create the node and add it to the tree or the table.
    Node<K, V> header = this.header;
    Node<K, V> created;
    if (nearest == null) {
      // Check that the value is comparable if we didn't do any comparisons.
      if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
        throw new ClassCastException(key.getClass().getName() + " is not Comparable");
      }
      created = new Node<K, V>(nearest, key, hash, header, header.prev);
      table[index] = created;
    } else {
      created = new Node<K, V>(nearest, key, hash, header, header.prev);
      if (comparison < 0) { // nearest.key is higher
        nearest.left = created;
      } else { // comparison > 0, nearest.key is lower
        nearest.right = created;
      }
      rebalance(nearest, true);
    }

    if (size++ > threshold) {
      doubleCapacity();
    }
    modCount++;

    return created;
  }

  @SuppressWarnings("unchecked")
  Node<K, V> findByObject(Object key) {
    try {
      return key != null ? find((K) key, false) : null;
    } catch (ClassCastException e) {
      return null;
    }
  }

  
Returns this map's entry that has the same key and value as 
entry, or null if this map has no such entry. 
This method uses the comparator for key equality rather than 
equals. If this map's comparator isn't consistent with equals (such as String.CASE_INSENSITIVE_ORDER), then remove() and 
contains() will violate the collections API. /**
   * Returns this map's entry that has the same key and value as {@code
   * entry}, or null if this map has no such entry.
   *
   * <p>This method uses the comparator for key equality rather than {@code
   * equals}. If this map's comparator isn't consistent with equals (such as
   * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code
   * contains()} will violate the collections API.
   */
  Node<K, V> findByEntry(Entry<?, ?> entry) {
    Node<K, V> mine = findByObject(entry.getKey());
    boolean valuesEqual = mine != null && equal(mine.value, entry.getValue());
    return valuesEqual ? mine : null;
  }

  private boolean equal(Object a, Object b) {
    return a == b || (a != null && a.equals(b));
  }

  
Applies a supplemental hash function to a given hashCode, which defends
against poor quality hash functions. This is critical because HashMap
uses power-of-two length hash tables, that otherwise encounter collisions
for hashCodes that do not differ in lower or upper bits.
/**
   * Applies a supplemental hash function to a given hashCode, which defends
   * against poor quality hash functions. This is critical because HashMap
   * uses power-of-two length hash tables, that otherwise encounter collisions
   * for hashCodes that do not differ in lower or upper bits.
   */
  private static int secondaryHash(int h) {
    // Doug Lea's supplemental hash function
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
  }

  
Removes node from this tree, rearranging the tree's structure as necessary. 
Params:
unlink – true to also unlink this node from the iteration linked list./**
   * Removes {@code node} from this tree, rearranging the tree's structure as
   * necessary.
   *
   * @param unlink true to also unlink this node from the iteration linked list.
   */
  void removeInternal(Node<K, V> node, boolean unlink) {
    if (unlink) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      node.next = node.prev = null; // Help the GC (for performance)
    }

    Node<K, V> left = node.left;
    Node<K, V> right = node.right;
    Node<K, V> originalParent = node.parent;
    if (left != null && right != null) {

      /*
       * To remove a node with both left and right subtrees, move an
       * adjacent node from one of those subtrees into this node's place.
       *
       * Removing the adjacent node may change this node's subtrees. This
       * node may no longer have two subtrees once the adjacent node is
       * gone!
       */

      Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first();
      removeInternal(adjacent, false); // takes care of rebalance and size--

      int leftHeight = 0;
      left = node.left;
      if (left != null) {
        leftHeight = left.height;
        adjacent.left = left;
        left.parent = adjacent;
        node.left = null;
      }
      int rightHeight = 0;
      right = node.right;
      if (right != null) {
        rightHeight = right.height;
        adjacent.right = right;
        right.parent = adjacent;
        node.right = null;
      }
      adjacent.height = Math.max(leftHeight, rightHeight) + 1;
      replaceInParent(node, adjacent);
      return;
    } else if (left != null) {
      replaceInParent(node, left);
      node.left = null;
    } else if (right != null) {
      replaceInParent(node, right);
      node.right = null;
    } else {
      replaceInParent(node, null);
    }

    rebalance(originalParent, false);
    size--;
    modCount++;
  }

  Node<K, V> removeInternalByKey(Object key) {
    Node<K, V> node = findByObject(key);
    if (node != null) {
      removeInternal(node, true);
    }
    return node;
  }

  private void replaceInParent(Node<K, V> node, Node<K, V> replacement) {
    Node<K, V> parent = node.parent;
    node.parent = null;
    if (replacement != null) {
      replacement.parent = parent;
    }

    if (parent != null) {
      if (parent.left == node) {
        parent.left = replacement;
      } else {
        assert (parent.right == node);
        parent.right = replacement;
      }
    } else {
      int index = node.hash & (table.length - 1);
      table[index] = replacement;
    }
  }

  
Rebalances the tree by making any AVL rotations necessary between the
newly-unbalanced node and the tree's root.
Params:
insert – true if the node was unbalanced by an insert; false if it
    was by a removal./**
   * Rebalances the tree by making any AVL rotations necessary between the
   * newly-unbalanced node and the tree's root.
   *
   * @param insert true if the node was unbalanced by an insert; false if it
   *     was by a removal.
   */
  private void rebalance(Node<K, V> unbalanced, boolean insert) {
    for (Node<K, V> node = unbalanced; node != null; node = node.parent) {
      Node<K, V> left = node.left;
      Node<K, V> right = node.right;
      int leftHeight = left != null ? left.height : 0;
      int rightHeight = right != null ? right.height : 0;

      int delta = leftHeight - rightHeight;
      if (delta == -2) {
        Node<K, V> rightLeft = right.left;
        Node<K, V> rightRight = right.right;
        int rightRightHeight = rightRight != null ? rightRight.height : 0;
        int rightLeftHeight = rightLeft != null ? rightLeft.height : 0;

        int rightDelta = rightLeftHeight - rightRightHeight;
        if (rightDelta == -1 || (rightDelta == 0 && !insert)) {
          rotateLeft(node); // AVL right right
        } else {
          assert (rightDelta == 1);
          rotateRight(right); // AVL right left
          rotateLeft(node);
        }
        if (insert) {
          break; // no further rotations will be necessary
        }

      } else if (delta == 2) {
        Node<K, V> leftLeft = left.left;
        Node<K, V> leftRight = left.right;
        int leftRightHeight = leftRight != null ? leftRight.height : 0;
        int leftLeftHeight = leftLeft != null ? leftLeft.height : 0;

        int leftDelta = leftLeftHeight - leftRightHeight;
        if (leftDelta == 1 || (leftDelta == 0 && !insert)) {
          rotateRight(node); // AVL left left
        } else {
          assert (leftDelta == -1);
          rotateLeft(left); // AVL left right
          rotateRight(node);
        }
        if (insert) {
          break; // no further rotations will be necessary
        }

      } else if (delta == 0) {
        node.height = leftHeight + 1; // leftHeight == rightHeight
        if (insert) {
          break; // the insert caused balance, so rebalancing is done!
        }

      } else {
        assert (delta == -1 || delta == 1);
        node.height = Math.max(leftHeight, rightHeight) + 1;
        if (!insert) {
          break; // the height hasn't changed, so rebalancing is done!
        }
      }
    }
  }

  
Rotates the subtree so that its root's right child is the new root.
/**
   * Rotates the subtree so that its root's right child is the new root.
   */
  private void rotateLeft(Node<K, V> root) {
    Node<K, V> left = root.left;
    Node<K, V> pivot = root.right;
    Node<K, V> pivotLeft = pivot.left;
    Node<K, V> pivotRight = pivot.right;

    // move the pivot's left child to the root's right
    root.right = pivotLeft;
    if (pivotLeft != null) {
      pivotLeft.parent = root;
    }

    replaceInParent(root, pivot);

    // move the root to the pivot's left
    pivot.left = root;
    root.parent = pivot;

    // fix heights
    root.height = Math.max(left != null ? left.height : 0,
        pivotLeft != null ? pivotLeft.height : 0) + 1;
    pivot.height = Math.max(root.height,
        pivotRight != null ? pivotRight.height : 0) + 1;
  }

  
Rotates the subtree so that its root's left child is the new root.
/**
   * Rotates the subtree so that its root's left child is the new root.
   */
  private void rotateRight(Node<K, V> root) {
    Node<K, V> pivot = root.left;
    Node<K, V> right = root.right;
    Node<K, V> pivotLeft = pivot.left;
    Node<K, V> pivotRight = pivot.right;

    // move the pivot's right child to the root's left
    root.left = pivotRight;
    if (pivotRight != null) {
      pivotRight.parent = root;
    }

    replaceInParent(root, pivot);

    // move the root to the pivot's right
    pivot.right = root;
    root.parent = pivot;

    // fixup heights
    root.height = Math.max(right != null ? right.height : 0,
        pivotRight != null ? pivotRight.height : 0) + 1;
    pivot.height = Math.max(root.height,
        pivotLeft != null ? pivotLeft.height : 0) + 1;
  }

  private EntrySet entrySet;
  private KeySet keySet;

  @Override public Set<Entry<K, V>> entrySet() {
    EntrySet result = entrySet;
    return result != null ? result : (entrySet = new EntrySet());
  }

  @Override public Set<K> keySet() {
    KeySet result = keySet;
    return result != null ? result : (keySet = new KeySet());
  }

  static final class Node<K, V> implements Entry<K, V> {
    Node<K, V> parent;
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> next;
    Node<K, V> prev;
    final K key;
    final int hash;
    V value;
    int height;

    
Create the header entry /** Create the header entry */
    Node() {
      key = null;
      hash = -1;
      next = prev = this;
    }

    
Create a regular entry /** Create a regular entry */
    Node(Node<K, V> parent, K key, int hash, Node<K, V> next, Node<K, V> prev) {
      this.parent = parent;
      this.key = key;
      this.hash = hash;
      this.height = 1;
      this.next = next;
      this.prev = prev;
      prev.next = this;
      next.prev = this;
    }

    public K getKey() {
      return key;
    }

    public V getValue() {
      return value;
    }

    public V setValue(V value) {
      V oldValue = this.value;
      this.value = value;
      return oldValue;
    }

    @SuppressWarnings("rawtypes")
    @Override public boolean equals(Object o) {
      if (o instanceof Entry) {
        Entry other = (Entry) o;
        return (key == null ? other.getKey() == null : key.equals(other.getKey()))
            && (value == null ? other.getValue() == null : value.equals(other.getValue()));
      }
      return false;
    }

    @Override public int hashCode() {
      return (key == null ? 0 : key.hashCode())
          ^ (value == null ? 0 : value.hashCode());
    }

    @Override public String toString() {
      return key + "=" + value;
    }

    
Returns the first node in this subtree.
/**
     * Returns the first node in this subtree.
     */
    public Node<K, V> first() {
      Node<K, V> node = this;
      Node<K, V> child = node.left;
      while (child != null) {
        node = child;
        child = node.left;
      }
      return node;
    }

    
Returns the last node in this subtree.
/**
     * Returns the last node in this subtree.
     */
    public Node<K, V> last() {
      Node<K, V> node = this;
      Node<K, V> child = node.right;
      while (child != null) {
        node = child;
        child = node.right;
      }
      return node;
    }
  }

  private void doubleCapacity() {
    table = doubleCapacity(table);
    threshold = (table.length / 2) + (table.length / 4); // 3/4 capacity
  }

  
Returns a new array containing the same nodes as oldTable, but with twice as many trees, each of (approximately) half the previous size. /**
   * Returns a new array containing the same nodes as {@code oldTable}, but with
   * twice as many trees, each of (approximately) half the previous size.
   */
  static <K, V> Node<K, V>[] doubleCapacity(Node<K, V>[] oldTable) {
    // TODO: don't do anything if we're already at MAX_CAPACITY
    int oldCapacity = oldTable.length;
    @SuppressWarnings("unchecked") // Arrays and generics don't get along.
    Node<K, V>[] newTable = new Node[oldCapacity * 2];
    AvlIterator<K, V> iterator = new AvlIterator<K, V>();
    AvlBuilder<K, V> leftBuilder = new AvlBuilder<K, V>();
    AvlBuilder<K, V> rightBuilder = new AvlBuilder<K, V>();

    // Split each tree into two trees.
    for (int i = 0; i < oldCapacity; i++) {
      Node<K, V> root = oldTable[i];
      if (root == null) {
        continue;
      }

      // Compute the sizes of the left and right trees.
      iterator.reset(root);
      int leftSize = 0;
      int rightSize = 0;
      for (Node<K, V> node; (node = iterator.next()) != null; ) {
        if ((node.hash & oldCapacity) == 0) {
          leftSize++;
        } else {
          rightSize++;
        }
      }

      // Split the tree into two.
      leftBuilder.reset(leftSize);
      rightBuilder.reset(rightSize);
      iterator.reset(root);
      for (Node<K, V> node; (node = iterator.next()) != null; ) {
        if ((node.hash & oldCapacity) == 0) {
          leftBuilder.add(node);
        } else {
          rightBuilder.add(node);
        }
      }

      // Populate the enlarged array with these new roots.
      newTable[i] = leftSize > 0 ? leftBuilder.root() : null;
      newTable[i + oldCapacity] = rightSize > 0 ? rightBuilder.root() : null;
    }
    return newTable;
  }

  
Walks an AVL tree in iteration order. Once a node has been returned, its
left, right and parent links are no longer used. For this
reason it is safe to transform these links as you walk a tree.
Warning: this iterator is destructive. It clears the
parent node of all nodes in the tree. It is an error to make a partial
iteration of a tree.
/**
   * Walks an AVL tree in iteration order. Once a node has been returned, its
   * left, right and parent links are <strong>no longer used</strong>. For this
   * reason it is safe to transform these links as you walk a tree.
   *
   * <p><strong>Warning:</strong> this iterator is destructive. It clears the
   * parent node of all nodes in the tree. It is an error to make a partial
   * iteration of a tree.
   */
  static class AvlIterator<K, V> {
    
This stack is a singly linked list, linked by the 'parent' field. /** This stack is a singly linked list, linked by the 'parent' field. */
    private Node<K, V> stackTop;

    void reset(Node<K, V> root) {
      Node<K, V> stackTop = null;
      for (Node<K, V> n = root; n != null; n = n.left) {
        n.parent = stackTop;
        stackTop = n; // Stack push.
      }
      this.stackTop = stackTop;
    }

    public Node<K, V> next() {
      Node<K, V> stackTop = this.stackTop;
      if (stackTop == null) {
        return null;
      }
      Node<K, V> result = stackTop;
      stackTop = result.parent;
      result.parent = null;
      for (Node<K, V> n = result.right; n != null; n = n.left) {
        n.parent = stackTop;
        stackTop = n; // Stack push.
      }
      this.stackTop = stackTop;
      return result;
    }
  }

  
Builds AVL trees of a predetermined size by accepting nodes of increasing
value. To use:

  
Call reset to initialize the target size size.
  
Call add size times with increasing values.
  
Call root to get the root of the balanced tree. 
The returned tree will satisfy the AVL constraint: for every node
N, the height of N.left and N.right is different by at
most 1. It accomplishes this by omitting deepest-level leaf nodes when
building trees whose size isn't a power of 2 minus 1.
Unlike rebuilding a tree from scratch, this approach requires no value
comparisons. Using this class to create a tree of size S is O(S). /**
   * Builds AVL trees of a predetermined size by accepting nodes of increasing
   * value. To use:
   * <ol>
   *   <li>Call {@link #reset} to initialize the target size <i>size</i>.
   *   <li>Call {@link #add} <i>size</i> times with increasing values.
   *   <li>Call {@link #root} to get the root of the balanced tree.
   * </ol>
   *
   * <p>The returned tree will satisfy the AVL constraint: for every node
   * <i>N</i>, the height of <i>N.left</i> and <i>N.right</i> is different by at
   * most 1. It accomplishes this by omitting deepest-level leaf nodes when
   * building trees whose size isn't a power of 2 minus 1.
   *
   * <p>Unlike rebuilding a tree from scratch, this approach requires no value
   * comparisons. Using this class to create a tree of size <i>S</i> is
   * {@code O(S)}.
   */
  final static class AvlBuilder<K, V> {
    
This stack is a singly linked list, linked by the 'parent' field. /** This stack is a singly linked list, linked by the 'parent' field. */
    private Node<K, V> stack;
    private int leavesToSkip;
    private int leavesSkipped;
    private int size;

    void reset(int targetSize) {
      // compute the target tree size. This is a power of 2 minus one, like 15 or 31.
      int treeCapacity = Integer.highestOneBit(targetSize) * 2 - 1;
      leavesToSkip = treeCapacity - targetSize;
      size = 0;
      leavesSkipped = 0;
      stack = null;
    }

    void add(Node<K, V> node) {
      node.left = node.parent = node.right = null;
      node.height = 1;

      // Skip a leaf if necessary.
      if (leavesToSkip > 0 && (size & 1) == 0) {
        size++;
        leavesToSkip--;
        leavesSkipped++;
      }

      node.parent = stack;
      stack = node; // Stack push.
      size++;

      // Skip a leaf if necessary.
      if (leavesToSkip > 0 && (size & 1) == 0) {
        size++;
        leavesToSkip--;
        leavesSkipped++;
      }

      /*
       * Combine 3 nodes into subtrees whenever the size is one less than a
       * multiple of 4. For example we combine the nodes A, B, C into a
       * 3-element tree with B as the root.
       *
       * Combine two subtrees and a spare single value whenever the size is one
       * less than a multiple of 8. For example at 8 we may combine subtrees
       * (A B C) and (E F G) with D as the root to form ((A B C) D (E F G)).
       *
       * Just as we combine single nodes when size nears a multiple of 4, and
       * 3-element trees when size nears a multiple of 8, we combine subtrees of
       * size (N-1) whenever the total size is 2N-1 whenever N is a power of 2.
       */
      for (int scale = 4; (size & scale - 1) == scale - 1; scale *= 2) {
        if (leavesSkipped == 0) {
          // Pop right, center and left, then make center the top of the stack.
          Node<K, V> right = stack;
          Node<K, V> center = right.parent;
          Node<K, V> left = center.parent;
          center.parent = left.parent;
          stack = center;
          // Construct a tree.
          center.left = left;
          center.right = right;
          center.height = right.height + 1;
          left.parent = center;
          right.parent = center;
        } else if (leavesSkipped == 1) {
          // Pop right and center, then make center the top of the stack.
          Node<K, V> right = stack;
          Node<K, V> center = right.parent;
          stack = center;
          // Construct a tree with no left child.
          center.right = right;
          center.height = right.height + 1;
          right.parent = center;
          leavesSkipped = 0;
        } else if (leavesSkipped == 2) {
          leavesSkipped = 0;
        }
      }
    }

    Node<K, V> root() {
      Node<K, V> stackTop = this.stack;
      if (stackTop.parent != null) {
        throw new IllegalStateException();
      }
      return stackTop;
    }
  }

  private abstract class LinkedTreeMapIterator<T> implements Iterator<T> {
    Node<K, V> next = header.next;
    Node<K, V> lastReturned = null;
    int expectedModCount = modCount;

    LinkedTreeMapIterator() {
    }

    public final boolean hasNext() {
      return next != header;
    }

    final Node<K, V> nextNode() {
      Node<K, V> e = next;
      if (e == header) {
        throw new NoSuchElementException();
      }
      if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }
      next = e.next;
      return lastReturned = e;
    }

    public final void remove() {
      if (lastReturned == null) {
        throw new IllegalStateException();
      }
      removeInternal(lastReturned, true);
      lastReturned = null;
      expectedModCount = modCount;
    }
  }

  final class EntrySet extends AbstractSet<Entry<K, V>> {
    @Override public int size() {
      return size;
    }

    @Override public Iterator<Entry<K, V>> iterator() {
      return new LinkedTreeMapIterator<Entry<K, V>>() {
        public Entry<K, V> next() {
          return nextNode();
        }
      };
    }

    @Override public boolean contains(Object o) {
      return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null;
    }

    @Override public boolean remove(Object o) {
      if (!(o instanceof Entry)) {
        return false;
      }

      Node<K, V> node = findByEntry((Entry<?, ?>) o);
      if (node == null) {
        return false;
      }
      removeInternal(node, true);
      return true;
    }

    @Override public void clear() {
      LinkedHashTreeMap.this.clear();
    }
  }

  final class KeySet extends AbstractSet<K> {
    @Override public int size() {
      return size;
    }

    @Override public Iterator<K> iterator() {
      return new LinkedTreeMapIterator<K>() {
        public K next() {
          return nextNode().key;
        }
      };
    }

    @Override public boolean contains(Object o) {
      return containsKey(o);
    }

    @Override public boolean remove(Object key) {
      return removeInternalByKey(key) != null;
    }

    @Override public void clear() {
      LinkedHashTreeMap.this.clear();
    }
  }

  
If somebody is unlucky enough to have to serialize one of these, serialize
it as a LinkedHashMap so that they won't need Gson on the other side to
deserialize it. Using serialization defeats our DoS defence, so most apps
shouldn't use it.
/**
   * If somebody is unlucky enough to have to serialize one of these, serialize
   * it as a LinkedHashMap so that they won't need Gson on the other side to
   * deserialize it. Using serialization defeats our DoS defence, so most apps
   * shouldn't use it.
   */
  private Object writeReplace() throws ObjectStreamException {
    return new LinkedHashMap<K, V>(this);
  }
}