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