diff options
author | Samuel Holland <samuel@sholland.org> | 2018-01-06 03:56:52 -0600 |
---|---|---|
committer | Samuel Holland <samuel@sholland.org> | 2018-01-06 04:09:30 -0600 |
commit | e24654ce7ceaa9a319421b420ea1a97c1b6058e4 (patch) | |
tree | 3fe6d48f5de73750e5745d06517b225c032e0482 | |
parent | 58eedfd6d90a11aa803277b2bfd9eef6dd2258be (diff) |
util: Add a keyed list class and a sorted variant
This is inspired by C#'s KeyedCollection. The sorted variant removes the
need for an observable SortedMap.
Signed-off-by: Samuel Holland <samuel@sholland.org>
5 files changed, 249 insertions, 0 deletions
diff --git a/app/src/main/java/com/wireguard/android/util/Keyed.java b/app/src/main/java/com/wireguard/android/util/Keyed.java new file mode 100644 index 00000000..d79fdb97 --- /dev/null +++ b/app/src/main/java/com/wireguard/android/util/Keyed.java @@ -0,0 +1,9 @@ +package com.wireguard.android.util; + +/** + * Interface for objects that have a identifying key of the given type. + */ + +public interface Keyed<K> { + K getKey(); +} diff --git a/app/src/main/java/com/wireguard/android/util/KeyedList.java b/app/src/main/java/com/wireguard/android/util/KeyedList.java new file mode 100644 index 00000000..4eae34ff --- /dev/null +++ b/app/src/main/java/com/wireguard/android/util/KeyedList.java @@ -0,0 +1,23 @@ +package com.wireguard.android.util; + +import java.util.Collection; +import java.util.List; + +/** + * A list containing elements that can be looked up by key. A {@code KeyedList} cannot contain + * {@code null} elements. + */ + +public interface KeyedList<K, E extends Keyed<? extends K>> extends List<E> { + boolean containsAllKeys(Collection<K> keys); + + boolean containsKey(K key); + + E get(K key); + + E getLast(K key); + + int indexOfKey(K key); + + int lastIndexOfKey(K key); +} diff --git a/app/src/main/java/com/wireguard/android/util/KeyedObservableArrayList.java b/app/src/main/java/com/wireguard/android/util/KeyedObservableArrayList.java new file mode 100644 index 00000000..101f0ba7 --- /dev/null +++ b/app/src/main/java/com/wireguard/android/util/KeyedObservableArrayList.java @@ -0,0 +1,100 @@ +package com.wireguard.android.util; + +import android.databinding.ObservableArrayList; +import android.support.annotation.NonNull; + +import java.util.Collection; +import java.util.ListIterator; +import java.util.Objects; + +/** + * ArrayList that allows looking up elements by some key property. As the key property must always + * be retrievable, this list cannot hold {@code null} elements. Because this class places no + * restrictions on the order or duplication of keys, lookup by key, as well as all list modification + * operations, require O(n) time. + */ + +public class KeyedObservableArrayList<K, E extends Keyed<? extends K>> + extends ObservableArrayList<E> implements KeyedObservableList<K, E> { + @Override + public boolean add(final E e) { + if (e == null) + throw new NullPointerException(); + return super.add(e); + } + + @Override + public void add(final int index, final E e) { + if (e == null) + throw new NullPointerException(); + super.add(index, e); + } + + @Override + public boolean addAll(@NonNull final Collection<? extends E> c) { + if (c.contains(null)) + throw new NullPointerException(); + return super.addAll(c); + } + + @Override + public boolean addAll(final int index, @NonNull final Collection<? extends E> c) { + if (c.contains(null)) + throw new NullPointerException(); + return super.addAll(index, c); + } + + @Override + public boolean containsAllKeys(final Collection<K> keys) { + for (final K key : keys) + if (!containsKey(key)) + return false; + return true; + } + + @Override + public boolean containsKey(final K key) { + return indexOfKey(key) >= 0; + } + + @Override + public E get(final K key) { + final int index = indexOfKey(key); + return index >= 0 ? get(index) : null; + } + + @Override + public E getLast(final K key) { + final int index = lastIndexOfKey(key); + return index >= 0 ? get(index) : null; + } + + @Override + public int indexOfKey(final K key) { + final ListIterator<E> iterator = listIterator(); + while (iterator.hasNext()) { + final int index = iterator.nextIndex(); + if (Objects.equals(iterator.next().getKey(), key)) + return index; + } + return -1; + } + + @Override + public int lastIndexOfKey(final K key) { + final ListIterator<E> iterator = listIterator(size()); + while (iterator.hasPrevious()) { + final int index = iterator.previousIndex(); + if (Objects.equals(iterator.previous().getKey(), key)) + return index; + } + return -1; + } + + @Override + public E set(final int index, final E e) { + if (e == null) + throw new NullPointerException(); + return super.set(index, e); + } +} diff --git a/app/src/main/java/com/wireguard/android/util/KeyedObservableList.java b/app/src/main/java/com/wireguard/android/util/KeyedObservableList.java new file mode 100644 index 00000000..15df0bba --- /dev/null +++ b/app/src/main/java/com/wireguard/android/util/KeyedObservableList.java @@ -0,0 +1,11 @@ +package com.wireguard.android.util; + +import android.databinding.ObservableList; + +/** + * A list that is both keyed and observable. + */ + +public interface KeyedObservableList<K, E extends Keyed<? extends K>> + extends KeyedList<K, E>, ObservableList<E> { +} diff --git a/app/src/main/java/com/wireguard/android/util/SortedKeyedObservableArrayList.java b/app/src/main/java/com/wireguard/android/util/SortedKeyedObservableArrayList.java new file mode 100644 index 00000000..21fcccd3 --- /dev/null +++ b/app/src/main/java/com/wireguard/android/util/SortedKeyedObservableArrayList.java @@ -0,0 +1,106 @@ +package com.wireguard.android.util; + +import android.support.annotation.NonNull; + +import java.util.AbstractList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; + +/** + * KeyedArrayList that enforces uniqueness and sorted order across the set of keys. This class uses + * binary search to improve lookup and replacement times to O(log(n)). However, due to the + * array-based nature of this class, insertion and removal of elements with anything but the largest + * key still require O(n) time. + */ + +public class SortedKeyedObservableArrayList<K extends Comparable<? super K>, + E extends Keyed<? extends K>> extends KeyedObservableArrayList<K, E> { + + private final transient List<K> keyList = new KeyList<>(this); + + @Override + public boolean add(final E e) { + final int insertionPoint = getInsertionPoint(e); + if (insertionPoint < 0) { + // Skipping insertion is non-destructive if the new and existing objects are the same. + if (e == get(-insertionPoint - 1)) + return false; + throw new IllegalArgumentException("Element with same key already exists in list"); + } + super.add(insertionPoint, e); + return true; + } + + @Override + public void add(final int index, final E e) { + final int insertionPoint = getInsertionPoint(e); + if (insertionPoint < 0) + throw new IllegalArgumentException("Element with same key already exists in list"); + if (insertionPoint != index) + throw new IndexOutOfBoundsException("Wrong index given for element"); + super.add(index, e); + } + + @Override + public boolean addAll(@NonNull final Collection<? extends E> c) { + boolean didChange = false; + for (final E e : c) + if (add(e)) + didChange = true; + return didChange; + } + + @Override + public boolean addAll(int index, @NonNull final Collection<? extends E> c) { + for (final E e : c) + add(index++, e); + return true; + } + + private int getInsertionPoint(final E e) { + return -Collections.binarySearch(keyList, e.getKey()) - 1; + } + + @Override + public int indexOfKey(final K key) { + final int index = Collections.binarySearch(keyList, key); + return index >= 0 ? index : -1; + } + + @Override + public int lastIndexOfKey(final K key) { + // There can never be more than one element with the same key in the list. + return indexOfKey(key); + } + + @Override + public E set(final int index, final E e) { + if (e.getKey().compareTo(get(index).getKey()) != 0) { + // Allow replacement if the new key would be inserted adjacent to the replaced element. + final int insertionPoint = getInsertionPoint(e); + if (insertionPoint < index || insertionPoint > index + 1) + throw new IndexOutOfBoundsException("Wrong index given for element"); + } + return super.set(index, e); + } + + private static final class KeyList<K extends Comparable<? super K>, + E extends Keyed<? extends K>> extends AbstractList<K> { + private final SortedKeyedObservableArrayList<K, E> list; + + private KeyList(final SortedKeyedObservableArrayList<K, E> list) { + this.list = list; + } + + @Override + public K get(final int index) { + return list.get(index).getKey(); + } + + @Override + public int size() { + return list.size(); + } + } +} |