Package com.google.gson.internal
Class LinkedHashTreeMap<K,V>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.gson.internal.LinkedHashTreeMap<K,V>
-
- All Implemented Interfaces:
java.io.Serializable
,java.util.Map<K,V>
public final class LinkedHashTreeMap<K,V> extends java.util.AbstractMap<K,V> implements java.io.Serializable
A map of comparable keys to values. UnlikeTreeMap
, 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.
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
LinkedHashTreeMap.AvlBuilder<K,V>
Builds AVL trees of a predetermined size by accepting nodes of increasing value.(package private) static class
LinkedHashTreeMap.AvlIterator<K,V>
Walks an AVL tree in iteration order.(package private) class
LinkedHashTreeMap.EntrySet
(package private) class
LinkedHashTreeMap.KeySet
private class
LinkedHashTreeMap.LinkedTreeMapIterator<T>
(package private) static class
LinkedHashTreeMap.Node<K,V>
-
Field Summary
Fields Modifier and Type Field Description (package private) java.util.Comparator<? super K>
comparator
private LinkedHashTreeMap.EntrySet
entrySet
(package private) LinkedHashTreeMap.Node<K,V>
header
private LinkedHashTreeMap.KeySet
keySet
(package private) int
modCount
private static java.util.Comparator<java.lang.Comparable>
NATURAL_ORDER
(package private) int
size
(package private) LinkedHashTreeMap.Node<K,V>[]
table
(package private) int
threshold
-
Constructor Summary
Constructors Constructor Description LinkedHashTreeMap()
Create a natural order, empty tree map whose keys must be mutually comparable and non-null.LinkedHashTreeMap(java.util.Comparator<? super K> comparator)
Create a tree map ordered bycomparator
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
boolean
containsKey(java.lang.Object key)
private void
doubleCapacity()
(package private) static <K,V>
LinkedHashTreeMap.Node<K,V>[]doubleCapacity(LinkedHashTreeMap.Node<K,V>[] oldTable)
Returns a new array containing the same nodes asoldTable
, but with twice as many trees, each of (approximately) half the previous size.java.util.Set<java.util.Map.Entry<K,V>>
entrySet()
private boolean
equal(java.lang.Object a, java.lang.Object b)
(package private) LinkedHashTreeMap.Node<K,V>
find(K key, boolean create)
Returns the node at or adjacent to the given key, creating it if requested.(package private) LinkedHashTreeMap.Node<K,V>
findByEntry(java.util.Map.Entry<?,?> entry)
Returns this map's entry that has the same key and value asentry
, or null if this map has no such entry.(package private) LinkedHashTreeMap.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(LinkedHashTreeMap.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(LinkedHashTreeMap.Node<K,V> node, boolean unlink)
Removesnode
from this tree, rearranging the tree's structure as necessary.(package private) LinkedHashTreeMap.Node<K,V>
removeInternalByKey(java.lang.Object key)
private void
replaceInParent(LinkedHashTreeMap.Node<K,V> node, LinkedHashTreeMap.Node<K,V> replacement)
private void
rotateLeft(LinkedHashTreeMap.Node<K,V> root)
Rotates the subtree so that its root's right child is the new root.private void
rotateRight(LinkedHashTreeMap.Node<K,V> root)
Rotates the subtree so that its root's left child is the new root.private static int
secondaryHash(int h)
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.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
-
-
-
-
Field Detail
-
NATURAL_ORDER
private static final java.util.Comparator<java.lang.Comparable> NATURAL_ORDER
-
comparator
java.util.Comparator<? super K> comparator
-
table
LinkedHashTreeMap.Node<K,V>[] table
-
header
final LinkedHashTreeMap.Node<K,V> header
-
size
int size
-
modCount
int modCount
-
threshold
int threshold
-
entrySet
private LinkedHashTreeMap.EntrySet entrySet
-
keySet
private LinkedHashTreeMap.KeySet keySet
-
-
Constructor Detail
-
LinkedHashTreeMap
public LinkedHashTreeMap()
Create a natural order, empty tree map whose keys must be mutually comparable and non-null.
-
LinkedHashTreeMap
public LinkedHashTreeMap(java.util.Comparator<? super K> comparator)
Create a tree map ordered bycomparator
. This map's keys may only be null ifcomparator
permits.- Parameters:
comparator
- the comparator to order elements with, ornull
to use the natural ordering.
-
-
Method Detail
-
size
public int size()
-
get
public V get(java.lang.Object key)
-
containsKey
public boolean containsKey(java.lang.Object key)
-
clear
public void clear()
-
remove
public V remove(java.lang.Object key)
-
find
LinkedHashTreeMap.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
- ifkey
and the tree's keys aren't mutually comparable.
-
findByObject
LinkedHashTreeMap.Node<K,V> findByObject(java.lang.Object key)
-
findByEntry
LinkedHashTreeMap.Node<K,V> findByEntry(java.util.Map.Entry<?,?> entry)
Returns this map's entry that has the same key and value asentry
, 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 asString.CASE_INSENSITIVE_ORDER
), thenremove()
andcontains()
will violate the collections API.
-
equal
private boolean equal(java.lang.Object a, java.lang.Object b)
-
secondaryHash
private static int secondaryHash(int h)
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.
-
removeInternal
void removeInternal(LinkedHashTreeMap.Node<K,V> node, boolean unlink)
Removesnode
from this tree, rearranging the tree's structure as necessary.- Parameters:
unlink
- true to also unlink this node from the iteration linked list.
-
removeInternalByKey
LinkedHashTreeMap.Node<K,V> removeInternalByKey(java.lang.Object key)
-
replaceInParent
private void replaceInParent(LinkedHashTreeMap.Node<K,V> node, LinkedHashTreeMap.Node<K,V> replacement)
-
rebalance
private void rebalance(LinkedHashTreeMap.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(LinkedHashTreeMap.Node<K,V> root)
Rotates the subtree so that its root's right child is the new root.
-
rotateRight
private void rotateRight(LinkedHashTreeMap.Node<K,V> root)
Rotates the subtree so that its root's left child is the new root.
-
keySet
public java.util.Set<K> keySet()
-
doubleCapacity
private void doubleCapacity()
-
doubleCapacity
static <K,V> LinkedHashTreeMap.Node<K,V>[] doubleCapacity(LinkedHashTreeMap.Node<K,V>[] oldTable)
Returns a new array containing the same nodes asoldTable
, but with twice as many trees, each of (approximately) half the previous size.
-
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
-
-