From b60ab8e8524b21a48b2440c346b1dd0c6ccc2d85 Mon Sep 17 00:00:00 2001 From: Ben Culkin Date: Sun, 15 Nov 2020 12:29:56 -0500 Subject: Add MinMaxList data type This is a list wrapper that automatically tracks the minimum/maximum element currently in the list --- src/main/java/bjc/esodata/MinMaxList.java | 238 ++++++++++++++++++++++++++ src/test/java/bjc/esodata/MinMaxListTest.java | 52 ++++++ 2 files changed, 290 insertions(+) create mode 100644 src/main/java/bjc/esodata/MinMaxList.java create mode 100644 src/test/java/bjc/esodata/MinMaxListTest.java (limited to 'src') diff --git a/src/main/java/bjc/esodata/MinMaxList.java b/src/main/java/bjc/esodata/MinMaxList.java new file mode 100644 index 0000000..6747831 --- /dev/null +++ b/src/main/java/bjc/esodata/MinMaxList.java @@ -0,0 +1,238 @@ +package bjc.esodata; + +import java.util.*; + +// @FIXME Nov 15th, 2020 Ben Culkin :RecalcMinMax +// Is there some sort of way to avoid having to recalculate these elements when +// that element is removed? +/** + * A list that automatically tracks the minimum & maximum element of a list. + * + * @author Ben Culkin + * + * @param The type of element stored in the list. + * + */ +public class MinMaxList extends AbstractList { + private final List backing; + private final Comparator picker; + + private ValueType minElement; + private boolean recalcMin = false; + + private ValueType maxElement; + private boolean recalcMax = false; + + // Create constructors + + /** + * Create a new min/max list using the given comparator. + * + * @param picker The comparator to use to determine min/max elements. + */ + public MinMaxList(Comparator picker) { + this(picker, new ArrayList<>()); + } + + /** + * Create a new min/max list using the given comparator. + * + * @param picker The comparator to use to determine min/max elements. + * @param values The values to fill the list from. + */ + @SafeVarargs + public MinMaxList(Comparator picker, ValueType... values) { + this(picker); + + for (ValueType value : values) { + add(value); + } + } + /** + * Create a new min/max list using the given comparator. + * + * @param picker The comparator to use to determine min/max elements. + * @param backing The collection to use values from. + */ + public MinMaxList(Comparator picker, Collection backing) { + this(picker, new ArrayList<>(backing)); + } + + /** + * Create a new min/max list using the given comparator. + * + * @param picker The comparator to use to determine min/max elements. + * @param backing The list to use as a backing list. + */ + public MinMaxList(Comparator picker, List backing) { + this.backing = backing; + this.picker = picker; + + calculateBoth(); + } + + @Override + public ValueType get(int index) { + return backing.get(index); + } + + @Override + public ValueType set(int index, ValueType element) { + ValueType oldElement = backing.set(index, element); + + if (minElement == null) { + minElement = element; + } else if (picker.compare(element, minElement) < 0) { + minElement = element; + recalcMin = false; + } else if (oldElement.equals(minElement)) { + minElement = null; + recalcMin = true; + } + + if (maxElement == null) { + maxElement = element; + } else if (picker.compare(element, maxElement) > 0) { + maxElement = element; + recalcMax = false; + } else if (oldElement.equals(maxElement)) { + maxElement = null; + recalcMax = true; + } + + return oldElement; + } + + @Override + public void add(int index, ValueType element) { + backing.add(index, element); + + if (minElement == null) { + minElement = element; + } else if (picker.compare(element, minElement) < 0) { + minElement = element; + recalcMin = false; + } + + if (maxElement == null) { + maxElement = element; + } else if (picker.compare(element, maxElement) > 0) { + maxElement = element; + recalcMax = false; + } + } + + @Override + public ValueType remove(int index) { + ValueType oldElement = backing.remove(index); + + if (oldElement.equals(minElement)) { + minElement = null; + recalcMin = true; + } + + if (oldElement.equals(maxElement)) { + maxElement = null; + recalcMax = true; + } + + return oldElement; + } + + @Override + public int size() { + return backing.size(); + } + + /** + * Get the minimum element currently stored in this list. + * + * @return The minimum element stored in the list. + */ + public ValueType minimum() { + if (recalcMin) calculateMinimum(); + + return minElement; + } + + /** + * Get the maximum element currently stored in this list. + * + * @return The maximum element stored in the list. + */ + public ValueType maximum() { + if (recalcMax) calculateMaximum(); + + return maxElement; + } + + private void calculateMinimum() { + for (ValueType element : backing) { + if (minElement == null) { + minElement = element; + } else if (picker.compare(element, minElement) < 0) { + minElement = element; + } + } + + recalcMin = false; + } + + private void calculateMaximum() { + for (ValueType element : backing) { + if (maxElement == null) { + maxElement = element; + } else if (picker.compare(element, maxElement) > 0) { + maxElement = element; + } + } + + recalcMax = false; + } + + private void calculateBoth() { + for (ValueType element : backing) { + if (minElement == null) { + minElement = element; + } else if (picker.compare(element, minElement) < 0) { + minElement = element; + } + + if (maxElement == null) { + maxElement = element; + } else if (picker.compare(element, maxElement) > 0) { + maxElement = element; + } + } + + recalcMin = false; + recalcMax = false; + } + + @Override + public String toString() { + return String.format("%s (min: %s) (max: %s)", backing, + recalcMin ? "(unknown)" : minElement, + recalcMax ? "(unknown)" : maxElement); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = super.hashCode(); + result = prime * result + Objects.hash(backing, picker); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (!super.equals(obj)) return false; + if (getClass() != obj.getClass()) return false; + + MinMaxList other = (MinMaxList) obj; + + return Objects.equals(backing, other.backing) + && Objects.equals(picker, other.picker); + } +} diff --git a/src/test/java/bjc/esodata/MinMaxListTest.java b/src/test/java/bjc/esodata/MinMaxListTest.java new file mode 100644 index 0000000..08901f0 --- /dev/null +++ b/src/test/java/bjc/esodata/MinMaxListTest.java @@ -0,0 +1,52 @@ +package bjc.esodata; + +import static org.junit.Assert.*; + +import java.util.*; + +import org.junit.*; + +@SuppressWarnings("javadoc") +public class MinMaxListTest { + private final static Comparator intComparator = (lhs, rhs) -> lhs - rhs;; + + @Test + public void minMaxListInitializesMinMax() { + MinMaxList list = new MinMaxList<>(intComparator, + 1, 2, 3, 4, 5); + + assertEquals("List contains 5 elements", 5, list.size()); + + assertEquals("Minimum is 1", 1, (int)list.minimum()); + assertEquals("Maximum is 5", 5, (int)list.maximum()); + } + + @Test + public void minMaxListAddUpdatesMinMax() { + MinMaxList list = new MinMaxList<>(intComparator, + 2, 3, 4); + + assertEquals("Minimum is 2", 2, (int)list.minimum()); + assertEquals("Maximum is 4", 4, (int)list.maximum()); + + list.add(1); + list.add(5); + + assertEquals("Minimum is 1", 1, (int)list.minimum()); + assertEquals("Maximum is 5", 5, (int)list.maximum()); + } + + public void minMaxListRemoveUpdatesMinMax() { + MinMaxList list = new MinMaxList<>(intComparator, + 1, 2, 3, 4, 5); + + assertEquals("Minimum is 1", 1, (int)list.minimum()); + assertEquals("Maximum is 5", 5, (int)list.maximum()); + + list.remove((Integer)1); + list.remove((Integer)5); + + assertEquals("Minimum is 2", 2, (int)list.minimum()); + assertEquals("Maximum is 4", 4, (int)list.maximum()); + } +} -- cgit v1.2.3