From 94acba30fd33fab513ae9f4c8816af0b9c7d497a Mon Sep 17 00:00:00 2001 From: afflux Date: Mon, 3 Nov 2008 02:14:11 -0500 Subject: [PATCH] meaningless comment --- ArachnidRocketgum/src/net/kezvh/two/Go.java | 2 +- .../graph/TestSingleSourceShortestPath.java | 93 ++++- .../Map2Test.java => DualMap/DualMapTest.java} | 56 ++- .../kezvh/collections/DualMap/HashDualMapTest.java | 27 ++ .../net/kezvh/collections/Map2/HashMap2Test.java | 24 -- .../directed/GraphWithEdgeValuesTemplate.java | 54 +-- .../graphs/directed/GraphWithValuesTemplate.java | 28 +- .../directed/HashDirectedGraphSetBuilder.java | 4 +- .../net/kezvh/algorithms/graph/Dijkstra.java | 76 +++-- .../algorithms/graph/SingleSourceShortestPath.java | 12 +- .../kezvh/collections/CollectionsUtilities.java | 205 ++++++----- .../AbstractDualMap.java} | 42 +-- .../{Map2/Map2.java => DualMap/DualMap.java} | 35 +- .../HashMap2.java => DualMap/HashDualMap.java} | 340 +++++++++--------- .../net/kezvh/collections/IntegerRange.java | 9 + KezvhLib/src-lib/net/kezvh/collections/Range.java | 54 +-- .../net/kezvh/collections/TreeIterator.java | 23 +- .../directed/AdjacencyCollectionDirectedGraph.java | 378 +++++++++++++++++++++ ...dGraphSet.java => GenericDirectedGraphSet.java} | 20 +- .../graphs/directed/HashDirectedGraph.java | 33 +- .../collections/graphs/directed/WrappedKeySet.java | 232 +++++++++++++ .../net/kezvh/collections/heaps/PairingHeap.java | 13 +- .../net/kezvh/collections/text/TrieMap.java | 62 ++-- .../AbstractUnmodifiableCollection.java | 25 +- .../kezvh/collections/views/CollectionView.java | 15 +- .../views/ConditionalCollectionView.java | 3 +- .../net/kezvh/collections/views/MapAsView.java | 5 +- .../src-lib/net/kezvh/functional/Operations.java | 234 +++++++++++++ .../src-lib/net/kezvh/functional/lambda/L1.java | 85 +---- .../src-lib/net/kezvh/functional/lambda/L2.java | 49 +-- .../net/kezvh/functional/lambda/Operations.java | 140 -------- .../net/kezvh/patterns/AbstractFactory.java | 4 +- 32 files changed, 1611 insertions(+), 771 deletions(-) rename KezvhLib/src-junit/net/kezvh/collections/{Map2/Map2Test.java => DualMap/DualMapTest.java} (70%) create mode 100644 KezvhLib/src-junit/net/kezvh/collections/DualMap/HashDualMapTest.java delete mode 100644 KezvhLib/src-junit/net/kezvh/collections/Map2/HashMap2Test.java rename KezvhLib/src-lib/net/kezvh/collections/{Map2/AbstractMap2.java => DualMap/AbstractDualMap.java} (69%) rename KezvhLib/src-lib/net/kezvh/collections/{Map2/Map2.java => DualMap/DualMap.java} (96%) rename KezvhLib/src-lib/net/kezvh/collections/{Map2/HashMap2.java => DualMap/HashDualMap.java} (78%) create mode 100644 KezvhLib/src-lib/net/kezvh/collections/graphs/directed/AdjacencyCollectionDirectedGraph.java rename KezvhLib/src-lib/net/kezvh/collections/graphs/directed/{HashDirectedGraphSet.java => GenericDirectedGraphSet.java} (86%) create mode 100644 KezvhLib/src-lib/net/kezvh/collections/graphs/directed/WrappedKeySet.java create mode 100644 KezvhLib/src-lib/net/kezvh/functional/Operations.java rewrite KezvhLib/src-lib/net/kezvh/functional/lambda/L1.java (85%) rewrite KezvhLib/src-lib/net/kezvh/functional/lambda/L2.java (61%) delete mode 100644 KezvhLib/src-lib/net/kezvh/functional/lambda/Operations.java diff --git a/ArachnidRocketgum/src/net/kezvh/two/Go.java b/ArachnidRocketgum/src/net/kezvh/two/Go.java index 7694cf1..fa042dc 100644 --- a/ArachnidRocketgum/src/net/kezvh/two/Go.java +++ b/ArachnidRocketgum/src/net/kezvh/two/Go.java @@ -1,5 +1,5 @@ /** - * + * */ package net.kezvh.two; diff --git a/KezvhLib/src-junit/net/kezvh/algorithms/graph/TestSingleSourceShortestPath.java b/KezvhLib/src-junit/net/kezvh/algorithms/graph/TestSingleSourceShortestPath.java index 3f92599..6c04141 100755 --- a/KezvhLib/src-junit/net/kezvh/algorithms/graph/TestSingleSourceShortestPath.java +++ b/KezvhLib/src-junit/net/kezvh/algorithms/graph/TestSingleSourceShortestPath.java @@ -1,5 +1,7 @@ package net.kezvh.algorithms.graph; +import java.util.Comparator; + import junit.framework.Assert; import junit.framework.TestCase; import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValues; @@ -14,14 +16,24 @@ import org.junit.Test; /** * @author mjacob - * */ public abstract class TestSingleSourceShortestPath extends TestCase { private final DirectedGraphWithEdgeValuesBuilder GRAPH_BUILDER = new HashDirectedGraphSetBuilder(); private final AbstractFactory> HEAP_MAKER = new AbstractFactory>() { @Override public Heap create() throws net.kezvh.patterns.AbstractFactory.CreationFailedException { - return new PairingHeap(); + return new PairingHeap(new Comparator() { + public int compare(final Integer o1, final Integer o2) { + if (o1.equals(-1)) { + if (o2.equals(-1)) + return 0; + return 1; + } else if (o2.equals(-1)) + return -1; + else + return o1.compareTo(o2); + } + }); } }; @@ -38,8 +50,83 @@ public abstract class TestSingleSourceShortestPath extends TestCase { */ @Test public void testCreate() throws Exception { - final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.TRIVIAL_GRAPH); + final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.TRIVIAL); final SingleSourceShortestPath it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER); Assert.assertNotNull(it); } + + /** + * @throws Exception might throw an exception + */ + @Test + public void testTrivial() throws Exception { + final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.TRIVIAL); + final SingleSourceShortestPath it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER); + final Path path = it.getShortestPath(1); + Assert.assertNotNull(path); + Assert.assertEquals(1, path.size()); + Assert.assertEquals(0, path.getLength()); + } + + /** + * @throws Exception might throw an exception + */ + @Test + public void testSimple() throws Exception { + final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.SIMPLE); + final SingleSourceShortestPath it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER); + + Assert.assertTrue(it.connected(2)); + + final Path path = it.getShortestPath(1); + Assert.assertNotNull(path); + Assert.assertEquals(1, path.size()); + Assert.assertEquals(0, path.getLength()); + final Path path2 = it.getShortestPath(2); + Assert.assertNotNull(path2); + Assert.assertEquals(path2.toString(), 2, path2.size()); + Assert.assertEquals(1, path2.getLength()); + } + + /** + * @throws Exception might throw an exception + */ + @Test + public void testComplete() throws Exception { + final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.COMPLETE); + final SingleSourceShortestPath it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER); + + for (int i = 0; i < 16; i++) { + Assert.assertTrue(it.connected(i)); + final Path path = it.getShortestPath(i); + Assert.assertNotNull(path); + if (i == 1) { + Assert.assertEquals(i + " " + path.size() + " " + path, 1, path.size()); + Assert.assertEquals(i + " " + path.size() + " " + path, 0, path.getLength()); + } else { + Assert.assertEquals(i + " ", 2, path.size()); + Assert.assertEquals(i + " ", 1, path.getLength()); + } + } + } + + /** + * @throws Exception might throw an exception + */ + @Test + public void testLinear() throws Exception { + final DirectedGraphWithEdgeValues graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.LINEAR); + final SingleSourceShortestPath it = this.getSingleSourceShortedPath(graph, 0, this.HEAP_MAKER); + + for (int i = 0; i < 100; i++) { + Assert.assertTrue("node " + i + " in graph + ", graph.contains(i)); + if (i != 99) + Assert.assertTrue("edge " + i + " " + (i + 1) + " is in graph", graph.containsEdge(i, i + 1)); + Assert.assertTrue("node " + i + " not connected?", it.connected(i)); + final Path path = it.getShortestPath(i); + Assert.assertNotNull(path); + Assert.assertEquals(i + " ", i + 1, path.size()); + Assert.assertEquals(i + " ", i, path.getLength()); + } + } } diff --git a/KezvhLib/src-junit/net/kezvh/collections/Map2/Map2Test.java b/KezvhLib/src-junit/net/kezvh/collections/DualMap/DualMapTest.java similarity index 70% rename from KezvhLib/src-junit/net/kezvh/collections/Map2/Map2Test.java rename to KezvhLib/src-junit/net/kezvh/collections/DualMap/DualMapTest.java index 906de2d..0350d49 100644 --- a/KezvhLib/src-junit/net/kezvh/collections/Map2/Map2Test.java +++ b/KezvhLib/src-junit/net/kezvh/collections/DualMap/DualMapTest.java @@ -1,10 +1,9 @@ /** * */ -package net.kezvh.collections.Map2; +package net.kezvh.collections.DualMap; import java.util.Collection; -import java.util.Iterator; import java.util.Map; import junit.framework.Assert; @@ -15,21 +14,21 @@ import org.junit.Test; /** * @author afflux */ -public abstract class Map2Test extends TestCase { +public abstract class DualMapTest extends TestCase { /** * @param COMMENT * @param COMMENT * @param COMMENT * @return COMMENT */ - protected abstract Map2 createMap2(); + protected abstract DualMap createMap2(); /** * */ @Test public void testCreate() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); Assert.assertNotNull(it); } @@ -38,7 +37,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void testPut() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); final Integer previous = it.put(1, 2, 3); Assert.assertNull(previous); } @@ -48,7 +47,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void testReput() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); it.put(1, 2, 3); final int previous = it.put(1, 2, 4); Assert.assertEquals(3, previous); @@ -61,7 +60,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void testRemove() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); it.put(1, 2, 3); final int previous = it.remove(1, 2); Assert.assertEquals(3, previous); @@ -72,7 +71,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void testSize() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 4; k++) { @@ -93,7 +92,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void test1WayMapSize() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 4; k++) @@ -110,7 +109,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void test1WayMapContents() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 4; k++) @@ -130,7 +129,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void test1WayMapModifications() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 4; k++) @@ -151,7 +150,7 @@ public abstract class Map2Test extends TestCase { */ @Test public void testRemove0() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) it.put(i, j, 10 * i + j); @@ -172,24 +171,21 @@ public abstract class Map2Test extends TestCase { */ @Test public void testRemove1() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) it.put(i, j, 10 * i + j); Assert.assertEquals(100, it.size()); - for (int i = 0; i < 10; i++) - System.out.println(it.get1(i).size()); final Collection> firstRow = it.remove1(1); + for (int i = 0; i < 10; i++) + if (i == 1) + Assert.assertNull("" + i, it.get1(i)); + else + Assert.assertEquals("" + i, 10, it.get1(i).size()); Assert.assertEquals(10, firstRow.size()); Assert.assertEquals(90, it.size()); Assert.assertEquals(9, it.get2(1).size()); - final Iterator> iterator = firstRow.iterator(); - for (int i = 0; i < 10; i++) { - final Map.Entry next = iterator.next(); - Assert.assertEquals(i, (int) next.getKey()); - Assert.assertEquals(i + 10, (int) next.getValue()); - } } /** @@ -197,18 +193,20 @@ public abstract class Map2Test extends TestCase { */ @Test public void testRemove2() { - final Map2 it = this.createMap2(); + final DualMap it = this.createMap2(); for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) it.put(j, i, 10 * i + j); + Assert.assertEquals(100, it.size()); final Collection> firstRow = it.remove2(1); + for (int i = 0; i < 10; i++) + if (i == 1) + Assert.assertNull("" + i, it.get2(i)); + else + Assert.assertEquals("" + i, 10, it.get2(i).size()); Assert.assertEquals(10, firstRow.size()); - final Iterator> iterator = firstRow.iterator(); - for (int i = 0; i < 10; i++) { - final Map.Entry next = iterator.next(); - Assert.assertEquals(i, (int) next.getKey()); - Assert.assertEquals(i + 10, (int) next.getValue()); - } + Assert.assertEquals(90, it.size()); + Assert.assertEquals(9, it.get1(1).size()); } } diff --git a/KezvhLib/src-junit/net/kezvh/collections/DualMap/HashDualMapTest.java b/KezvhLib/src-junit/net/kezvh/collections/DualMap/HashDualMapTest.java new file mode 100644 index 0000000..3b2b95e --- /dev/null +++ b/KezvhLib/src-junit/net/kezvh/collections/DualMap/HashDualMapTest.java @@ -0,0 +1,27 @@ +/** + * + */ +package net.kezvh.collections.DualMap; + +import net.kezvh.collections.DualMap.DualMap; +import net.kezvh.collections.DualMap.HashDualMap; + + +/** + * @author afflux + */ +public class HashDualMapTest extends DualMapTest { + + /** + * @see net.kezvh.collections.DualMap.DualMapTest#createMap2() + * @param COMMENT + * @param COMMENT + * @param COMMENT + * @return COMMENT + */ + @Override + protected DualMap createMap2() { + return new HashDualMap(); + } + +} diff --git a/KezvhLib/src-junit/net/kezvh/collections/Map2/HashMap2Test.java b/KezvhLib/src-junit/net/kezvh/collections/Map2/HashMap2Test.java deleted file mode 100644 index b92a5f9..0000000 --- a/KezvhLib/src-junit/net/kezvh/collections/Map2/HashMap2Test.java +++ /dev/null @@ -1,24 +0,0 @@ -/** - * - */ -package net.kezvh.collections.Map2; - - -/** - * @author afflux - */ -public class HashMap2Test extends Map2Test { - - /** - * @see net.kezvh.collections.Map2.Map2Test#createMap2() - * @param COMMENT - * @param COMMENT - * @param COMMENT - * @return COMMENT - */ - @Override - protected Map2 createMap2() { - return new HashMap2(); - } - -} diff --git a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithEdgeValuesTemplate.java b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithEdgeValuesTemplate.java index ec9a417..26365a5 100755 --- a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithEdgeValuesTemplate.java +++ b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithEdgeValuesTemplate.java @@ -8,23 +8,25 @@ import java.util.Arrays; import java.util.Collections; import java.util.List; -import net.kezvh.collections.IntegerRange; -import net.kezvh.collections.Map2.HashMap2; -import net.kezvh.collections.Map2.Map2; +import net.kezvh.collections.CollectionsUtilities; +import net.kezvh.collections.DualMap.DualMap; +import net.kezvh.collections.DualMap.HashDualMap; +import net.kezvh.functional.Operations; /** * @author mjacob - * */ public enum GraphWithEdgeValuesTemplate { /** - * + * nodes: [] + * edges: [] */ - EMPTY_GRAPH(new ArrayList(), new HashMap2()), + EMPTY(new ArrayList(), new HashDualMap()), /** - * + * nodes: [0..15] + * edges: all on [0..7], all on [8..15] (weight 1) */ - DISCONECTED_GRAPH(new IntegerRange(0, 16), new HashMap2() { + DISCONECTED(CollectionsUtilities.range(0, 16, Operations.INTEGER_INCREMENTER), new HashDualMap() { { for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) @@ -36,49 +38,55 @@ public enum GraphWithEdgeValuesTemplate { } }), /** - * + * nodes: [0..15] + * edges: all (weight 1) */ - COMPLETE_GRAPH(new IntegerRange(0, 16), new HashMap2() { + COMPLETE(CollectionsUtilities.range(0, 16, Operations.INTEGER_INCREMENTER), new HashDualMap() { { for (int i = 0; i < 16; i++) for (int j = 0; j < 16; j++) - this.put(i, j, 1); + if (i != j) + this.put(i, j, 1); } }), /** - * + * nodes: [0..99] + * edges: [i => (i + 1) % 100] (weight 1) */ - CIRCULAR_GRAPH(new IntegerRange(0, 100), new HashMap2() { + CIRCULAR(CollectionsUtilities.range(0, 100, Operations.INTEGER_INCREMENTER), new HashDualMap() { { for (int i = 0; i < 100; i++) this.put(i, (i + 1) % 100, 1); } }), /** - * + * nodes: [0..99] + * edges: [i => i + 1] (weight 1) */ - LINEAR_GRAPH(new IntegerRange(0, 100), new HashMap2() { + LINEAR(CollectionsUtilities.range(0, 100, Operations.INTEGER_INCREMENTER), new HashDualMap() { { for (int i = 0; i < 99; i++) this.put(i, i + 1, 1); } }), /** - * + * nodes: [1,2] + * edges: [1 => 2] (weight 1) */ - SIMPLE_GRAPH(Arrays.asList(1, 2), new HashMap2() { + SIMPLE(Arrays.asList(1, 2), new HashDualMap() { { - this.put(1, 2, 100); + this.put(1, 2, 1); } }), /** - * + * nodes: [1] + * edges: [] */ - TRIVIAL_GRAPH(Collections.singletonList(1), new HashMap2()), ; + TRIVIAL(Collections.singletonList(1), new HashDualMap()), ; private final List nodes; - private final HashMap2 edges; + private final HashDualMap edges; - GraphWithEdgeValuesTemplate(final List nodes, final HashMap2 edges) { + GraphWithEdgeValuesTemplate(final List nodes, final HashDualMap edges) { this.nodes = nodes; this.edges = edges; } @@ -87,7 +95,7 @@ public enum GraphWithEdgeValuesTemplate { return this.nodes; } - Map2 getEdges() { + DualMap getEdges() { return this.edges; } } \ No newline at end of file diff --git a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithValuesTemplate.java b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithValuesTemplate.java index 750ef10..e4ac5a9 100755 --- a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithValuesTemplate.java +++ b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/GraphWithValuesTemplate.java @@ -9,11 +9,11 @@ import java.util.Map; import java.util.Set; import net.kezvh.collections.IntegerRange; -import net.kezvh.collections.Map2.HashMap2; -import net.kezvh.collections.Map2.Map2; +import net.kezvh.collections.DualMap.DualMap; +import net.kezvh.collections.DualMap.HashDualMap; import net.kezvh.collections.views.MapAsView; +import net.kezvh.functional.Operations; import net.kezvh.functional.lambda.L1; -import net.kezvh.functional.lambda.Operations; /** * @author mjacob @@ -23,11 +23,11 @@ public enum GraphWithValuesTemplate { /** * */ - EMPTY_GRAPH(new HashMap(), new HashMap2()), + EMPTY_GRAPH(new HashMap(), new HashDualMap()), /** * */ - DISCONECTED_GRAPH(new IntegerRange(0, 16), new HashMap2() { + DISCONECTED_GRAPH(new IntegerRange(0, 16), new HashDualMap() { { for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) @@ -41,7 +41,7 @@ public enum GraphWithValuesTemplate { /** * */ - COMPLETE_GRAPH(new IntegerRange(0, 16), new HashMap2() { + COMPLETE_GRAPH(new IntegerRange(0, 16), new HashDualMap() { { for (int i = 0; i < 16; i++) for (int j = 0; j < 16; j++) @@ -51,7 +51,7 @@ public enum GraphWithValuesTemplate { /** * */ - CIRCULAR_GRAPH(new IntegerRange(0, 100), new HashMap2() { + CIRCULAR_GRAPH(new IntegerRange(0, 100), new HashDualMap() { { for (int i = 0; i < 100; i++) this.put(i, (i + 1) % 100, 1); @@ -60,7 +60,7 @@ public enum GraphWithValuesTemplate { /** * */ - LINEAR_GRAPH(new IntegerRange(0, 100), new HashMap2() { + LINEAR_GRAPH(new IntegerRange(0, 100), new HashDualMap() { { for (int i = 0; i < 99; i++) this.put(i, i + 1, 1); @@ -69,7 +69,7 @@ public enum GraphWithValuesTemplate { /** * */ - SIMPLE_GRAPH(new IntegerRange(1, 2), new HashMap2() { + SIMPLE_GRAPH(new IntegerRange(1, 2), new HashDualMap() { { this.put(1, 2, 100); } @@ -77,17 +77,17 @@ public enum GraphWithValuesTemplate { /** * */ - TRIVIAL_GRAPH(Collections.singleton(1), new HashMap2()), ; + TRIVIAL_GRAPH(Collections.singleton(1), new HashDualMap()), ; private final Map nodes; - private final HashMap2 edges; + private final HashDualMap edges; private final L1 identityOpOnIntegers = Operations.identity(); - GraphWithValuesTemplate(final Set numbers, final HashMap2 edges) { + GraphWithValuesTemplate(final Set numbers, final HashDualMap edges) { this.nodes = new MapAsView(numbers, this.identityOpOnIntegers, this.identityOpOnIntegers); this.edges = edges; } - GraphWithValuesTemplate(final Map nodes, final HashMap2 edges) { + GraphWithValuesTemplate(final Map nodes, final HashDualMap edges) { this.nodes = nodes; this.edges = edges; } @@ -96,7 +96,7 @@ public enum GraphWithValuesTemplate { return this.nodes; } - Map2 getEdges() { + DualMap getEdges() { return this.edges; } } \ No newline at end of file diff --git a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/HashDirectedGraphSetBuilder.java b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/HashDirectedGraphSetBuilder.java index 80a7aa2..d38a4a7 100755 --- a/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/HashDirectedGraphSetBuilder.java +++ b/KezvhLib/src-junit/net/kezvh/collections/graphs/directed/HashDirectedGraphSetBuilder.java @@ -2,12 +2,10 @@ package net.kezvh.collections.graphs.directed; /** * @author mjacob - * */ public class HashDirectedGraphSetBuilder extends DirectedGraphWithEdgeValuesBuilder { @Override public DirectedGraphWithEdgeValues create() throws net.kezvh.patterns.AbstractFactory.CreationFailedException { - return new HashDirectedGraphSet(); + return new GenericDirectedGraphSet(new HashDirectedGraph()); } - } diff --git a/KezvhLib/src-lib/net/kezvh/algorithms/graph/Dijkstra.java b/KezvhLib/src-lib/net/kezvh/algorithms/graph/Dijkstra.java index 2b29054..3b84006 100755 --- a/KezvhLib/src-lib/net/kezvh/algorithms/graph/Dijkstra.java +++ b/KezvhLib/src-lib/net/kezvh/algorithms/graph/Dijkstra.java @@ -10,39 +10,34 @@ import java.util.Map; import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValues; import net.kezvh.collections.heaps.Heap; +import net.kezvh.lang.AlgorithmException; import net.kezvh.patterns.AbstractFactory; import net.kezvh.patterns.AbstractFactory.CreationFailedException; /** * @author mjacob - * * @param node type */ public class Dijkstra implements SingleSourceShortestPath { - + final T source; private final Map dist = new HashMap(); private final Map previous = new HashMap(); private final Map shortestPaths = new HashMap(); - private final int INFINITY = -1; + private static final int INFINITY = -1; /** - * 1 function Dijkstra(Graph, source): - * 2 for each vertex v in Graph: // Initializations - * 3 dist[v] := infinity // Unknown distance function from source to v - * 4 previous[v] := undefined // Previous node in optimal path from source - * 5 dist[source] := 0 // Distance from source to source - * 6 Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q - * 7 while Q is not empty: // The main loop - * 8 u := node in Q with smallest dist[] - * 9 remove u from Q - * 10 for each neighbor v of u: // where v has not yet been removed from Q. - * 11 alt := dist[u] + dist_between(u, v) - * 12 if alt < dist[v] // Relax (u,v) - * 13 dist[v] := alt - * 14 previous[v] := u - * 15 return previous[] + * 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // + * Initializations 3 dist[v] := infinity // Unknown distance function from + * source to v 4 previous[v] := undefined // Previous node in optimal path + * from source 5 dist[source] := 0 // Distance from source to source 6 Q := + * the set of all nodes in Graph // All nodes in the graph are unoptimized - + * thus are in Q 7 while Q is not empty: // The main loop 8 u := node in Q + * with smallest dist[] 9 remove u from Q 10 for each neighbor v of u: // + * where v has not yet been removed from Q. 11 alt := dist[u] + + * dist_between(u, v) 12 if alt < dist[v] // Relax (u,v) 13 dist[v] := alt + * 14 previous[v] := u 15 return previous[] */ private final class ShortestPath extends AbstractList implements Path { @@ -62,6 +57,11 @@ public class Dijkstra implements SingleSourceShortestPath { } this.nodes = previa.toArray((T[]) Array.newInstance(dest.getClass(), previa.size())); + + if (this.nodes[0] != Dijkstra.this.source) + throw new AlgorithmException(); + if (dest != Dijkstra.this.source && this.nodes.length == 1) + throw new AlgorithmException(); } @Override @@ -81,16 +81,17 @@ public class Dijkstra implements SingleSourceShortestPath { } /** - * * @param graph COMMENT * @param source COMMENT - * @param heapMaker needs to create a heap w/ a priority which ranks -1 as INFINITY + * @param heapMaker needs to create a heap w/ a priority which ranks -1 as + * INFINITY */ public Dijkstra(final DirectedGraphWithEdgeValues graph, final T source, final AbstractFactory> heapMaker) { super(); + this.source = source; this.dist.put(source, 0); - Heap Q; + final Heap Q; try { Q = heapMaker.create(); } catch (final CreationFailedException e) { @@ -99,17 +100,19 @@ public class Dijkstra implements SingleSourceShortestPath { final Comparator comparator = Q.comparator(); - for (final T v : graph) - if (!source.equals(v)) { - this.dist.put(v, this.INFINITY); - Q.add(v, this.INFINITY); - } + for (final T v : graph) { // to break the algorithm, move this { one line down + if (!source.equals(v)) + this.dist.put(v, Dijkstra.INFINITY); + Q.add(v, Dijkstra.INFINITY); + } while (!Q.isEmpty()) { final T u = Q.remove(); for (final T v : graph.adjacentFrom(u)) { - final int alt = ((int) this.dist.get(u)) == this.INFINITY ? this.INFINITY : this.dist.get(u) + graph.getEdgeValue(u, v); + final int alt = ((int) this.dist.get(u)) == Dijkstra.INFINITY ? Dijkstra.INFINITY : this.dist.get(u) + graph.getEdgeValue(u, v); if (comparator.compare(alt, this.dist.get(v)) < 0) { + if (Q.contains(v)) + Q.reweight(v, alt); this.dist.put(v, alt); this.previous.put(v, u); } @@ -119,6 +122,11 @@ public class Dijkstra implements SingleSourceShortestPath { @Override public Path getShortestPath(final T dest) { + if (!this.dist.containsKey(dest)) + throw new IllegalArgumentException("Node " + dest + " is not in the graph"); + if (this.dist.get(dest) == Dijkstra.INFINITY) + return null; + if (this.shortestPaths.containsKey(dest)) return this.shortestPaths.get(dest); @@ -127,4 +135,18 @@ public class Dijkstra implements SingleSourceShortestPath { return shortestPath; } + public boolean connected(final T dest) { + if (!this.dist.containsKey(dest)) + throw new IllegalArgumentException("Node " + dest + " is not in the graph"); + return this.dist.get(dest) != Dijkstra.INFINITY; + } + + /** + * @see net.kezvh.algorithms.graph.SingleSourceShortestPath#getSource() + * @return the source of the sssp + */ + @Override + public T getSource() { + return this.source; + } } diff --git a/KezvhLib/src-lib/net/kezvh/algorithms/graph/SingleSourceShortestPath.java b/KezvhLib/src-lib/net/kezvh/algorithms/graph/SingleSourceShortestPath.java index 07ef951..3647f56 100755 --- a/KezvhLib/src-lib/net/kezvh/algorithms/graph/SingleSourceShortestPath.java +++ b/KezvhLib/src-lib/net/kezvh/algorithms/graph/SingleSourceShortestPath.java @@ -2,7 +2,6 @@ package net.kezvh.algorithms.graph; /** * @author mjacob - * * @param node type */ public interface SingleSourceShortestPath { @@ -11,4 +10,15 @@ public interface SingleSourceShortestPath { * @return shortest path between the two points */ Path getShortestPath(T dest); + + /** + * @param dest + * @return true if the source is connected to the destination; + */ + boolean connected(T dest); + + /** + * @return the source for this sssp instance + */ + T getSource(); } diff --git a/KezvhLib/src-lib/net/kezvh/collections/CollectionsUtilities.java b/KezvhLib/src-lib/net/kezvh/collections/CollectionsUtilities.java index 8265603..9c62b99 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/CollectionsUtilities.java +++ b/KezvhLib/src-lib/net/kezvh/collections/CollectionsUtilities.java @@ -7,6 +7,7 @@ import java.util.AbstractSet; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; +import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.List; @@ -17,6 +18,7 @@ import java.util.SortedSet; import java.util.TreeSet; import net.kezvh.functional.lambda.EquivalenceRelation; +import net.kezvh.functional.lambda.L1; import net.kezvh.functional.lambda.Predicate1; import net.kezvh.math.KezvhMath; import net.kezvh.patterns.AbstractFactory; @@ -117,9 +119,9 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param iterator FIXME comment - * @return FIXME comment + * @param COMMENT + * @param iterator COMMENT + * @return COMMENT */ public static int count(final Iterator iterator) { int count = 0; @@ -131,18 +133,35 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param iterators FIXME comment - * @return FIXME comment + * @param COMMENT + * @param start COMMENT + * @param end COMMENT + * @param incrementer COMMENT + * @return COMMENT + */ + public static > List range(final T start, final T end, final L1 incrementer) { + final List range = new ArrayList(); + T current = start; + while (current.compareTo(end) < 0) { + range.add(current); + current = incrementer.op(current); + } + return Collections.unmodifiableList(range); + } + + /** + * @param COMMENT + * @param iterators COMMENT + * @return COMMENT */ public static Iterator concatenate(final Iterator[] iterators) { return new ConcatenatedIterator(iterators); } /** - * @param FIXME comment - * @param iterators FIXME comment - * @return FIXME comment + * @param COMMENT + * @param iterators COMMENT + * @return COMMENT */ public static Iterator concatenate(final Collection> iterators) { final Iterator[] array = (Iterator[]) Array.newInstance(iterators.iterator().next().getClass(), iterators.size()); @@ -150,20 +169,20 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param c FIXME comment - * @param toAdd FIXME comment - * @return FIXME comment + * @param COMMENT + * @param c COMMENT + * @param toAdd COMMENT + * @return COMMENT */ public static boolean addAll(final Collection c, final T[] toAdd) { return c.addAll(Arrays.asList(toAdd)); } /** - * @param FIXME comment - * @param collection FIXME comment - * @param condition FIXME comment - * @return FIXME comment + * @param COMMENT + * @param collection COMMENT + * @param condition COMMENT + * @return COMMENT */ // ////////////////////////////////////// public static List match(final List collection, final Predicate1 condition) { @@ -181,20 +200,20 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param iterator FIXME comment - * @param condition FIXME comment - * @return FIXME comment + * @param COMMENT + * @param iterator COMMENT + * @param condition COMMENT + * @return COMMENT */ public static Iterator matchView(final Iterator iterator, final Predicate1 condition) { return new ConditionalIterator(iterator, condition); } /** - * @param FIXME comment - * @param set FIXME comment - * @param condition FIXME comment - * @return FIXME comment + * @param COMMENT + * @param set COMMENT + * @param condition COMMENT + * @return COMMENT */ public static Set matchView(final Set set, final Predicate1 condition) { return new ConditionalSet(set, condition); @@ -202,14 +221,14 @@ public final class CollectionsUtilities { // ////////// /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param key FIXME comment - * @param defaultValueClass FIXME comment - * @return FIXME comment - * @throws InstantiationException FIXME comment - * @throws IllegalAccessException FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param key COMMENT + * @param defaultValueClass COMMENT + * @return COMMENT + * @throws InstantiationException COMMENT + * @throws IllegalAccessException COMMENT */ public static V ensureContainsKey(final Map map, final K key, final Class defaultValueClass) throws InstantiationException, IllegalAccessException { if (map.containsKey(key)) @@ -223,15 +242,15 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param key FIXME comment - * @param clonableDefaultValue FIXME comment - * @return FIXME comment - * @throws NoSuchMethodException FIXME comment - * @throws InvocationTargetException FIXME comment - * @throws IllegalAccessException FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param key COMMENT + * @param clonableDefaultValue COMMENT + * @return COMMENT + * @throws NoSuchMethodException COMMENT + * @throws InvocationTargetException COMMENT + * @throws IllegalAccessException COMMENT */ public static V ensureContainsKey(final Map map, final K key, final Cloneable clonableDefaultValue) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException { if (map.containsKey(key)) @@ -246,13 +265,13 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param key FIXME comment - * @param defaultValueConstructor FIXME comment - * @return FIXME comment - * @throws CreationFailedException FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param key COMMENT + * @param defaultValueConstructor COMMENT + * @return COMMENT + * @throws CreationFailedException COMMENT */ public static V ensureContainsKey(final Map map, final K key, final AbstractFactory defaultValueConstructor) throws CreationFailedException { if (map.containsKey(key)) @@ -266,11 +285,11 @@ public final class CollectionsUtilities { // /////////////////////////////////////// /** - * @param FIXME comment - * @param c FIXME comment - * @param o FIXME comment - * @param e FIXME comment - * @return FIXME comment + * @param COMMENT + * @param c COMMENT + * @param o COMMENT + * @param e COMMENT + * @return COMMENT */ public static boolean removeFirst(final Collection c, final V o, final EquivalenceRelation e) { for (final Iterator i = c.iterator(); i.hasNext();) @@ -282,11 +301,11 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param c FIXME comment - * @param o FIXME comment - * @param e FIXME comment - * @return FIXME comment + * @param COMMENT + * @param c COMMENT + * @param o COMMENT + * @param e COMMENT + * @return COMMENT */ public static boolean removeAll(final Collection c, final V o, final EquivalenceRelation e) { boolean removed = false; @@ -301,11 +320,11 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param l FIXME comment - * @param o FIXME comment - * @param e FIXME comment - * @return FIXME comment + * @param COMMENT + * @param l COMMENT + * @param o COMMENT + * @param e COMMENT + * @return COMMENT */ public static boolean replaceFirst(final List l, final V o, final EquivalenceRelation e) { for (int i = 0; i < l.size(); i++) @@ -320,11 +339,11 @@ public final class CollectionsUtilities { // /////////////////////////////////////// /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param keys FIXME comment - * @return FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param keys COMMENT + * @return COMMENT */ public static V[] slice(final Map map, final K... keys) { final V[] values = (V[]) Array.newInstance(map.get(keys[0]).getClass(), keys.length); @@ -334,11 +353,11 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param keys FIXME comment - * @return FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param keys COMMENT + * @return COMMENT */ public static List slice(final Map map, final List keys) { List values; @@ -358,9 +377,9 @@ public final class CollectionsUtilities { // ////////////////////////////////////////////// /** - * @param FIXME comment - * @param comparator FIXME comment - * @return FIXME comment + * @param COMMENT + * @param comparator COMMENT + * @return COMMENT */ public static Comparator reverse(final Comparator comparator) { return new Comparator() { @@ -373,10 +392,10 @@ public final class CollectionsUtilities { // //////////////////////////////////////////////// /** - * @param FIXME comment - * @param a FIXME comment - * @param b FIXME comment - * @return FIXME comment + * @param COMMENT + * @param a COMMENT + * @param b COMMENT + * @return COMMENT */ public static boolean sameContents(final Collection a, final Collection b) { final Multiset x = new MappedMultiset(a); @@ -393,10 +412,10 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @return FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @return COMMENT */ public static > SortedSet keySetByValues(final Map map) { return CollectionsUtilities.keySetByValues(map, new ComparableComarator()); @@ -427,11 +446,11 @@ public final class CollectionsUtilities { } /** - * @param FIXME comment - * @param FIXME comment - * @param map FIXME comment - * @param c FIXME comment - * @return FIXME comment + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param c COMMENT + * @return COMMENT */ public static SortedSet keySetByValues(final Map map, final Comparator c) { final Comparator orderByValue = new Comparator() { @@ -459,9 +478,9 @@ public final class CollectionsUtilities { // /////////////////////////////////////////////// /** - * @param FIXME comment - * @param c FIXME comment - * @return FIXME comment + * @param COMMENT + * @param c COMMENT + * @return COMMENT */ public static int hash(final Iterable c) { if (c == null) diff --git a/KezvhLib/src-lib/net/kezvh/collections/Map2/AbstractMap2.java b/KezvhLib/src-lib/net/kezvh/collections/DualMap/AbstractDualMap.java similarity index 69% rename from KezvhLib/src-lib/net/kezvh/collections/Map2/AbstractMap2.java rename to KezvhLib/src-lib/net/kezvh/collections/DualMap/AbstractDualMap.java index a6cab3a..734e2e8 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/Map2/AbstractMap2.java +++ b/KezvhLib/src-lib/net/kezvh/collections/DualMap/AbstractDualMap.java @@ -1,4 +1,4 @@ -package net.kezvh.collections.Map2; +package net.kezvh.collections.DualMap; import java.util.AbstractMap; import java.util.Collection; @@ -18,7 +18,7 @@ import net.kezvh.functional.lambda.Predicate1; * @param key 2 type * @param value type */ -public abstract class AbstractMap2 extends AbstractMap, V> implements Map2 { +public abstract class AbstractDualMap extends AbstractMap, V> implements DualMap { private static final class AbstractCouple implements Pair { private final K1 key1; private final K2 key2; @@ -69,10 +69,10 @@ public abstract class AbstractMap2 extends AbstractMap, } } - private final L1, Map.Entry, V>> ENTRY_CONVERTER = new L1, Map.Entry, V>>() { + private final L1, Map.Entry, V>> ENTRY_CONVERTER = new L1, Map.Entry, V>>() { @Override - public Map2.Entry op(final Map.Entry, V> param) { - return new Map2.Entry() { + public DualMap.Entry op(final Map.Entry, V> param) { + return new DualMap.Entry() { @Override public Pair getKey() { return param.getKey(); @@ -111,7 +111,7 @@ public abstract class AbstractMap2 extends AbstractMap, if (this.getClass() != obj.getClass()) return false; - final Map2.Entry other = (Map2.Entry) obj; + final DualMap.Entry other = (DualMap.Entry) obj; return this.getKey1().equals(other.getKey1()) && this.getKey2().equals(other.getKey2()); } }; @@ -119,15 +119,15 @@ public abstract class AbstractMap2 extends AbstractMap, }; @Override - public Set> entrySetOnKey1(final K1 key1) { + public Set> entrySetOnKey1(final K1 key1) { final Set, V>> filtered = new ConditionalSetView, V>>(new K1Filter(key1), this.entrySet()); - return new SetView, V>, Map2.Entry>(filtered, this.ENTRY_CONVERTER); + return new SetView, V>, DualMap.Entry>(filtered, this.ENTRY_CONVERTER); } @Override - public Set> entrySetOnKey2(final K2 key2) { + public Set> entrySetOnKey2(final K2 key2) { final Set, V>> filtered = new ConditionalSetView, V>>(new K2Filter(key2), this.entrySet()); - return new SetView, V>, Map2.Entry>(filtered, this.ENTRY_CONVERTER); + return new SetView, V>, DualMap.Entry>(filtered, this.ENTRY_CONVERTER); } @Override @@ -138,35 +138,35 @@ public abstract class AbstractMap2 extends AbstractMap, return null; } - private final L1> K2VIEW = new L1>() { + private final L1> K2VIEW = new L1>() { @Override - public K2 op(final net.kezvh.collections.Map2.Map2.Entry param) { + public K2 op(final net.kezvh.collections.DualMap.DualMap.Entry param) { return param.getKey2(); } }; - private final L1> K1VIEW = new L1>() { + private final L1> K1VIEW = new L1>() { @Override - public K1 op(final net.kezvh.collections.Map2.Map2.Entry param) { + public K1 op(final net.kezvh.collections.DualMap.DualMap.Entry param) { return param.getKey1(); } }; - private final L1> VVIEW = new L1>() { + private final L1> VVIEW = new L1>() { @Override - public V op(final net.kezvh.collections.Map2.Map2.Entry param) { + public V op(final net.kezvh.collections.DualMap.DualMap.Entry param) { return param.getValue(); } }; @Override public Set keySetOnKey1(final K1 key1) { - return new SetView, K2>(this.entrySetOnKey1(key1), this.K2VIEW); + return new SetView, K2>(this.entrySetOnKey1(key1), this.K2VIEW); } @Override public Set keySetOnKey2(final K2 key2) { - return new SetView, K1>(this.entrySetOnKey2(key2), this.K1VIEW); + return new SetView, K1>(this.entrySetOnKey2(key2), this.K1VIEW); } @Override @@ -184,7 +184,7 @@ public abstract class AbstractMap2 extends AbstractMap, } @Override - public void putAll(final Map2 m) { + public void putAll(final DualMap m) { for (final Map.Entry, V> entry : this.entrySet()) this.put(entry.getKey(), entry.getValue()); } @@ -203,11 +203,11 @@ public abstract class AbstractMap2 extends AbstractMap, @Override public Collection valuesOnKey1(final K1 key1) { - return new SetView, V>(this.entrySetOnKey1(key1), this.VVIEW); + return new SetView, V>(this.entrySetOnKey1(key1), this.VVIEW); } @Override public Collection valuesOnKey2(final K2 key2) { - return new SetView, V>(this.entrySetOnKey2(key2), this.VVIEW); + return new SetView, V>(this.entrySetOnKey2(key2), this.VVIEW); } } \ No newline at end of file diff --git a/KezvhLib/src-lib/net/kezvh/collections/Map2/Map2.java b/KezvhLib/src-lib/net/kezvh/collections/DualMap/DualMap.java similarity index 96% rename from KezvhLib/src-lib/net/kezvh/collections/Map2/Map2.java rename to KezvhLib/src-lib/net/kezvh/collections/DualMap/DualMap.java index 6917656..a04b91c 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/Map2/Map2.java +++ b/KezvhLib/src-lib/net/kezvh/collections/DualMap/DualMap.java @@ -1,4 +1,4 @@ -package net.kezvh.collections.Map2; +package net.kezvh.collections.DualMap; import java.util.Collection; import java.util.Map; @@ -7,14 +7,15 @@ import java.util.Set; import net.kezvh.collections.Pair; /** - * Renamed from Bimap because google's already using that for "Bijective Map". Bastards. + * Renamed from Bimap because google's already using that for "Bijective Map". + * Bastards. * * @author mjacob * @param first key type * @param second key type * @param value type */ -public interface Map2 extends Map, V> { +public interface DualMap extends Map, V> { /** * Returns the number of key-value mappings in this map. If the map contains * more than Integer.MAX_VALUE elements, returns @@ -50,6 +51,18 @@ public interface Map2 extends Map, V> { boolean containsKey(K1 key1, K2 key2); /** + * @param key1 + * @return true if the map has any keys with key1 specified + */ + boolean containsKey1(K1 key1); + + /** + * @param key2 + * @return true if the map has any keys with key2 specified + */ + boolean containsKey2(K2 key2); + + /** * Returns the value to which the specified key is mapped, or {@code null} * if this map contains no mapping for the key. *

@@ -180,7 +193,7 @@ public interface Map2 extends Map, V> { * @throws IllegalArgumentException if some property of a key or value in * the specified map prevents it from being stored in this map */ - void putAll(Map2 m); + void putAll(DualMap m); /** * Removes all of the mappings from this map (optional operation). The map @@ -304,7 +317,7 @@ public interface Map2 extends Map, V> { * @param key1 * @return entries for which there is a value for (key1, key2) */ - Set> entrySetOnKey1(K1 key1); + Set> entrySetOnKey1(K1 key1); /** * Returns a {@link Set} view of the mappings contained in this map. The set @@ -321,11 +334,11 @@ public interface Map2 extends Map, V> { * @param key2 * @return entries for which there is a value for (key1, key2) */ - Set> entrySetOnKey2(K2 key2); + Set> entrySetOnKey2(K2 key2); /** - * Returns a map m such that m(key2) == this(key1, key2). - * It is backed by this map. + * Returns a map m such that m(key2) == this(key1, key2). It is backed by + * this map. * * @param key1 * @return map @@ -333,8 +346,8 @@ public interface Map2 extends Map, V> { Map entryMapOnKey1(K1 key1); /** - * Returns a map m such that m(key1) == this(key1, key2). - * It is backed by this map. + * Returns a map m such that m(key1) == this(key1, key2). It is backed by + * this map. * * @param key2 * @return map @@ -351,7 +364,7 @@ public interface Map2 extends Map, V> { * after the entry was returned by the iterator, except through the * setValue operation on the map entry. * - * @see Map2#entrySet() + * @see DualMap#entrySet() * @author mjacob * @param * @param diff --git a/KezvhLib/src-lib/net/kezvh/collections/Map2/HashMap2.java b/KezvhLib/src-lib/net/kezvh/collections/DualMap/HashDualMap.java similarity index 78% rename from KezvhLib/src-lib/net/kezvh/collections/Map2/HashMap2.java rename to KezvhLib/src-lib/net/kezvh/collections/DualMap/HashDualMap.java index 4a41b7d..757be05 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/Map2/HashMap2.java +++ b/KezvhLib/src-lib/net/kezvh/collections/DualMap/HashDualMap.java @@ -1,7 +1,7 @@ /** * */ -package net.kezvh.collections.Map2; +package net.kezvh.collections.DualMap; import java.io.IOException; import java.lang.reflect.Array; @@ -24,37 +24,29 @@ import net.kezvh.collections.views.SetView; import net.kezvh.functional.lambda.L1; /** - * Sometimes you want a map with 2 keys. While one could just use java's maps but with - * something like Couple as the key, there's an additional opperation I often - * want to do that you just can't do with something like that. In particular, this - * operation is incredibly useful if you use this collection to map the edges of a graph, - * and you want to iterate through all the edges into or out of a particular node. - * - * That operation is to slice the map by 1 key or the other. - * - * This class grepped a lot of its guts out of java's hashmap implementation (is that - * an ip issue?). However, each entry in the table also maintains connections to - * other entries which share it's first or second key. This way, you've got a linked - * list of entries for each key along each dimension. - * - * Time complexity: - * get(k1, k2) - * this is operationally identical to getting on a hashmap, so O(1) - * put(k1, k2, v) - * hashtable put + 2 linked list head inserts, so also O(1) amortized - * remove(k1, k2) - * hashtable remove + 2 doubly linked list remove, so O(1) - * get(k1) || get(k2) - * returns a list of elements backed by the map in O(1) time - * remove(k1) || remove(k2) - * O(n), where n is the number of elements in get(k1) or get(k2) respectively. + * Sometimes you want a map with 2 keys. While one could just use java's maps + * but with something like Couple as the key, there's an additional + * opperation I often want to do that you just can't do with something like + * that. In particular, this operation is incredibly useful if you use this + * collection to map the edges of a graph, and you want to iterate through all + * the edges into or out of a particular node. That operation is to slice the + * map by 1 key or the other. This class grepped a lot of its guts out of java's + * hashmap implementation (is that an ip issue?). However, each entry in the + * table also maintains connections to other entries which share it's first or + * second key. This way, you've got a linked list of entries for each key along + * each dimension. Time complexity: get(k1, k2) this is operationally identical + * to getting on a hashmap, so O(1) put(k1, k2, v) hashtable put + 2 linked list + * head inserts, so also O(1) amortized remove(k1, k2) hashtable remove + 2 + * doubly linked list remove, so O(1) get(k1) || get(k2) returns a list of + * elements backed by the map in O(1) time remove(k1) || remove(k2) O(n), where + * n is the number of elements in get(k1) or get(k2) respectively. * * @author afflux * @param COMMENT * @param COMMENT * @param COMMENT */ -public class HashMap2 implements Map2 { +public class HashDualMap implements DualMap { /** * The default initial capacity - MUST be a power of two. */ @@ -73,7 +65,7 @@ public class HashMap2 implements Map2 { static final float DEFAULT_LOAD_FACTOR = 0.75f; private static final Entry[] createEntries(final Entry[] other, final int capacity) { - return HashMap2.createEntries(other.getClass().getComponentType(), capacity); + return HashDualMap.createEntries(other.getClass().getComponentType(), capacity); } @SuppressWarnings("unchecked") @@ -99,7 +91,7 @@ public class HashMap2 implements Map2 { } private static final int hash(final Pair entry) { - return HashMap2.hash(entry.get1(), entry.get2()); + return HashDualMap.hash(entry.get1(), entry.get2()); } private static final int indexFor(final int hash, final int length) { @@ -130,7 +122,7 @@ public class HashMap2 implements Map2 { * @param * @param */ - private static final class Entry implements Map2.Entry, Pair { + private static final class Entry implements DualMap.Entry, Pair { private final K1 k1; private final K2 k2; private V value; @@ -141,6 +133,15 @@ public class HashMap2 implements Map2 { private Entry prev1; // prev in loop w/ fixed k1 private Entry prev2; // prev in loop w/ fixed k2 + @Override + public String toString() { + return "(" + this.k1 + ", " + this.k2 + ") => " + this.value; + } + + public String specialString() { + return "next1: " + this.next1 + " next2: " + this.next2 + " prev1: " + this.prev1 + " prev2: " + this.prev2; + } + public Entry(final int hash, final K1 k1, final K2 k2, final V v, final Entry nextCollision) { this.k1 = k1; this.k2 = k2; @@ -154,7 +155,7 @@ public class HashMap2 implements Map2 { * * @param bimap COMMENT */ - public void removeSelf(final HashMap2 bimap) { + public void removeSelf(final HashDualMap bimap) { if (this.next1 != null) this.next1.setPrev1(this.prev1); if (this.next2 != null) @@ -248,7 +249,7 @@ public class HashMap2 implements Map2 { } public boolean matchesKeys(final K1 key1, final K2 key2) { - return HashMap2.objectsEqual(this.k1, key1) && HashMap2.objectsEqual(this.k2, key2); + return HashDualMap.objectsEqual(this.k1, key1) && HashDualMap.objectsEqual(this.k2, key2); } /** @@ -302,7 +303,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2.Entry#getKey1() + * @see net.kezvh.collections.DualMap.DualMap.Entry#getKey1() * @return COMMENT */ @Override @@ -311,7 +312,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2.Entry#getKey2() + * @see net.kezvh.collections.DualMap.DualMap.Entry#getKey2() * @return COMMENT */ @Override @@ -320,7 +321,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2.Entry#getValue() + * @see net.kezvh.collections.DualMap.DualMap.Entry#getValue() * @return COMMENT */ @Override @@ -329,7 +330,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2.Entry#setValue(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap.Entry#setValue(java.lang.Object) * @param value COMMENT * @return COMMENT */ @@ -399,7 +400,7 @@ public class HashMap2 implements Map2 { */ @Override public void remove() { - HashMap2.this.remove(HeadSet.this.getPrev(this.current)); + HashDualMap.this.remove(HeadSet.this.getPrev(this.current)); } } @@ -450,7 +451,7 @@ public class HashMap2 implements Map2 { */ @Override public boolean add(final Entry o) { - return HashMap2.this.put(o) != null; + return HashDualMap.this.put(o) != null; } /** @@ -460,7 +461,7 @@ public class HashMap2 implements Map2 { */ @Override public boolean addAll(final Collection> c) { - return HashMap2.this.putAll(c); + return HashDualMap.this.putAll(c); } /** @@ -469,7 +470,7 @@ public class HashMap2 implements Map2 { @Override public void clear() { for (final Entry entry : this) - HashMap2.this.remove(entry); + HashDualMap.this.remove(entry); } /** @@ -480,11 +481,11 @@ public class HashMap2 implements Map2 { @SuppressWarnings("unchecked") @Override public boolean contains(final Object o) { - if (!(o instanceof Map2.Entry)) + if (!(o instanceof DualMap.Entry)) return false; - final Map2.Entry other = (Map2.Entry) o; - return HashMap2.this.containsKey(other.getKey1(), other.getKey2()); + final DualMap.Entry other = (DualMap.Entry) o; + return HashDualMap.this.containsKey(other.getKey1(), other.getKey2()); } /** @@ -516,7 +517,7 @@ public class HashMap2 implements Map2 { */ @Override public boolean remove(final Object o) { - return HashMap2.this.remove(o) != null; + return HashDualMap.this.remove(o) != null; } /** @@ -529,7 +530,7 @@ public class HashMap2 implements Map2 { boolean modified = false; for (final Entry entry : this) if (!c.contains(entry)) - modified |= HashMap2.this.remove(entry) != null; + modified |= HashDualMap.this.remove(entry) != null; return modified; } @@ -540,14 +541,14 @@ public class HashMap2 implements Map2 { */ @Override public Object[] toArray() { - final Entry[] array = HashMap2.createEntries(this.head.getClass(), HashMap2.this.size); + final Entry[] array = HashDualMap.createEntries(this.head.getClass(), HashDualMap.this.size); return this.toArray(array); } @SuppressWarnings("unchecked") @Override public T[] toArray(final T[] a) { - final T[] b = a.length >= HashMap2.this.size ? a : (T[]) HashMap2.createEntries(a.getClass().getComponentType(), HashMap2.this.size); + final T[] b = a.length >= HashDualMap.this.size ? a : (T[]) HashDualMap.createEntries(a.getClass().getComponentType(), HashDualMap.this.size); int i = 0; for (final Entry entry : this) a[i++] = (T) entry; @@ -558,12 +559,12 @@ public class HashMap2 implements Map2 { private final class HeadSet1 extends HeadSet { @Override protected Entry getPrev(final Entry arg0) { - return arg0.getNext1(); + return arg0.getPrev1(); } @Override protected Entry getNext(final Entry arg0) { - return arg0.getPrev1(); + return arg0.getNext1(); } @Override @@ -580,12 +581,12 @@ public class HashMap2 implements Map2 { private final class HeadSet2 extends HeadSet { @Override protected Entry getPrev(final Entry arg0) { - return arg0.getNext2(); + return arg0.getPrev2(); } @Override protected Entry getNext(final Entry arg0) { - return arg0.getPrev2(); + return arg0.getNext2(); } @Override @@ -643,11 +644,11 @@ public class HashMap2 implements Map2 { Entry current; // current entry public HashIterator() { - this.expectedModCount = HashMap2.this.modCount; - final Entry[] t = HashMap2.this.entries; + this.expectedModCount = HashDualMap.this.modCount; + final Entry[] t = HashDualMap.this.entries; int i = t.length; Entry n = null; - if (HashMap2.this.size != 0) + if (HashDualMap.this.size != 0) while (i > 0 && (n = t[--i]) == null) { // nothing TODO maybe refactor this so it's.. not so ugly } @@ -660,14 +661,14 @@ public class HashMap2 implements Map2 { } protected Entry nextEntry() { - if (HashMap2.this.modCount != this.expectedModCount) + if (HashDualMap.this.modCount != this.expectedModCount) throw new ConcurrentModificationException(); final Entry e = this.next; if (e == null) throw new NoSuchElementException(); Entry n = e.getNextCollision(); - final Entry[] t = HashMap2.this.entries; + final Entry[] t = HashDualMap.this.entries; int i = this.index; while (n == null && i > 0) n = t[--i]; @@ -679,12 +680,12 @@ public class HashMap2 implements Map2 { public void remove() { if (this.current == null) throw new IllegalStateException(); - if (HashMap2.this.modCount != this.expectedModCount) + if (HashDualMap.this.modCount != this.expectedModCount) throw new ConcurrentModificationException(); final Pair k = this.current.getKey(); this.current = null; - HashMap2.this.removeEntryForKey(k.get1(), k.get2()); - this.expectedModCount = HashMap2.this.modCount; + HashDualMap.this.removeEntryForKey(k.get1(), k.get2()); + this.expectedModCount = HashDualMap.this.modCount; } } @@ -749,29 +750,29 @@ public class HashMap2 implements Map2 { private class KeySet extends AbstractSet> { @Override public Iterator> iterator() { - return HashMap2.this.newKeyIterator(); + return HashDualMap.this.newKeyIterator(); } @Override public int size() { - return HashMap2.this.size; + return HashDualMap.this.size; } @Override public boolean contains(final Object o) { - return HashMap2.this.containsKey(o); + return HashDualMap.this.containsKey(o); } @SuppressWarnings("unchecked") @Override public boolean remove(final Object o) { final Pair other = (Pair) o; - return HashMap2.this.removeEntryForKey(other.get1(), other.get2()) != null; + return HashDualMap.this.removeEntryForKey(other.get1(), other.get2()) != null; } @Override public void clear() { - HashMap2.this.clear(); + HashDualMap.this.clear(); } } @@ -794,22 +795,22 @@ public class HashMap2 implements Map2 { private class Values extends AbstractCollection { @Override public Iterator iterator() { - return HashMap2.this.newValueIterator(); + return HashDualMap.this.newValueIterator(); } @Override public int size() { - return HashMap2.this.size; + return HashDualMap.this.size; } @Override public boolean contains(final Object o) { - return HashMap2.this.containsValue(o); + return HashDualMap.this.containsValue(o); } @Override public void clear() { - HashMap2.this.clear(); + HashDualMap.this.clear(); } } @@ -832,7 +833,7 @@ public class HashMap2 implements Map2 { } private Entry getEntry(final K1 key1, final K2 key2) { - for (Entry entry = this.entries[HashMap2.indexFor(HashMap2.hash(key1, key2), this.entries.length)]; entry != null; entry = entry.getNextCollision()) + for (Entry entry = this.entries[HashDualMap.indexFor(HashDualMap.hash(key1, key2), this.entries.length)]; entry != null; entry = entry.getNextCollision()) if (entry.matchesKeys(key1, key2)) return entry; return null; @@ -841,33 +842,33 @@ public class HashMap2 implements Map2 { private class EntrySet extends AbstractSet, V>> { @Override public Iterator, V>> iterator() { - return HashMap2.this.newEntryIterator(); + return HashDualMap.this.newEntryIterator(); } @SuppressWarnings("unchecked") @Override public boolean contains(final Object o) { - if (!(o instanceof Map2.Entry)) + if (!(o instanceof DualMap.Entry)) return false; - final Map2.Entry e = (Map2.Entry) o; - final Entry candidate = HashMap2.this.getEntry(e.getKey1(), e.getKey2()); + final DualMap.Entry e = (DualMap.Entry) o; + final Entry candidate = HashDualMap.this.getEntry(e.getKey1(), e.getKey2()); return candidate != null && candidate.equals(e); } @SuppressWarnings("unchecked") @Override public boolean remove(final Object o) { - return HashMap2.this.removeMapping((Map.Entry, V>) o) != null; + return HashDualMap.this.removeMapping((Map.Entry, V>) o) != null; } @Override public int size() { - return HashMap2.this.size; + return HashDualMap.this.size; } @Override public void clear() { - HashMap2.this.clear(); + HashDualMap.this.clear(); } } @@ -923,7 +924,7 @@ public class HashMap2 implements Map2 { // Read in number of buckets and allocate the bucket array; final int numBuckets = s.readInt(); - this.entries = HashMap2.createEntries(new Entry(0, null, null, null, null).getClass(), numBuckets); + this.entries = HashDualMap.createEntries(new Entry(0, null, null, null, null).getClass(), numBuckets); this.init(); // Give subclass a chance to do its thing. @@ -951,17 +952,17 @@ public class HashMap2 implements Map2 { /** * */ - public HashMap2() { - this.entries = HashMap2.createEntries(new Entry(0, null, null, null, null).getClass(), HashMap2.DEFAULT_INITIAL_CAPACITY); - this.loadFactor = HashMap2.DEFAULT_LOAD_FACTOR; + public HashDualMap() { + this.entries = HashDualMap.createEntries(new Entry(0, null, null, null, null).getClass(), HashDualMap.DEFAULT_INITIAL_CAPACITY); + this.loadFactor = HashDualMap.DEFAULT_LOAD_FACTOR; } /** - * @see net.kezvh.collections.Map2.Map2#clear() + * @see net.kezvh.collections.DualMap.DualMap#clear() */ @Override public void clear() { - this.entries = HashMap2.createEntries(this.entries, HashMap2.DEFAULT_INITIAL_CAPACITY); + this.entries = HashDualMap.createEntries(this.entries, HashDualMap.DEFAULT_INITIAL_CAPACITY); this.k1Heads.clear(); this.k2Heads.clear(); } @@ -970,13 +971,13 @@ public class HashMap2 implements Map2 { * Special version of remove for EntrySet. */ private Entry removeMapping(final Map.Entry, V> o) { - if (!(o instanceof Map2.Entry)) + if (!(o instanceof DualMap.Entry)) return null; final Map.Entry, V> entry = o; final Pair k = entry.getKey(); final int hash = k.hashCode(); - final int i = HashMap2.indexFor(hash, this.entries.length); + final int i = HashDualMap.indexFor(hash, this.entries.length); Entry prev = this.entries[i]; Entry e = prev; @@ -1000,7 +1001,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#containsKey(java.lang.Object, + * @see net.kezvh.collections.DualMap.DualMap#containsKey(java.lang.Object, * java.lang.Object) * @param key1 COMMENT * @param key2 COMMENT @@ -1017,8 +1018,8 @@ public class HashMap2 implements Map2 { * comodification, etc. It calls createEntry rather than addEntry. */ private void putForCreate(final K1 key1, final K2 key2, final V value) { - final int hash = HashMap2.hash(key1, key2); - final int i = HashMap2.indexFor(hash, this.entries.length); + final int hash = HashDualMap.hash(key1, key2); + final int i = HashDualMap.indexFor(hash, this.entries.length); /** * Look for preexisting entry for key. This will never happen for clone @@ -1026,7 +1027,7 @@ public class HashMap2 implements Map2 { * is a sorted map whose ordering is inconsistent w/ equals. */ for (Entry e = this.entries[i]; e != null; e = e.nextCollision) - if (e.hash == hash && HashMap2.objectsEqual(key1, e.get1()) && HashMap2.objectsEqual(key2, e.get2())) { + if (e.hash == hash && HashDualMap.objectsEqual(key1, e.get1()) && HashDualMap.objectsEqual(key2, e.get2())) { e.value = value; return; } @@ -1048,33 +1049,23 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#entrySetOnKey1(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#entrySetOnKey1(java.lang.Object) * @param key1 COMMENT * @return COMMENT */ @Override - public Set> entrySetOnKey1(final K1 key1) { - return new SetView, Map2.Entry>(this.k1Heads.get(key1), this.getBimapEntry); + public Set> entrySetOnKey1(final K1 key1) { + return new SetView, DualMap.Entry>(this.k1Heads.get(key1), this.getBimapEntry); } - private final L1, Entry> getBimapEntry = new L1, Entry>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param param COMMENT - * @return COMMENT - */ + private final L1, Entry> getBimapEntry = new L1, Entry>() { @Override - public Map2.Entry op(final Entry param) { + public DualMap.Entry op(final Entry param) { return param; } }; private final L1> getKey1 = new L1>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param param COMMENT - * @return COMMENT - */ @Override public K1 op(final Entry param) { return param.getKey1(); @@ -1082,11 +1073,6 @@ public class HashMap2 implements Map2 { }; private final L1> getKey2 = new L1>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param param COMMENT - * @return COMMENT - */ @Override public K2 op(final Entry param) { return param.getKey2(); @@ -1094,11 +1080,6 @@ public class HashMap2 implements Map2 { }; private final L1> getValue = new L1>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param param COMMENT - * @return COMMENT - */ @Override public V op(final Entry param) { return param.getValue(); @@ -1106,28 +1087,31 @@ public class HashMap2 implements Map2 { }; /** - * @see net.kezvh.collections.Map2.Map2#entrySetOnKey2(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#entrySetOnKey2(java.lang.Object) * @param key2 COMMENT * @return COMMENT */ @Override - public Set> entrySetOnKey2(final K2 key2) { - return new SetView, Map2.Entry>(this.k2Heads.get(key2), this.getBimapEntry); + public Set> entrySetOnKey2(final K2 key2) { + return new SetView, DualMap.Entry>(this.k2Heads.get(key2), this.getBimapEntry); } /** - * @see net.kezvh.collections.Map2.Map2#get(java.lang.Object, java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#get(java.lang.Object, + * java.lang.Object) * @param key1 COMMENT * @param key2 COMMENT * @return COMMENT */ @Override public V get(final K1 key1, final K2 key2) { - return this.getEntry(key1, key2).value; + if (this.containsKey(key1, key2)) + return this.getEntry(key1, key2).value; + return null; } /** - * @see net.kezvh.collections.Map2.Map2#isEmpty() + * @see net.kezvh.collections.DualMap.DualMap#isEmpty() * @return COMMENT */ @Override @@ -1136,28 +1120,32 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#keySetOnKey1(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#keySetOnKey1(java.lang.Object) * @param key1 COMMENT * @return COMMENT */ @Override public Set keySetOnKey1(final K1 key1) { + if (!this.k1Heads.containsKey(key1)) + return null; return new SetView, K2>(this.k1Heads.get(key1), this.getKey2); } /** - * @see net.kezvh.collections.Map2.Map2#keySetOnKey2(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#keySetOnKey2(java.lang.Object) * @param key2 COMMENT * @return COMMENT */ @Override public Set keySetOnKey2(final K2 key2) { + if (!this.k2Heads.containsKey(key2)) + return null; return new SetView, K1>(this.k2Heads.get(key2), this.getKey1); } /** - * @see net.kezvh.collections.Map2.Map2#put(java.lang.Object, java.lang.Object, - * java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#put(java.lang.Object, + * java.lang.Object, java.lang.Object) * @param key1 COMMENT * @param key2 COMMENT * @param value COMMENT @@ -1176,11 +1164,12 @@ public class HashMap2 implements Map2 { private void addEntry(final K1 key1, final K2 key2, final V value) { if (this.size++ >= this.threshold) this.resize(this.entries.length << 1); - final int hash = HashMap2.hash(key1, key2); - final int index = HashMap2.indexFor(hash, this.entries.length); + final int hash = HashDualMap.hash(key1, key2); + final int index = HashDualMap.indexFor(hash, this.entries.length); final Entry e = this.entries[index]; final Entry newEntry = new Entry(hash, key1, key2, value, e); this.entries[index] = newEntry; + HeadSet1 key1Head = this.k1Heads.get(key1); if (key1Head == null) { key1Head = new HeadSet1(); @@ -1198,18 +1187,18 @@ public class HashMap2 implements Map2 { } private void resize(final int newSize) { - final Entry[] newTable = HashMap2.createEntries(this.entries.getClass().getComponentType(), newSize); + final Entry[] newTable = HashDualMap.createEntries(this.entries.getClass().getComponentType(), newSize); for (final Entry entry : this.entries) if (entry != null) - newTable[HashMap2.indexFor(HashMap2.hash(entry), newSize)] = entry; + newTable[HashDualMap.indexFor(HashDualMap.hash(entry), newSize)] = entry; } /** - * @see net.kezvh.collections.Map2.Map2#putAll(net.kezvh.collections.Map2.Map2) + * @see net.kezvh.collections.DualMap.DualMap#putAll(net.kezvh.collections.DualMap.DualMap) * @param m COMMENT */ @Override - public void putAll(final Map2 m) { + public void putAll(final DualMap m) { if (this.size + m.size() > this.threshold) { final int newSize = Integer.highestOneBit(this.size + m.size()) << 1; this.resize(newSize); @@ -1219,7 +1208,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#remove(java.lang.Object, + * @see net.kezvh.collections.DualMap.DualMap#remove(java.lang.Object, * java.lang.Object) * @param key1 COMMENT * @param key2 COMMENT @@ -1232,8 +1221,8 @@ public class HashMap2 implements Map2 { } private Entry removeEntryForKey(final K1 key1, final K2 key2) { - final int hash = HashMap2.hash(key1, key2); - final int index = HashMap2.indexFor(hash, this.entries.length); + final int hash = HashDualMap.hash(key1, key2); + final int index = HashDualMap.indexFor(hash, this.entries.length); Entry prev = this.entries[index]; Entry e = prev; @@ -1258,7 +1247,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#size() + * @see net.kezvh.collections.DualMap.DualMap#size() * @return COMMENT */ @Override @@ -1267,7 +1256,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#valuesOnKey1(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#valuesOnKey1(java.lang.Object) * @param key1 COMMENT * @return COMMENT */ @@ -1277,7 +1266,7 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#valuesOnKey2(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#valuesOnKey2(java.lang.Object) * @param key2 COMMENT * @return COMMENT */ @@ -1309,7 +1298,7 @@ public class HashMap2 implements Map2 { @Override public boolean containsValue(final Object value) { for (final Entry entry : this.entries) - if (entry != null && HashMap2.objectsEqual(entry.getValue(), value)) + if (entry != null && HashDualMap.objectsEqual(entry.getValue(), value)) return true; return false; @@ -1345,7 +1334,7 @@ public class HashMap2 implements Map2 { * @param entry COMMENT * @return COMMENT */ - public V put(final Map2.Entry entry) { + public V put(final DualMap.Entry entry) { return this.put(entry.getKey1(), entry.getKey2(), entry.getValue()); } @@ -1354,13 +1343,13 @@ public class HashMap2 implements Map2 { * @param c COMMENT * @return COMMENT */ - public boolean putAll(final Collection> c) { + public boolean putAll(final Collection> c) { if (this.size + c.size() > this.threshold) { final int newSize = Integer.highestOneBit(this.size + c.size()) << 1; this.resize(newSize); } boolean changed = false; - for (final Map2.Entry o : c) + for (final DualMap.Entry o : c) changed |= this.put(o.getKey().get1(), o.getKey().get2(), o.getValue()) != null; return changed; } @@ -1399,14 +1388,14 @@ public class HashMap2 implements Map2 { private final Set> entryMapSet; - private final L1, HashMap2.Entry> forwardMap = new L1, HashMap2.Entry>() { + private final L1, HashDualMap.Entry> forwardMap = new L1, HashDualMap.Entry>() { /** * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) * @param param COMMENT * @return COMMENT */ @Override - public Map.Entry op(final HashMap2.Entry param) { + public Map.Entry op(final HashDualMap.Entry param) { return new Map.Entry() { /** * @see java.util.Map.Entry#getKey() @@ -1442,12 +1431,12 @@ public class HashMap2 implements Map2 { @SuppressWarnings("unchecked") @Override public V get(final Object key) { - return HashMap2.this.get(this.key1, (K2) key); + return HashDualMap.this.get(this.key1, (K2) key); } @Override public V put(final K2 key, final V value) { - return HashMap2.this.put(this.key1, key, value); + return HashDualMap.this.put(this.key1, key, value); } /** @@ -1458,12 +1447,12 @@ public class HashMap2 implements Map2 { @SuppressWarnings("unchecked") @Override public V remove(final Object key) { - return HashMap2.this.remove(this.key1, (K2) key); + return HashDualMap.this.remove(this.key1, (K2) key); } public EntryMap1(final K1 key1) { this.key1 = key1; - this.entryMapSet = new SetView, Map.Entry>(HashMap2.this.k1Heads.get(key1), this.forwardMap) { + this.entryMapSet = new SetView, Map.Entry>(HashDualMap.this.k1Heads.get(key1), this.forwardMap) { /** * @see java.util.AbstractCollection#add(java.lang.Object) * @param o COMMENT @@ -1471,7 +1460,7 @@ public class HashMap2 implements Map2 { */ @Override public boolean add(final java.util.Map.Entry o) { - return HashMap2.this.put(key1, o.getKey(), o.getValue()) != null; + return HashDualMap.this.put(key1, o.getKey(), o.getValue()) != null; } /** @@ -1479,7 +1468,7 @@ public class HashMap2 implements Map2 { */ @Override public void clear() { - HashMap2.this.k1Heads.get(key1).clear(); + HashDualMap.this.k1Heads.get(key1).clear(); } /** @@ -1494,7 +1483,7 @@ public class HashMap2 implements Map2 { return false; final Map.Entry other = (Map.Entry) o; - return HashMap2.this.containsKey(key1, other.getKey()); + return HashDualMap.this.containsKey(key1, other.getKey()); } /** @@ -1506,7 +1495,7 @@ public class HashMap2 implements Map2 { @Override public boolean remove(final Object o) { final Map.Entry other = (Map.Entry) o; - return HashMap2.this.remove(key1, other.getKey()) != null; + return HashDualMap.this.remove(key1, other.getKey()) != null; } }; } @@ -1522,27 +1511,29 @@ public class HashMap2 implements Map2 { } /** - * @see net.kezvh.collections.Map2.Map2#entryMapOnKey1(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#entryMapOnKey1(java.lang.Object) * @param key1 COMMENT * @return COMMENT */ @Override public Map entryMapOnKey1(final K1 key1) { - return new EntryMap1(key1); + if (this.k1Heads.containsKey(key1)) + return new EntryMap1(key1); + return null; } private class EntryMap2 extends AbstractMap { private final K2 key2; private final Set> entryMapSet; - private final L1, HashMap2.Entry> forwardMap = new L1, HashMap2.Entry>() { + private final L1, HashDualMap.Entry> forwardMap = new L1, HashDualMap.Entry>() { /** * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) * @param param COMMENT * @return COMMENT */ @Override - public Map.Entry op(final HashMap2.Entry param) { + public Map.Entry op(final HashDualMap.Entry param) { return new Map.Entry() { /** * @see java.util.Map.Entry#getKey() @@ -1572,7 +1563,7 @@ public class HashMap2 implements Map2 { public EntryMap2(final K2 key2) { this.key2 = key2; - this.entryMapSet = new SetView, Map.Entry>(HashMap2.this.k1Heads.get(key2), this.forwardMap) { + this.entryMapSet = new SetView, Map.Entry>(HashDualMap.this.k2Heads.get(key2), this.forwardMap) { /** * @see java.util.AbstractCollection#add(java.lang.Object) * @param o COMMENT @@ -1580,7 +1571,7 @@ public class HashMap2 implements Map2 { */ @Override public boolean add(final java.util.Map.Entry o) { - return HashMap2.this.put(o.getKey(), key2, o.getValue()) != null; + return HashDualMap.this.put(o.getKey(), key2, o.getValue()) != null; } /** @@ -1588,7 +1579,7 @@ public class HashMap2 implements Map2 { */ @Override public void clear() { - HashMap2.this.k2Heads.get(key2).clear(); + HashDualMap.this.k2Heads.get(key2).clear(); } /** @@ -1603,7 +1594,7 @@ public class HashMap2 implements Map2 { return false; final Map.Entry other = (Map.Entry) o; - return HashMap2.this.containsKey(other.getKey(), key2); + return HashDualMap.this.containsKey(other.getKey(), key2); } /** @@ -1615,7 +1606,7 @@ public class HashMap2 implements Map2 { @Override public boolean remove(final Object o) { final Map.Entry other = (Map.Entry) o; - return HashMap2.this.remove(other.getKey(), key2) != null; + return HashDualMap.this.remove(other.getKey(), key2) != null; } }; } @@ -1637,12 +1628,12 @@ public class HashMap2 implements Map2 { @SuppressWarnings("unchecked") @Override public V get(final Object key) { - return HashMap2.this.get((K1) key, this.key2); + return HashDualMap.this.get((K1) key, this.key2); } @Override public V put(final K1 key, final V value) { - return HashMap2.this.put(key, this.key2, value); + return HashDualMap.this.put(key, this.key2, value); } /** @@ -1653,32 +1644,40 @@ public class HashMap2 implements Map2 { @SuppressWarnings("unchecked") @Override public V remove(final Object key) { - return HashMap2.this.remove((K1) key, this.key2); + return HashDualMap.this.remove((K1) key, this.key2); } } /** - * @see net.kezvh.collections.Map2.Map2#entryMapOnKey2(java.lang.Object) + * @see net.kezvh.collections.DualMap.DualMap#entryMapOnKey2(java.lang.Object) * @param key2 COMMENT * @return COMMENT */ @Override public Map entryMapOnKey2(final K2 key2) { - return new EntryMap2(key2); + if (this.k2Heads.containsKey(key2)) + return new EntryMap2(key2); + return null; } @Override public Collection> get1(final K1 key1) { - return this.entryMapOnKey1(key1).entrySet(); + if (this.k1Heads.containsKey(key1)) + return this.entryMapOnKey1(key1).entrySet(); + return null; } @Override public Collection> get2(final K2 key2) { - return this.entryMapOnKey2(key2).entrySet(); + if (this.k2Heads.containsKey(key2)) + return this.entryMapOnKey2(key2).entrySet(); + return null; } @Override public Collection> remove1(final K1 key1) { + if (!this.k1Heads.containsKey(key1)) + return null; final Collection> removedEntries = new ArrayList>(this.k1Heads.get(key1).size()); for (final Entry entry : this.k1Heads.get(key1)) @@ -1692,9 +1691,12 @@ public class HashMap2 implements Map2 { @Override public Collection> remove2(final K2 key2) { + if (!this.k2Heads.containsKey(key2)) + return null; + final Collection> removedEntries = new ArrayList>(this.k2Heads.get(key2).size()); - for (final Entry entry : this.k1Heads.get(key2)) + for (final Entry entry : this.k2Heads.get(key2)) removedEntries.add(new MapEntryImpl(entry.get1(), entry.getValue())); for (final Map.Entry removedEntry : removedEntries) @@ -1702,4 +1704,12 @@ public class HashMap2 implements Map2 { return removedEntries; } + + public boolean containsKey1(final K1 key1) { + return this.k1Heads.containsKey(key1); + } + + public boolean containsKey2(final K2 key2) { + return this.k2Heads.containsKey(key2); + } } diff --git a/KezvhLib/src-lib/net/kezvh/collections/IntegerRange.java b/KezvhLib/src-lib/net/kezvh/collections/IntegerRange.java index 3169936..668f740 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/IntegerRange.java +++ b/KezvhLib/src-lib/net/kezvh/collections/IntegerRange.java @@ -22,4 +22,13 @@ public class IntegerRange extends Range { public IntegerRange(final int first, final int last, final boolean firstOpen, final boolean lastOpen) { super(first, last, firstOpen, lastOpen, Navigator.INTEGER_NAVIGATOR); } + + /** + * @see net.kezvh.collections.Range#size() + * @return COMMENT + */ + @Override + public int size() { + return this.last() - this.first(); + } } diff --git a/KezvhLib/src-lib/net/kezvh/collections/Range.java b/KezvhLib/src-lib/net/kezvh/collections/Range.java index ca0dd14..1572465 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/Range.java +++ b/KezvhLib/src-lib/net/kezvh/collections/Range.java @@ -133,23 +133,24 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @param navigator navigator */ public Range(final E first, final E last, final boolean firstOpen, final boolean lastOpen, final Navigator navigator) { - this.first = first; - this.last = last; - - if (navigator == null && first instanceof Number) - this.navigator = Navigator.Utilities.getNumberNavigator(first.getClass()); - else - this.navigator = navigator; - this.firstOpen = firstOpen; - this.lastOpen = lastOpen; - - this.directlyNavigable = navigator != null; - - if (first == null || (this.directlyNavigable && !(first instanceof Navigable) && !(first instanceof Number))) - throw new IllegalArgumentException(first + " is not comparable"); - - if (last == null || (this.directlyNavigable && !(last instanceof Navigable) && !(first instanceof Number))) - throw new IllegalArgumentException(last + " is not comparable"); + throw new RuntimeException("too buggy to use"); + // this.first = first; + // this.last = last; + // + // if (navigator == null && first instanceof Number) + // this.navigator = Navigator.Utilities.getNumberNavigator(first.getClass()); + // else + // this.navigator = navigator; + // this.firstOpen = firstOpen; + // this.lastOpen = lastOpen; + // + // this.directlyNavigable = navigator != null; + // + // if (first == null || (this.directlyNavigable && !(first instanceof Navigable) && !(first instanceof Number))) + // throw new IllegalArgumentException(first + " is not comparable"); + // + // if (last == null || (this.directlyNavigable && !(last instanceof Navigable) && !(first instanceof Number))) + // throw new IllegalArgumentException(last + " is not comparable"); } /** @@ -166,6 +167,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @return contains */ @SuppressWarnings("unchecked") + @Override public boolean contains(final Object o) { final int f = this.navigator.compare(this.first, (E) o); final int l = this.navigator.compare((E) o, this.last); @@ -183,6 +185,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @param c other collection * @return containsAll */ + @Override public boolean containsAll(final Collection c) { for (final Object o : c) if (!this.contains(o)) @@ -200,7 +203,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe /** * @see java.util.SortedSet#headSet(java.lang.Object) - * @param toElement FIXME comment + * @param toElement COMMENT * @return headset */ public SortedSet headSet(final E toElement) { @@ -211,6 +214,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @see java.util.Collection#isEmpty() * @return isempty */ + @Override public boolean isEmpty() { if (this.firstOpen && this.lastOpen) return this.navigator.compare(this.navigator.next(this.first), this.last) > 0; @@ -223,6 +227,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @see java.util.Collection#iterator() * @return iterator */ + @Override public Iterator iterator() { return new RangeIterator(); } @@ -239,14 +244,15 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @see java.util.Collection#size() * @return size */ + @Override public int size() { return CollectionsUtilities.count(this.iterator()); } /** * @see java.util.SortedSet#subSet(java.lang.Object, java.lang.Object) - * @param fromElement FIXME comment - * @param toElement FIXME comment + * @param fromElement COMMENT + * @param toElement COMMENT * @return subset */ public SortedSet subSet(final E fromElement, final E toElement) { @@ -255,7 +261,7 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe /** * @see java.util.SortedSet#tailSet(java.lang.Object) - * @param fromElement FIXME comment + * @param fromElement COMMENT * @return fromelement */ public SortedSet tailSet(final E fromElement) { @@ -266,16 +272,18 @@ public class Range extends AbstractUnmodifiableList implements NavigableSe * @see java.util.Collection#toArray() * @return toarray */ + @Override public Object[] toArray() { return new LinkedList(this).toArray(); } /** * @see java.util.Collection#toArray(T[]) - * @param FIXME comment - * @param a FIXME comment + * @param COMMENT + * @param a COMMENT * @return toarray */ + @Override public T[] toArray(final T[] a) { return new LinkedList(this).toArray(a); } diff --git a/KezvhLib/src-lib/net/kezvh/collections/TreeIterator.java b/KezvhLib/src-lib/net/kezvh/collections/TreeIterator.java index ea516a4..91c4dbf 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/TreeIterator.java +++ b/KezvhLib/src-lib/net/kezvh/collections/TreeIterator.java @@ -7,6 +7,7 @@ import java.util.Collections; import java.util.Deque; import java.util.Iterator; import java.util.LinkedList; +import java.util.List; import java.util.Set; /** @@ -31,6 +32,12 @@ public class TreeIterator implements Iterator { private final ChildrenAccessor childrenAccessor; private final Deque> iteratorStack = new LinkedList>(); + private final LinkedList stack = new LinkedList() { + { + this.add(null); + } + }; + private final List unmodifiableStack = Collections.unmodifiableList(this.stack); /** * @param rootNode FIXME comment @@ -59,12 +66,17 @@ public class TreeIterator implements Iterator { */ @Override public T next() { - while (!this.last().hasNext()) + while (!this.last().hasNext()) { this.iteratorStack.removeLast(); // will throw a NSEE if hasNext() is false + this.stack.removeLast(); + } final T nextNode = this.last().next(); + this.stack.set(this.stack.size() - 1, nextNode); final Set children = this.childrenAccessor.getChildren(nextNode); - if (!children.isEmpty()) + if (!children.isEmpty()) { this.iteratorStack.addLast(children.iterator()); + this.stack.add(null); + } return nextNode; } @@ -80,4 +92,11 @@ public class TreeIterator implements Iterator { this.iteratorStack.peekLast().remove(); } + /** + * @return the stack + */ + public List getStack() { + return this.unmodifiableStack; + } + } diff --git a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/AdjacencyCollectionDirectedGraph.java b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/AdjacencyCollectionDirectedGraph.java new file mode 100644 index 0000000..2d3b59f --- /dev/null +++ b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/AdjacencyCollectionDirectedGraph.java @@ -0,0 +1,378 @@ +/** + * + */ +package net.kezvh.collections.graphs.directed; + +import java.util.AbstractMap; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import java.util.Set; + +import net.kezvh.collections.views.MapAsView; +import net.kezvh.functional.lambda.L1; +import net.kezvh.patterns.AbstractFactory; + +/** + * @author afflux + * @param COMMENT + * @param COMMENT + * @param COMMENT + * @param COMMENT + */ +public class AdjacencyCollectionDirectedGraph> extends AbstractMap implements DirectedGraphWithValues { + /** + * @param collectionMaker something that makes a collection + */ + public AdjacencyCollectionDirectedGraph(final AbstractFactory collectionMaker) { + super(); + this.collectionMaker = collectionMaker; + } + + private static final class Entry { + + private NodeValue value; + private final M destinations; + + /** + * @return the value + */ + public NodeValue getValue() { + return this.value; + } + + /** + * @param value the value to set + * @return the old value + */ + public NodeValue setValue(final NodeValue value) { + try { + return this.value; + } finally { + this.value = value; + } + } + + /** + * @return the m + */ + public M getDestinations() { + return this.destinations; + } + + public Entry(final NodeValue value, final M m) { + super(); + this.value = value; + this.destinations = m; + } + } + + private final AbstractFactory collectionMaker; + private final Map> adjacencyListsByNode = new HashMap>(); + + DirectedGraphWithEdgeValues keySet = new WrappedKeySet(this); + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#keySet() + * @return COMMENT + */ + @Override + public DirectedGraphWithEdgeValues keySet() { + return this.keySet; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphNodesWithValues#inEdgeSources(java.lang.Object) + * @param destination COMMENT + * @return COMMENT + */ + @Override + public Map inEdgeSources(final Node destination) { + // TODO Auto-generated method stub + return null; + } + + private final L1 getNodeValue = new L1() { + public NodeValue op(final Node param) { + return AdjacencyCollectionDirectedGraph.this.adjacencyListsByNode.get(param).getValue(); + } + }; + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphNodesWithValues#outEdgeDestinations(java.lang.Object) + * @param source COMMENT + * @return COMMENT + */ + @Override + public Map outEdgeDestinations(final Node source) { + final Entry entry = this.adjacencyListsByNode.get(source); + return new MapAsView(entry.getDestinations().keySet(), this.getNodeValue) { + @Override + public NodeValue put(final Node key, final NodeValue value) { + return AdjacencyCollectionDirectedGraph.this.adjacencyListsByNode.get(key).setValue(value); + } + }; + } + + /** + * @see java.util.Map#clear() + */ + @Override + public void clear() { + this.adjacencyListsByNode.clear(); + } + + /** + * @see java.util.Map#containsKey(java.lang.Object) + * @param key COMMENT + * @return COMMENT + */ + @Override + public boolean containsKey(final Object key) { + return this.adjacencyListsByNode.containsKey(key); + } + + /** + * @see java.util.Map#containsValue(java.lang.Object) + * @param value COMMENT + * @return COMMENT + */ + @Override + public boolean containsValue(final Object value) { + // TODO Auto-generated method stub + return false; + } + + /** + * @see java.util.Map#entrySet() + * @return COMMENT + */ + @Override + public Set> entrySet() { + // TODO Auto-generated method stub + return null; + } + + /** + * @see java.util.Map#get(java.lang.Object) + * @param key COMMENT + * @return COMMENT + */ + @Override + public NodeValue get(final Object key) { + return this.adjacencyListsByNode.get(key).getValue(); + } + + /** + * @see java.util.Map#isEmpty() + * @return COMMENT + */ + @Override + public boolean isEmpty() { + return this.adjacencyListsByNode.isEmpty(); + } + + /** + * @see java.util.Map#put(java.lang.Object, java.lang.Object) + * @param key COMMENT + * @param value COMMENT + * @return COMMENT + */ + @Override + public NodeValue put(final Node key, final NodeValue value) { + if (this.adjacencyListsByNode.containsKey(key)) + return this.adjacencyListsByNode.get(key).setValue(value); + + this.adjacencyListsByNode.put(key, new Entry(value, this.collectionMaker.create())); + return null; + } + + /** + * @see java.util.Map#remove(java.lang.Object) + * @param key COMMENT + * @return COMMENT + */ + @Override + public NodeValue remove(final Object key) { + if (this.adjacencyListsByNode.containsKey(key)) + return this.adjacencyListsByNode.remove(key).getValue(); + return null; + } + + /** + * @see java.util.Map#size() + * @return COMMENT + */ + @Override + public int size() { + return this.adjacencyListsByNode.size(); + } + + /** + * @see java.util.Map#values() + * @return COMMENT + */ + @Override + public Collection values() { + // TODO Auto-generated method stub + return null; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdgesWithValues#addEdge(java.lang.Object, + * java.lang.Object, java.lang.Object) + * @param source COMMENT + * @param destination COMMENT + * @param edgeValue COMMENT + * @return COMMENT + */ + @Override + public EdgeValue addEdge(final Node source, final Node destination, final EdgeValue edgeValue) { + return this.adjacencyListsByNode.get(source).getDestinations().put(destination, edgeValue); + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdgesWithValues#getEdgeValue(java.lang.Object, + * java.lang.Object) + * @param source COMMENT + * @param destination COMMENT + * @return COMMENT + */ + @Override + public EdgeValue getEdgeValue(final Node source, final Node destination) { + return this.adjacencyListsByNode.get(source).getDestinations().get(destination); + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdgesWithValues#removeEdge(java.lang.Object, + * java.lang.Object) + * @param source COMMENT + * @param destination COMMENT + * @return COMMENT + */ + @Override + public EdgeValue removeEdge(final Node source, final Node destination) { + return this.adjacencyListsByNode.get(source).getDestinations().remove(destination); + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdgesWithValues#removeEdge(net.kezvh.collections.graphs.directed.EdgeWithEdgeValue) + * @param edge COMMENT + * @return COMMENT + */ + @Override + public EdgeValue removeEdge(final EdgeWithValues edge) { + return this.removeEdge(edge.getSourceNode(), edge.getDestinationNode()); + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#adjacentFrom(java.lang.Object) + * @param source COMMENT + * @return COMMENT + */ + @Override + public Set adjacentFrom(final Node source) { + // TODO Auto-generated method stub + return null; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#adjacentTo(java.lang.Object) + * @param destination COMMENT + * @return COMMENT + */ + @Override + public Set adjacentTo(final Node destination) { + // TODO Auto-generated method stub + return null; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#containsEdge(java.lang.Object, + * java.lang.Object) + * @param source COMMENT + * @param destination COMMENT + * @return COMMENT + */ + @Override + public boolean containsEdge(final Node source, final Node destination) { + // TODO Auto-generated method stub + return false; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#containsEdge(net.kezvh.collections.graphs.directed.Edge) + * @param edge COMMENT + * @return COMMENT + */ + @Override + public boolean containsEdge(final EdgeWithValues edge) { + // TODO Auto-generated method stub + return false; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#edgeCount() + * @return COMMENT + */ + @Override + public long edgeCount() { + // TODO Auto-generated method stub + return 0; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#edges() + * @return COMMENT + */ + @Override + public Set> edges() { + // TODO Auto-generated method stub + return null; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#inDegree(java.lang.Object) + * @param destination COMMENT + * @return COMMENT + */ + @Override + public int inDegree(final Node destination) { + // TODO Auto-generated method stub + return 0; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#inEdges(java.lang.Object) + * @param destination COMMENT + * @return COMMENT + */ + @Override + public Set> inEdges(final Node destination) { + // TODO Auto-generated method stub + return null; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#outDegree(java.lang.Object) + * @param source COMMENT + * @return COMMENT + */ + @Override + public int outDegree(final Node source) { + // TODO Auto-generated method stub + return 0; + } + + /** + * @see net.kezvh.collections.graphs.directed.DirectedGraphEdges#outEdges(java.lang.Object) + * @param source COMMENT + * @return COMMENT + */ + @Override + public Set> outEdges(final Node source) { + // TODO Auto-generated method stub + return null; + } + +} diff --git a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraphSet.java b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/GenericDirectedGraphSet.java similarity index 86% rename from KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraphSet.java rename to KezvhLib/src-lib/net/kezvh/collections/graphs/directed/GenericDirectedGraphSet.java index 7ccc552..8f02b8d 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraphSet.java +++ b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/GenericDirectedGraphSet.java @@ -11,11 +11,11 @@ import net.kezvh.functional.lambda.L1; /** * @author mjacob - * * @param COMMENT * @param COMMENT */ -public class HashDirectedGraphSet extends AbstractSet implements DirectedGraphWithEdgeValues { +public class GenericDirectedGraphSet extends AbstractSet implements DirectedGraphWithEdgeValues { + @Override public int hashCode() { final int prime = 31; @@ -32,7 +32,7 @@ public class HashDirectedGraphSet extends AbstractSet imp return false; if (this.getClass() != obj.getClass()) return false; - final HashDirectedGraphSet other = (HashDirectedGraphSet) obj; + final GenericDirectedGraphSet other = (GenericDirectedGraphSet) obj; if (this.innerGraph == null) { if (other.innerGraph != null) return false; @@ -42,17 +42,25 @@ public class HashDirectedGraphSet extends AbstractSet imp } private static final Object PRESENT = new Object(); - private final HashDirectedGraph innerGraph = new HashDirectedGraph(); + private final DirectedGraphWithValues innerGraph; + + /** + * @param innerGraph a graph on which to build the set + */ + public GenericDirectedGraphSet(final DirectedGraphWithValues innerGraph) { + super(); + this.innerGraph = innerGraph; + } private final L1 presentMapper = new L1() { public Object op(final Node param) { - return HashDirectedGraphSet.PRESENT; + return GenericDirectedGraphSet.PRESENT; } }; @Override public boolean add(final Node e) { - return this.innerGraph.put(e, HashDirectedGraphSet.PRESENT) != null; + return this.innerGraph.put(e, GenericDirectedGraphSet.PRESENT) != null; } @SuppressWarnings("unchecked") diff --git a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraph.java b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraph.java index 3e6ee6e..5104a35 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraph.java +++ b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/HashDirectedGraph.java @@ -3,14 +3,15 @@ */ package net.kezvh.collections.graphs.directed; +import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import net.kezvh.collections.Pair; -import net.kezvh.collections.Map2.HashMap2; -import net.kezvh.collections.Map2.Map2; +import net.kezvh.collections.DualMap.DualMap; +import net.kezvh.collections.DualMap.HashDualMap; import net.kezvh.collections.views.MapAsView; import net.kezvh.collections.views.SetView; import net.kezvh.collections.wrappers.WrappedSet; @@ -19,8 +20,8 @@ import net.kezvh.functional.lambda.L1; import com.google.common.collect.AbstractMapEntry; /** - * Nodes are tracked by a HashMap. Edges are tracked by a HashMap2. - * This gives O(1) performance for adding or querying anything. + * Nodes are tracked by a HashMap. Edges are tracked by a HashMap2. This gives + * O(1) performance for adding or querying anything. * * @author afflux * @param COMMENT @@ -34,7 +35,7 @@ public class HashDirectedGraph extends HashMap edges = new HashMap2(); + private final DualMap edges = new HashDualMap(); private final L1, Map.Entry, EdgeValue>> getEdges = new L1, Map.Entry, EdgeValue>>() { /** * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) @@ -132,14 +133,14 @@ public class HashDirectedGraph extends HashMap, Map2.Entry> getEdges2 = new L1, Map2.Entry>() { + private final L1, DualMap.Entry> getEdges2 = new L1, DualMap.Entry>() { /** * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) * @param param COMMENT * @return COMMENT */ @Override - public EdgeWithValues op(final Map2.Entry param) { + public EdgeWithValues op(final DualMap.Entry param) { return new EdgeWithValues() { /** * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getDestination() @@ -345,7 +346,7 @@ public class HashDirectedGraph extends HashMap> inEdges(final Node destination) { - return new SetView, EdgeWithValues>(this.edges.entrySetOnKey2(destination), this.getEdges2); + return new SetView, EdgeWithValues>(this.edges.entrySetOnKey2(destination), this.getEdges2); } /** @@ -375,7 +376,7 @@ public class HashDirectedGraph extends HashMap> outEdges(final Node source) { - return new SetView, EdgeWithValues>(this.edges.entrySetOnKey1(source), this.getEdges2); + return new SetView, EdgeWithValues>(this.edges.entrySetOnKey1(source), this.getEdges2); } @@ -588,11 +589,21 @@ public class HashDirectedGraph extends HashMap adjacentFrom(final Node source) { - return this.edges.keySetOnKey1(source); + if (this.containsKey(source)) { + if (this.edges.containsKey1(source)) + return this.edges.keySetOnKey1(source); + return Collections.emptySet(); + } + return null; } @Override public Set adjacentTo(final Node destination) { - return this.edges.keySetOnKey2(destination); + if (this.containsKey(destination)) { + if (this.edges.containsKey2(destination)) + return this.edges.keySetOnKey2(destination); + return Collections.emptySet(); + } + return null; } } diff --git a/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/WrappedKeySet.java b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/WrappedKeySet.java new file mode 100644 index 0000000..fc4eaa8 --- /dev/null +++ b/KezvhLib/src-lib/net/kezvh/collections/graphs/directed/WrappedKeySet.java @@ -0,0 +1,232 @@ +/** + * + */ +package net.kezvh.collections.graphs.directed; + +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.Set; +import java.util.Map.Entry; + +import net.kezvh.collections.views.SetView; +import net.kezvh.functional.Operations; +import net.kezvh.functional.lambda.L1; + +import com.google.common.collect.AbstractMapEntry; + +/** + * @author afflux + * @param node type + * @param node value type + * @param edge value type + */ +class WrappedKeySet extends AbstractSet implements DirectedGraphWithEdgeValues { + private final DirectedGraphWithValues wrappedGraph; + + /** + * @param wrappedGraph wrapped graph + */ + public WrappedKeySet(final DirectedGraphWithValues wrappedGraph) { + this.wrappedGraph = wrappedGraph; + } + + @Override + public boolean containsEdge(final Node source, final Node destination) { + return this.wrappedGraph.containsEdge(source, destination); + } + + @Override + public long edgeCount() { + return this.wrappedGraph.edgeCount(); + } + + @Override + public int inDegree(final Node destination) { + return this.wrappedGraph.inDegree(destination); + } + + @Override + public int outDegree(final Node source) { + return this.wrappedGraph.outDegree(source); + } + + @Override + public Set adjacentFrom(final Node source) { + return this.wrappedGraph.adjacentFrom(source); + } + + @Override + public Set adjacentTo(final Node destination) { + return this.wrappedGraph.adjacentTo(destination); + } + + @Override + public EdgeValue addEdge(final Node source, final Node destination, final EdgeValue edgeValue) { + return this.wrappedGraph.addEdge(source, destination, edgeValue); + } + + @Override + public EdgeValue getEdgeValue(final Node source, final Node destination) { + return this.wrappedGraph.getEdgeValue(source, destination); + } + + @Override + public EdgeValue removeEdge(final Node source, final Node destination) { + return this.wrappedGraph.removeEdge(source, destination); + } + + @Override + public EdgeValue removeEdge(final EdgeWithEdgeValue edge) { + return this.wrappedGraph.removeEdge(edge.getSourceNode(), edge.getDestinationNode()); + } + + @Override + public boolean containsEdge(final EdgeWithEdgeValue edge) { + return this.wrappedGraph.containsEdge(edge.getSourceNode(), edge.getDestinationNode()); + } + + private final L1, EdgeWithValues> getSetEdges = new L1, EdgeWithValues>() { + @Override + public EdgeWithEdgeValue op(final EdgeWithValues param) { + return new EdgeWithEdgeValue() { + @Override + public Node getDestinationNode() { + return param.getDestinationNode(); + } + + @Override + public Node getSourceNode() { + return param.getSourceNode(); + } + + @Override + public EdgeValue getValue() { + return param.getValue(); + } + + public EdgeValue setValue(final EdgeValue newValue) { + return param.setValue(newValue); + } + }; + } + }; + + private final L1, EdgeWithEdgeValue> inverseSetEdges = new L1, EdgeWithEdgeValue>() { + @Override + public EdgeWithValues op(final EdgeWithEdgeValue param) { + return new EdgeWithValues() { + @Override + public java.util.Map.Entry getDestination() { + return new AbstractMapEntry() { + @Override + public Node getKey() { + return getDestinationNode(); + } + + @Override + public NodeValue getValue() { + return WrappedKeySet.this.wrappedGraph.get(this.getKey()); + } + }; + } + + @Override + public Node getDestinationNode() { + return param.getDestinationNode(); + } + + @Override + public java.util.Map.Entry getSource() { + return new AbstractMapEntry() { + @Override + public Node getKey() { + return getSourceNode(); + } + + @Override + public NodeValue getValue() { + return WrappedKeySet.this.wrappedGraph.get(this.getKey()); + } + }; + } + + @Override + public Node getSourceNode() { + return param.getSourceNode(); + } + + @Override + public EdgeValue getValue() { + return param.getValue(); + } + + public EdgeValue setValue(final EdgeValue newValue) { + return param.setValue(newValue); + } + }; + } + }; + + private final Set> edgesView = new SetView, EdgeWithEdgeValue>(this.wrappedGraph.edges(), this.getSetEdges, this.inverseSetEdges); + + @Override + public Set> edges() { + return this.edgesView; + } + + @Override + public Set> inEdges(final Node destination) { + return new SetView, EdgeWithEdgeValue>(this.wrappedGraph.inEdges(destination), this.getSetEdges, this.inverseSetEdges); + } + + @Override + public Set> outEdges(final Node source) { + return new SetView, EdgeWithEdgeValue>(this.wrappedGraph.outEdges(source), this.getSetEdges, this.inverseSetEdges); + } + + /** + * @see java.util.Set#clear() + */ + @Override + public void clear() { + this.wrappedGraph.clear(); + } + + @Override + public boolean contains(final Object o) { + return this.wrappedGraph.containsKey(o); + } + + @Override + public boolean isEmpty() { + return this.wrappedGraph.isEmpty(); + } + + private final L1> getKey = Operations.getKey(); + private final Set entrySet = new SetView, Node>(this.wrappedGraph.entrySet(), this.getKey); + + @Override + public Iterator iterator() { + return this.entrySet.iterator(); + } + + @Override + public boolean remove(final Object o) { + return this.wrappedGraph.remove(o) != null; + } + + @Override + public int size() { + return this.wrappedGraph.size(); + } + + @Override + public Object[] toArray() { + return this.entrySet.toArray(); + } + + @Override + public T[] toArray(final T[] a) { + return this.entrySet.toArray(a); + } +} \ No newline at end of file diff --git a/KezvhLib/src-lib/net/kezvh/collections/heaps/PairingHeap.java b/KezvhLib/src-lib/net/kezvh/collections/heaps/PairingHeap.java index 2d518fb..3e13f7d 100755 --- a/KezvhLib/src-lib/net/kezvh/collections/heaps/PairingHeap.java +++ b/KezvhLib/src-lib/net/kezvh/collections/heaps/PairingHeap.java @@ -189,17 +189,22 @@ public class PairingHeap> extends AbstractHeap @Override public W reweight(final E t, final W newWeight) { if (!(this.map.containsKey(t))) - throw new IllegalArgumentException("element must be in the heap in order to reweight it"); + throw new IllegalArgumentException("element " + t + " must be in the heap in order to reweight it"); final PairingHeapNode node = this.map.get(t); + final W oldWeight = node.getValue(); try { return node.setValue(newWeight); } finally { - if (this.root != node) + if (this.root == node) { + if (this.size() != 1) + if (this.comparator.compare(newWeight, oldWeight) > 0) + throw new UnimplementedException("haven't yet implemented increasing the root node's weight (node " + t + " old weight: " + oldWeight + " new eight: " + newWeight); + } else { node.pruneSelf(); - - this.root = this.merge(this.root, node); + this.root = this.merge(this.root, node); + } } } diff --git a/KezvhLib/src-lib/net/kezvh/collections/text/TrieMap.java b/KezvhLib/src-lib/net/kezvh/collections/text/TrieMap.java index d46f0fa..5549741 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/text/TrieMap.java +++ b/KezvhLib/src-lib/net/kezvh/collections/text/TrieMap.java @@ -21,13 +21,13 @@ import net.kezvh.functional.lambda.L1; /** * @author afflux - * @param FIXME document + * @param COMMENT */ public class TrieMap extends AbstractMap implements SortedMap { private final TreeIterator.ChildrenAccessor> childrenAccessor = new TreeIterator.ChildrenAccessor>() { /** * @see net.kezvh.collections.TreeIterator.ChildrenAccessor#getChildren(java.lang.Object) - * @param node FIXME document + * @param node COMMENT * @return x */ @Override @@ -65,7 +65,6 @@ public class TrieMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap next() { - // TODO Auto-generated method stub return iterator.next(); } @@ -86,13 +84,6 @@ public class TrieMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap getSuffixNode(final int index) { @@ -116,7 +107,7 @@ public class TrieMap extends AbstractMap implements SortedMap find(final char key) { @@ -124,7 +115,7 @@ public class TrieMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap newValue, final int insertionPoint) { final char[] newKeys = new char[this.keys.length + 1]; @@ -167,8 +158,8 @@ public class TrieMap extends AbstractMap implements SortedMap put(final char key, final TrieNode newValue) { @@ -196,7 +187,7 @@ public class TrieMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap, TrieNode> map = new L1, TrieNode>() { /** * @see L1 - * @param param FIXME document + * @param param COMMENT * @return x */ @Override @@ -310,6 +301,7 @@ public class TrieMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap extends AbstractMap implements SortedMap headMap(final String toKey) { @@ -456,8 +446,8 @@ public class TrieMap extends AbstractMap implements SortedMap subMap(final String fromKey, final String toKey) { @@ -466,7 +456,7 @@ public class TrieMap extends AbstractMap implements SortedMap tailMap(final String fromKey) { @@ -510,7 +500,7 @@ public class TrieMap extends AbstractMap implements SortedMap getKeysSimilarTo(final String key) { diff --git a/KezvhLib/src-lib/net/kezvh/collections/unmodifiable/AbstractUnmodifiableCollection.java b/KezvhLib/src-lib/net/kezvh/collections/unmodifiable/AbstractUnmodifiableCollection.java index dc8146e..2a7ad66 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/unmodifiable/AbstractUnmodifiableCollection.java +++ b/KezvhLib/src-lib/net/kezvh/collections/unmodifiable/AbstractUnmodifiableCollection.java @@ -1,34 +1,18 @@ package net.kezvh.collections.unmodifiable; +import java.util.AbstractCollection; import java.util.Collection; /** * @author afflux * @param FIXME comment */ -public abstract class AbstractUnmodifiableCollection implements Collection { - - /** - * @see java.util.Collection#add(java.lang.Object) - * @param e FIXME comment - * @return b - */ - public final boolean add(final E e) { - throw new UnsupportedOperationException(); - } - - /** - * @see java.util.Collection#addAll(java.util.Collection) - * @param c FIXME comment - * @return b - */ - public final boolean addAll(final Collection c) { - throw new UnsupportedOperationException(); - } +public abstract class AbstractUnmodifiableCollection extends AbstractCollection { /** * @see java.util.Collection#clear() */ + @Override public final void clear() { throw new UnsupportedOperationException(); } @@ -38,6 +22,7 @@ public abstract class AbstractUnmodifiableCollection implements Collection * @param o FIXME comment * @return b */ + @Override public final boolean remove(final Object o) { throw new UnsupportedOperationException(); } @@ -47,6 +32,7 @@ public abstract class AbstractUnmodifiableCollection implements Collection * @param c FIXME comment * @return b */ + @Override public final boolean removeAll(final Collection c) { throw new UnsupportedOperationException(); } @@ -56,6 +42,7 @@ public abstract class AbstractUnmodifiableCollection implements Collection * @param c FIXME comment * @return b */ + @Override public final boolean retainAll(final Collection c) { throw new UnsupportedOperationException(); } diff --git a/KezvhLib/src-lib/net/kezvh/collections/views/CollectionView.java b/KezvhLib/src-lib/net/kezvh/collections/views/CollectionView.java index 3833217..525726c 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/views/CollectionView.java +++ b/KezvhLib/src-lib/net/kezvh/collections/views/CollectionView.java @@ -7,6 +7,7 @@ import java.util.AbstractCollection; import java.util.Collection; import java.util.Iterator; +import net.kezvh.functional.Operations; import net.kezvh.functional.lambda.L1; /** @@ -26,7 +27,7 @@ public class CollectionView extends AbstractCollection { */ @SuppressWarnings("unchecked") public CollectionView(final Collection innerCollection, final L1 mappingFunction) { - this(innerCollection, mappingFunction, (L1) L1.UNSUPPORTED); + this(innerCollection, mappingFunction, (L1) Operations.UNSUPPORTED); } /** @@ -36,6 +37,8 @@ public class CollectionView extends AbstractCollection { */ public CollectionView(final Collection innerCollection, final L1 mappingFunction, final L1 inverseFunction) { super(); + if (innerCollection == null) + throw new IllegalArgumentException(); this.innerCollection = innerCollection; this.mappingFunction = mappingFunction; this.inverseFunction = inverseFunction; @@ -145,7 +148,7 @@ public class CollectionView extends AbstractCollection { @SuppressWarnings("unchecked") @Override public boolean contains(final Object o) { - if (this.inverseFunction.equals(L1.UNSUPPORTED)) + if (this.inverseFunction.equals(Operations.UNSUPPORTED)) return super.contains(o); return this.innerCollection.contains(this.inverseFunction.op((D) o)); } @@ -158,7 +161,7 @@ public class CollectionView extends AbstractCollection { @SuppressWarnings("unchecked") @Override public boolean containsAll(final Collection c) { - if (this.inverseFunction.equals(L1.UNSUPPORTED)) + if (this.inverseFunction.equals(Operations.UNSUPPORTED)) return super.containsAll(c); final Collection inverse = new CollectionView((Collection) c, this.inverseFunction, this.mappingFunction); @@ -173,7 +176,7 @@ public class CollectionView extends AbstractCollection { @SuppressWarnings("unchecked") @Override public boolean remove(final Object o) { - if (this.inverseFunction.equals(L1.UNSUPPORTED)) + if (this.inverseFunction.equals(Operations.UNSUPPORTED)) super.remove(o); return this.innerCollection.remove(this.inverseFunction.op((D) o)); @@ -196,7 +199,7 @@ public class CollectionView extends AbstractCollection { @SuppressWarnings("unchecked") @Override public boolean removeAll(final Collection c) { - if (this.inverseFunction.equals(L1.UNSUPPORTED)) + if (this.inverseFunction.equals(Operations.UNSUPPORTED)) return super.removeAll(c); final Collection inverse = new CollectionView((Collection) c, this.inverseFunction, this.mappingFunction); @@ -211,7 +214,7 @@ public class CollectionView extends AbstractCollection { @SuppressWarnings("unchecked") @Override public boolean retainAll(final Collection c) { - if (this.inverseFunction.equals(L1.UNSUPPORTED)) + if (this.inverseFunction.equals(Operations.UNSUPPORTED)) return super.removeAll(c); final Collection inverse = new CollectionView((Collection) c, this.inverseFunction, this.mappingFunction); diff --git a/KezvhLib/src-lib/net/kezvh/collections/views/ConditionalCollectionView.java b/KezvhLib/src-lib/net/kezvh/collections/views/ConditionalCollectionView.java index 6fc0907..fc95ebd 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/views/ConditionalCollectionView.java +++ b/KezvhLib/src-lib/net/kezvh/collections/views/ConditionalCollectionView.java @@ -7,6 +7,7 @@ import java.util.AbstractCollection; import java.util.Collection; import java.util.Iterator; +import net.kezvh.functional.Operations; import net.kezvh.functional.lambda.L1; /** @@ -43,7 +44,7 @@ public class ConditionalCollectionView extends AbstractCollection { */ @Override public int size() { - return L1.ITERATOR_COUNT.op(this.iterator()); + return Operations.ITERATOR_COUNT.op(this.iterator()); } } diff --git a/KezvhLib/src-lib/net/kezvh/collections/views/MapAsView.java b/KezvhLib/src-lib/net/kezvh/collections/views/MapAsView.java index 1eb056d..e11ca62 100644 --- a/KezvhLib/src-lib/net/kezvh/collections/views/MapAsView.java +++ b/KezvhLib/src-lib/net/kezvh/collections/views/MapAsView.java @@ -8,6 +8,7 @@ import java.util.Map; import java.util.Set; import net.kezvh.collections.MapEntryImpl; +import net.kezvh.functional.Operations; import net.kezvh.functional.lambda.L1; /** @@ -64,7 +65,7 @@ public class MapAsView extends AbstractMap { */ @SuppressWarnings("unchecked") public MapAsView(final Set sourceSet, final L1 op) { - this(sourceSet, op, (L1) L1.UNSUPPORTED); + this(sourceSet, op, (L1) Operations.UNSUPPORTED); } /** @@ -85,7 +86,7 @@ public class MapAsView extends AbstractMap { @SuppressWarnings("unchecked") @Override public boolean containsValue(final Object value) { - if (L1.UNSUPPORTED.equals(this.inverseEntryOp)) + if (Operations.UNSUPPORTED.equals(this.inverseEntryOp)) return super.containsValue(value); return this.sourceSet.contains(this.inverseMapOp.op((D) value)); diff --git a/KezvhLib/src-lib/net/kezvh/functional/Operations.java b/KezvhLib/src-lib/net/kezvh/functional/Operations.java new file mode 100644 index 0000000..c440c2f --- /dev/null +++ b/KezvhLib/src-lib/net/kezvh/functional/Operations.java @@ -0,0 +1,234 @@ +package net.kezvh.functional; + +import java.util.Collection; +import java.util.Iterator; +import java.util.Map; +import java.util.Map.Entry; + +import net.kezvh.collections.DualMap.DualMap; +import net.kezvh.functional.lambda.L0; +import net.kezvh.functional.lambda.L1; +import net.kezvh.functional.lambda.L2; +import net.kezvh.functional.lambda.Predicate2; +import net.kezvh.lang.UtilityClass; + +/** + * @author afflux + */ +public final class Operations extends UtilityClass { + /** + * + */ + public static final Predicate2 EQUALS = new Predicate2() { + /** + * @see net.kezvh.functional.lambda.L2#op(java.lang.Object, + * java.lang.Object) + * @param param1 param1 + * @param param2 param2 + * @return x + */ + @Override + public Boolean op(final Object param1, final Object param2) { + return (param1 == null) ? param2 == null : param1.equals(param2); + } + }; + + /** + * @param key type + * @param value type + * @return function which returns the value of a map entry + */ + public static L1> getValue() { + return new L1>() { + @Override + public V op(final Entry arg0) { + return arg0.getValue(); + } + }; + } + + /** + * @param key type + * @param value type + * @return function which returns the value of a map entry + */ + public static L1> getKey() { + return new L1>() { + @Override + public K op(final Entry arg0) { + return arg0.getKey(); + } + }; + } + + /** + * @param COMMENT + * @return COMMENT + */ + @SuppressWarnings("unchecked") + public static final Predicate2 equals() { + return (Predicate2) Operations.EQUALS; + } + + /** + * @param COMMENT + * @param t COMMENT + * @return COMMENT + */ + public static final L0 constant0(final T t) { + return new L0() { + @Override + public T op() { + return t; + } + }; + } + + /** + * @param COMMENT + * @param COMMENT + * @param s COMMENT + * @return COMMENT + */ + public static final L1 constant1(final S s) { + return new L1() { + public S op(final T param) { + return s; + } + }; + } + + /** + * @param COMMENT + * @param COMMENT + * @param COMMENT + * @param s COMMENT + * @return COMMENT + */ + public static final L2 constant2(final S s) { + return new L2() { + public S op(final T param, final U param2) { + return s; + } + }; + } + + /** + * @param COMMENT + * @param COMMENT + * @param COMMENT + * @param a COMMENT + * @param b COMMENT + * @return COMMENT + */ + public static final L1 compose(final L1 a, final L1 b) { + return new L1() { + public S op(final U param) { + return a.op(b.op(param)); + } + }; + } + + /** + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param defaultValue COMMENT + * @return COMMENT + */ + public static final L1 forMap(final Map map, final S defaultValue) { + return new L1() { + public S op(final T param) { + if (map.containsKey(param)) + return map.get(param); + return defaultValue; + } + }; + } + + /** + * @param COMMENT + * @param COMMENT + * @param COMMENT + * @param map COMMENT + * @param defaultValue COMMENT + * @return COMMENT + */ + public static final L2 forMap2(final DualMap map, final D defaultValue) { + return new L2() { + public D op(final K1 param1, final K2 param2) { + return map.get(param1, param2); + } + }; + } + + /** + * @param type + * @return map which returns its argument + */ + public static final L1 identity() { + return new L1() { + public T op(final T param) { + return param; + } + }; + } + + /** + * returns the size of a collection + */ + public static final L1> COLLECTION_SIZE = new L1>() { + public Integer op(final Collection value) { + return value.size(); + } + }; + /** + * returns the number of elements in the iterator (by iterating them, silly) + */ + public static final L1> ITERATOR_COUNT = new L1>() { + /** + * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) + * @param arg0 some argument + * @return number of elements + */ + @Override + public Integer op(final Iterator arg0) { + int i; + for (i = 0; arg0.hasNext(); i++) + arg0.next(); + return i; + } + }; + /** + * + */ + public static final L1 UNSUPPORTED = new L1() { + public Object op(final Object param) { + throw new UnsupportedOperationException(); + } + }; + /** + * + */ + public static final L2 SUMI = new L2() { + /** + * @see net.kezvh.functional.lambda.L2#op(java.lang.Object, + * java.lang.Object) + * @param arg0 some argument + * @param arg1 some argument + * @return the sum of the arguments + */ + @Override + public Integer op(final Integer arg0, final Integer arg1) { + return Integer.valueOf(arg0.intValue() + arg1.intValue()); + } + }; + /** + * + */ + public static final L1 INTEGER_INCREMENTER = new L1() { + public Integer op(final Integer param) { + return param + 1; + } + }; +} diff --git a/KezvhLib/src-lib/net/kezvh/functional/lambda/L1.java b/KezvhLib/src-lib/net/kezvh/functional/lambda/L1.java dissimilarity index 85% index 4bc2cc4..900b25a 100644 --- a/KezvhLib/src-lib/net/kezvh/functional/lambda/L1.java +++ b/KezvhLib/src-lib/net/kezvh/functional/lambda/L1.java @@ -1,70 +1,15 @@ -package net.kezvh.functional.lambda; - -import java.util.Collection; -import java.util.Iterator; -import java.util.Map; -import java.util.Map.Entry; - -/** - * @author afflux - * @param return type - * @param

parameter type - */ -public interface L1 { - /** - * returns the size of a collection - */ - L1> COLLECTION_SIZE = new L1>() { - public Integer op(final Collection value) { - return value.size(); - } - }; - - /** - * returns the number of elements in the iterator - */ - L1> ITERATOR_COUNT = new L1>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param arg0 some argument - * @return number of elements - */ - @Override - public Integer op(final Iterator arg0) { - int i; - for (i = 0; arg0.hasNext(); i++) - arg0.next(); - return i; - } - }; - - /** - * returns the key of the map - */ - L1> VALUE = new L1>() { - /** - * @see net.kezvh.functional.lambda.L1#op(java.lang.Object) - * @param arg0 some argument - * @return object - */ - @Override - public Object op(final Entry arg0) { - return arg0.getValue(); - } - }; - - /** - * - */ - public static final L1 UNSUPPORTED = new L1() { - public Object op(final Object param) { - throw new UnsupportedOperationException(); - } - }; - - /** - * @param param - * @return stuff - */ - R op(P param); -} \ No newline at end of file +package net.kezvh.functional.lambda; + + +/** + * @author afflux + * @param return type + * @param

parameter type + */ +public interface L1 { + /** + * @param param + * @return stuff + */ + R op(P param); +} \ No newline at end of file diff --git a/KezvhLib/src-lib/net/kezvh/functional/lambda/L2.java b/KezvhLib/src-lib/net/kezvh/functional/lambda/L2.java dissimilarity index 61% index 9850d08..ad283fa 100644 --- a/KezvhLib/src-lib/net/kezvh/functional/lambda/L2.java +++ b/KezvhLib/src-lib/net/kezvh/functional/lambda/L2.java @@ -1,33 +1,16 @@ -package net.kezvh.functional.lambda; - -/** - * @author afflux - * @param return type - * @param first parameter type - * @param second parameter type - */ -public interface L2 { - /** - * - */ - L2 SUMI = new L2() { - /** - * @see net.kezvh.functional.lambda.L2#op(java.lang.Object, - * java.lang.Object) - * @param arg0 some argument - * @param arg1 some argument - * @return the sum of the arguments - */ - @Override - public Integer op(final Integer arg0, final Integer arg1) { - return Integer.valueOf(arg0.intValue() + arg1.intValue()); - } - }; - - /** - * @param param1 - * @param param2 - * @return stuff - */ - R op(P1 param1, P2 param2); -} \ No newline at end of file +package net.kezvh.functional.lambda; + +/** + * @author afflux + * @param return type + * @param first parameter type + * @param second parameter type + */ +public interface L2 { + /** + * @param param1 + * @param param2 + * @return stuff + */ + R op(P1 param1, P2 param2); +} \ No newline at end of file diff --git a/KezvhLib/src-lib/net/kezvh/functional/lambda/Operations.java b/KezvhLib/src-lib/net/kezvh/functional/lambda/Operations.java deleted file mode 100644 index 029cf9b..0000000 --- a/KezvhLib/src-lib/net/kezvh/functional/lambda/Operations.java +++ /dev/null @@ -1,140 +0,0 @@ -package net.kezvh.functional.lambda; - -import java.util.Map; - -import net.kezvh.collections.Map2.Map2; -import net.kezvh.lang.UtilityClass; - -/** - * @author afflux - */ -public final class Operations extends UtilityClass { - /** - * - */ - public static final Predicate2 EQUALS = new Predicate2() { - /** - * @see net.kezvh.functional.lambda.L2#op(java.lang.Object, java.lang.Object) - * @param param1 param1 - * @param param2 param2 - * @return x - */ - @Override - public Boolean op(final Object param1, final Object param2) { - return (param1 == null) ? param2 == null : param1.equals(param2); - } - }; - - /** - * @param COMMENT - * @return COMMENT - */ - @SuppressWarnings("unchecked") - public static final Predicate2 EQUALS() { - return (Predicate2) Operations.EQUALS; - } - - /** - * @param COMMENT - * @param t COMMENT - * @return COMMENT - */ - public static final L0 CONSTANT(final T t) { - return new L0() { - @Override - public T op() { - return t; - } - }; - } - - /** - * @param COMMENT - * @param COMMENT - * @param s COMMENT - * @return COMMENT - */ - public static final L1 CONSTANT(final S s) { - return new L1() { - public S op(final T param) { - return s; - } - }; - } - - /** - * @param COMMENT - * @param COMMENT - * @param COMMENT - * @param s COMMENT - * @return COMMENT - */ - public static final L2 CONSTANT(final S s) { - return new L2() { - public S op(final T param, final U param2) { - return s; - } - }; - } - - /** - * @param COMMENT - * @param COMMENT - * @param COMMENT - * @param a COMMENT - * @param b COMMENT - * @return COMMENT - */ - public static final L1 compose(final L1 a, final L1 b) { - return new L1() { - public S op(final U param) { - return a.op(b.op(param)); - } - }; - } - - /** - * @param COMMENT - * @param COMMENT - * @param map COMMENT - * @param defaultValue COMMENT - * @return COMMENT - */ - public static final L1 forMap(final Map map, final S defaultValue) { - return new L1() { - public S op(final T param) { - if (map.containsKey(param)) - return map.get(param); - return defaultValue; - } - }; - } - - /** - * @param COMMENT - * @param COMMENT - * @param COMMENT - * @param map COMMENT - * @param defaultValue COMMENT - * @return COMMENT - */ - public static final L2 forMap2(final Map2 map, final D defaultValue) { - return new L2() { - public D op(final K1 param1, final K2 param2) { - return map.get(param1, param2); - } - }; - } - - /** - * @param type - * @return map which returns its argument - */ - public static final L1 identity() { - return new L1() { - public T op(final T param) { - return param; - } - }; - } -} diff --git a/KezvhLib/src-lib/net/kezvh/patterns/AbstractFactory.java b/KezvhLib/src-lib/net/kezvh/patterns/AbstractFactory.java index 008fd3b..64d8a95 100755 --- a/KezvhLib/src-lib/net/kezvh/patterns/AbstractFactory.java +++ b/KezvhLib/src-lib/net/kezvh/patterns/AbstractFactory.java @@ -2,15 +2,13 @@ package net.kezvh.patterns; /** * @author mjacob - * * @param FIXME comment */ public interface AbstractFactory { /** * @author mjacob - * */ - class CreationFailedException extends Exception { + class CreationFailedException extends RuntimeException { public CreationFailedException() { super(); -- 2.11.4.GIT