public final class LinkedTreeMap<K,V>
extends java.util.AbstractMap<K,V>
implements java.io.Serializable
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.
Modifier and Type | Class and Description |
---|---|
(package private) class |
LinkedTreeMap.EntrySet |
(package private) class |
LinkedTreeMap.KeySet |
private class |
LinkedTreeMap.LinkedTreeMapIterator<T> |
(package private) static class |
LinkedTreeMap.Node<K,V> |
Modifier and Type | Field and Description |
---|---|
(package 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 and Description |
---|
LinkedTreeMap()
Create a natural order, empty tree map whose keys must be mutually
comparable and non-null.
|
LinkedTreeMap(java.util.Comparator<? super K> comparator)
Create a tree map ordered by
comparator . |
Modifier and Type | Method and 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 |
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.
|
clone, containsValue, equals, hashCode, isEmpty, putAll, toString, values
private static final java.util.Comparator<java.lang.Comparable> NATURAL_ORDER
java.util.Comparator<? super K> comparator
LinkedTreeMap.Node<K,V> root
int size
int modCount
final LinkedTreeMap.Node<K,V> header
private LinkedTreeMap.EntrySet entrySet
private LinkedTreeMap.KeySet keySet
public LinkedTreeMap()
public LinkedTreeMap(java.util.Comparator<? super K> comparator)
comparator
. This map's keys may only
be null if comparator
permits.comparator
- the comparator to order elements with, or null
to
use the natural ordering.public int size()
public V get(java.lang.Object key)
public boolean containsKey(java.lang.Object key)
public void clear()
public V remove(java.lang.Object key)
LinkedTreeMap.Node<K,V> find(K key, boolean create)
java.lang.ClassCastException
- if key
and the tree's keys aren't
mutually comparable.LinkedTreeMap.Node<K,V> findByObject(java.lang.Object key)
LinkedTreeMap.Node<K,V> findByEntry(java.util.Map.Entry<?,?> entry)
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.
private boolean equal(java.lang.Object a, java.lang.Object b)
void removeInternal(LinkedTreeMap.Node<K,V> node, boolean unlink)
node
from this tree, rearranging the tree's structure as
necessary.unlink
- true to also unlink this node from the iteration linked list.LinkedTreeMap.Node<K,V> removeInternalByKey(java.lang.Object key)
private void replaceInParent(LinkedTreeMap.Node<K,V> node, LinkedTreeMap.Node<K,V> replacement)
private void rebalance(LinkedTreeMap.Node<K,V> unbalanced, boolean insert)
insert
- true if the node was unbalanced by an insert; false if it
was by a removal.private void rotateLeft(LinkedTreeMap.Node<K,V> root)
private void rotateRight(LinkedTreeMap.Node<K,V> root)
public java.util.Set<K> keySet()
private java.lang.Object writeReplace() throws java.io.ObjectStreamException
java.io.ObjectStreamException