G
Solche Probleme, wie du sie gerade hast, kenne ich. Ich poste da unten mal eine Klasse, in der ich ein ähnliches Problem hatte/habe. Es ist die Klasse eines gerichteten Graphen. Bei dieser Klasse hatte ich das Problem, dass die Methoden, mit denen man die Vorgänger eines Wertes erhält, und die Methoden, mit denen man die Nachfolger erhält, sich sehr ähnlich waren. Wie du siehst, habe ich das Problem zwar gelöst, dafür habe ich jetzt aber Code, der deutlich komplizierter ist (dafür aber kleiner). Es sollte dir also klar sein, dass es nicht nur positive Auswirkungen hat, wenn man Redundanz beseitigt.
Hier ist der Code:
package container;
import java.util.*;
public class DirectedGraph<ElementType> extends AbstractCollection<ElementType>
{
private final HashMap<ElementType,Node> nodeMap;
public DirectedGraph ()
{
nodeMap = new HashMap<ElementType,Node> ();
}
public DirectedGraph (final int initialCapacity)
{
if (initialCapacity < 0) throw new IllegalArgumentException();
nodeMap = new HashMap<ElementType,Node> (initialCapacity);
}
@Overrides
public boolean add (final ElementType value)
{
if (value == null) return false;
if (nodeMap.keySet().contains(value)) return false;
nodeMap.put (value, new Node (value));
return true;
}
@Overrides
public void clear ()
{
nodeMap.clear();
}
@Overrides
public boolean contains (final Object o)
{
return nodeMap.keySet().contains(o);
}
@Overrides
public int size()
{
return nodeMap.size();
}
@Overrides
public boolean remove (final Object value)
{
final Node node = nodeMap.get(value);
if (node == null) return false;
nodeMap.remove(value);
removeConnections(node);
return true;
}
private void removeConnections (final Node node)
{
final LinkedList<Node> successorList =
node.getNeighborNodes(NeighborType.SUCCESSOR);
final LinkedList<Node> predecessorList =
node.getNeighborNodes(NeighborType.PREDECESSOR);
for (final Node currentNode : successorList)
{
currentNode.removeNeighborNode(NeighborType.PREDECESSOR,node);
}
for (final Node currentNode : predecessorList)
{
currentNode.removeNeighborNode(NeighborType.SUCCESSOR,node);
}
}
@Overrides
public Iterator<ElementType> iterator()
{
return new GraphIterator ();
}
public void addEdge (final ElementType predecessor, final ElementType successor)
{
if (predecessor == null) throw new NullPointerException();
if (successor == null) throw new NullPointerException();
add(predecessor);
add(successor);
final Node predecessorNode = nodeMap.get(predecessor);
final Node successorNode = nodeMap.get(successor);
predecessorNode.addNeighborNode(NeighborType.SUCCESSOR,successorNode);
successorNode.addNeighborNode(NeighborType.PREDECESSOR,predecessorNode);
}
public void removeEdge (final ElementType predecessor, final ElementType successor)
{
final Node predecessorNode = nodeMap.get(predecessor);
if (predecessorNode == null) return;
final Node successorNode = nodeMap.get(successor);
if (successorNode == null) return;
predecessorNode.removeNeighborNode(NeighborType.SUCCESSOR,successorNode);
successorNode.removeNeighborNode(NeighborType.PREDECESSOR,predecessorNode);
}
private LinkedList<ElementType> getValuesFromNodes(final LinkedList<Node> nodeList)
{
final LinkedList<ElementType> valueList = new LinkedList<ElementType>();
for (final Node node : nodeList)
{
valueList.add(node.getValue());
}
return valueList;
}
public LinkedList<ElementType> getDirectSuccessors (final ElementType value)
{
return getDirectNeighbors(NeighborType.SUCCESSOR, value);
}
public LinkedList<ElementType> getDirectPredecessors (final ElementType value)
{
return getDirectNeighbors(NeighborType.PREDECESSOR, value);
}
private LinkedList<ElementType> getDirectNeighbors (final NeighborType type,
final ElementType value)
{
assert(type != null);
final Node node = nodeMap.get(value);
if (node == null) return null;
return getValuesFromNodes(node.getNeighborNodes(type));
}
public LinkedList<ElementType> getAllSuccessors (final ElementType value)
{
return getAllNeighbors(NeighborType.SUCCESSOR, value);
}
public LinkedList<ElementType> getAllPredecessors (final ElementType value)
{
return getAllNeighbors(NeighborType.PREDECESSOR, value);
}
private LinkedList<ElementType> getAllNeighbors (final NeighborType type,
final ElementType value)
{
assert(type != null);
final Node node = nodeMap.get(value);
if (node == null) return null;
LinkedList<Node> currentNeighbors = node.getNeighborNodes(type);
final LinkedList<ElementType> neighborList = new LinkedList<ElementType>();
while (currentNeighbors.size() != 0)
{
final LinkedList<Node> nextNeighbors = new LinkedList<Node>();
for (Node currentNode : currentNeighbors)
{
final ElementType currentValue = currentNode.getValue();
if (neighborList.contains(value)) continue;
neighborList.add(currentValue);
nextNeighbors.addAll(currentNode.getNeighborNodes(type));
}
currentNeighbors = new LinkedList<Node>();
for (Node currentNode : nextNeighbors)
{
if (currentNeighbors.contains(currentNode)) continue;
currentNeighbors.add(currentNode);
}
}
return neighborList;
}
private static enum NeighborType
{
PREDECESSOR(0), SUCCESSOR(1);
private final int value;
private NeighborType(final int value)
{
this.value = value;
}
public int value()
{
return value;
}
}
private class Node
{
private final ArrayList<LinkedList<Node>> neighbors;
private final ElementType value;
public Node (final ElementType value)
{
assert(value != null);
neighbors = new ArrayList<LinkedList<Node>> (2);
for (NeighborType type : NeighborType.values())
{
neighbors.add(type.value(),new LinkedList<Node>());
}
this.value = value;
}
public void addNeighborNode (final NeighborType type, final Node neighbor)
{
assert(neighbor != null);
final LinkedList<Node> list = neighbors.get(type.value());
if (list.contains(neighbor)) return;
list.add(neighbor);
}
public void removeNeighborNode (final NeighborType type, final Node neighbor)
{
neighbors.get(type.value()).remove(neighbor);
}
public LinkedList<Node> getNeighborNodes (final NeighborType type)
{
return neighbors.get(type.value());
}
public ElementType getValue()
{
assert(value != null);
return value;
}
}
private class GraphIterator implements Iterator<ElementType>
{
private final Iterator<ElementType> keyIterator;
private ElementType current;
public GraphIterator ()
{
keyIterator = nodeMap.keySet().iterator();
}
public boolean hasNext()
{
return keyIterator.hasNext();
}
public ElementType next()
{
current = keyIterator.next();
assert(current != null);
return current;
}
public void remove()
{
if (current == null) throw new IllegalStateException();
final Node node = nodeMap.get(current);
assert(node != null);
keyIterator.remove();
removeConnections(node);
current = null;
}
}
}