001package net.automatalib.util.graphs; 002 003import java.util.AbstractList; 004import java.util.Collections; 005import java.util.Iterator; 006import java.util.List; 007 008import net.automatalib.graphs.IndefiniteGraph; 009 010public class Path<N, E> extends AbstractList<E> { 011 012 public static final class PathData<N,E> { 013 public final N start; 014 public final List<? extends E> edgeList; 015 public PathData(N start, List<? extends E> edgeList) { 016 this.start = start; 017 this.edgeList = edgeList; 018 } 019 public Path<N,E> toPath(IndefiniteGraph<N,E> graph) { 020 return new Path<>(graph, start, edgeList); 021 } 022 } 023 024 private final class NodeIterator implements Iterator<N> { 025 private Iterator<? extends E> edgeIt; 026 @Override 027 public boolean hasNext() { 028 if(edgeIt == null) 029 return true; 030 return edgeIt.hasNext(); 031 } 032 @Override 033 public N next() { 034 if(edgeIt == null) { 035 edgeIt = edgeList.iterator(); 036 return start; 037 } 038 E edge = edgeIt.next(); 039 return graph.getTarget(edge); 040 } 041 @Override 042 public void remove() { 043 throw new UnsupportedOperationException(); 044 } 045 } 046 047 private class NodeList extends AbstractList<N> { 048 @Override 049 public N get(int index) { 050 if(index < 0) 051 throw new IndexOutOfBoundsException(); 052 if(index == 0) 053 return start; 054 E edge = edgeList.get(index - 1); 055 return graph.getTarget(edge); 056 } 057 @Override 058 public int size() { 059 return edgeList.size() + 1; 060 } 061 @Override 062 public Iterator<N> iterator() { 063 return nodeIterator(); 064 } 065 @Override 066 public boolean isEmpty() { 067 return false; 068 } 069 } 070 071 private final IndefiniteGraph<N,E> graph; 072 private final N start; 073 private final List<? extends E> edgeList; 074 075 public Path(IndefiniteGraph<N,E> graph, N start, List<? extends E> edgeList) { 076 this.graph = graph; 077 this.start = start; 078 this.edgeList = edgeList; 079 } 080 081 @Override 082 @SuppressWarnings("unchecked") 083 public Iterator<E> iterator() { 084 return (Iterator<E>)edgeList.iterator(); 085 } 086 087 public Iterator<N> nodeIterator() { 088 return new NodeIterator(); 089 } 090 091 public Iterable<N> nodes() { 092 return new Iterable<N>() { 093 @Override 094 public Iterator<N> iterator() { 095 return nodeIterator(); 096 } 097 }; 098 } 099 100 public List<? extends E> edgeList() { 101 return Collections.unmodifiableList(edgeList); 102 } 103 104 public List<N> nodeList() { 105 return new NodeList(); 106 } 107 108 109 public N firstNode() { 110 return start; 111 } 112 113 public E firstEdge() { 114 if(edgeList.isEmpty()) 115 return null; 116 return edgeList.get(0); 117 } 118 119 public E lastEdge() { 120 int idx = edgeList.size() - 1; 121 if(idx < 0) 122 return null; 123 return edgeList.get(idx); 124 } 125 126 public N endNode() { 127 E edge = lastEdge(); 128 if(edge == null) 129 return start; 130 return graph.getTarget(edge); 131 } 132 133 @Override 134 public E get(int index) { 135 return edgeList.get(index); 136 } 137 @Override 138 public int size() { 139 return edgeList.size(); 140 } 141 @Override 142 public boolean isEmpty() { 143 return edgeList.isEmpty(); 144 } 145}