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. |