package com.google.firebase.database.collection;

import com.google.firebase.database.collection.ImmutableSortedMap;
import com.google.firebase.database.collection.LLRBNode;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/* JADX INFO: loaded from: classes3.dex */
public class ArraySortedMap<K, V> extends ImmutableSortedMap<K, V> {
    private final Comparator<K> comparator;
    private final K[] keys;
    private final V[] values;

    public ArraySortedMap(Comparator<K> comparator) {
        this.keys = (K[]) new Object[0];
        this.values = (V[]) new Object[0];
        this.comparator = comparator;
    }

    private static <T> T[] addToArray(T[] tArr, int i6, T t6) {
        T[] tArr2 = (T[]) new Object[tArr.length + 1];
        System.arraycopy(tArr, 0, tArr2, 0, i6);
        tArr2[i6] = t6;
        System.arraycopy(tArr, i6, tArr2, i6 + 1, (r0 - i6) - 1);
        return tArr2;
    }

    public static <A, B, C> ArraySortedMap<A, C> buildFrom(List<A> list, Map<B, C> map, ImmutableSortedMap.Builder.KeyTranslator<A, B> keyTranslator, Comparator<A> comparator) {
        Collections.sort(list, comparator);
        int size = list.size();
        Object[] objArr = new Object[size];
        Object[] objArr2 = new Object[size];
        int i6 = 0;
        for (A a6 : list) {
            objArr[i6] = a6;
            objArr2[i6] = map.get(keyTranslator.translate(a6));
            i6++;
        }
        return new ArraySortedMap<>(comparator, objArr, objArr2);
    }

    private int findKey(K k6) {
        int i6 = 0;
        for (K k7 : this.keys) {
            if (this.comparator.compare(k6, k7) == 0) {
                return i6;
            }
            i6++;
        }
        return -1;
    }

    private int findKeyOrInsertPosition(K k6) {
        int i6 = 0;
        while (true) {
            K[] kArr = this.keys;
            if (i6 >= kArr.length || this.comparator.compare(kArr[i6], k6) >= 0) {
                break;
            }
            i6++;
        }
        return i6;
    }

    public static <K, V> ArraySortedMap<K, V> fromMap(Map<K, V> map, Comparator<K> comparator) {
        return buildFrom(new ArrayList(map.keySet()), map, ImmutableSortedMap.Builder.identityTranslator(), comparator);
    }

    private Iterator<Map.Entry<K, V>> iterator(int i6, boolean z6) {
        return new Iterator<Map.Entry<K, V>>(i6, z6) { // from class: com.google.firebase.database.collection.ArraySortedMap.1
            int currentPos;
            final /* synthetic */ int val$pos;
            final /* synthetic */ boolean val$reverse;

            {
                this.val$pos = i6;
                this.val$reverse = z6;
                this.currentPos = i6;
            }

            @Override // java.util.Iterator
            public boolean hasNext() {
                return this.val$reverse ? this.currentPos >= 0 : this.currentPos < ArraySortedMap.this.keys.length;
            }

            @Override // java.util.Iterator
            public void remove() {
                throw new UnsupportedOperationException("Can't remove elements from ImmutableSortedMap");
            }

            @Override // java.util.Iterator
            public Map.Entry<K, V> next() {
                Object obj = ArraySortedMap.this.keys[this.currentPos];
                Object[] objArr = ArraySortedMap.this.values;
                int i7 = this.currentPos;
                Object obj2 = objArr[i7];
                this.currentPos = this.val$reverse ? i7 - 1 : i7 + 1;
                return new AbstractMap.SimpleImmutableEntry(obj, obj2);
            }
        };
    }

    private static <T> T[] removeFromArray(T[] tArr, int i6) {
        int length = tArr.length - 1;
        T[] tArr2 = (T[]) new Object[length];
        System.arraycopy(tArr, 0, tArr2, 0, i6);
        System.arraycopy(tArr, i6 + 1, tArr2, i6, length - i6);
        return tArr2;
    }

    private static <T> T[] replaceInArray(T[] tArr, int i6, T t6) {
        int length = tArr.length;
        T[] tArr2 = (T[]) new Object[length];
        System.arraycopy(tArr, 0, tArr2, 0, length);
        tArr2[i6] = t6;
        return tArr2;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public boolean containsKey(K k6) {
        return findKey(k6) != -1;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public V get(K k6) {
        int iFindKey = findKey(k6);
        if (iFindKey != -1) {
            return this.values[iFindKey];
        }
        return null;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public Comparator<K> getComparator() {
        return this.comparator;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public K getMaxKey() {
        K[] kArr = this.keys;
        if (kArr.length > 0) {
            return kArr[kArr.length - 1];
        }
        return null;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public K getMinKey() {
        K[] kArr = this.keys;
        if (kArr.length > 0) {
            return kArr[0];
        }
        return null;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public K getPredecessorKey(K k6) {
        int iFindKey = findKey(k6);
        if (iFindKey == -1) {
            throw new IllegalArgumentException("Can't find predecessor of nonexistent key");
        }
        if (iFindKey > 0) {
            return this.keys[iFindKey - 1];
        }
        return null;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public K getSuccessorKey(K k6) {
        int iFindKey = findKey(k6);
        if (iFindKey == -1) {
            throw new IllegalArgumentException("Can't find successor of nonexistent key");
        }
        K[] kArr = this.keys;
        if (iFindKey < kArr.length - 1) {
            return kArr[iFindKey + 1];
        }
        return null;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public void inOrderTraversal(LLRBNode.NodeVisitor<K, V> nodeVisitor) {
        int i6 = 0;
        while (true) {
            K[] kArr = this.keys;
            if (i6 >= kArr.length) {
                return;
            }
            nodeVisitor.visitEntry(kArr[i6], this.values[i6]);
            i6++;
        }
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public int indexOf(K k6) {
        return findKey(k6);
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public ImmutableSortedMap<K, V> insert(K k6, V v3) {
        int iFindKey = findKey(k6);
        if (iFindKey != -1) {
            K[] kArr = this.keys;
            if (kArr[iFindKey] == k6 && this.values[iFindKey] == v3) {
                return this;
            }
            return new ArraySortedMap(this.comparator, replaceInArray(kArr, iFindKey, k6), replaceInArray(this.values, iFindKey, v3));
        }
        if (this.keys.length <= 25) {
            int iFindKeyOrInsertPosition = findKeyOrInsertPosition(k6);
            return new ArraySortedMap(this.comparator, addToArray(this.keys, iFindKeyOrInsertPosition, k6), addToArray(this.values, iFindKeyOrInsertPosition, v3));
        }
        HashMap map = new HashMap(this.keys.length + 1);
        int i6 = 0;
        while (true) {
            K[] kArr2 = this.keys;
            if (i6 >= kArr2.length) {
                map.put(k6, v3);
                return RBTreeSortedMap.fromMap(map, this.comparator);
            }
            map.put(kArr2[i6], this.values[i6]);
            i6++;
        }
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public boolean isEmpty() {
        return this.keys.length == 0;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public Iterator<Map.Entry<K, V>> iteratorFrom(K k6) {
        return iterator(findKeyOrInsertPosition(k6), false);
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public ImmutableSortedMap<K, V> remove(K k6) {
        int iFindKey = findKey(k6);
        if (iFindKey == -1) {
            return this;
        }
        return new ArraySortedMap(this.comparator, removeFromArray(this.keys, iFindKey), removeFromArray(this.values, iFindKey));
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public Iterator<Map.Entry<K, V>> reverseIterator() {
        return iterator(this.keys.length - 1, true);
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public Iterator<Map.Entry<K, V>> reverseIteratorFrom(K k6) {
        int iFindKeyOrInsertPosition = findKeyOrInsertPosition(k6);
        K[] kArr = this.keys;
        return (iFindKeyOrInsertPosition >= kArr.length || this.comparator.compare(kArr[iFindKeyOrInsertPosition], k6) != 0) ? iterator(iFindKeyOrInsertPosition - 1, true) : iterator(iFindKeyOrInsertPosition, true);
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap
    public int size() {
        return this.keys.length;
    }

    @Override // com.google.firebase.database.collection.ImmutableSortedMap, java.lang.Iterable
    public Iterator<Map.Entry<K, V>> iterator() {
        return iterator(0, false);
    }

    private ArraySortedMap(Comparator<K> comparator, K[] kArr, V[] vArr) {
        this.keys = kArr;
        this.values = vArr;
        this.comparator = comparator;
    }
}