- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.gson.internal.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. 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 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>
-
Field Summary
Fields Modifier and Type Field Description private boolean
allowNullValues
private java.util.Comparator<? super K>
comparator
private LinkedTreeMap.EntrySet
entrySet
(package private) LinkedTreeMap.Node<K,V>
header
private LinkedTreeMap.KeySet
keySet
(package private) int
modCount
private static java.util.Comparator<java.lang.Comparable>
NATURAL_ORDER
(package private) LinkedTreeMap.Node<K,V>
root
(package private) int
size
-
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 benull
.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 bycomparator
.
-
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 asentry
, 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)
Removesnode
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
-
-
-
-
Field Detail
-
NATURAL_ORDER
private static final java.util.Comparator<java.lang.Comparable> NATURAL_ORDER
-
comparator
private final java.util.Comparator<? super K> comparator
-
allowNullValues
private final boolean allowNullValues
-
root
LinkedTreeMap.Node<K,V> root
-
size
int size
-
modCount
int modCount
-
header
final LinkedTreeMap.Node<K,V> header
-
entrySet
private LinkedTreeMap.EntrySet entrySet
-
keySet
private LinkedTreeMap.KeySet keySet
-
-
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 benull
.
-
LinkedTreeMap
public LinkedTreeMap(boolean allowNullValues)
Create a natural order, empty tree map whose keys must be mutually comparable and non-null.- Parameters:
allowNullValues
- whethernull
is allowed as entry value
-
LinkedTreeMap
public LinkedTreeMap(java.util.Comparator<? super K> comparator, boolean allowNullValues)
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.allowNullValues
- whethernull
is allowed as entry value
-
-
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
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
- ifkey
and the tree's keys aren't mutually comparable.
-
findByObject
LinkedTreeMap.Node<K,V> findByObject(java.lang.Object key)
-
findByEntry
LinkedTreeMap.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)
-
removeInternal
void removeInternal(LinkedTreeMap.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
LinkedTreeMap.Node<K,V> removeInternalByKey(java.lang.Object key)
-
replaceInParent
private void replaceInParent(LinkedTreeMap.Node<K,V> node, LinkedTreeMap.Node<K,V> replacement)
-
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.
-
keySet
public java.util.Set<K> keySet()
-
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
-
-