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