From e401fb037c555eb18db54708037a796523258c32 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Wed, 10 Jul 2019 17:10:51 -0400 Subject: General improvements to stack --- src/main/java/bjc/esodata/QueueStack.java | 6 +- src/main/java/bjc/esodata/SimpleStack.java | 6 +- src/main/java/bjc/esodata/SpaghettiStack.java | 8 +- src/main/java/bjc/esodata/Stack.java | 33 +++-- src/main/java/bjc/esodata/ThresholdSet.java | 28 ++++- src/test/java/bjc/TestUtils.java | 81 ++++++++++++- src/test/java/bjc/esodata/StackTest.java | 152 ++++++++++++++++++++++++ src/test/java/bjc/esodata/ThresholdSetTest.java | 60 ++++++++-- 8 files changed, 337 insertions(+), 37 deletions(-) create mode 100644 src/test/java/bjc/esodata/StackTest.java (limited to 'src') diff --git a/src/main/java/bjc/esodata/QueueStack.java b/src/main/java/bjc/esodata/QueueStack.java index 49476f0..55c6fc4 100644 --- a/src/main/java/bjc/esodata/QueueStack.java +++ b/src/main/java/bjc/esodata/QueueStack.java @@ -29,14 +29,14 @@ public class QueueStack extends Stack { @Override public T pop() { - if(backing.isEmpty()) throw new StackUnderflowException(); + if(backing.isEmpty()) throw new StackUnderflow(); return backing.remove(); } @Override public T top() { - if(backing.isEmpty()) throw new StackUnderflowException(); + if(backing.isEmpty()) throw new StackUnderflow(); return backing.peek(); } @@ -47,7 +47,7 @@ public class QueueStack extends Stack { } @Override - public boolean empty() { + public boolean isEmpty() { return backing.size() == 0; } diff --git a/src/main/java/bjc/esodata/SimpleStack.java b/src/main/java/bjc/esodata/SimpleStack.java index 41b217d..dc6566c 100644 --- a/src/main/java/bjc/esodata/SimpleStack.java +++ b/src/main/java/bjc/esodata/SimpleStack.java @@ -27,14 +27,14 @@ public class SimpleStack extends Stack { @Override public T pop() { - if(backing.isEmpty()) throw new StackUnderflowException(); + if(backing.isEmpty()) throw new StackUnderflow(); return backing.pop(); } @Override public T top() { - if(backing.isEmpty()) throw new StackUnderflowException(); + if(backing.isEmpty()) throw new StackUnderflow(); return backing.peek(); } @@ -45,7 +45,7 @@ public class SimpleStack extends Stack { } @Override - public boolean empty() { + public boolean isEmpty() { return backing.size() == 0; } diff --git a/src/main/java/bjc/esodata/SpaghettiStack.java b/src/main/java/bjc/esodata/SpaghettiStack.java index 9280c28..1b7af25 100644 --- a/src/main/java/bjc/esodata/SpaghettiStack.java +++ b/src/main/java/bjc/esodata/SpaghettiStack.java @@ -37,14 +37,14 @@ class SpaghettiStack extends Stack { @Override public T pop() { - if(backing.empty()) return parent.pop(); + if(backing.isEmpty()) return parent.pop(); return backing.pop(); } @Override public T top() { - if(backing.empty()) return parent.top(); + if(backing.isEmpty()) return parent.top(); return backing.top(); } @@ -55,8 +55,8 @@ class SpaghettiStack extends Stack { } @Override - public boolean empty() { - return backing.empty() && parent.empty(); + public boolean isEmpty() { + return backing.isEmpty() && parent.isEmpty(); } @SuppressWarnings("unchecked") diff --git a/src/main/java/bjc/esodata/Stack.java b/src/main/java/bjc/esodata/Stack.java index 13480a3..f28e882 100644 --- a/src/main/java/bjc/esodata/Stack.java +++ b/src/main/java/bjc/esodata/Stack.java @@ -1,13 +1,14 @@ package bjc.esodata; -import java.util.ArrayList; -import java.util.List; -import java.util.function.Consumer; +import java.util.*; + +import java.util.function.*; /* * @TODO 10/11/17 Ben Culkin :StackCombinators * Implement more combinators for the stack. */ + /** * A stack, with support for forth/factor style stack combinators. * @@ -15,7 +16,7 @@ import java.util.function.Consumer; *

Stack underflow

*

* NOTE: In general, using any operation that attempts to remove more data from - * the stack than exists will cause a {@link StackUnderflowException} to be + * the stack than exists will cause a {@link StackUnderflow} to be * thrown. Check the size of the stack if you want to avoid this. *

*

@@ -32,7 +33,7 @@ public abstract class Stack { * * @author EVE */ - public static class StackUnderflowException extends RuntimeException { + public static class StackUnderflow extends RuntimeException { /* The ID of the exception */ private static final long serialVersionUID = 1423867176204571539L; } @@ -45,6 +46,18 @@ public abstract class Stack { */ public abstract void push(T elm); + /** + * Push multiple elements onto the stack. + * + * @param elms + * The elements to insert. + */ + public void pushAll(T... elms) { + for (T elm : elms) { + push(elm); + } + } + /** * Pop an element off of the stack. * @@ -72,7 +85,9 @@ public abstract class Stack { * * @return Whether or not the stack is empty. */ - public abstract boolean empty(); + public boolean isEmpty() { + return size() == 0; + } /** * Create a spaghetti stack branching off of this one. @@ -136,10 +151,10 @@ public abstract class Stack { final List lst = new ArrayList<>(n); for(int i = n; i > 0; i--) { - lst.set(i - 1, pop()); + lst.add(0, pop()); } - for(int i = 0; i < m; i++) { + for(int i = 0; i <= m; i++) { for(final T elm : lst) { push(elm); } @@ -153,7 +168,7 @@ public abstract class Stack { * The number of items to duplicate. */ public void dup(final int n) { - multidup(n, 2); + multidup(n, 1); } /** Duplicate the top item on the stack. */ diff --git a/src/main/java/bjc/esodata/ThresholdSet.java b/src/main/java/bjc/esodata/ThresholdSet.java index bc1b517..245eb5f 100644 --- a/src/main/java/bjc/esodata/ThresholdSet.java +++ b/src/main/java/bjc/esodata/ThresholdSet.java @@ -57,7 +57,7 @@ public class ThresholdSet { // Will throw a ClassCastException if you give us something bad. KeyType k = (KeyType)o; - int ret = ThresholdSet.this.remove(k); + int ret = ThresholdSet.this.contains(k); // The object is set-visible if (ret == 1) return true; @@ -235,6 +235,32 @@ public class ThresholdSet { return new SetView(); } + /** + * Static threshold set constructor. + * + * @param keys + * The initial keys to add to the threshold set. + */ + public static ThresholdSet TS(KType... keys) { + ThresholdSet ts = new ThresholdSet<>(); + + ts.addKeys(keys); + + return ts; + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + + sb.append("Set: "); + sb.append(keySet); + sb.append("\nMap: "); + sb.append(keyMap); + + return sb.toString(); + } + // Implementation methods for setView int setSize() { diff --git a/src/test/java/bjc/TestUtils.java b/src/test/java/bjc/TestUtils.java index 3c2efa7..a8cbf43 100644 --- a/src/test/java/bjc/TestUtils.java +++ b/src/test/java/bjc/TestUtils.java @@ -1,10 +1,14 @@ package bjc; -import java.util.Iterator; -import java.util.List; +import java.util.*; import static org.junit.Assert.*; +/** + * Utility methods for doing testing + * + * @author Ben Culkin + */ public class TestUtils { /** * Assert an iterator provides a particular sequence of values. @@ -16,8 +20,15 @@ public class TestUtils { */ @SafeVarargs public static void assertIteratorEquals(Iterator src, T... vals) { - for (T val : vals) { - assertEquals(val, src.next()); + for (int i = 0; i < vals.length; i++) { + if (src.hasNext()) { + assertEquals(vals[i], src.next()); + } else { + String msg = String.format("not enough values: got %d, wanted %d", + i, vals.length); + + assertTrue(msg, false); + } } } @@ -46,6 +57,68 @@ public class TestUtils { assertEquals("iterator not exhausted", hasMore, src.hasNext()); } + /** + * Assert an iterator provides a particular sequence of values. + * + * @param src + * The iterator to pull values from. + * @param vals + * The values to expect from the iterator. + */ + @SafeVarargs + public static void assertIteratorSet(Iterator src, T... vals) { + Set s1 = new HashSet<>(); + Set s2 = new HashSet<>(); + + for (int i = 0; i < vals.length; i++) { + if (src.hasNext()) { + s1.add(vals[i]); + s2.add(src.next()); + } else { + String msg = String.format("not enough values: got %d, wanted %d", + i, vals.length); + + assertTrue(msg, false); + } + } + + assertEquals(s1, s2); + } + + /** + * Assert an iterator provides a particular sequence of values. + * + * @param src + * The iterator to pull values from. + * @param hasMore + * The expected value of hasNext for the iterator. + * @param vals + * The values to expect from the iterator. + */ + @SafeVarargs + public static void assertIteratorSet(boolean hasMore, Iterator src, T... vals) { + /* + * @NOTE + * + * Even though it's awkward, the boolean has to come first. + * Otherwise, there are cases where the compiler will get + * confused as to what the right value for T is, and be unable + * to pick an overload. + */ + assertIteratorSet(src, vals); + + assertEquals("iterator not exhausted", hasMore, src.hasNext()); + } + + /** + * Assert that a list contains a certain set of values. + * + * @param src + * The list to read values from. + * + * @param exps + * The values to expect in the list. + */ @SafeVarargs public static void assertListEquals(List src, T... exps) { assertEquals(exps.length, src.size()); diff --git a/src/test/java/bjc/esodata/StackTest.java b/src/test/java/bjc/esodata/StackTest.java new file mode 100644 index 0000000..568e6ea --- /dev/null +++ b/src/test/java/bjc/esodata/StackTest.java @@ -0,0 +1,152 @@ +package bjc.esodata; + +import org.junit.Test; + +import bjc.TestUtils; + +import java.util.*; + +import static bjc.TestUtils.*; + +import static org.junit.Assert.*; + +/** + * Tests of Stack. + * + * @author Ben Culkin + */ +public class StackTest { + @Test + public void testBasic() { + Stack st = new SimpleStack<>(); + + assertEquals(0, st.size()); + + st.push("a"); + assertEquals(1, st.size()); + + assertEquals("a", st.top()); + assertEquals(1, st.size()); + + assertEquals("a", st.pop()); + assertEquals(0, st.size()); + assertTrue(st.isEmpty()); + } + + @Test + public void testSpaghetti() { + Stack st = new SimpleStack<>(); + + st.pushAll("a", "b", "c"); + + Stack spst1 = st.spaghettify(); + Stack spst2 = st.spaghettify(); + + // st should be [a, b, c] + // spst1 should be [[a, b, c]] + // spst2 should be [[a, b, c]] + + assertEquals("c", st.top()); + assertEquals("c", spst1.top()); + assertEquals("c", spst2.top()); + + assertEquals(3, st.size()); + assertEquals(3, spst1.size()); + assertEquals(3, spst2.size()); + + st.push("d"); + spst1.push("e"); + spst2.push("f"); + + // st should be [a, b, c, d] + // spst1 should be [[a, b, c, d], e] + // spst2 should be [[a, b, c, d], f] + + assertEquals("d", st.top()); + assertEquals("e", spst1.top()); + assertEquals("f", spst2.top()); + + assertEquals(4, st.size()); + assertEquals(5, spst1.size()); + assertEquals(5, spst2.size()); + + spst1.pop(); + + // st should be [a, b, c] + // spst1 should be [[a, b, c]] + // spst2 should be [[a, b, c], f] + + assertEquals("d", spst1.pop()); + assertEquals("c", st.top()); + + assertEquals(3, st.size()); + assertEquals(3, spst1.size()); + assertEquals(4, spst2.size()); + } + + @Test + public void testBasicComb() { + Stack st = new SimpleStack<>(); + + st.pushAll("a", "b", "c", "d"); + + st.drop(); + + // stack should be [a, b, c] + + assertEquals("c", st.top()); + assertEquals(3, st.size()); + + st.drop(2); + + // stack should be [a] + + assertEquals("a", st.top()); + assertEquals(1, st.size()); + + st.pushAll("b", "c", "d"); + + st.nip(); + st.nip(); + + // stack should be [a, d] + assertEquals("d", st.top()); + assertEquals(2, st.size()); + + st.pop(); + + assertEquals("a", st.top()); + assertEquals(1, st.size()); + + st.multidup(1, 1); + + // stack should be [a, a] + assertEquals("a", st.top()); + assertEquals(2, st.size()); + + st.pushAll("b", "c"); + + st.multidup(3, 1); + + // stack should be [a, a, b, c, a, b, c] + assertEquals("c", st.top()); + assertEquals(7, st.size()); + + st.pop(); + assertEquals("b", st.pop()); + assertEquals("a", st.pop()); + assertEquals("c", st.top()); + + // stack should be [a, a, b, c] + + st.dup(); + assertEquals("c", st.top()); + assertEquals(5, st.size()); + + // stack should be [a, a, b, c, c] + assertEquals("c", st.pop()); + assertEquals(4, st.size()); + + // stack should be [a, a, b, c] + } +} diff --git a/src/test/java/bjc/esodata/ThresholdSetTest.java b/src/test/java/bjc/esodata/ThresholdSetTest.java index b37f866..6995ad8 100644 --- a/src/test/java/bjc/esodata/ThresholdSetTest.java +++ b/src/test/java/bjc/esodata/ThresholdSetTest.java @@ -3,11 +3,13 @@ package bjc.esodata; import org.junit.Test; import bjc.TestUtils; -import bjc.esodata.ThresholdSet; -import java.util.Iterator; +import java.util.*; import static bjc.TestUtils.*; + +import static bjc.esodata.ThresholdSet.*; + import static org.junit.Assert.*; /** @@ -18,29 +20,61 @@ import static org.junit.Assert.*; public class ThresholdSetTest { @Test public void testAdd() { - ThresholdSet thst = new ThresholdSet<>(); - - thst.addKeys("a", "b"); + ThresholdSet thst = TS("a", "b"); - assertIteratorEquals(false, thst.setView().iterator(), "a", "b"); + assertIteratorSet(false, thst.setView().iterator(), "a", "b"); + assertEquals(thst.setSize(), 2); } @Test public void testAddMulti() { - ThresholdSet thst = new ThresholdSet<>(); + ThresholdSet thst = TS("a", "b", "a"); - thst.addKeys("a", "b", "a"); + assertIteratorSet(false, thst.setView().iterator(), "b"); + assertEquals(thst.setSize(), 1); + } - assertIteratorEquals(false, thst.setView().iterator(), "b"); + @Test + public void testAddMulti2() { + ThresholdSet thst = TS("a", "b"); + thst.add("a"); + + assertIteratorSet(false, thst.setView().iterator(), "b"); + assertEquals(thst.setSize(), 1); + } + + @Test + public void testContains() { + ThresholdSet thst = TS("1", "2", "2", "x", "z"); + + int[] exps = new int[] {1, 2, -1}; + assertArrayEquals(exps, thst.containsKeys("1", "2", "y")); } @Test public void testRemoveMulti() { - ThresholdSet thst = new ThresholdSet<>(); + ThresholdSet thst = TS("a", "a", "b"); + + thst.remove("a"); + + assertIteratorSet(false, thst.setView().iterator(), "a", "b"); + assertEquals(2, thst.setSize()); + + thst.remove("a"); + + assertIteratorSet(false, thst.setView().iterator(), "b"); + assertEquals(1, thst.setSize()); + } + + @Test + public void testSetTransparency() { + ThresholdSet thst = TS("a", "b", "c"); - thst.addKeys("a", "a", "b"); - thst.removeKeys("a"); + thst.setView().add("b"); + assertIteratorSet(false, thst.setView().iterator(), "a", "c"); + assertEquals(2, thst.setView().size()); - assertIteratorEquals(false, thst.setView().iterator(), "a", "b"); + thst.setView().remove("c"); + assertIteratorSet(false, thst.setView().iterator(), "a"); } } -- cgit v1.2.3