1 package org.apache.maven.repository.metadata;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 import java.util.ArrayList;
23 import java.util.HashMap;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.TreeSet;
27
28 import org.apache.maven.artifact.ArtifactScopeEnum;
29
30
31
32
33
34
35
36 public class MetadataGraph
37 {
38 public static final int DEFAULT_VERTICES = 32;
39 public static final int DEFAULT_EDGES = 64;
40
41
42 private boolean versionedVertices = false;
43 private boolean scopedVertices = false;
44
45
46
47 MetadataGraphVertex entry;
48
49
50 TreeSet<MetadataGraphVertex> vertices;
51
52
53
54
55 Map<MetadataGraphVertex, List<MetadataGraphEdge>> incidentEdges;
56 Map<MetadataGraphVertex, List<MetadataGraphEdge>> excidentEdges;
57
58
59
60
61
62 ArtifactScopeEnum scope;
63
64
65
66
67
68 public MetadataGraph( int nVertices )
69 {
70 init( nVertices, 2 * nVertices );
71 }
72 public MetadataGraph( int nVertices, int nEdges )
73 {
74 init( nVertices, nEdges );
75 }
76
77
78
79
80 public MetadataGraph( MetadataGraphVertex entry )
81 throws MetadataResolutionException
82 {
83 checkVertex( entry );
84 checkVertices( 1 );
85
86 entry.setCompareVersion( versionedVertices );
87 entry.setCompareScope( scopedVertices );
88
89 vertices.add( entry );
90 this.entry = entry;
91 }
92
93
94
95
96 public MetadataGraph( MetadataTreeNode tree )
97 throws MetadataResolutionException
98 {
99 this( tree, false, false );
100 }
101
102
103
104
105
106
107
108
109
110
111 public MetadataGraph( MetadataTreeNode tree, boolean versionedVertices, boolean scopedVertices )
112 throws MetadataResolutionException
113 {
114 if ( tree == null )
115 {
116 throw new MetadataResolutionException( "tree is null" );
117 }
118
119 setVersionedVertices( versionedVertices );
120 setScopedVertices( scopedVertices );
121
122 this.versionedVertices = scopedVertices || versionedVertices;
123 this.scopedVertices = scopedVertices;
124
125 int count = countNodes( tree );
126
127 init( count, count + ( count / 2 ) );
128
129 processTreeNodes( null, tree, 0, 0 );
130 }
131
132 private void processTreeNodes( MetadataGraphVertex parentVertex, MetadataTreeNode node, int depth, int pomOrder )
133 throws MetadataResolutionException
134 {
135 if ( node == null )
136 {
137 return;
138 }
139
140 MetadataGraphVertex vertex = new MetadataGraphVertex( node.md, versionedVertices, scopedVertices );
141 if ( !vertices.contains( vertex ) )
142 {
143 vertices.add( vertex );
144 }
145
146 if ( parentVertex != null )
147 {
148 ArtifactMetadata md = node.getMd();
149 MetadataGraphEdge e =
150 new MetadataGraphEdge( md.version, md.resolved, md.artifactScope, md.artifactUri, depth, pomOrder );
151 addEdge( parentVertex, vertex, e );
152 }
153 else
154 {
155 entry = vertex;
156 }
157
158 MetadataTreeNode[] kids = node.getChildren();
159 if ( kids == null || kids.length < 1 )
160 {
161 return;
162 }
163
164 for ( int i = 0; i < kids.length; i++ )
165 {
166 MetadataTreeNode n = kids[i];
167 processTreeNodes( vertex, n, depth + 1, i );
168 }
169 }
170
171 public MetadataGraphVertex findVertex( ArtifactMetadata md )
172 {
173 if ( md == null || vertices == null || vertices.size() < 1 )
174 {
175 return null;
176 }
177
178 MetadataGraphVertex v = new MetadataGraphVertex( md );
179 v.setCompareVersion( versionedVertices );
180 v.setCompareScope( scopedVertices );
181
182 for ( MetadataGraphVertex gv : vertices )
183 {
184 if ( gv.equals( v ) )
185 {
186 return gv;
187 }
188 }
189
190 return null;
191 }
192
193 public MetadataGraphVertex addVertex( ArtifactMetadata md )
194 {
195 if ( md == null )
196 {
197 return null;
198 }
199
200 checkVertices();
201
202 MetadataGraphVertex v = findVertex( md );
203 if ( v != null )
204 {
205 return v;
206 }
207
208 v = new MetadataGraphVertex( md );
209
210 v.setCompareVersion( versionedVertices );
211 v.setCompareScope( scopedVertices );
212
213 vertices.add( v );
214 return v;
215 }
216
217
218
219
220 private void init( int nVertices, int nEdges )
221 {
222 int nV = nVertices;
223 if ( nVertices < 1 )
224 {
225 nV = 1;
226 }
227
228 checkVertices( nV );
229
230 int nE = nVertices;
231 if ( nEdges <= nV )
232 {
233 nE = 2 * nE;
234 }
235
236 checkEdges( nE );
237 }
238
239 private void checkVertices()
240 {
241 checkVertices( DEFAULT_VERTICES );
242 }
243
244 private void checkVertices( int nVertices )
245 {
246 if ( vertices == null )
247 {
248 vertices = new TreeSet<>();
249 }
250 }
251 private void checkEdges()
252 {
253 int count = DEFAULT_EDGES;
254
255 if ( vertices != null )
256 {
257 count = vertices.size() + vertices.size() / 2;
258 }
259
260 checkEdges( count );
261 }
262 private void checkEdges( int nEdges )
263 {
264 if ( incidentEdges == null )
265 {
266 incidentEdges = new HashMap<>( nEdges );
267 }
268 if ( excidentEdges == null )
269 {
270 excidentEdges = new HashMap<>( nEdges );
271 }
272 }
273
274 private static void checkVertex( MetadataGraphVertex v )
275 throws MetadataResolutionException
276 {
277 if ( v == null )
278 {
279 throw new MetadataResolutionException( "null vertex" );
280 }
281 if ( v.getMd() == null )
282 {
283 throw new MetadataResolutionException( "vertex without metadata" );
284 }
285 }
286
287 private static void checkEdge( MetadataGraphEdge e )
288 throws MetadataResolutionException
289 {
290 if ( e == null )
291 {
292 throw new MetadataResolutionException( "badly formed edge" );
293 }
294 }
295
296 public List<MetadataGraphEdge> getEdgesBetween( MetadataGraphVertex vFrom, MetadataGraphVertex vTo )
297 {
298 List<MetadataGraphEdge> edges = getIncidentEdges( vTo );
299 if ( edges == null || edges.isEmpty() )
300 {
301 return null;
302 }
303
304 List<MetadataGraphEdge> res = new ArrayList<>( edges.size() );
305
306 for ( MetadataGraphEdge e : edges )
307 {
308 if ( e.getSource().equals( vFrom ) )
309 {
310 res.add( e );
311 }
312 }
313
314 return res;
315 }
316
317 public MetadataGraph addEdge( MetadataGraphVertex vFrom, MetadataGraphVertex vTo, MetadataGraphEdge e )
318 throws MetadataResolutionException
319 {
320 checkVertex( vFrom );
321 checkVertex( vTo );
322
323 checkVertices();
324
325 checkEdge( e );
326 checkEdges();
327
328 e.setSource( vFrom );
329 e.setTarget( vTo );
330
331 vFrom.setCompareVersion( versionedVertices );
332 vFrom.setCompareScope( scopedVertices );
333
334 List<MetadataGraphEdge> exList = excidentEdges.get( vFrom );
335 if ( exList == null )
336 {
337 exList = new ArrayList<>();
338 excidentEdges.put( vFrom, exList );
339 }
340
341 if ( !exList.contains( e ) )
342 {
343 exList.add( e );
344 }
345
346 List<MetadataGraphEdge> inList = incidentEdges.get( vTo );
347 if ( inList == null )
348 {
349 inList = new ArrayList<>();
350 incidentEdges.put( vTo, inList );
351 }
352
353 if ( !inList.contains( e ) )
354 {
355 inList.add( e );
356 }
357
358 return this;
359 }
360
361 public MetadataGraph removeVertex( MetadataGraphVertex v )
362 {
363 if ( vertices != null && v != null )
364 {
365 vertices.remove( v );
366 }
367
368 if ( incidentEdges != null )
369 {
370 incidentEdges.remove( v );
371 }
372
373 if ( excidentEdges != null )
374 {
375 excidentEdges.remove( v );
376 }
377
378 return this;
379
380 }
381
382 private static int countNodes( MetadataTreeNode tree )
383 {
384 if ( tree == null )
385 {
386 return 0;
387 }
388
389 int count = 1;
390 MetadataTreeNode[] kids = tree.getChildren();
391 if ( kids == null || kids.length < 1 )
392 {
393 return count;
394 }
395 for ( MetadataTreeNode n : kids )
396 {
397 count += countNodes( n );
398 }
399
400 return count;
401 }
402
403
404 public MetadataGraphVertex getEntry()
405 {
406 return entry;
407 }
408
409 public void setEntry( MetadataGraphVertex entry )
410 {
411 this.entry = entry;
412 }
413
414 public TreeSet<MetadataGraphVertex> getVertices()
415 {
416 return vertices;
417 }
418
419 public List<MetadataGraphEdge> getIncidentEdges( MetadataGraphVertex vertex )
420 {
421 checkEdges();
422 return incidentEdges.get( vertex );
423 }
424
425 public List<MetadataGraphEdge> getExcidentEdges( MetadataGraphVertex vertex )
426 {
427 checkEdges();
428 return excidentEdges.get( vertex );
429 }
430
431 public boolean isVersionedVertices()
432 {
433 return versionedVertices;
434 }
435
436 public void setVersionedVertices( boolean versionedVertices )
437 {
438 this.versionedVertices = versionedVertices;
439 }
440
441 public boolean isScopedVertices()
442 {
443 return scopedVertices;
444 }
445
446 public void setScopedVertices( boolean scopedVertices )
447 {
448 this.scopedVertices = scopedVertices;
449
450
451 if ( scopedVertices )
452 {
453 versionedVertices = true;
454 }
455 }
456
457 public ArtifactScopeEnum getScope()
458 {
459 return scope;
460 }
461
462 public void setScope( ArtifactScopeEnum scope )
463 {
464 this.scope = scope;
465 }
466
467
468 public boolean isEmpty()
469 {
470 return entry == null || vertices == null || vertices.isEmpty();
471 }
472
473
474 public boolean isEmptyEdges()
475 {
476 return isEmpty() || incidentEdges == null || incidentEdges.isEmpty();
477 }
478
479 @Override
480 public String toString()
481 {
482 StringBuilder sb = new StringBuilder( 512 );
483 if ( isEmpty() )
484 {
485 return "empty";
486 }
487 for ( MetadataGraphVertex v : vertices )
488 {
489 sb.append( "Vertex: " ).append( v.getMd().toString() ).append( '\n' );
490 List<MetadataGraphEdge> ins = getIncidentEdges( v );
491 if ( ins != null )
492 {
493 for ( MetadataGraphEdge e : ins )
494 {
495 sb.append( " from : " ).append( e.toString() ).append( '\n' );
496 }
497 }
498 else
499 {
500 sb.append( " no entries\n" );
501 }
502
503 List<MetadataGraphEdge> outs = getExcidentEdges( v );
504 if ( outs != null )
505 {
506 for ( MetadataGraphEdge e : outs )
507 {
508 sb.append( " to : " ).append( e.toString() ).append( '\n' );
509 }
510 }
511 else
512 {
513 sb.append( " no exit\n" );
514 }
515
516 sb.append( "-------------------------------------------------\n" );
517 }
518 sb.append( "=============================================================\n" );
519 return sb.toString();
520 }
521
522
523
524 }