Class LinkedTreeMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>

    public final class LinkedTreeMap<K,​V>
    extends java.util.AbstractMap<K,​V>
    implements java.io.Serializable
    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 class.

    See Also:
    Serialized Form
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) class  LinkedTreeMap.EntrySet  
      (package private) class  LinkedTreeMap.KeySet  
      private class  LinkedTreeMap.LinkedTreeMapIterator<T>  
      (package private) static class  LinkedTreeMap.Node<K,​V>  
      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Constructor Summary

      Constructors 
      Constructor Description
      LinkedTreeMap()
      Create a natural order, empty tree map whose keys must be mutually comparable and non-null, and whose values can be null.
      LinkedTreeMap​(boolean allowNullValues)
      Create a natural order, empty tree map whose keys must be mutually comparable and non-null.
      LinkedTreeMap​(java.util.Comparator<? super K> comparator, boolean allowNullValues)
      Create a tree map ordered by comparator.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()  
      boolean containsKey​(java.lang.Object key)  
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()  
      private boolean equal​(java.lang.Object a, java.lang.Object b)  
      (package private) LinkedTreeMap.Node<K,​V> find​(K key, boolean create)
      Returns the node at or adjacent to the given key, creating it if requested.
      (package private) LinkedTreeMap.Node<K,​V> findByEntry​(java.util.Map.Entry<?,​?> entry)
      Returns this map's entry that has the same key and value as entry, or null if this map has no such entry.
      (package private) LinkedTreeMap.Node<K,​V> findByObject​(java.lang.Object key)  
      V get​(java.lang.Object key)  
      java.util.Set<K> keySet()  
      V put​(K key, V value)  
      private void readObject​(java.io.ObjectInputStream in)  
      private void rebalance​(LinkedTreeMap.Node<K,​V> unbalanced, boolean insert)
      Rebalances the tree by making any AVL rotations necessary between the newly-unbalanced node and the tree's root.
      V remove​(java.lang.Object key)  
      (package private) void removeInternal​(LinkedTreeMap.Node<K,​V> node, boolean unlink)
      Removes node from this tree, rearranging the tree's structure as necessary.
      (package private) LinkedTreeMap.Node<K,​V> removeInternalByKey​(java.lang.Object key)  
      private void replaceInParent​(LinkedTreeMap.Node<K,​V> node, LinkedTreeMap.Node<K,​V> replacement)  
      private void rotateLeft​(LinkedTreeMap.Node<K,​V> root)
      Rotates the subtree so that its root's right child is the new root.
      private void rotateRight​(LinkedTreeMap.Node<K,​V> root)
      Rotates the subtree so that its root's left child is the new root.
      int size()  
      private java.lang.Object writeReplace()
      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.
      • Methods inherited from class java.util.AbstractMap

        clone, containsValue, equals, hashCode, isEmpty, putAll, toString, values
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
    • Constructor Detail

      • LinkedTreeMap

        public LinkedTreeMap()
        Create a natural order, empty tree map whose keys must be mutually comparable and non-null, and whose values can be null.
      • LinkedTreeMap

        public LinkedTreeMap​(boolean allowNullValues)
        Create a natural order, empty tree map whose keys must be mutually comparable and non-null.
        Parameters:
        allowNullValues - whether null is allowed as entry value
      • LinkedTreeMap

        public LinkedTreeMap​(java.util.Comparator<? super K> comparator,
                             boolean allowNullValues)
        Create a tree map ordered by comparator. This map's keys may only be null if comparator permits.
        Parameters:
        comparator - the comparator to order elements with, or null to use the natural ordering.
        allowNullValues - whether null is allowed as entry value
    • Method Detail

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>
      • put

        public V put​(K key,
                     V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>
      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
      • find

        LinkedTreeMap.Node<K,​V> find​(K key,
                                           boolean create)
        Returns the node at or adjacent to the given key, creating it if requested.
        Throws:
        java.lang.ClassCastException - if key and the tree's keys aren't mutually comparable.
      • findByEntry

        LinkedTreeMap.Node<K,​V> findByEntry​(java.util.Map.Entry<?,​?> entry)
        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.

      • equal

        private boolean equal​(java.lang.Object a,
                              java.lang.Object b)
      • removeInternal

        void removeInternal​(LinkedTreeMap.Node<K,​V> node,
                            boolean unlink)
        Removes node from this tree, rearranging the tree's structure as necessary.
        Parameters:
        unlink - true to also unlink this node from the iteration linked list.
      • rebalance

        private void rebalance​(LinkedTreeMap.Node<K,​V> unbalanced,
                               boolean insert)
        Rebalances the tree by making any AVL rotations necessary between the newly-unbalanced node and the tree's root.
        Parameters:
        insert - true if the node was unbalanced by an insert; false if it was by a removal.
      • rotateLeft

        private void rotateLeft​(LinkedTreeMap.Node<K,​V> root)
        Rotates the subtree so that its root's right child is the new root.
      • rotateRight

        private void rotateRight​(LinkedTreeMap.Node<K,​V> root)
        Rotates the subtree so that its root's left child is the new root.
      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>
      • keySet

        public java.util.Set<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
      • writeReplace

        private java.lang.Object writeReplace()
                                       throws java.io.ObjectStreamException
        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.
        Throws:
        java.io.ObjectStreamException
      • readObject

        private void readObject​(java.io.ObjectInputStream in)
                         throws java.io.IOException
        Throws:
        java.io.IOException