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     LinkedTreeMapIterator() {
532     }
533
534     public final boolean hasNext() {
535       return next != header;
536     }
537
538     final Node<K, V> nextNode() {
539       Node<K, V> e = next;
540       if (e == header) {
541         throw new NoSuchElementException();
542       }
543       if (modCount != expectedModCount) {
544         throw new ConcurrentModificationException();
545       }
546       next = e.next;
547       return lastReturned = e;
548     }
549
550     public final void remove() {
551       if (lastReturned == null) {
552         throw new IllegalStateException();
553       }
554       removeInternal(lastReturned, true);
555       lastReturned = null;
556       expectedModCount = modCount;
557     }
558   }
559
560   class EntrySet extends AbstractSet<Entry<K, V>> {
561     @Override public int size() {
562       return size;
563     }
564
565     @Override public Iterator<Entry<K, V>> iterator() {
566       return new LinkedTreeMapIterator<Entry<K, V>>() {
567         public Entry<K, V> next() {
568           return nextNode();
569         }
570       };
571     }
572
573     @Override public boolean contains(Object o) {
574       return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null;
575     }
576
577     @Override public boolean remove(Object o) {
578       if (!(o instanceof Entry)) {
579         return false;
580       }
581
582       Node<K, V> node = findByEntry((Entry<?, ?>) o);
583       if (node == null) {
584         return false;
585       }
586       removeInternal(node, true);
587       return true;
588     }
589
590     @Override public void clear() {
591       LinkedTreeMap.this.clear();
592     }
593   }
594
595   final class KeySet extends AbstractSet<K> {
596     @Override public int size() {
597       return size;
598     }
599
600     @Override public Iterator<K> iterator() {
601       return new LinkedTreeMapIterator<K>() {
602         public K next() {
603           return nextNode().key;
604         }
605       };
606     }
607
608     @Override public boolean contains(Object o) {
609       return containsKey(o);
610     }
611
612     @Override public boolean remove(Object key) {
613       return removeInternalByKey(key) != null;
614     }
615
616     @Override public void clear() {
617       LinkedTreeMap.this.clear();
618     }
619   }
620
621   /**
622    * If somebody is unlucky enough to have to serialize one of these, serialize
623    * it as a LinkedHashMap so that they won't need Gson on the other side to
624    * deserialize it. Using serialization defeats our DoS defence, so most apps
625    * shouldn't use it.
626    */
627   private Object writeReplace() throws ObjectStreamException {
628     return new LinkedHashMap<K, V>(this);
629   }
630 }
631