From e24654ce7ceaa9a319421b420ea1a97c1b6058e4 Mon Sep 17 00:00:00 2001 From: Samuel Holland Date: Sat, 6 Jan 2018 03:56:52 -0600 Subject: 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 --- .../java/com/wireguard/android/util/Keyed.java | 9 ++ .../java/com/wireguard/android/util/KeyedList.java | 23 +++++ .../android/util/KeyedObservableArrayList.java | 100 +++++++++++++++++++ .../android/util/KeyedObservableList.java | 11 +++ .../util/SortedKeyedObservableArrayList.java | 106 +++++++++++++++++++++ 5 files changed, 249 insertions(+) create mode 100644 app/src/main/java/com/wireguard/android/util/Keyed.java create mode 100644 app/src/main/java/com/wireguard/android/util/KeyedList.java create mode 100644 app/src/main/java/com/wireguard/android/util/KeyedObservableArrayList.java create mode 100644 app/src/main/java/com/wireguard/android/util/KeyedObservableList.java create mode 100644 app/src/main/java/com/wireguard/android/util/SortedKeyedObservableArrayList.java (limited to 'app/src/main/java/com/wireguard/android') 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 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> extends List { + boolean containsAllKeys(Collection 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> + extends ObservableArrayList implements KeyedObservableList { + @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 c) { + if (c.contains(null)) + throw new NullPointerException(); + return super.addAll(c); + } + + @Override + public boolean addAll(final int index, @NonNull final Collection c) { + if (c.contains(null)) + throw new NullPointerException(); + return super.addAll(index, c); + } + + @Override + public boolean containsAllKeys(final Collection 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 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 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> + extends KeyedList, ObservableList { +} 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, + E extends Keyed> extends KeyedObservableArrayList { + + private final transient List 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 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 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, + E extends Keyed> extends AbstractList { + private final SortedKeyedObservableArrayList list; + + private KeyList(final SortedKeyedObservableArrayList list) { + this.list = list; + } + + @Override + public K get(final int index) { + return list.get(index).getKey(); + } + + @Override + public int size() { + return list.size(); + } + } +} -- cgit v1.2.3