| Line | Hits | Source |
|---|---|---|
| 1 | /* | |
| 2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University of | |
| 3 | * California All rights reserved. | |
| 4 | * | |
| 5 | * This software is open-source under the BSD license; see either "license.txt" | |
| 6 | * or http://jung.sourceforge.net/license.txt for a description. | |
| 7 | */ | |
| 8 | /* | |
| 9 | * Created on Jun 13, 2003 | |
| 10 | * | |
| 11 | */ | |
| 12 | package edu.uci.ics.jung.graph.decorators; | |
| 13 | ||
| 14 | import java.util.HashMap; | |
| 15 | import java.util.Iterator; | |
| 16 | import java.util.Map; | |
| 17 | ||
| 18 | import edu.uci.ics.jung.exceptions.FatalException; | |
| 19 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
| 20 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
| 21 | import edu.uci.ics.jung.utils.UserData; | |
| 22 | ||
| 23 | /** | |
| 24 | * | |
| 25 | * An Indexer applies an index to a Graph. The Indexer, specifically, attaches | |
| 26 | * itself to a Graph's UserData and keeps a set of vertex keys as integers. An | |
| 27 | * indexer can be used to look up both forward (Vertex - Index) and backward | |
| 28 | * (Index - Vertex) . | |
| 29 | * | |
| 30 | * FIXME: note that there's currently no way to ask an Indexer instance what its | |
| 31 | * offset is. | |
| 32 | * | |
| 33 | * @author danyelf | |
| 34 | * | |
| 35 | */ | |
| 36 | public class Indexer { | |
| 37 | ||
| 38 | /** This is the key in the Graph's UserData where the Indexer is stored */ | |
| 39 | 39 | static final Object INDEX_DEFAULT_KEY = "IndexDefaultKey"; |
| 40 | ||
| 41 | /** | |
| 42 | * Gets the indexer associated with this graph. This uses the default | |
| 43 | * INDEX_DEFAULT_KEY as its user data key. | |
| 44 | * | |
| 45 | * @throws FatalException | |
| 46 | * if the graph has changed detectably since the last run. Note | |
| 47 | * that "has changed" merely looks at the number of nodes for | |
| 48 | * now. | |
| 49 | */ | |
| 50 | public static Indexer getIndexer(ArchetypeGraph g) { | |
| 51 | 437 | return getIndexer(g, INDEX_DEFAULT_KEY, false, false, 0); |
| 52 | } | |
| 53 | ||
| 54 | /** | |
| 55 | * Gets the indexer associated with this graph. Forces the system to create | |
| 56 | * a new Index on the graph. | |
| 57 | * | |
| 58 | * This uses the default INDEX_DEFAULT_KEY as its user data key. | |
| 59 | */ | |
| 60 | public static Indexer getAndUpdateIndexer(ArchetypeGraph g) { | |
| 61 | 0 | return getIndexer(g, INDEX_DEFAULT_KEY, true, false, 0); |
| 62 | } | |
| 63 | ||
| 64 | /** | |
| 65 | * Creates a new indexer associated with this graph. Starts the count at | |
| 66 | * "offset". WARNING: This graph may be hard to use in some other methods | |
| 67 | * that assume a zero offset. If the Graph has changed, this will update | |
| 68 | * the index. Note that the "has Changed" parameter is a little thin; it | |
| 69 | * merely checks whether the size has changed or not | |
| 70 | * | |
| 71 | * This uses the default INDEX_DEFAULT_KEY as its user data key. | |
| 72 | * | |
| 73 | * @param g | |
| 74 | * the Graph to index. | |
| 75 | * @param offset | |
| 76 | * a starting value to index from | |
| 77 | * @return an indexer that has been indexed | |
| 78 | */ | |
| 79 | public static Indexer newIndexer(ArchetypeGraph g, int offset) { | |
| 80 | 108 | return getIndexer(g, INDEX_DEFAULT_KEY, false, true, offset); |
| 81 | } | |
| 82 | ||
| 83 | /** | |
| 84 | * * Gets an indexer associated with this graph at this key | |
| 85 | * | |
| 86 | * @param g | |
| 87 | * The graph to check | |
| 88 | * @param key | |
| 89 | * The user data key to check | |
| 90 | * @return the indexer | |
| 91 | * | |
| 92 | * @throws FatalException | |
| 93 | * if the graph has changed detectably since the last run. Note | |
| 94 | * that "has changed" merely looks at the number of nodes for | |
| 95 | * now. | |
| 96 | * | |
| 97 | */ | |
| 98 | public static Indexer getIndexer(ArchetypeGraph g, Object key) { | |
| 99 | 1 | return getIndexer(g, key, false, false, 0); |
| 100 | } | |
| 101 | ||
| 102 | /** | |
| 103 | * Gets the indexer associated with this graph. Forces the system to create | |
| 104 | * a new Index on the graph at the given key. | |
| 105 | * | |
| 106 | * @throws FatalException | |
| 107 | * if the graph has changed detectably since the last run. Note | |
| 108 | * that "has changed" merely looks at the number of nodes for | |
| 109 | * now. | |
| 110 | */ | |
| 111 | public static Indexer getAndUpdateIndexer(ArchetypeGraph g, Object key) { | |
| 112 | 0 | return getIndexer(g, key, true, false, 0); |
| 113 | } | |
| 114 | ||
| 115 | /** | |
| 116 | * Checks if there is an indexer assocated with this graph. | |
| 117 | * | |
| 118 | * This uses the default INDEX_DEFAULT_KEY as its user data key. | |
| 119 | * | |
| 120 | * @param g | |
| 121 | * The graph to check | |
| 122 | * @return true if there is an indexer associated with this graph. | |
| 123 | */ | |
| 124 | public static boolean hasIndexer(ArchetypeGraph g) { | |
| 125 | 2 | return hasIndexer(g, INDEX_DEFAULT_KEY); |
| 126 | } | |
| 127 | ||
| 128 | /** | |
| 129 | * Checks if there is an indexer assocated with this graph. | |
| 130 | * | |
| 131 | * @param g | |
| 132 | * The graph to check | |
| 133 | * @return true if there is an indexer associated with this graph. | |
| 134 | */ | |
| 135 | public static boolean hasIndexer(ArchetypeGraph g, Object key) { | |
| 136 | 2 | Indexer id = (Indexer) g.getUserDatum(key); |
| 137 | 2 | return (id != null); |
| 138 | } | |
| 139 | ||
| 140 | // reCreate: create a new index on the graph. | |
| 141 | // reIndex: only applicable if recreate is false and the graph has an old | |
| 142 | // index: we shoudl throw an exception if the graph has changed | |
| 143 | private static Indexer getIndexer( | |
| 144 | ArchetypeGraph g, | |
| 145 | Object key, | |
| 146 | boolean reIndex, | |
| 147 | boolean recreate, | |
| 148 | int offset) { | |
| 149 | 546 | Indexer id = (Indexer) g.getUserDatum(key); |
| 150 | 546 | if (!recreate && id != null) { |
| 151 | 233 | if (id.numNodes != g.getVertices().size()) { |
| 152 | 0 | if (reIndex == false) { |
| 153 | 0 | throw new FatalException("Graph changed since last index update"); |
| 154 | } else { | |
| 155 | 0 | id = null; |
| 156 | } | |
| 157 | } else { | |
| 158 | 233 | return id; |
| 159 | } | |
| 160 | } | |
| 161 | 313 | id = new Indexer(g); |
| 162 | 313 | id.updateIndex(offset); |
| 163 | 313 | g.setUserDatum(key, id, UserData.REMOVE); |
| 164 | 313 | return id; |
| 165 | } | |
| 166 | ||
| 167 | int numNodes; | |
| 168 | ||
| 169 | /** | |
| 170 | * Clears previous index (if it existed); puts in a new one. Merely follows | |
| 171 | * graph.getVertices() iterator order, which is not guaranteed to have any | |
| 172 | * nice properties at all. When complete, the index will be numbered from <code>offset</code> | |
| 173 | * to <code>offset + n - 1</code> (where <code>n = g.numVertices()</code>), | |
| 174 | * and will be accessible through | |
| 175 | * <code>getIndex( Vertex)</code> and <code>getVertex( index )</code>. | |
| 176 | */ | |
| 177 | public void updateIndex(int offset) { | |
| 178 | // indexToVertex.clear(); | |
| 179 | 314 | indexToVertex = new ArchetypeVertex[graph.numVertices() + offset]; |
| 180 | 314 | vertexToIndex.clear(); |
| 181 | 314 | int i = offset; |
| 182 | 314 | for (Iterator iter = graph.getVertices().iterator(); iter.hasNext();) { |
| 183 | 8754 | ArchetypeVertex v = (ArchetypeVertex) iter.next(); |
| 184 | 8754 | Integer ix = new Integer(i); |
| 185 | 8754 | indexToVertex[i] = v; |
| 186 | // indexToVertex.put(ix, v); | |
| 187 | 8754 | vertexToIndex.put(v, ix); |
| 188 | 8754 | i++; |
| 189 | } | |
| 190 | 314 | numNodes = graph.getVertices().size(); |
| 191 | 314 | } |
| 192 | ||
| 193 | /** | |
| 194 | * Forces an index update, reindexing from zero. | |
| 195 | * Equivalent to <code>updateIndex(0)</code>. | |
| 196 | */ | |
| 197 | public void updateIndex() { | |
| 198 | 1 | updateIndex(0); |
| 199 | 1 | } |
| 200 | ||
| 201 | /** | |
| 202 | * Gets the index assocated with this vertex. | |
| 203 | */ | |
| 204 | public int getIndex(ArchetypeVertex v) { | |
| 205 | 7942 | return ((Integer) vertexToIndex.get(v)).intValue(); |
| 206 | } | |
| 207 | ||
| 208 | /** | |
| 209 | * Gets the vertex associated with this index. | |
| 210 | */ | |
| 211 | public ArchetypeVertex getVertex(int i) { | |
| 212 | // return (ArchetypeVertex) indexToVertex.get(new Integer(i)); | |
| 213 | 546466 | return indexToVertex[i]; |
| 214 | } | |
| 215 | ||
| 216 | // private Map indexToVertex = new HashMap(); | |
| 217 | private ArchetypeVertex[] indexToVertex; | |
| 218 | 313 | private Map vertexToIndex = new HashMap(); |
| 219 | private ArchetypeGraph graph; | |
| 220 | ||
| 221 | 313 | private Indexer(ArchetypeGraph g) { |
| 222 | 313 | this.graph = g; |
| 223 | 313 | } |
| 224 | ||
| 225 | // public void setIndex(Vertex v, Integer i) { //throws ImproperIndexException { | |
| 226 | // if (graph.getVertices().contains(v)) { | |
| 227 | // //if (indexToVertex.containsKey(i)) { | |
| 228 | // // we already have a vertex with this label | |
| 229 | // // throw new ImproperIndexException(i + "is already on vertex " + indexToVertex.get(i)); | |
| 230 | // // } | |
| 231 | // // ok, we know we don't have this label anywhere yet | |
| 232 | // if (vertexToIndex.containsKey(v)) { | |
| 233 | // Object junk = vertexToIndex.get(v); | |
| 234 | // indexToVertex.remove(junk); | |
| 235 | // } | |
| 236 | // vertexToIndex.put(v, i); | |
| 237 | // indexToVertex.put(i, v); | |
| 238 | // } else { | |
| 239 | // // throw some sort of exception here | |
| 240 | // throw new IllegalArgumentException("This vertex is not a part of this graph"); | |
| 241 | // } | |
| 242 | // | |
| 243 | // } | |
| 244 | // | |
| 245 | // public static class ImproperIndexException extends Exception { | |
| 246 | // | |
| 247 | // public ImproperIndexException(String string) { | |
| 248 | // super(string); | |
| 249 | // } | |
| 250 | // | |
| 251 | // } | |
| 252 | ||
| 253 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |