X-Git-Url: http://git.ieval.ro/?a=blobdiff_plain;f=gson%2Fcom%2Fgoogle%2Fgson%2Finternal%2FLinkedTreeMap.java;fp=gson%2Fcom%2Fgoogle%2Fgson%2Finternal%2FLinkedTreeMap.java;h=578795a733096556e95d9f18f5aacc7b0f73b257;hb=5c86ae2f45d293408d98a291e826948052d207bc;hp=0000000000000000000000000000000000000000;hpb=5cf4714f0675349ed599707e024cf0e70fe114b2;p=unical.git
diff --git a/gson/com/google/gson/internal/LinkedTreeMap.java b/gson/com/google/gson/internal/LinkedTreeMap.java
new file mode 100644
index 0000000..578795a
--- /dev/null
+++ b/gson/com/google/gson/internal/LinkedTreeMap.java
@@ -0,0 +1,627 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * Copyright (C) 2012 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.gson.internal;
+
+import java.io.ObjectStreamException;
+import java.io.Serializable;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.Comparator;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A map of comparable keys to values. Unlike {@code 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.
+ */
+public final class LinkedTreeMap extends AbstractMap implements Serializable {
+ @SuppressWarnings({ "unchecked", "rawtypes" }) // to avoid Comparable>>
+ private static final Comparator NATURAL_ORDER = new Comparator() {
+ public int compare(Comparable a, Comparable b) {
+ return a.compareTo(b);
+ }
+ };
+
+ Comparator super K> comparator;
+ Node root;
+ int size = 0;
+ int modCount = 0;
+
+ // Used to preserve iteration order
+ final Node header = new Node();
+
+ /**
+ * Create a natural order, empty tree map whose keys must be mutually
+ * comparable and non-null.
+ */
+ @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable
+ public LinkedTreeMap() {
+ this((Comparator super K>) NATURAL_ORDER);
+ }
+
+ /**
+ * Create a tree map ordered by {@code comparator}. This map's keys may only
+ * be null if {@code comparator} permits.
+ *
+ * @param comparator the comparator to order elements with, or {@code null} to
+ * use the natural ordering.
+ */
+ @SuppressWarnings({ "unchecked", "rawtypes" }) // unsafe! if comparator is null, this assumes K is comparable
+ public LinkedTreeMap(Comparator super K> comparator) {
+ this.comparator = comparator != null
+ ? comparator
+ : (Comparator) NATURAL_ORDER;
+ }
+
+ @Override public int size() {
+ return size;
+ }
+
+ @Override public V get(Object key) {
+ Node node = findByObject(key);
+ return node != null ? node.value : null;
+ }
+
+ @Override public boolean containsKey(Object key) {
+ return findByObject(key) != null;
+ }
+
+ @Override public V put(K key, V value) {
+ if (key == null) {
+ throw new NullPointerException("key == null");
+ }
+ Node created = find(key, true);
+ V result = created.value;
+ created.value = value;
+ return result;
+ }
+
+ @Override public void clear() {
+ root = null;
+ size = 0;
+ modCount++;
+
+ // Clear iteration order
+ Node header = this.header;
+ header.next = header.prev = header;
+ }
+
+ @Override public V remove(Object key) {
+ Node node = removeInternalByKey(key);
+ return node != null ? node.value : null;
+ }
+
+ /**
+ * Returns the node at or adjacent to the given key, creating it if requested.
+ *
+ * @throws ClassCastException if {@code key} and the tree's keys aren't
+ * mutually comparable.
+ */
+ Node find(K key, boolean create) {
+ Comparator super K> comparator = this.comparator;
+ Node nearest = root;
+ int comparison = 0;
+
+ if (nearest != null) {
+ // Micro-optimization: avoid polymorphic calls to Comparator.compare().
+ @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble.
+ Comparable