Package com.google.gson.internal
Class LinkedTreeMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
com.google.gson.internal.LinkedTreeMap<K,V>
- All Implemented Interfaces:
Serializable
,Map<K,
V>
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
(package private) final class
private class
(package private) static final class
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final boolean
private final Comparator
<? super K> private LinkedTreeMap<K,
V>.EntrySet (package private) final LinkedTreeMap.Node
<K, V> private LinkedTreeMap<K,
V>.KeySet (package private) int
private static final Comparator
<Comparable> (package private) LinkedTreeMap.Node
<K, V> (package private) int
-
Constructor Summary
ConstructorsConstructorDescriptionCreate 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
(Comparator<? super K> comparator, boolean allowNullValues) Create a tree map ordered bycomparator
. -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
boolean
containsKey
(Object key) entrySet()
private static boolean
(package private) LinkedTreeMap.Node
<K, V> Returns the node at or adjacent to the given key, creating it if requested.(package private) LinkedTreeMap.Node
<K, V> findByEntry
(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
(Object key) keySet()
private void
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.(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> 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 Object
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
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
NATURAL_ORDER
-
comparator
-
allowNullValues
private final boolean allowNullValues -
root
LinkedTreeMap.Node<K,V> root -
size
int size -
modCount
int modCount -
header
-
entrySet
-
keySet
-
-
Constructor Details
-
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
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 Details
-
size
public int size() -
get
-
containsKey
- Specified by:
containsKey
in interfaceMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V>
-
put
-
clear
public void clear() -
remove
-
find
Returns the node at or adjacent to the given key, creating it if requested.- Throws:
ClassCastException
- ifkey
and the tree's keys aren't mutually comparable.
-
findByObject
-
findByEntry
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
-
removeInternal
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
-
replaceInParent
-
rebalance
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
Rotates the subtree so that its root's right child is the new root. -
rotateRight
Rotates the subtree so that its root's left child is the new root. -
entrySet
-
keySet
-
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. Using serialization defeats our DoS defence, so most apps shouldn't use it.- Throws:
ObjectStreamException
-
readObject
- Throws:
IOException
-