summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorSamuel Holland <samuel@sholland.org>2018-01-06 03:56:52 -0600
committerSamuel Holland <samuel@sholland.org>2018-01-06 04:09:30 -0600
commite24654ce7ceaa9a319421b420ea1a97c1b6058e4 (patch)
tree3fe6d48f5de73750e5745d06517b225c032e0482
parent58eedfd6d90a11aa803277b2bfd9eef6dd2258be (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>
-rw-r--r--app/src/main/java/com/wireguard/android/util/Keyed.java9
-rw-r--r--app/src/main/java/com/wireguard/android/util/KeyedList.java23
-rw-r--r--app/src/main/java/com/wireguard/android/util/KeyedObservableArrayList.java100
-rw-r--r--app/src/main/java/com/wireguard/android/util/KeyedObservableList.java11
-rw-r--r--app/src/main/java/com/wireguard/android/util/SortedKeyedObservableArrayList.java106
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();
+ }
+ }
+}