public final class LinkedHashTreeMap<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 and LinkedHashMap classes.
Modifier and Type | Class and 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> |
Modifier and Type | Field and 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 and 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 by
comparator . |
Modifier and Type | Method and 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 as
oldTable , 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 as
entry , 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 |
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)
Removes
node 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.
|
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
LinkedHashTreeMap.Node<K,V>[] table
final LinkedHashTreeMap.Node<K,V> header
int size
int modCount
int threshold
private LinkedHashTreeMap.EntrySet entrySet
private LinkedHashTreeMap.KeySet keySet
public LinkedHashTreeMap()
public LinkedHashTreeMap(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)
LinkedHashTreeMap.Node<K,V> find(K key, boolean create)
java.lang.ClassCastException
- if key
and the tree's keys aren't
mutually comparable.LinkedHashTreeMap.Node<K,V> findByObject(java.lang.Object key)
LinkedHashTreeMap.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)
private static int secondaryHash(int h)
void removeInternal(LinkedHashTreeMap.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.LinkedHashTreeMap.Node<K,V> removeInternalByKey(java.lang.Object key)
private void replaceInParent(LinkedHashTreeMap.Node<K,V> node, LinkedHashTreeMap.Node<K,V> replacement)
private void rebalance(LinkedHashTreeMap.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(LinkedHashTreeMap.Node<K,V> root)
private void rotateRight(LinkedHashTreeMap.Node<K,V> root)
public java.util.Set<K> keySet()
private void doubleCapacity()
static <K,V> LinkedHashTreeMap.Node<K,V>[] doubleCapacity(LinkedHashTreeMap.Node<K,V>[] oldTable)
oldTable
, but with
twice as many trees, each of (approximately) half the previous size.private java.lang.Object writeReplace() throws java.io.ObjectStreamException
java.io.ObjectStreamException