2 * Copyright (C) 2010 The Android Open Source Project
3 * Copyright (C) 2012 Google Inc.
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
18 package com
.google
.gson
.internal
;
20 import java
.io
.ObjectStreamException
;
21 import java
.io
.Serializable
;
22 import java
.util
.AbstractMap
;
23 import java
.util
.AbstractSet
;
24 import java
.util
.Comparator
;
25 import java
.util
.ConcurrentModificationException
;
26 import java
.util
.Iterator
;
27 import java
.util
.LinkedHashMap
;
28 import java
.util
.NoSuchElementException
;
32 * A map of comparable keys to values. Unlike {@code TreeMap}, this class uses
33 * insertion order for iteration order. Comparison order is only used as an
34 * optimization for efficient insertion and removal.
36 * <p>This implementation was derived from Android 4.1's TreeMap class.
38 public final class LinkedTreeMap
<K
, V
> extends AbstractMap
<K
, V
> implements Serializable
{
39 @SuppressWarnings({ "unchecked", "rawtypes" }) // to avoid Comparable<Comparable<Comparable<...>>>
40 private static final Comparator
<Comparable
> NATURAL_ORDER
= new Comparator
<Comparable
>() {
41 public int compare(Comparable a
, Comparable b
) {
42 return a
.compareTo(b
);
46 Comparator
<?
super K
> comparator
;
51 // Used to preserve iteration order
52 final Node
<K
, V
> header
= new Node
<K
, V
>();
55 * Create a natural order, empty tree map whose keys must be mutually
56 * comparable and non-null.
58 @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable
59 public LinkedTreeMap() {
60 this((Comparator
<?
super K
>) NATURAL_ORDER
);
64 * Create a tree map ordered by {@code comparator}. This map's keys may only
65 * be null if {@code comparator} permits.
67 * @param comparator the comparator to order elements with, or {@code null} to
68 * use the natural ordering.
70 @SuppressWarnings({ "unchecked", "rawtypes" }) // unsafe! if comparator is null, this assumes K is comparable
71 public LinkedTreeMap(Comparator
<?
super K
> comparator
) {
72 this.comparator
= comparator
!= null
74 : (Comparator
) NATURAL_ORDER
;
77 @Override public int size() {
81 @Override public V
get(Object key
) {
82 Node
<K
, V
> node
= findByObject(key
);
83 return node
!= null ? node
.value
: null;
86 @Override public boolean containsKey(Object key
) {
87 return findByObject(key
) != null;
90 @Override public V
put(K key
, V value
) {
92 throw new NullPointerException("key == null");
94 Node
<K
, V
> created
= find(key
, true);
95 V result
= created
.value
;
96 created
.value
= value
;
100 @Override public void clear() {
105 // Clear iteration order
106 Node
<K
, V
> header
= this.header
;
107 header
.next
= header
.prev
= header
;
110 @Override public V
remove(Object key
) {
111 Node
<K
, V
> node
= removeInternalByKey(key
);
112 return node
!= null ? node
.value
: null;
116 * Returns the node at or adjacent to the given key, creating it if requested.
118 * @throws ClassCastException if {@code key} and the tree's keys aren't
119 * mutually comparable.
121 Node
<K
, V
> find(K key
, boolean create
) {
122 Comparator
<?
super K
> comparator
= this.comparator
;
123 Node
<K
, V
> nearest
= root
;
126 if (nearest
!= null) {
127 // Micro-optimization: avoid polymorphic calls to Comparator.compare().
128 @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble.
129 Comparable
<Object
> comparableKey
= (comparator
== NATURAL_ORDER
)
130 ?
(Comparable
<Object
>) key
134 comparison
= (comparableKey
!= null)
135 ? comparableKey
.compareTo(nearest
.key
)
136 : comparator
.compare(key
, nearest
.key
);
138 // We found the requested key.
139 if (comparison
== 0) {
143 // If it exists, the key is in a subtree. Go deeper.
144 Node
<K
, V
> child
= (comparison
< 0) ? nearest
.left
: nearest
.right
;
153 // The key doesn't exist in this tree.
158 // Create the node and add it to the tree or the table.
159 Node
<K
, V
> header
= this.header
;
161 if (nearest
== null) {
162 // Check that the value is comparable if we didn't do any comparisons.
163 if (comparator
== NATURAL_ORDER
&& !(key
instanceof Comparable
)) {
164 throw new ClassCastException(key
.getClass().getName() + " is not Comparable");
166 created
= new Node
<K
, V
>(nearest
, key
, header
, header
.prev
);
169 created
= new Node
<K
, V
>(nearest
, key
, header
, header
.prev
);
170 if (comparison
< 0) { // nearest.key is higher
171 nearest
.left
= created
;
172 } else { // comparison > 0, nearest.key is lower
173 nearest
.right
= created
;
175 rebalance(nearest
, true);
183 @SuppressWarnings("unchecked")
184 Node
<K
, V
> findByObject(Object key
) {
186 return key
!= null ?
find((K
) key
, false) : null;
187 } catch (ClassCastException e
) {
193 * Returns this map's entry that has the same key and value as {@code
194 * entry}, or null if this map has no such entry.
196 * <p>This method uses the comparator for key equality rather than {@code
197 * equals}. If this map's comparator isn't consistent with equals (such as
198 * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code
199 * contains()} will violate the collections API.
201 Node
<K
, V
> findByEntry(Entry
<?
, ?
> entry
) {
202 Node
<K
, V
> mine
= findByObject(entry
.getKey());
203 boolean valuesEqual
= mine
!= null && equal(mine
.value
, entry
.getValue());
204 return valuesEqual ? mine
: null;
207 private boolean equal(Object a
, Object b
) {
208 return a
== b
|| (a
!= null && a
.equals(b
));
212 * Removes {@code node} from this tree, rearranging the tree's structure as
215 * @param unlink true to also unlink this node from the iteration linked list.
217 void removeInternal(Node
<K
, V
> node
, boolean unlink
) {
219 node
.prev
.next
= node
.next
;
220 node
.next
.prev
= node
.prev
;
223 Node
<K
, V
> left
= node
.left
;
224 Node
<K
, V
> right
= node
.right
;
225 Node
<K
, V
> originalParent
= node
.parent
;
226 if (left
!= null && right
!= null) {
229 * To remove a node with both left and right subtrees, move an
230 * adjacent node from one of those subtrees into this node's place.
232 * Removing the adjacent node may change this node's subtrees. This
233 * node may no longer have two subtrees once the adjacent node is
237 Node
<K
, V
> adjacent
= (left
.height
> right
.height
) ? left
.last() : right
.first();
238 removeInternal(adjacent
, false); // takes care of rebalance and size--
243 leftHeight
= left
.height
;
244 adjacent
.left
= left
;
245 left
.parent
= adjacent
;
252 rightHeight
= right
.height
;
253 adjacent
.right
= right
;
254 right
.parent
= adjacent
;
258 adjacent
.height
= Math
.max(leftHeight
, rightHeight
) + 1;
259 replaceInParent(node
, adjacent
);
261 } else if (left
!= null) {
262 replaceInParent(node
, left
);
264 } else if (right
!= null) {
265 replaceInParent(node
, right
);
268 replaceInParent(node
, null);
271 rebalance(originalParent
, false);
276 Node
<K
, V
> removeInternalByKey(Object key
) {
277 Node
<K
, V
> node
= findByObject(key
);
279 removeInternal(node
, true);
284 private void replaceInParent(Node
<K
, V
> node
, Node
<K
, V
> replacement
) {
285 Node
<K
, V
> parent
= node
.parent
;
287 if (replacement
!= null) {
288 replacement
.parent
= parent
;
291 if (parent
!= null) {
292 if (parent
.left
== node
) {
293 parent
.left
= replacement
;
295 assert (parent
.right
== node
);
296 parent
.right
= replacement
;
304 * Rebalances the tree by making any AVL rotations necessary between the
305 * newly-unbalanced node and the tree's root.
307 * @param insert true if the node was unbalanced by an insert; false if it
310 private void rebalance(Node
<K
, V
> unbalanced
, boolean insert
) {
311 for (Node
<K
, V
> node
= unbalanced
; node
!= null; node
= node
.parent
) {
312 Node
<K
, V
> left
= node
.left
;
313 Node
<K
, V
> right
= node
.right
;
314 int leftHeight
= left
!= null ? left
.height
: 0;
315 int rightHeight
= right
!= null ? right
.height
: 0;
317 int delta
= leftHeight
- rightHeight
;
319 Node
<K
, V
> rightLeft
= right
.left
;
320 Node
<K
, V
> rightRight
= right
.right
;
321 int rightRightHeight
= rightRight
!= null ? rightRight
.height
: 0;
322 int rightLeftHeight
= rightLeft
!= null ? rightLeft
.height
: 0;
324 int rightDelta
= rightLeftHeight
- rightRightHeight
;
325 if (rightDelta
== -1 || (rightDelta
== 0 && !insert
)) {
326 rotateLeft(node
); // AVL right right
328 assert (rightDelta
== 1);
329 rotateRight(right
); // AVL right left
333 break; // no further rotations will be necessary
336 } else if (delta
== 2) {
337 Node
<K
, V
> leftLeft
= left
.left
;
338 Node
<K
, V
> leftRight
= left
.right
;
339 int leftRightHeight
= leftRight
!= null ? leftRight
.height
: 0;
340 int leftLeftHeight
= leftLeft
!= null ? leftLeft
.height
: 0;
342 int leftDelta
= leftLeftHeight
- leftRightHeight
;
343 if (leftDelta
== 1 || (leftDelta
== 0 && !insert
)) {
344 rotateRight(node
); // AVL left left
346 assert (leftDelta
== -1);
347 rotateLeft(left
); // AVL left right
351 break; // no further rotations will be necessary
354 } else if (delta
== 0) {
355 node
.height
= leftHeight
+ 1; // leftHeight == rightHeight
357 break; // the insert caused balance, so rebalancing is done!
361 assert (delta
== -1 || delta
== 1);
362 node
.height
= Math
.max(leftHeight
, rightHeight
) + 1;
364 break; // the height hasn't changed, so rebalancing is done!
371 * Rotates the subtree so that its root's right child is the new root.
373 private void rotateLeft(Node
<K
, V
> root
) {
374 Node
<K
, V
> left
= root
.left
;
375 Node
<K
, V
> pivot
= root
.right
;
376 Node
<K
, V
> pivotLeft
= pivot
.left
;
377 Node
<K
, V
> pivotRight
= pivot
.right
;
379 // move the pivot's left child to the root's right
380 root
.right
= pivotLeft
;
381 if (pivotLeft
!= null) {
382 pivotLeft
.parent
= root
;
385 replaceInParent(root
, pivot
);
387 // move the root to the pivot's left
392 root
.height
= Math
.max(left
!= null ? left
.height
: 0,
393 pivotLeft
!= null ? pivotLeft
.height
: 0) + 1;
394 pivot
.height
= Math
.max(root
.height
,
395 pivotRight
!= null ? pivotRight
.height
: 0) + 1;
399 * Rotates the subtree so that its root's left child is the new root.
401 private void rotateRight(Node
<K
, V
> root
) {
402 Node
<K
, V
> pivot
= root
.left
;
403 Node
<K
, V
> right
= root
.right
;
404 Node
<K
, V
> pivotLeft
= pivot
.left
;
405 Node
<K
, V
> pivotRight
= pivot
.right
;
407 // move the pivot's right child to the root's left
408 root
.left
= pivotRight
;
409 if (pivotRight
!= null) {
410 pivotRight
.parent
= root
;
413 replaceInParent(root
, pivot
);
415 // move the root to the pivot's right
420 root
.height
= Math
.max(right
!= null ? right
.height
: 0,
421 pivotRight
!= null ? pivotRight
.height
: 0) + 1;
422 pivot
.height
= Math
.max(root
.height
,
423 pivotLeft
!= null ? pivotLeft
.height
: 0) + 1;
426 private EntrySet entrySet
;
427 private KeySet keySet
;
429 @Override public Set
<Entry
<K
, V
>> entrySet() {
430 EntrySet result
= entrySet
;
431 return result
!= null ? result
: (entrySet
= new EntrySet());
434 @Override public Set
<K
> keySet() {
435 KeySet result
= keySet
;
436 return result
!= null ? result
: (keySet
= new KeySet());
439 static final class Node
<K
, V
> implements Entry
<K
, V
> {
449 /** Create the header entry */
455 /** Create a regular entry */
456 Node(Node
<K
, V
> parent
, K key
, Node
<K
, V
> next
, Node
<K
, V
> prev
) {
457 this.parent
= parent
;
470 public V
getValue() {
474 public V
setValue(V value
) {
475 V oldValue
= this.value
;
480 @SuppressWarnings("rawtypes")
481 @Override public boolean equals(Object o
) {
482 if (o
instanceof Entry
) {
483 Entry other
= (Entry
) o
;
484 return (key
== null ? other
.getKey() == null : key
.equals(other
.getKey()))
485 && (value
== null ? other
.getValue() == null : value
.equals(other
.getValue()));
490 @Override public int hashCode() {
491 return (key
== null ?
0 : key
.hashCode())
492 ^
(value
== null ?
0 : value
.hashCode());
495 @Override public String
toString() {
496 return key
+ "=" + value
;
500 * Returns the first node in this subtree.
502 public Node
<K
, V
> first() {
503 Node
<K
, V
> node
= this;
504 Node
<K
, V
> child
= node
.left
;
505 while (child
!= null) {
513 * Returns the last node in this subtree.
515 public Node
<K
, V
> last() {
516 Node
<K
, V
> node
= this;
517 Node
<K
, V
> child
= node
.right
;
518 while (child
!= null) {
526 private abstract class LinkedTreeMapIterator
<T
> implements Iterator
<T
> {
527 Node
<K
, V
> next
= header
.next
;
528 Node
<K
, V
> lastReturned
= null;
529 int expectedModCount
= modCount
;
531 public final boolean hasNext() {
532 return next
!= header
;
535 final Node
<K
, V
> nextNode() {
538 throw new NoSuchElementException();
540 if (modCount
!= expectedModCount
) {
541 throw new ConcurrentModificationException();
544 return lastReturned
= e
;
547 public final void remove() {
548 if (lastReturned
== null) {
549 throw new IllegalStateException();
551 removeInternal(lastReturned
, true);
553 expectedModCount
= modCount
;
557 class EntrySet
extends AbstractSet
<Entry
<K
, V
>> {
558 @Override public int size() {
562 @Override public Iterator
<Entry
<K
, V
>> iterator() {
563 return new LinkedTreeMapIterator
<Entry
<K
, V
>>() {
564 public Entry
<K
, V
> next() {
570 @Override public boolean contains(Object o
) {
571 return o
instanceof Entry
&& findByEntry((Entry
<?
, ?
>) o
) != null;
574 @Override public boolean remove(Object o
) {
575 if (!(o
instanceof Entry
)) {
579 Node
<K
, V
> node
= findByEntry((Entry
<?
, ?
>) o
);
583 removeInternal(node
, true);
587 @Override public void clear() {
588 LinkedTreeMap
.this.clear();
592 class KeySet
extends AbstractSet
<K
> {
593 @Override public int size() {
597 @Override public Iterator
<K
> iterator() {
598 return new LinkedTreeMapIterator
<K
>() {
600 return nextNode().key
;
605 @Override public boolean contains(Object o
) {
606 return containsKey(o
);
609 @Override public boolean remove(Object key
) {
610 return removeInternalByKey(key
) != null;
613 @Override public void clear() {
614 LinkedTreeMap
.this.clear();
619 * If somebody is unlucky enough to have to serialize one of these, serialize
620 * it as a LinkedHashMap so that they won't need Gson on the other side to
621 * deserialize it. Using serialization defeats our DoS defence, so most apps
624 private Object
writeReplace() throws ObjectStreamException
{
625 return new LinkedHashMap
<K
, V
>(this);