what-the-bank/sources/com/google/common/collect/LinkedListMultimap.java

766 lines
26 KiB
Java
Raw Permalink Normal View History

2024-07-27 18:17:47 +07:00
package com.google.common.collect;
import com.google.common.base.Preconditions;
import com.google.common.collect.Multimaps;
import com.google.common.collect.Sets;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
/* loaded from: classes2.dex */
public class LinkedListMultimap<K, V> extends AbstractMultimap<K, V> implements ListMultimap<K, V>, Serializable {
private static final long serialVersionUID = 0;
private transient Node<K, V> head;
private transient Map<K, KeyList<K, V>> keyToKeyList;
private transient int modCount;
private transient int size;
private transient Node<K, V> tail;
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap, com.google.common.collect.ListMultimap
public /* bridge */ /* synthetic */ Map asMap() {
return super.asMap();
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ boolean containsEntry(Object obj, Object obj2) {
return super.containsEntry(obj, obj2);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap, com.google.common.collect.ListMultimap
public /* bridge */ /* synthetic */ boolean equals(Object obj) {
return super.equals(obj);
}
/* JADX WARN: Multi-variable type inference failed */
@Override // com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ Collection get(Object obj) {
return get((LinkedListMultimap<K, V>) obj);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ int hashCode() {
return super.hashCode();
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ Set keySet() {
return super.keySet();
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ Multiset keys() {
return super.keys();
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ boolean putAll(Multimap multimap) {
return super.putAll(multimap);
}
/* JADX WARN: Multi-variable type inference failed */
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ boolean putAll(Object obj, Iterable iterable) {
return super.putAll(obj, iterable);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ boolean remove(Object obj, Object obj2) {
return super.remove(obj, obj2);
}
/* JADX WARN: Multi-variable type inference failed */
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public /* bridge */ /* synthetic */ Collection replaceValues(Object obj, Iterable iterable) {
return replaceValues((LinkedListMultimap<K, V>) obj, iterable);
}
@Override // com.google.common.collect.AbstractMultimap
public /* bridge */ /* synthetic */ String toString() {
return super.toString();
}
/* JADX INFO: Access modifiers changed from: package-private */
/* loaded from: classes2.dex */
public static final class Node<K, V> extends AbstractMapEntry<K, V> {
final K key;
Node<K, V> next;
Node<K, V> nextSibling;
Node<K, V> previous;
Node<K, V> previousSibling;
V value;
Node(K k, V v) {
this.key = k;
this.value = v;
}
@Override // com.google.common.collect.AbstractMapEntry, java.util.Map.Entry
public final V setValue(V v) {
V v2 = this.value;
this.value = v;
return v2;
}
@Override // com.google.common.collect.AbstractMapEntry, java.util.Map.Entry
public final V getValue() {
return this.value;
}
@Override // com.google.common.collect.AbstractMapEntry, java.util.Map.Entry
public final K getKey() {
return this.key;
}
}
/* JADX INFO: Access modifiers changed from: package-private */
/* loaded from: classes2.dex */
public static class KeyList<K, V> {
int count;
Node<K, V> head;
Node<K, V> tail;
KeyList(Node<K, V> node) {
this.head = node;
this.tail = node;
node.previousSibling = null;
node.nextSibling = null;
this.count = 1;
}
}
public static <K, V> LinkedListMultimap<K, V> create() {
return new LinkedListMultimap<>();
}
public static <K, V> LinkedListMultimap<K, V> create(int i) {
return new LinkedListMultimap<>(i);
}
public static <K, V> LinkedListMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
return new LinkedListMultimap<>(multimap);
}
LinkedListMultimap() {
this(12);
}
private LinkedListMultimap(int i) {
this.keyToKeyList = Platform.newHashMapWithExpectedSize(i);
}
private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
this(multimap.keySet().size());
putAll(multimap);
}
/* JADX INFO: Access modifiers changed from: private */
public Node<K, V> addNode(K k, V v, Node<K, V> node) {
Node<K, V> node2 = new Node<>(k, v);
if (this.head == null) {
this.tail = node2;
this.head = node2;
this.keyToKeyList.put(k, new KeyList<>(node2));
this.modCount++;
} else if (node == null) {
this.tail.next = node2;
node2.previous = this.tail;
this.tail = node2;
KeyList<K, V> keyList = this.keyToKeyList.get(k);
if (keyList == null) {
this.keyToKeyList.put(k, new KeyList<>(node2));
this.modCount++;
} else {
keyList.count++;
Node<K, V> node3 = keyList.tail;
node3.nextSibling = node2;
node2.previousSibling = node3;
keyList.tail = node2;
}
} else {
this.keyToKeyList.get(k).count++;
node2.previous = node.previous;
node2.previousSibling = node.previousSibling;
node2.next = node;
node2.nextSibling = node;
if (node.previousSibling == null) {
this.keyToKeyList.get(k).head = node2;
} else {
node.previousSibling.nextSibling = node2;
}
if (node.previous == null) {
this.head = node2;
} else {
node.previous.next = node2;
}
node.previous = node2;
node.previousSibling = node2;
}
this.size++;
return node2;
}
/* JADX INFO: Access modifiers changed from: private */
public void removeNode(Node<K, V> node) {
if (node.previous != null) {
node.previous.next = node.next;
} else {
this.head = node.next;
}
if (node.next != null) {
node.next.previous = node.previous;
} else {
this.tail = node.previous;
}
if (node.previousSibling == null && node.nextSibling == null) {
this.keyToKeyList.remove(node.key).count = 0;
this.modCount++;
} else {
KeyList<K, V> keyList = this.keyToKeyList.get(node.key);
keyList.count--;
if (node.previousSibling == null) {
keyList.head = node.nextSibling;
} else {
node.previousSibling.nextSibling = node.nextSibling;
}
if (node.nextSibling == null) {
keyList.tail = node.previousSibling;
} else {
node.nextSibling.previousSibling = node.previousSibling;
}
}
this.size--;
}
/* JADX INFO: Access modifiers changed from: private */
public void removeAllNodes(Object obj) {
Iterators.clear(new ValueForKeyIterator(this, obj));
}
/* JADX INFO: Access modifiers changed from: private */
public static void checkElement(Object obj) {
if (obj == null) {
throw new NoSuchElementException();
}
}
/* loaded from: classes2.dex */
class NodeIterator implements ListIterator<Map.Entry<K, V>> {
Node<K, V> current;
int expectedModCount;
Node<K, V> next;
int nextIndex;
Node<K, V> previous;
final LinkedListMultimap this$0;
NodeIterator(LinkedListMultimap linkedListMultimap, int i) {
this.this$0 = linkedListMultimap;
this.expectedModCount = linkedListMultimap.modCount;
int size = linkedListMultimap.size();
Preconditions.checkPositionIndex(i, size);
if (i >= size / 2) {
this.previous = linkedListMultimap.tail;
this.nextIndex = size;
while (i < size) {
previous();
i++;
}
} else {
this.next = linkedListMultimap.head;
while (i > 0) {
next();
i--;
}
}
this.current = null;
}
private void checkForConcurrentModification() {
if (this.this$0.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
@Override // java.util.ListIterator, java.util.Iterator
public boolean hasNext() {
checkForConcurrentModification();
return this.next != null;
}
@Override // java.util.ListIterator, java.util.Iterator
public Node<K, V> next() {
checkForConcurrentModification();
LinkedListMultimap.checkElement(this.next);
Node<K, V> node = this.next;
this.current = node;
this.previous = node;
this.next = node.next;
this.nextIndex++;
return this.current;
}
@Override // java.util.ListIterator, java.util.Iterator
public void remove() {
checkForConcurrentModification();
CollectPreconditions.checkRemove(this.current != null);
Node<K, V> node = this.current;
if (node != this.next) {
this.previous = node.previous;
this.nextIndex--;
} else {
this.next = node.next;
}
this.this$0.removeNode(this.current);
this.current = null;
this.expectedModCount = this.this$0.modCount;
}
@Override // java.util.ListIterator
public boolean hasPrevious() {
checkForConcurrentModification();
return this.previous != null;
}
@Override // java.util.ListIterator
public Node<K, V> previous() {
checkForConcurrentModification();
LinkedListMultimap.checkElement(this.previous);
Node<K, V> node = this.previous;
this.current = node;
this.next = node;
this.previous = node.previous;
this.nextIndex--;
return this.current;
}
@Override // java.util.ListIterator
public void set(Map.Entry<K, V> entry) {
throw new UnsupportedOperationException();
}
@Override // java.util.ListIterator
public void add(Map.Entry<K, V> entry) {
throw new UnsupportedOperationException();
}
void setValue(V v) {
Preconditions.checkState(this.current != null);
this.current.value = v;
}
@Override // java.util.ListIterator
public int previousIndex() {
return this.nextIndex - 1;
}
@Override // java.util.ListIterator
public int nextIndex() {
return this.nextIndex;
}
}
/* loaded from: classes2.dex */
class DistinctKeyIterator implements Iterator<K> {
Node<K, V> current;
int expectedModCount;
Node<K, V> next;
final Set<K> seenKeys;
final LinkedListMultimap this$0;
private DistinctKeyIterator(LinkedListMultimap linkedListMultimap) {
this.this$0 = linkedListMultimap;
this.seenKeys = Sets.newHashSetWithExpectedSize(linkedListMultimap.keySet().size());
this.next = linkedListMultimap.head;
this.expectedModCount = linkedListMultimap.modCount;
}
private void checkForConcurrentModification() {
if (this.this$0.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
@Override // java.util.Iterator
public boolean hasNext() {
checkForConcurrentModification();
return this.next != null;
}
@Override // java.util.Iterator
public K next() {
Node<K, V> node;
checkForConcurrentModification();
LinkedListMultimap.checkElement(this.next);
Node<K, V> node2 = this.next;
this.current = node2;
this.seenKeys.add(node2.key);
do {
node = this.next.next;
this.next = node;
if (node == null) {
break;
}
} while (!this.seenKeys.add(node.key));
return this.current.key;
}
@Override // java.util.Iterator
public void remove() {
checkForConcurrentModification();
CollectPreconditions.checkRemove(this.current != null);
this.this$0.removeAllNodes(this.current.key);
this.current = null;
this.expectedModCount = this.this$0.modCount;
}
}
/* JADX INFO: Access modifiers changed from: package-private */
/* loaded from: classes2.dex */
public class ValueForKeyIterator implements ListIterator<V> {
Node<K, V> current;
final Object key;
Node<K, V> next;
int nextIndex;
Node<K, V> previous;
final LinkedListMultimap this$0;
ValueForKeyIterator(LinkedListMultimap linkedListMultimap, Object obj) {
this.this$0 = linkedListMultimap;
this.key = obj;
KeyList keyList = (KeyList) linkedListMultimap.keyToKeyList.get(obj);
this.next = keyList == null ? null : keyList.head;
}
public ValueForKeyIterator(LinkedListMultimap linkedListMultimap, Object obj, int i) {
this.this$0 = linkedListMultimap;
KeyList keyList = (KeyList) linkedListMultimap.keyToKeyList.get(obj);
int i2 = keyList == null ? 0 : keyList.count;
Preconditions.checkPositionIndex(i, i2);
if (i >= i2 / 2) {
this.previous = keyList == null ? null : keyList.tail;
this.nextIndex = i2;
while (i < i2) {
previous();
i++;
}
} else {
this.next = keyList == null ? null : keyList.head;
while (i > 0) {
next();
i--;
}
}
this.key = obj;
this.current = null;
}
@Override // java.util.ListIterator, java.util.Iterator
public V next() {
LinkedListMultimap.checkElement(this.next);
Node<K, V> node = this.next;
this.current = node;
this.previous = node;
this.next = node.nextSibling;
this.nextIndex++;
return this.current.value;
}
@Override // java.util.ListIterator
public V previous() {
LinkedListMultimap.checkElement(this.previous);
Node<K, V> node = this.previous;
this.current = node;
this.next = node;
this.previous = node.previousSibling;
this.nextIndex--;
return this.current.value;
}
@Override // java.util.ListIterator, java.util.Iterator
public void remove() {
CollectPreconditions.checkRemove(this.current != null);
Node<K, V> node = this.current;
if (node != this.next) {
this.previous = node.previousSibling;
this.nextIndex--;
} else {
this.next = node.nextSibling;
}
this.this$0.removeNode(this.current);
this.current = null;
}
@Override // java.util.ListIterator
public void set(V v) {
Preconditions.checkState(this.current != null);
this.current.value = v;
}
@Override // java.util.ListIterator
public void add(V v) {
this.previous = this.this$0.addNode(this.key, v, this.next);
this.nextIndex++;
this.current = null;
}
@Override // java.util.ListIterator
public int previousIndex() {
return this.nextIndex - 1;
}
@Override // java.util.ListIterator
public int nextIndex() {
return this.nextIndex;
}
@Override // java.util.ListIterator
public boolean hasPrevious() {
return this.previous != null;
}
@Override // java.util.ListIterator, java.util.Iterator
public boolean hasNext() {
return this.next != null;
}
}
@Override // com.google.common.collect.Multimap
public boolean containsKey(Object obj) {
return this.keyToKeyList.containsKey(obj);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public boolean containsValue(Object obj) {
return values().contains(obj);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public boolean put(K k, V v) {
addNode(k, v, null);
return true;
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public List<V> replaceValues(K k, Iterable<? extends V> iterable) {
List<V> copy = getCopy(k);
ValueForKeyIterator valueForKeyIterator = new ValueForKeyIterator(this, k);
Iterator<? extends V> it = iterable.iterator();
while (valueForKeyIterator.hasNext() && it.hasNext()) {
valueForKeyIterator.next();
valueForKeyIterator.set(it.next());
}
while (valueForKeyIterator.hasNext()) {
valueForKeyIterator.next();
valueForKeyIterator.remove();
}
while (it.hasNext()) {
valueForKeyIterator.add(it.next());
}
return copy;
}
private List<V> getCopy(Object obj) {
return Collections.unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(this, obj)));
}
@Override // com.google.common.collect.Multimap
public List<V> removeAll(Object obj) {
List<V> copy = getCopy(obj);
removeAllNodes(obj);
return copy;
}
@Override // com.google.common.collect.Multimap
public void clear() {
this.head = null;
this.tail = null;
this.keyToKeyList.clear();
this.size = 0;
this.modCount++;
}
@Override // com.google.common.collect.Multimap
public List<V> get(K k) {
return new AbstractSequentialList<V>(this, k) { // from class: com.google.common.collect.LinkedListMultimap.1
final LinkedListMultimap this$0;
final Object val$key;
{
this.this$0 = this;
this.val$key = k;
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.List
public int size() {
KeyList keyList = (KeyList) this.this$0.keyToKeyList.get(this.val$key);
if (keyList == null) {
return 0;
}
return keyList.count;
}
@Override // java.util.AbstractSequentialList, java.util.AbstractList, java.util.List
public ListIterator<V> listIterator(int i) {
return new ValueForKeyIterator(this.this$0, this.val$key, i);
}
};
}
@Override // com.google.common.collect.AbstractMultimap
Set<K> createKeySet() {
return new Sets.ImprovedAbstractSet<K>(this) { // from class: com.google.common.collect.LinkedListMultimap.1KeySetImpl
final LinkedListMultimap this$0;
{
this.this$0 = this;
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
public int size() {
return this.this$0.keyToKeyList.size();
}
@Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable, java.util.Set
public Iterator<K> iterator() {
return new DistinctKeyIterator();
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
public boolean contains(Object obj) {
return this.this$0.containsKey(obj);
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
public boolean remove(Object obj) {
return !this.this$0.removeAll(obj).isEmpty();
}
};
}
@Override // com.google.common.collect.AbstractMultimap
Multiset<K> createKeys() {
return new Multimaps.Keys(this);
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public List<V> values() {
return (List) super.values();
}
/* JADX INFO: Access modifiers changed from: package-private */
@Override // com.google.common.collect.AbstractMultimap
public List<V> createValues() {
return new AbstractSequentialList<V>(this) { // from class: com.google.common.collect.LinkedListMultimap.1ValuesImpl
final LinkedListMultimap this$0;
{
this.this$0 = this;
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.List
public int size() {
return this.this$0.size;
}
@Override // java.util.AbstractSequentialList, java.util.AbstractList, java.util.List
public ListIterator<V> listIterator(int i) {
NodeIterator nodeIterator = new NodeIterator(this.this$0, i);
return new TransformedListIterator<Map.Entry<K, V>, V>(this, nodeIterator, nodeIterator) { // from class: com.google.common.collect.LinkedListMultimap.1ValuesImpl.1
final NodeIterator val$nodeItr;
{
this.val$nodeItr = nodeIterator;
}
/* JADX INFO: Access modifiers changed from: package-private */
@Override // com.google.common.collect.TransformedIterator
public V transform(Map.Entry<K, V> entry) {
return entry.getValue();
}
@Override // com.google.common.collect.TransformedListIterator, java.util.ListIterator
public void set(V v) {
this.val$nodeItr.setValue(v);
}
};
}
};
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public List<Map.Entry<K, V>> entries() {
return (List) super.entries();
}
/* JADX INFO: Access modifiers changed from: package-private */
@Override // com.google.common.collect.AbstractMultimap
public List<Map.Entry<K, V>> createEntries() {
return new AbstractSequentialList<Map.Entry<K, V>>(this) { // from class: com.google.common.collect.LinkedListMultimap.1EntriesImpl
final LinkedListMultimap this$0;
{
this.this$0 = this;
}
@Override // java.util.AbstractCollection, java.util.Collection, java.util.List
public int size() {
return this.this$0.size;
}
@Override // java.util.AbstractSequentialList, java.util.AbstractList, java.util.List
public ListIterator<Map.Entry<K, V>> listIterator(int i) {
return new NodeIterator(this.this$0, i);
}
};
}
@Override // com.google.common.collect.AbstractMultimap
Iterator<Map.Entry<K, V>> entryIterator() {
throw new AssertionError("should never be called");
}
@Override // com.google.common.collect.AbstractMultimap
Map<K, Collection<V>> createAsMap() {
return new Multimaps.AsMap(this);
}
private void writeObject(ObjectOutputStream objectOutputStream) throws IOException {
objectOutputStream.defaultWriteObject();
objectOutputStream.writeInt(size());
for (Map.Entry<K, V> entry : entries()) {
objectOutputStream.writeObject(entry.getKey());
objectOutputStream.writeObject(entry.getValue());
}
}
/* JADX WARN: Multi-variable type inference failed */
private void readObject(ObjectInputStream objectInputStream) throws IOException, ClassNotFoundException {
objectInputStream.defaultReadObject();
this.keyToKeyList = CompactLinkedHashMap.create();
int readInt = objectInputStream.readInt();
for (int i = 0; i < readInt; i++) {
put(objectInputStream.readObject(), objectInputStream.readObject());
}
}
@Override // com.google.common.collect.Multimap
public int size() {
return this.size;
}
@Override // com.google.common.collect.AbstractMultimap, com.google.common.collect.Multimap
public boolean isEmpty() {
return this.head == null;
}
}