?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
meaningless comment
[ephemerata.git] / KezvhLib / src-lib / net / kezvh / collections / graphs / directed / HashDirectedGraph.java
blob5104a35b9426fff8c6340467cf3281e3c0b90373
1 /**
2 *
3 */
4 package net.kezvh.collections.graphs.directed;
5
6 import java.util.Collections;
7 import java.util.HashMap;
8 import java.util.Map;
9 import java.util.NoSuchElementException;
10 import java.util.Set;
11
12 import net.kezvh.collections.Pair;
13 import net.kezvh.collections.DualMap.DualMap;
14 import net.kezvh.collections.DualMap.HashDualMap;
15 import net.kezvh.collections.views.MapAsView;
16 import net.kezvh.collections.views.SetView;
17 import net.kezvh.collections.wrappers.WrappedSet;
18 import net.kezvh.functional.lambda.L1;
19
20 import com.google.common.collect.AbstractMapEntry;
21
22 /**
23 * Nodes are tracked by a HashMap. Edges are tracked by a HashMap2. This gives
24 * O(1) performance for adding or querying anything.
25 *
26 * @author afflux
27 * @param <Node> COMMENT
28 * @param <NodeValue> COMMENT
29 * @param <EdgeValue> COMMENT
30 */
31 public class HashDirectedGraph<Node, NodeValue, EdgeValue> extends HashMap<Node, NodeValue> implements DirectedGraphWithValues<Node, NodeValue, EdgeValue> {
32 private final L1<NodeValue, Node> getValue = new L1<NodeValue, Node>() {
33 public NodeValue op(final Node param) {
34 return HashDirectedGraph.this.get(param);
35 }
36 };
37
38 private final DualMap<Node, Node, EdgeValue> edges = new HashDualMap<Node, Node, EdgeValue>();
39 private final L1<EdgeWithValues<Node, NodeValue, EdgeValue>, Map.Entry<Pair<Node, Node>, EdgeValue>> getEdges = new L1<EdgeWithValues<Node, NodeValue, EdgeValue>, Map.Entry<Pair<Node, Node>, EdgeValue>>() {
40 /**
41 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
42 * @param param COMMENT
43 * @return COMMENT
44 */
45 @Override
46 public EdgeWithValues<Node, NodeValue, EdgeValue> op(final Map.Entry<Pair<Node, Node>, EdgeValue> param) {
47 return new EdgeWithValues<Node, NodeValue, EdgeValue>() {
48 /**
49 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getDestination()
50 * @return COMMENT
51 */
52 @Override
53 public java.util.Map.Entry<Node, NodeValue> getDestination() {
54 return new Map.Entry<Node, NodeValue>() {
55 /**
56 * @see java.util.Map.Entry#getKey()
57 * @return COMMENT
58 */
59 @Override
60 public Node getKey() {
61 return param.getKey().get2();
62 }
63
64 /**
65 * @see java.util.Map.Entry#getValue()
66 * @return COMMENT
67 */
68 @Override
69 public NodeValue getValue() {
70 return HashDirectedGraph.this.get(this.getKey());
71 }
72
73 public NodeValue setValue(final NodeValue arg0) {
74 return HashDirectedGraph.this.put(this.getKey(), arg0);
75 }
76 };
77 }
78
79 /**
80 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getSource()
81 * @return COMMENT
82 */
83 @Override
84 public java.util.Map.Entry<Node, NodeValue> getSource() {
85 return new Map.Entry<Node, NodeValue>() {
86 /**
87 * @see java.util.Map.Entry#getKey()
88 * @return COMMENT
89 */
90 @Override
91 public Node getKey() {
92 return param.getKey().get1();
93 }
94
95 /**
96 * @see java.util.Map.Entry#getValue()
97 * @return COMMENT
98 */
99 @Override
100 public NodeValue getValue() {
101 return HashDirectedGraph.this.get(this.getKey());
102 }
103
104 public NodeValue setValue(final NodeValue arg0) {
105 return HashDirectedGraph.this.put(this.getKey(), arg0);
106 }
107 };
108 }
109
110 /**
111 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getValue()
112 * @return COMMENT
113 */
114 @Override
115 public EdgeValue getValue() {
116 return param.getValue();
117 }
118
119 public EdgeValue setValue(final EdgeValue newValue) {
120 return param.setValue(newValue);
121 }
122
123 @Override
124 public Node getDestinationNode() {
125 return param.getKey().get2();
126 }
127
128 @Override
129 public Node getSourceNode() {
130 return param.getKey().get1();
131 }
132 };
133 }
134 };
135
136 private final L1<EdgeWithValues<Node, NodeValue, EdgeValue>, DualMap.Entry<Node, Node, EdgeValue>> getEdges2 = new L1<EdgeWithValues<Node, NodeValue, EdgeValue>, DualMap.Entry<Node, Node, EdgeValue>>() {
137 /**
138 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
139 * @param param COMMENT
140 * @return COMMENT
141 */
142 @Override
143 public EdgeWithValues<Node, NodeValue, EdgeValue> op(final DualMap.Entry<Node, Node, EdgeValue> param) {
144 return new EdgeWithValues<Node, NodeValue, EdgeValue>() {
145 /**
146 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getDestination()
147 * @return COMMENT
148 */
149 @Override
150 public java.util.Map.Entry<Node, NodeValue> getDestination() {
151 return new Map.Entry<Node, NodeValue>() {
152 /**
153 * @see java.util.Map.Entry#getKey()
154 * @return COMMENT
155 */
156 @Override
157 public Node getKey() {
158 return param.getKey().get2();
159 }
160
161 /**
162 * @see java.util.Map.Entry#getValue()
163 * @return COMMENT
164 */
165 @Override
166 public NodeValue getValue() {
167 return HashDirectedGraph.this.get(this.getKey());
168 }
169
170 public NodeValue setValue(final NodeValue arg0) {
171 return HashDirectedGraph.this.put(this.getKey(), arg0);
172 }
173 };
174 }
175
176 /**
177 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getSource()
178 * @return COMMENT
179 */
180 @Override
181 public java.util.Map.Entry<Node, NodeValue> getSource() {
182 return new Map.Entry<Node, NodeValue>() {
183 /**
184 * @see java.util.Map.Entry#getKey()
185 * @return COMMENT
186 */
187 @Override
188 public Node getKey() {
189 return param.getKey().get1();
190 }
191
192 /**
193 * @see java.util.Map.Entry#getValue()
194 * @return COMMENT
195 */
196 @Override
197 public NodeValue getValue() {
198 return HashDirectedGraph.this.get(this.getKey());
199 }
200
201 public NodeValue setValue(final NodeValue arg0) {
202 return HashDirectedGraph.this.put(this.getKey(), arg0);
203 }
204 };
205 }
206
207 /**
208 * @see net.kezvh.collections.graphs.directed.EdgeWithValues#getValue()
209 * @return COMMENT
210 */
211 @Override
212 public EdgeValue getValue() {
213 return param.getValue();
214 }
215
216 public EdgeValue setValue(final EdgeValue newValue) {
217 return param.setValue(newValue);
218 }
219
220 @Override
221 public Node getDestinationNode() {
222 return param.getKey().get2();
223 }
224
225 @Override
226 public Node getSourceNode() {
227 return param.getKey().get1();
228 }
229 };
230 }
231 };
232
233 private final Set<EdgeWithValues<Node, NodeValue, EdgeValue>> edgesSet = new SetView<Map.Entry<Pair<Node, Node>, EdgeValue>, EdgeWithValues<Node, NodeValue, EdgeValue>>(this.edges.entrySet(), this.getEdges) {
234 /**
235 * @see java.util.AbstractCollection#remove(java.lang.Object)
236 * @param o COMMENT
237 * @return COMMENT
238 */
239 @SuppressWarnings("unchecked")
240 @Override
241 public boolean remove(final Object o) {
242 final EdgeWithValues<Node, NodeValue, EdgeValue> other = (EdgeWithValues<Node, NodeValue, EdgeValue>) o;
243 return HashDirectedGraph.this.edges.remove(other.getSource().getKey(), other.getDestination().getKey()) != null;
244 }
245 };
246
247 private void assertContains(final Object... nodes) {
248 for (final Object node : nodes)
249 if (!this.containsKey(node))
250 throw new NoSuchElementException();
251 }
252
253 /**
254 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#addEdge(java.lang.Object,
255 * java.lang.Object, java.lang.Object)
256 * @param source COMMENT
257 * @param destination COMMENT
258 * @param edgeValue COMMENT
259 * @return COMMENT
260 */
261 @Override
262 public EdgeValue addEdge(final Node source, final Node destination, final EdgeValue edgeValue) {
263 this.assertContains(source, destination);
264
265 return this.edges.put(source, destination, edgeValue);
266 }
267
268 /**
269 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#containsEdge(java.lang.Object,
270 * java.lang.Object)
271 * @param source COMMENT
272 * @param destination COMMENT
273 * @return COMMENT
274 */
275 @Override
276 public boolean containsEdge(final Node source, final Node destination) {
277 this.assertContains(source, destination);
278
279 return this.edges.containsKey(source, destination);
280 }
281
282 /**
283 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#containsEdge(net.kezvh.collections.graphs.directed.Edge)
284 * @param edge COMMENT
285 * @return COMMENT
286 */
287 @Override
288 public boolean containsEdge(final EdgeWithValues<Node, NodeValue, EdgeValue> edge) {
289 return this.containsEdge(edge.getSource().getKey(), edge.getDestination().getKey());
290 }
291
292 /**
293 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#edgeCount()
294 * @return COMMENT
295 */
296 @Override
297 public long edgeCount() {
298 return this.edges.size();
299 }
300
301 /**
302 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#edges()
303 * @return COMMENT
304 */
305 @Override
306 public Set<EdgeWithValues<Node, NodeValue, EdgeValue>> edges() {
307 return this.edgesSet;
308 }
309
310 /**
311 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#getEdgeValue(java.lang.Object,
312 * java.lang.Object)
313 * @param source COMMENT
314 * @param destination COMMENT
315 * @return COMMENT
316 */
317 @Override
318 public EdgeValue getEdgeValue(final Node source, final Node destination) {
319 return this.edges.get(source, destination);
320 }
321
322 /**
323 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#inDegree(java.lang.Object)
324 * @param destination COMMENT
325 * @return COMMENT
326 */
327 @Override
328 public int inDegree(final Node destination) {
329 return this.edges.entrySetOnKey2(destination).size();
330 }
331
332 /**
333 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#inEdgeSources(java.lang.Object)
334 * @param destination COMMENT
335 * @return COMMENT
336 */
337 @Override
338 public Map<Node, NodeValue> inEdgeSources(final Node destination) {
339 return new MapAsView<Node, NodeValue>(this.edges.keySetOnKey2(destination), this.getValue);
340 }
341
342 /**
343 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#inEdges(java.lang.Object)
344 * @param destination COMMENT
345 * @return COMMENT
346 */
347 @Override
348 public Set<EdgeWithValues<Node, NodeValue, EdgeValue>> inEdges(final Node destination) {
349 return new SetView<DualMap.Entry<Node, Node, EdgeValue>, EdgeWithValues<Node, NodeValue, EdgeValue>>(this.edges.entrySetOnKey2(destination), this.getEdges2);
350 }
351
352 /**
353 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#outDegree(java.lang.Object)
354 * @param source COMMENT
355 * @return COMMENT
356 */
357 @Override
358 public int outDegree(final Node source) {
359 return this.edges.entrySetOnKey1(source).size();
360 }
361
362 /**
363 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#outEdgeDestinations(java.lang.Object)
364 * @param source COMMENT
365 * @return COMMENT
366 */
367 @Override
368 public Map<Node, NodeValue> outEdgeDestinations(final Node source) {
369 return new MapAsView<Node, NodeValue>(this.edges.keySetOnKey1(source), this.getValue);
370 }
371
372 /**
373 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#outEdges(java.lang.Object)
374 * @param source COMMENT
375 * @return COMMENT
376 */
377 @Override
378 public Set<EdgeWithValues<Node, NodeValue, EdgeValue>> outEdges(final Node source) {
379 return new SetView<DualMap.Entry<Node, Node, EdgeValue>, EdgeWithValues<Node, NodeValue, EdgeValue>>(this.edges.entrySetOnKey1(source), this.getEdges2);
380
381 }
382
383 /**
384 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#removeEdge(java.lang.Object,
385 * java.lang.Object)
386 * @param source COMMENT
387 * @param destination COMMENT
388 * @return COMMENT
389 */
390 @Override
391 public EdgeValue removeEdge(final Node source, final Node destination) {
392 return this.edges.remove(source, destination);
393 }
394
395 /**
396 * @see net.kezvh.collections.graphs.directed.DirectedGraphWithValues#removeEdge(net.kezvh.collections.graphs.directed.EdgeWithEdgeValue)
397 * @param edge COMMENT
398 * @return COMMENT
399 */
400 @Override
401 public EdgeValue removeEdge(final EdgeWithValues<Node, NodeValue, EdgeValue> edge) {
402 return this.edges.remove(edge.getSourceNode(), edge.getDestinationNode());
403 }
404
405 @SuppressWarnings("unchecked")
406 @Override
407 public NodeValue remove(final Object key) {
408 this.edges.remove1((Node) key);
409 this.edges.remove2((Node) key);
410 return super.remove(key);
411 }
412
413 /**
414 * @see java.util.Map#clear()
415 */
416 @Override
417 public void clear() {
418 this.edges.clear();
419 super.clear();
420 }
421
422 @Override
423 public DirectedGraphWithEdgeValues<Node, EdgeValue> keySet() {
424 return this.keyset;
425 }
426
427 private final KeySet keyset = new KeySet();
428
429 private final class KeySet extends WrappedSet<Node, Set<Node>> implements DirectedGraphWithEdgeValues<Node, EdgeValue> {
430
431 public KeySet() {
432 super(HashDirectedGraph.super.keySet());
433 }
434
435 @Override
436 public boolean containsEdge(final Node source, final Node destination) {
437 return HashDirectedGraph.this.containsEdge(source, destination);
438 }
439
440 @Override
441 public long edgeCount() {
442 return HashDirectedGraph.this.edgeCount();
443 }
444
445 @Override
446 public int inDegree(final Node destination) {
447 return HashDirectedGraph.this.inDegree(destination);
448 }
449
450 @Override
451 public int outDegree(final Node source) {
452 return HashDirectedGraph.this.outDegree(source);
453 }
454
455 @Override
456 public Set<Node> adjacentFrom(final Node source) {
457 return HashDirectedGraph.this.adjacentFrom(source);
458 }
459
460 @Override
461 public Set<Node> adjacentTo(final Node destination) {
462 return HashDirectedGraph.this.adjacentTo(destination);
463 }
464
465 @Override
466 public EdgeValue addEdge(final Node source, final Node destination, final EdgeValue edgeValue) {
467 return HashDirectedGraph.this.addEdge(source, destination, edgeValue);
468 }
469
470 @Override
471 public EdgeValue getEdgeValue(final Node source, final Node destination) {
472 return HashDirectedGraph.this.getEdgeValue(source, destination);
473 }
474
475 @Override
476 public EdgeValue removeEdge(final Node source, final Node destination) {
477 return HashDirectedGraph.this.removeEdge(source, destination);
478 }
479
480 @Override
481 public EdgeValue removeEdge(final EdgeWithEdgeValue<Node, EdgeValue> edge) {
482 return HashDirectedGraph.this.removeEdge(edge.getSourceNode(), edge.getDestinationNode());
483 }
484
485 @Override
486 public boolean containsEdge(final EdgeWithEdgeValue<Node, EdgeValue> edge) {
487 return HashDirectedGraph.this.containsEdge(edge.getSourceNode(), edge.getDestinationNode());
488 }
489
490 private final L1<EdgeWithEdgeValue<Node, EdgeValue>, EdgeWithValues<Node, NodeValue, EdgeValue>> getSetEdges = new L1<EdgeWithEdgeValue<Node, EdgeValue>, EdgeWithValues<Node, NodeValue, EdgeValue>>() {
491 @Override
492 public EdgeWithEdgeValue<Node, EdgeValue> op(final EdgeWithValues<Node, NodeValue, EdgeValue> param) {
493 return new EdgeWithEdgeValue<Node, EdgeValue>() {
494 @Override
495 public Node getDestinationNode() {
496 return param.getDestinationNode();
497 }
498
499 @Override
500 public Node getSourceNode() {
501 return param.getSourceNode();
502 }
503
504 @Override
505 public EdgeValue getValue() {
506 return param.getValue();
507 }
508
509 public EdgeValue setValue(final EdgeValue newValue) {
510 return param.setValue(newValue);
511 }
512 };
513 }
514 };
515
516 private final L1<EdgeWithValues<Node, NodeValue, EdgeValue>, EdgeWithEdgeValue<Node, EdgeValue>> inverseSetEdges = new L1<EdgeWithValues<Node, NodeValue, EdgeValue>, EdgeWithEdgeValue<Node, EdgeValue>>() {
517 @Override
518 public EdgeWithValues<Node, NodeValue, EdgeValue> op(final EdgeWithEdgeValue<Node, EdgeValue> param) {
519 return new EdgeWithValues<Node, NodeValue, EdgeValue>() {
520 @Override
521 public java.util.Map.Entry<Node, NodeValue> getDestination() {
522 return new AbstractMapEntry<Node, NodeValue>() {
523 @Override
524 public Node getKey() {
525 return getDestinationNode();
526 }
527
528 @Override
529 public NodeValue getValue() {
530 return HashDirectedGraph.this.get(this.getKey());
531 }
532 };
533 }
534
535 @Override
536 public Node getDestinationNode() {
537 return param.getDestinationNode();
538 }
539
540 @Override
541 public java.util.Map.Entry<Node, NodeValue> getSource() {
542 return new AbstractMapEntry<Node, NodeValue>() {
543 @Override
544 public Node getKey() {
545 return getSourceNode();
546 }
547
548 @Override
549 public NodeValue getValue() {
550 return HashDirectedGraph.this.get(this.getKey());
551 }
552 };
553 }
554
555 @Override
556 public Node getSourceNode() {
557 return param.getSourceNode();
558 }
559
560 @Override
561 public EdgeValue getValue() {
562 return param.getValue();
563 }
564
565 public EdgeValue setValue(final EdgeValue newValue) {
566 return param.setValue(newValue);
567 }
568 };
569 }
570 };
571
572 private final Set<EdgeWithEdgeValue<Node, EdgeValue>> edgesView = new SetView<EdgeWithValues<Node, NodeValue, EdgeValue>, EdgeWithEdgeValue<Node, EdgeValue>>(HashDirectedGraph.this.edges(), this.getSetEdges, this.inverseSetEdges);
573
574 @Override
575 public Set<EdgeWithEdgeValue<Node, EdgeValue>> edges() {
576 return this.edgesView;
577 }
578
579 @Override
580 public Set<EdgeWithEdgeValue<Node, EdgeValue>> inEdges(final Node destination) {
581 return new SetView<EdgeWithValues<Node, NodeValue, EdgeValue>, EdgeWithEdgeValue<Node, EdgeValue>>(HashDirectedGraph.this.inEdges(destination), this.getSetEdges, this.inverseSetEdges);
582 }
583
584 @Override
585 public Set<EdgeWithEdgeValue<Node, EdgeValue>> outEdges(final Node source) {
586 return new SetView<EdgeWithValues<Node, NodeValue, EdgeValue>, EdgeWithEdgeValue<Node, EdgeValue>>(HashDirectedGraph.this.outEdges(source), this.getSetEdges, this.inverseSetEdges);
587 }
588 }
589
590 @Override
591 public Set<Node> adjacentFrom(final Node source) {
592 if (this.containsKey(source)) {
593 if (this.edges.containsKey1(source))
594 return this.edges.keySetOnKey1(source);
595 return Collections.emptySet();
596 }
597 return null;
598 }
599
600 @Override
601 public Set<Node> adjacentTo(final Node destination) {
602 if (this.containsKey(destination)) {
603 if (this.edges.containsKey2(destination))
604 return this.edges.keySetOnKey2(destination);
605 return Collections.emptySet();
606 }
607 return null;
608 }
609 }
ephemerata