162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets/* 2bdc4c86d3dff74f6634a38e2f7b316b0e823a2c8Alan Viverette * Copyright 2018 The Android Open Source Project 362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * Licensed under the Apache License, Version 2.0 (the "License"); 562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * you may not use this file except in compliance with the License. 662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * You may obtain a copy of the License at 762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * http://www.apache.org/licenses/LICENSE-2.0 962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 1062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * Unless required by applicable law or agreed to in writing, software 1162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * distributed under the License is distributed on an "AS IS" BASIS, 1262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * See the License for the specific language governing permissions and 1462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * limitations under the License. 1562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets */ 1662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 17bdc4c86d3dff74f6634a38e2f7b316b0e823a2c8Alan Viverettepackage androidx.arch.core.internal; 1862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 19bdc4c86d3dff74f6634a38e2f7b316b0e823a2c8Alan Viveretteimport androidx.annotation.NonNull; 20bdc4c86d3dff74f6634a38e2f7b316b0e823a2c8Alan Viveretteimport androidx.annotation.RestrictTo; 2162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 2262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinetsimport java.util.Iterator; 2362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinetsimport java.util.Map; 2462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinetsimport java.util.WeakHashMap; 2562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 2662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets/** 27b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * LinkedList, which pretends to be a map and supports modifications during iterations. 2862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * It is NOT thread safe. 2962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 3062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @param <K> Key type 3162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @param <V> Value type 3262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @hide 3362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets */ 3462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets@RestrictTo(RestrictTo.Scope.LIBRARY_GROUP) 3562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinetspublic class SafeIterableMap<K, V> implements Iterable<Map.Entry<K, V>> { 3662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 3762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets private Entry<K, V> mStart; 3862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets private Entry<K, V> mEnd; 3962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets // using WeakHashMap over List<WeakReference>, so we don't have to manually remove 4062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets // WeakReferences that have null in them. 41b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets private WeakHashMap<SupportRemove<K, V>, Boolean> mIterators = new WeakHashMap<>(); 4262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets private int mSize = 0; 4362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 44b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets protected Entry<K, V> get(K k) { 45b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> currentNode = mStart; 46b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets while (currentNode != null) { 47b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (currentNode.mKey.equals(k)) { 4862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets break; 4962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 50b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets currentNode = currentNode.mNext; 5162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 52b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return currentNode; 5362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 5462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 5562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets /** 5662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * If the specified key is not already associated 5762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * with a value, associates it with the given value. 5862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 5962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @param key key with which the specified value is to be associated 6062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @param v value to be associated with the specified key 6162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @return the previous value associated with the specified key, 6262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * or {@code null} if there was no mapping for the key 6362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets */ 6462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public V putIfAbsent(@NonNull K key, @NonNull V v) { 65b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> entry = get(key); 6662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (entry != null) { 6762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return entry.mValue; 6862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 69b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets put(key, v); 70b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return null; 71b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 72b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 73b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets protected Entry<K, V> put(@NonNull K key, @NonNull V v) { 7462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry<K, V> newEntry = new Entry<>(key, v); 7562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mSize++; 7662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (mEnd == null) { 7762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mStart = newEntry; 7862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mEnd = mStart; 79b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return newEntry; 8062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 8162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 8262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mEnd.mNext = newEntry; 8362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets newEntry.mPrevious = mEnd; 8462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mEnd = newEntry; 85b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return newEntry; 86b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 8762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 8862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 8962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets /** 9062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * Removes the mapping for a key from this map if it is present. 9162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * 9262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @param key key whose mapping is to be removed from the map 9362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @return the previous value associated with the specified key, 9462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * or {@code null} if there was no mapping for the key 9562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets */ 9662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public V remove(@NonNull K key) { 97b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> toRemove = get(key); 9862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (toRemove == null) { 9962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return null; 10062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 10162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mSize--; 10262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (!mIterators.isEmpty()) { 103b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets for (SupportRemove<K, V> iter : mIterators.keySet()) { 10462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets iter.supportRemove(toRemove); 10562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 10662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 10762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 10862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (toRemove.mPrevious != null) { 10962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets toRemove.mPrevious.mNext = toRemove.mNext; 11062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } else { 11162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mStart = toRemove.mNext; 11262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 11362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 11462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (toRemove.mNext != null) { 11562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets toRemove.mNext.mPrevious = toRemove.mPrevious; 11662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } else { 11762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mEnd = toRemove.mPrevious; 11862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 11962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 12062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets toRemove.mNext = null; 12162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets toRemove.mPrevious = null; 12262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return toRemove.mValue; 12362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 12462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 12562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets /** 12662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets * @return the number of elements in this map 12762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets */ 12862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public int size() { 12962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mSize; 13062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 13162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 132b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets /** 133b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * @return an ascending iterator, which doesn't include new elements added during an 134b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * iteration. 135b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets */ 136b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @NonNull 13762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 138b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public Iterator<Map.Entry<K, V>> iterator() { 139b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets ListIterator<K, V> iterator = new AscendingIterator<>(mStart, mEnd); 14062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mIterators.put(iterator, false); 14162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return iterator; 14262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 14362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 144c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets /** 145b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * @return an descending iterator, which doesn't include new elements added during an 146b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * iteration. 147c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets */ 148b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public Iterator<Map.Entry<K, V>> descendingIterator() { 149b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets DescendingIterator<K, V> iterator = new DescendingIterator<>(mEnd, mStart); 150b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets mIterators.put(iterator, false); 151b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return iterator; 152b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 153b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 154b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets /** 155b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * return an iterator with additions. 156b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets */ 157b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public IteratorWithAdditions iteratorWithAdditions() { 158c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets @SuppressWarnings("unchecked") 159b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets IteratorWithAdditions iterator = new IteratorWithAdditions(); 160c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets mIterators.put(iterator, false); 161c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets return iterator; 162c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets } 163c43ce90b803cdfa033dfc94fa4161371ed6f3ec6Sergey Vasilinets 164b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets /** 165b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * @return eldest added entry or null 166b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets */ 167b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public Map.Entry<K, V> eldest() { 168b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return mStart; 169b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 170b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 171b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets /** 172b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets * @return newest added entry or null 173b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets */ 174b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public Map.Entry<K, V> newest() { 175b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return mEnd; 176b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 177b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 178b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 179b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public boolean equals(Object obj) { 180b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (obj == this) { 181b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return true; 182b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 183b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (!(obj instanceof SafeIterableMap)) { 184b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return false; 185b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 186b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets SafeIterableMap map = (SafeIterableMap) obj; 187b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (this.size() != map.size()) { 188b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return false; 189b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 190b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Iterator<Map.Entry<K, V>> iterator1 = iterator(); 191b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Iterator iterator2 = map.iterator(); 192b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets while (iterator1.hasNext() && iterator2.hasNext()) { 193b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Map.Entry<K, V> next1 = iterator1.next(); 194b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Object next2 = iterator2.next(); 195b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if ((next1 == null && next2 != null) 196b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets || (next1 != null && !next1.equals(next2))) { 197b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return false; 198b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 199b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 200b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return !iterator1.hasNext() && !iterator2.hasNext(); 201b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 202b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 203b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 2047cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton public int hashCode() { 2057cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton int h = 0; 2067cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton Iterator<Map.Entry<K, V>> i = iterator(); 2077cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton while (i.hasNext()) { 2087cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton h += i.next().hashCode(); 2097cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton } 2107cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton return h; 2117cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton } 2127cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton 2137cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton @Override 214b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public String toString() { 215b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets StringBuilder builder = new StringBuilder(); 216b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets builder.append("["); 217b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Iterator<Map.Entry<K, V>> iterator = iterator(); 218b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets while (iterator.hasNext()) { 219b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets builder.append(iterator.next().toString()); 220b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (iterator.hasNext()) { 221b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets builder.append(", "); 222b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 223b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 224b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets builder.append("]"); 225b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return builder.toString(); 226b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 227b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 228b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets private abstract static class ListIterator<K, V> implements Iterator<Map.Entry<K, V>>, 229b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets SupportRemove<K, V> { 23062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry<K, V> mExpectedEnd; 23162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry<K, V> mNext; 23262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 23362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets ListIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { 23462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets this.mExpectedEnd = expectedEnd; 23562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets this.mNext = start; 23662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 23762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 23862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 23962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public boolean hasNext() { 24062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mNext != null; 24162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 24262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 243b1433f75d87710262b14824c98854a4865f98836Aurimas Liutikas @SuppressWarnings("ReferenceEquality") 244b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 245b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public void supportRemove(@NonNull Entry<K, V> entry) { 24662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (mExpectedEnd == entry && entry == mNext) { 24762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mNext = null; 24862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mExpectedEnd = null; 24962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 25062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 25162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (mExpectedEnd == entry) { 252b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets mExpectedEnd = backward(mExpectedEnd); 25362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 25462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 25562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (mNext == entry) { 25662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mNext = nextNode(); 25762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 25862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 25962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 260b1433f75d87710262b14824c98854a4865f98836Aurimas Liutikas @SuppressWarnings("ReferenceEquality") 26162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets private Entry<K, V> nextNode() { 26262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (mNext == mExpectedEnd || mExpectedEnd == null) { 26362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return null; 26462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 265b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return forward(mNext); 26662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 26762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 26862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 26962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public Map.Entry<K, V> next() { 27062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Map.Entry<K, V> result = mNext; 27162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mNext = nextNode(); 27262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return result; 27362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 274b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 275b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets abstract Entry<K, V> forward(Entry<K, V> entry); 276b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 277b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets abstract Entry<K, V> backward(Entry<K, V> entry); 27862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 27962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 280b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets static class AscendingIterator<K, V> extends ListIterator<K, V> { 281b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets AscendingIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { 282b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets super(start, expectedEnd); 28362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 284b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 285b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 286b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> forward(Entry<K, V> entry) { 287b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return entry.mNext; 28862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 289b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 290b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 291b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> backward(Entry<K, V> entry) { 292b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return entry.mPrevious; 29362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 294b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 295b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 296b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets private static class DescendingIterator<K, V> extends ListIterator<K, V> { 297b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 298b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets DescendingIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { 299b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets super(start, expectedEnd); 300b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 301b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 302b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 303b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> forward(Entry<K, V> entry) { 304b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return entry.mPrevious; 305b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 306b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 307b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 308b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets Entry<K, V> backward(Entry<K, V> entry) { 309b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return entry.mNext; 31062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 31162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 31262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 313b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets private class IteratorWithAdditions implements Iterator<Map.Entry<K, V>>, SupportRemove<K, V> { 314b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets private Entry<K, V> mCurrent; 3153facabd26326a3f4274b04dc7ab03442839c5601Sergey Vasilinets private boolean mBeforeStart = true; 316b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 317b1433f75d87710262b14824c98854a4865f98836Aurimas Liutikas @SuppressWarnings("ReferenceEquality") 318b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 319b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public void supportRemove(@NonNull Entry<K, V> entry) { 320b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets if (entry == mCurrent) { 321b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets mCurrent = mCurrent.mPrevious; 3223facabd26326a3f4274b04dc7ab03442839c5601Sergey Vasilinets mBeforeStart = mCurrent == null; 32362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 32462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 325b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 326b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 327b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public boolean hasNext() { 3283facabd26326a3f4274b04dc7ab03442839c5601Sergey Vasilinets if (mBeforeStart) { 329b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return mStart != null; 330b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 331b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return mCurrent != null && mCurrent.mNext != null; 332b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 333b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 334b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets @Override 335b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets public Map.Entry<K, V> next() { 3363facabd26326a3f4274b04dc7ab03442839c5601Sergey Vasilinets if (mBeforeStart) { 3373facabd26326a3f4274b04dc7ab03442839c5601Sergey Vasilinets mBeforeStart = false; 338b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets mCurrent = mStart; 339b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } else { 340b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets mCurrent = mCurrent != null ? mCurrent.mNext : null; 341b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 342b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets return mCurrent; 343b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 344b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets } 345b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets 346b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets interface SupportRemove<K, V> { 347b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets void supportRemove(@NonNull Entry<K, V> entry); 34862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 34962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 350b546e977676e83f932e88e6c6d4e6e2710621bc9Sergey Vasilinets static class Entry<K, V> implements Map.Entry<K, V> { 35162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @NonNull 35262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets final K mKey; 35362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @NonNull 35462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets final V mValue; 35562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry<K, V> mNext; 35662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry<K, V> mPrevious; 35762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 35862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry(@NonNull K key, @NonNull V value) { 35962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets mKey = key; 36062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets this.mValue = value; 36162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 36262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 36362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @NonNull 36462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 36562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public K getKey() { 36662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mKey; 36762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 36862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 36962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @NonNull 37062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 37162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public V getValue() { 37262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mValue; 37362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 37462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 37562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 37662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public V setValue(V value) { 37762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets throw new UnsupportedOperationException("An entry modification is not supported"); 37862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 37962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 38062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 38162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public String toString() { 38262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mKey + "=" + mValue; 38362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 38462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets 385b1433f75d87710262b14824c98854a4865f98836Aurimas Liutikas @SuppressWarnings("ReferenceEquality") 38662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets @Override 38762bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets public boolean equals(Object obj) { 38862bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (obj == this) { 38962bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return true; 39062bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 39162bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets if (!(obj instanceof Entry)) { 39262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return false; 39362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 39462bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets Entry entry = (Entry) obj; 39562bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets return mKey.equals(entry.mKey) && mValue.equals(entry.mValue); 39662bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 3977cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton 3987cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton @Override 3997cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton public int hashCode() { 4007cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton return mKey.hashCode() ^ mValue.hashCode(); 4017cab6d3b9e094bad53c5b2e730fc5f3fd3d9f38bJake Wharton } 40262bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets } 40362bb8a137f7dce7a18f63a6bdf7a63bf1ce3b4a4Sergey Vasilinets} 404