]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Copyright (C) 2010 The Android Open Source Project | |
3 | * Copyright (C) 2012 Google Inc. | |
4 | * | |
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 | |
8 | * | |
9 | * http://www.apache.org/licenses/LICENSE-2.0 | |
10 | * | |
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. | |
16 | */ | |
17 | ||
18 | package com.google.gson.internal; | |
19 | ||
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; | |
29 | import java.util.Set; | |
30 | ||
31 | /** | |
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. | |
35 | * | |
36 | * <p>This implementation was derived from Android 4.1's TreeMap class. | |
37 | */ | |
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); | |
43 | } | |
44 | }; | |
45 | ||
46 | Comparator<? super K> comparator; | |
47 | Node<K, V> root; | |
48 | int size = 0; | |
49 | int modCount = 0; | |
50 | ||
51 | // Used to preserve iteration order | |
52 | final Node<K, V> header = new Node<K, V>(); | |
53 | ||
54 | /** | |
55 | * Create a natural order, empty tree map whose keys must be mutually | |
56 | * comparable and non-null. | |
57 | */ | |
58 | @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable | |
59 | public LinkedTreeMap() { | |
60 | this((Comparator<? super K>) NATURAL_ORDER); | |
61 | } | |
62 | ||
63 | /** | |
64 | * Create a tree map ordered by {@code comparator}. This map's keys may only | |
65 | * be null if {@code comparator} permits. | |
66 | * | |
67 | * @param comparator the comparator to order elements with, or {@code null} to | |
68 | * use the natural ordering. | |
69 | */ | |
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 | |
73 | ? comparator | |
74 | : (Comparator) NATURAL_ORDER; | |
75 | } | |
76 | ||
77 | @Override public int size() { | |
78 | return size; | |
79 | } | |
80 | ||
81 | @Override public V get(Object key) { | |
82 | Node<K, V> node = findByObject(key); | |
83 | return node != null ? node.value : null; | |
84 | } | |
85 | ||
86 | @Override public boolean containsKey(Object key) { | |
87 | return findByObject(key) != null; | |
88 | } | |
89 | ||
90 | @Override public V put(K key, V value) { | |
91 | if (key == null) { | |
92 | throw new NullPointerException("key == null"); | |
93 | } | |
94 | Node<K, V> created = find(key, true); | |
95 | V result = created.value; | |
96 | created.value = value; | |
97 | return result; | |
98 | } | |
99 | ||
100 | @Override public void clear() { | |
101 | root = null; | |
102 | size = 0; | |
103 | modCount++; | |
104 | ||
105 | // Clear iteration order | |
106 | Node<K, V> header = this.header; | |
107 | header.next = header.prev = header; | |
108 | } | |
109 | ||
110 | @Override public V remove(Object key) { | |
111 | Node<K, V> node = removeInternalByKey(key); | |
112 | return node != null ? node.value : null; | |
113 | } | |
114 | ||
115 | /** | |
116 | * Returns the node at or adjacent to the given key, creating it if requested. | |
117 | * | |
118 | * @throws ClassCastException if {@code key} and the tree's keys aren't | |
119 | * mutually comparable. | |
120 | */ | |
121 | Node<K, V> find(K key, boolean create) { | |
122 | Comparator<? super K> comparator = this.comparator; | |
123 | Node<K, V> nearest = root; | |
124 | int comparison = 0; | |
125 | ||
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 | |
131 | : null; | |
132 | ||
133 | while (true) { | |
134 | comparison = (comparableKey != null) | |
135 | ? comparableKey.compareTo(nearest.key) | |
136 | : comparator.compare(key, nearest.key); | |
137 | ||
138 | // We found the requested key. | |
139 | if (comparison == 0) { | |
140 | return nearest; | |
141 | } | |
142 | ||
143 | // If it exists, the key is in a subtree. Go deeper. | |
144 | Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right; | |
145 | if (child == null) { | |
146 | break; | |
147 | } | |
148 | ||
149 | nearest = child; | |
150 | } | |
151 | } | |
152 | ||
153 | // The key doesn't exist in this tree. | |
154 | if (!create) { | |
155 | return null; | |
156 | } | |
157 | ||
158 | // Create the node and add it to the tree or the table. | |
159 | Node<K, V> header = this.header; | |
160 | Node<K, V> created; | |
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"); | |
165 | } | |
166 | created = new Node<K, V>(nearest, key, header, header.prev); | |
167 | root = created; | |
168 | } else { | |
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; | |
174 | } | |
175 | rebalance(nearest, true); | |
176 | } | |
177 | size++; | |
178 | modCount++; | |
179 | ||
180 | return created; | |
181 | } | |
182 | ||
183 | @SuppressWarnings("unchecked") | |
184 | Node<K, V> findByObject(Object key) { | |
185 | try { | |
186 | return key != null ? find((K) key, false) : null; | |
187 | } catch (ClassCastException e) { | |
188 | return null; | |
189 | } | |
190 | } | |
191 | ||
192 | /** | |
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. | |
195 | * | |
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. | |
200 | */ | |
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; | |
205 | } | |
206 | ||
207 | private boolean equal(Object a, Object b) { | |
208 | return a == b || (a != null && a.equals(b)); | |
209 | } | |
210 | ||
211 | /** | |
212 | * Removes {@code node} from this tree, rearranging the tree's structure as | |
213 | * necessary. | |
214 | * | |
215 | * @param unlink true to also unlink this node from the iteration linked list. | |
216 | */ | |
217 | void removeInternal(Node<K, V> node, boolean unlink) { | |
218 | if (unlink) { | |
219 | node.prev.next = node.next; | |
220 | node.next.prev = node.prev; | |
221 | } | |
222 | ||
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) { | |
227 | ||
228 | /* | |
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. | |
231 | * | |
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 | |
234 | * gone! | |
235 | */ | |
236 | ||
237 | Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first(); | |
238 | removeInternal(adjacent, false); // takes care of rebalance and size-- | |
239 | ||
240 | int leftHeight = 0; | |
241 | left = node.left; | |
242 | if (left != null) { | |
243 | leftHeight = left.height; | |
244 | adjacent.left = left; | |
245 | left.parent = adjacent; | |
246 | node.left = null; | |
247 | } | |
248 | ||
249 | int rightHeight = 0; | |
250 | right = node.right; | |
251 | if (right != null) { | |
252 | rightHeight = right.height; | |
253 | adjacent.right = right; | |
254 | right.parent = adjacent; | |
255 | node.right = null; | |
256 | } | |
257 | ||
258 | adjacent.height = Math.max(leftHeight, rightHeight) + 1; | |
259 | replaceInParent(node, adjacent); | |
260 | return; | |
261 | } else if (left != null) { | |
262 | replaceInParent(node, left); | |
263 | node.left = null; | |
264 | } else if (right != null) { | |
265 | replaceInParent(node, right); | |
266 | node.right = null; | |
267 | } else { | |
268 | replaceInParent(node, null); | |
269 | } | |
270 | ||
271 | rebalance(originalParent, false); | |
272 | size--; | |
273 | modCount++; | |
274 | } | |
275 | ||
276 | Node<K, V> removeInternalByKey(Object key) { | |
277 | Node<K, V> node = findByObject(key); | |
278 | if (node != null) { | |
279 | removeInternal(node, true); | |
280 | } | |
281 | return node; | |
282 | } | |
283 | ||
284 | private void replaceInParent(Node<K, V> node, Node<K, V> replacement) { | |
285 | Node<K, V> parent = node.parent; | |
286 | node.parent = null; | |
287 | if (replacement != null) { | |
288 | replacement.parent = parent; | |
289 | } | |
290 | ||
291 | if (parent != null) { | |
292 | if (parent.left == node) { | |
293 | parent.left = replacement; | |
294 | } else { | |
295 | assert (parent.right == node); | |
296 | parent.right = replacement; | |
297 | } | |
298 | } else { | |
299 | root = replacement; | |
300 | } | |
301 | } | |
302 | ||
303 | /** | |
304 | * Rebalances the tree by making any AVL rotations necessary between the | |
305 | * newly-unbalanced node and the tree's root. | |
306 | * | |
307 | * @param insert true if the node was unbalanced by an insert; false if it | |
308 | * was by a removal. | |
309 | */ | |
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; | |
316 | ||
317 | int delta = leftHeight - rightHeight; | |
318 | if (delta == -2) { | |
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; | |
323 | ||
324 | int rightDelta = rightLeftHeight - rightRightHeight; | |
325 | if (rightDelta == -1 || (rightDelta == 0 && !insert)) { | |
326 | rotateLeft(node); // AVL right right | |
327 | } else { | |
328 | assert (rightDelta == 1); | |
329 | rotateRight(right); // AVL right left | |
330 | rotateLeft(node); | |
331 | } | |
332 | if (insert) { | |
333 | break; // no further rotations will be necessary | |
334 | } | |
335 | ||
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; | |
341 | ||
342 | int leftDelta = leftLeftHeight - leftRightHeight; | |
343 | if (leftDelta == 1 || (leftDelta == 0 && !insert)) { | |
344 | rotateRight(node); // AVL left left | |
345 | } else { | |
346 | assert (leftDelta == -1); | |
347 | rotateLeft(left); // AVL left right | |
348 | rotateRight(node); | |
349 | } | |
350 | if (insert) { | |
351 | break; // no further rotations will be necessary | |
352 | } | |
353 | ||
354 | } else if (delta == 0) { | |
355 | node.height = leftHeight + 1; // leftHeight == rightHeight | |
356 | if (insert) { | |
357 | break; // the insert caused balance, so rebalancing is done! | |
358 | } | |
359 | ||
360 | } else { | |
361 | assert (delta == -1 || delta == 1); | |
362 | node.height = Math.max(leftHeight, rightHeight) + 1; | |
363 | if (!insert) { | |
364 | break; // the height hasn't changed, so rebalancing is done! | |
365 | } | |
366 | } | |
367 | } | |
368 | } | |
369 | ||
370 | /** | |
371 | * Rotates the subtree so that its root's right child is the new root. | |
372 | */ | |
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; | |
378 | ||
379 | // move the pivot's left child to the root's right | |
380 | root.right = pivotLeft; | |
381 | if (pivotLeft != null) { | |
382 | pivotLeft.parent = root; | |
383 | } | |
384 | ||
385 | replaceInParent(root, pivot); | |
386 | ||
387 | // move the root to the pivot's left | |
388 | pivot.left = root; | |
389 | root.parent = pivot; | |
390 | ||
391 | // fix heights | |
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; | |
396 | } | |
397 | ||
398 | /** | |
399 | * Rotates the subtree so that its root's left child is the new root. | |
400 | */ | |
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; | |
406 | ||
407 | // move the pivot's right child to the root's left | |
408 | root.left = pivotRight; | |
409 | if (pivotRight != null) { | |
410 | pivotRight.parent = root; | |
411 | } | |
412 | ||
413 | replaceInParent(root, pivot); | |
414 | ||
415 | // move the root to the pivot's right | |
416 | pivot.right = root; | |
417 | root.parent = pivot; | |
418 | ||
419 | // fixup heights | |
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; | |
424 | } | |
425 | ||
426 | private EntrySet entrySet; | |
427 | private KeySet keySet; | |
428 | ||
429 | @Override public Set<Entry<K, V>> entrySet() { | |
430 | EntrySet result = entrySet; | |
431 | return result != null ? result : (entrySet = new EntrySet()); | |
432 | } | |
433 | ||
434 | @Override public Set<K> keySet() { | |
435 | KeySet result = keySet; | |
436 | return result != null ? result : (keySet = new KeySet()); | |
437 | } | |
438 | ||
439 | static final class Node<K, V> implements Entry<K, V> { | |
440 | Node<K, V> parent; | |
441 | Node<K, V> left; | |
442 | Node<K, V> right; | |
443 | Node<K, V> next; | |
444 | Node<K, V> prev; | |
445 | final K key; | |
446 | V value; | |
447 | int height; | |
448 | ||
449 | /** Create the header entry */ | |
450 | Node() { | |
451 | key = null; | |
452 | next = prev = this; | |
453 | } | |
454 | ||
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; | |
458 | this.key = key; | |
459 | this.height = 1; | |
460 | this.next = next; | |
461 | this.prev = prev; | |
462 | prev.next = this; | |
463 | next.prev = this; | |
464 | } | |
465 | ||
466 | public K getKey() { | |
467 | return key; | |
468 | } | |
469 | ||
470 | public V getValue() { | |
471 | return value; | |
472 | } | |
473 | ||
474 | public V setValue(V value) { | |
475 | V oldValue = this.value; | |
476 | this.value = value; | |
477 | return oldValue; | |
478 | } | |
479 | ||
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())); | |
486 | } | |
487 | return false; | |
488 | } | |
489 | ||
490 | @Override public int hashCode() { | |
491 | return (key == null ? 0 : key.hashCode()) | |
492 | ^ (value == null ? 0 : value.hashCode()); | |
493 | } | |
494 | ||
495 | @Override public String toString() { | |
496 | return key + "=" + value; | |
497 | } | |
498 | ||
499 | /** | |
500 | * Returns the first node in this subtree. | |
501 | */ | |
502 | public Node<K, V> first() { | |
503 | Node<K, V> node = this; | |
504 | Node<K, V> child = node.left; | |
505 | while (child != null) { | |
506 | node = child; | |
507 | child = node.left; | |
508 | } | |
509 | return node; | |
510 | } | |
511 | ||
512 | /** | |
513 | * Returns the last node in this subtree. | |
514 | */ | |
515 | public Node<K, V> last() { | |
516 | Node<K, V> node = this; | |
517 | Node<K, V> child = node.right; | |
518 | while (child != null) { | |
519 | node = child; | |
520 | child = node.right; | |
521 | } | |
522 | return node; | |
523 | } | |
524 | } | |
525 | ||
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; | |
530 | ||
531 | public final boolean hasNext() { | |
532 | return next != header; | |
533 | } | |
534 | ||
535 | final Node<K, V> nextNode() { | |
536 | Node<K, V> e = next; | |
537 | if (e == header) { | |
538 | throw new NoSuchElementException(); | |
539 | } | |
540 | if (modCount != expectedModCount) { | |
541 | throw new ConcurrentModificationException(); | |
542 | } | |
543 | next = e.next; | |
544 | return lastReturned = e; | |
545 | } | |
546 | ||
547 | public final void remove() { | |
548 | if (lastReturned == null) { | |
549 | throw new IllegalStateException(); | |
550 | } | |
551 | removeInternal(lastReturned, true); | |
552 | lastReturned = null; | |
553 | expectedModCount = modCount; | |
554 | } | |
555 | } | |
556 | ||
557 | class EntrySet extends AbstractSet<Entry<K, V>> { | |
558 | @Override public int size() { | |
559 | return size; | |
560 | } | |
561 | ||
562 | @Override public Iterator<Entry<K, V>> iterator() { | |
563 | return new LinkedTreeMapIterator<Entry<K, V>>() { | |
564 | public Entry<K, V> next() { | |
565 | return nextNode(); | |
566 | } | |
567 | }; | |
568 | } | |
569 | ||
570 | @Override public boolean contains(Object o) { | |
571 | return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null; | |
572 | } | |
573 | ||
574 | @Override public boolean remove(Object o) { | |
575 | if (!(o instanceof Entry)) { | |
576 | return false; | |
577 | } | |
578 | ||
579 | Node<K, V> node = findByEntry((Entry<?, ?>) o); | |
580 | if (node == null) { | |
581 | return false; | |
582 | } | |
583 | removeInternal(node, true); | |
584 | return true; | |
585 | } | |
586 | ||
587 | @Override public void clear() { | |
588 | LinkedTreeMap.this.clear(); | |
589 | } | |
590 | } | |
591 | ||
592 | class KeySet extends AbstractSet<K> { | |
593 | @Override public int size() { | |
594 | return size; | |
595 | } | |
596 | ||
597 | @Override public Iterator<K> iterator() { | |
598 | return new LinkedTreeMapIterator<K>() { | |
599 | public K next() { | |
600 | return nextNode().key; | |
601 | } | |
602 | }; | |
603 | } | |
604 | ||
605 | @Override public boolean contains(Object o) { | |
606 | return containsKey(o); | |
607 | } | |
608 | ||
609 | @Override public boolean remove(Object key) { | |
610 | return removeInternalByKey(key) != null; | |
611 | } | |
612 | ||
613 | @Override public void clear() { | |
614 | LinkedTreeMap.this.clear(); | |
615 | } | |
616 | } | |
617 | ||
618 | /** | |
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 | |
622 | * shouldn't use it. | |
623 | */ | |
624 | private Object writeReplace() throws ObjectStreamException { | |
625 | return new LinkedHashMap<K, V>(this); | |
626 | } | |
627 | } |