View Javadoc

1   /*
2    * ModeShape (http://www.modeshape.org)
3    * See the COPYRIGHT.txt file distributed with this work for information
4    * regarding copyright ownership.  Some portions may be licensed
5    * to Red Hat, Inc. under one or more contributor license agreements.
6    * See the AUTHORS.txt file in the distribution for a full listing of 
7    * individual contributors. 
8    *
9    * ModeShape is free software. Unless otherwise indicated, all code in ModeShape
10   * is licensed to you under the terms of the GNU Lesser General Public License as
11   * published by the Free Software Foundation; either version 2.1 of
12   * the License, or (at your option) any later version.
13   *
14   * ModeShape is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17   * Lesser General Public License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this software; if not, write to the Free
21   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
22   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
23   */
24  package org.modeshape.graph.property.basic;
25  
26  import java.util.ArrayList;
27  import java.util.Collections;
28  import java.util.Iterator;
29  import java.util.LinkedList;
30  import java.util.List;
31  import java.util.NoSuchElementException;
32  import net.jcip.annotations.Immutable;
33  import net.jcip.annotations.NotThreadSafe;
34  import org.modeshape.common.CommonI18n;
35  import org.modeshape.common.text.TextEncoder;
36  import org.modeshape.common.util.CheckArg;
37  import org.modeshape.graph.GraphI18n;
38  import org.modeshape.graph.property.InvalidPathException;
39  import org.modeshape.graph.property.Name;
40  import org.modeshape.graph.property.NamespaceRegistry;
41  import org.modeshape.graph.property.Path;
42  
43  /**
44   * An abstract foundation for different {@link Path} implementations. This class does not manage any of the {@link Path}'s state,
45   * but it does provide implementations for most of the methods based upon a few abstract methods. For example, any implementaton
46   * that requires the {@link Path.Segment path's segments} are written to use the {@link #iterator()}, since that is likely more
47   * efficient for the majority of implementations.
48   */
49  @Immutable
50  public abstract class AbstractPath implements Path {
51  
52      /**
53       * The initial serializable version. Version {@value}
54       */
55      private static final long serialVersionUID = 1L;
56  
57      public static final Path SELF_PATH = new BasicPath(Collections.singletonList(Path.SELF_SEGMENT), false);
58  
59      protected static Iterator<Path.Segment> EMPTY_PATH_ITERATOR = new Iterator<Segment>() {
60          /**
61           * {@inheritDoc}
62           * 
63           * @see java.util.Iterator#hasNext()
64           */
65          public boolean hasNext() {
66              return false;
67          }
68  
69          /**
70           * {@inheritDoc}
71           * 
72           * @see java.util.Iterator#next()
73           */
74          public Segment next() {
75              throw new NoSuchElementException();
76          }
77  
78          /**
79           * {@inheritDoc}
80           * 
81           * @see java.util.Iterator#remove()
82           */
83          public void remove() {
84              throw new UnsupportedOperationException();
85          }
86      };
87  
88      @NotThreadSafe
89      protected static class SingleIterator<T> implements Iterator<T> {
90          private T value;
91  
92          protected SingleIterator( T value ) {
93              this.value = value;
94          }
95  
96          /**
97           * {@inheritDoc}
98           * 
99           * @see java.util.Iterator#hasNext()
100          */
101         public boolean hasNext() {
102             return value != null;
103         }
104 
105         /**
106          * {@inheritDoc}
107          * 
108          * @see java.util.Iterator#next()
109          */
110         public T next() {
111             if (value == null) throw new NoSuchElementException();
112             T next = value;
113             value = null;
114             return next;
115         }
116 
117         /**
118          * {@inheritDoc}
119          * 
120          * @see java.util.Iterator#remove()
121          */
122         public void remove() {
123             throw new UnsupportedOperationException();
124         }
125     }
126 
127     private transient int hc = 0;
128 
129     protected boolean isNormalized( List<Segment> segments ) {
130         boolean nonParentReference = false;
131         boolean first = isAbsolute(); // only care about first one when it's absolute
132         for (Segment segment : segments) {
133             if (segment.isSelfReference()) return false;
134             if (segment.isParentReference()) {
135                 if (nonParentReference || first) return false;
136             } else {
137                 nonParentReference = true;
138             }
139             first = false;
140         }
141         return true;
142     }
143 
144     /**
145      * {@inheritDoc}
146      * 
147      * @see org.modeshape.graph.property.Path#isIdentifier()
148      */
149     public boolean isIdentifier() {
150         return false;
151     }
152 
153     /**
154      * {@inheritDoc}
155      * 
156      * @see org.modeshape.graph.property.Path#getCanonicalPath()
157      */
158     public Path getCanonicalPath() {
159         if (!this.isAbsolute()) {
160             String msg = GraphI18n.pathIsNotAbsolute.text(this);
161             throw new InvalidPathException(msg);
162         }
163         if (this.isNormalized()) return this;
164         return this.getNormalizedPath();
165     }
166 
167     /**
168      * {@inheritDoc}
169      */
170     public Path getCommonAncestor( Path that ) {
171         CheckArg.isNotNull(that, "that");
172         if (that.isRoot()) return that;
173         Path normalizedPath = this.getNormalizedPath();
174         int lastIndex = 0;
175         Iterator<Segment> thisIter = normalizedPath.iterator();
176         Iterator<Segment> thatIter = that.getNormalizedPath().iterator();
177         while (thisIter.hasNext() && thatIter.hasNext()) {
178             Segment thisSeg = thisIter.next();
179             Segment thatSeg = thatIter.next();
180             if (thisSeg.equals(thatSeg)) {
181                 ++lastIndex;
182             } else {
183                 break;
184             }
185         }
186         if (lastIndex == 0) return RootPath.INSTANCE;
187         return normalizedPath.subpath(0, lastIndex);
188     }
189 
190     /**
191      * {@inheritDoc}
192      */
193     public Path.Segment getLastSegment() {
194         return this.getSegmentsList().get(size() - 1);
195     }
196 
197     /**
198      * {@inheritDoc}
199      * 
200      * @see org.modeshape.graph.property.Path#endsWith(org.modeshape.graph.property.Name)
201      */
202     public boolean endsWith( Name nameOfLastSegment ) {
203         Segment segment = getLastSegment();
204         return segment != null && segment.getName().equals(nameOfLastSegment) && !segment.hasIndex();
205     }
206 
207     /**
208      * {@inheritDoc}
209      * 
210      * @see org.modeshape.graph.property.Path#endsWith(org.modeshape.graph.property.Name, int)
211      */
212     public boolean endsWith( Name nameOfLastSegment,
213                              int snsIndex ) {
214         Segment segment = getLastSegment();
215         return segment != null && segment.getName().equals(nameOfLastSegment) && segment.getIndex() == snsIndex;
216     }
217 
218     /**
219      * {@inheritDoc}
220      * 
221      * @see org.modeshape.graph.property.Path#getParent()
222      */
223     public Path getParent() {
224         return getAncestor(1);
225     }
226 
227     /**
228      * {@inheritDoc}
229      */
230     public Segment getSegment( int index ) {
231         CheckArg.isNonNegative(index, "index");
232         return this.getSegmentsList().get(index);
233     }
234 
235     /**
236      * {@inheritDoc}
237      */
238     public Segment[] getSegmentsArray() {
239         // By default, make a new array every time since arrays are mutable, and use the iterator
240         // since that is probably more efficient than creating a list ...
241         Segment[] result = new Path.Segment[size()];
242         int i = 0;
243         for (Segment segment : this) {
244             result[i] = segment;
245             ++i;
246         }
247         return result;
248     }
249 
250     /**
251      * {@inheritDoc}
252      */
253     public Path getNormalizedPath() {
254         if (this.isNormalized()) return this;
255         LinkedList<Segment> newSegments = new LinkedList<Segment>();
256         for (Segment segment : this) {
257             if (segment.isSelfReference()) continue;
258             if (segment.isParentReference()) {
259                 if (newSegments.isEmpty()) {
260                     if (this.isAbsolute()) {
261                         throw new InvalidPathException(CommonI18n.pathCannotBeNormalized.text(this));
262                     }
263                 } else if (!newSegments.getLast().isParentReference()) {
264                     newSegments.removeLast();
265                     continue;
266                 }
267             }
268             newSegments.add(segment);
269         }
270         if (newSegments.isEmpty()) {
271             if (this.isAbsolute()) return RootPath.INSTANCE;
272             // Otherwise relative and it had contained nothing but self references ...
273             return SELF_PATH;
274         }
275         return new BasicPath(newSegments, this.isAbsolute());
276     }
277 
278     /**
279      * {@inheritDoc}
280      */
281     public String getString() {
282         return doGetString(null, null, null);
283     }
284 
285     /**
286      * {@inheritDoc}
287      */
288     public String getString( TextEncoder encoder ) {
289         return doGetString(null, encoder, null);
290     }
291 
292     /**
293      * {@inheritDoc}
294      */
295     public String getString( NamespaceRegistry namespaceRegistry ) {
296         CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
297         return doGetString(namespaceRegistry, null, null);
298     }
299 
300     /**
301      * {@inheritDoc}
302      */
303     public String getString( NamespaceRegistry namespaceRegistry,
304                              TextEncoder encoder ) {
305         CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
306         return doGetString(namespaceRegistry, encoder, null);
307     }
308 
309     /**
310      * {@inheritDoc}
311      * 
312      * @see org.modeshape.graph.property.Path#getString(org.modeshape.graph.property.NamespaceRegistry,
313      *      org.modeshape.common.text.TextEncoder, org.modeshape.common.text.TextEncoder)
314      */
315     public String getString( NamespaceRegistry namespaceRegistry,
316                              TextEncoder encoder,
317                              TextEncoder delimiterEncoder ) {
318         return doGetString(namespaceRegistry, encoder, delimiterEncoder);
319     }
320 
321     /**
322      * Method that creates the string representation. This method works two different ways depending upon whether the namespace
323      * registry is provided.
324      * 
325      * @param namespaceRegistry
326      * @param encoder
327      * @param delimiterEncoder
328      * @return this path as a string
329      */
330     protected String doGetString( NamespaceRegistry namespaceRegistry,
331                                   TextEncoder encoder,
332                                   TextEncoder delimiterEncoder ) {
333         if (encoder == null) encoder = DEFAULT_ENCODER;
334         final String delimiter = delimiterEncoder != null ? delimiterEncoder.encode(DELIMITER_STR) : DELIMITER_STR;
335 
336         // Since the segments are immutable, this code need not be synchronized because concurrent threads
337         // may just compute the same value (with no harm done)
338         StringBuilder sb = new StringBuilder();
339         if (this.isAbsolute()) sb.append(delimiter);
340         boolean first = true;
341         for (Segment segment : this) {
342             if (first) {
343                 first = false;
344             } else {
345                 sb.append(delimiter);
346             }
347             assert segment != null;
348             sb.append(segment.getString(namespaceRegistry, encoder, delimiterEncoder));
349         }
350         String result = sb.toString();
351         // Save the result to the internal string if this the default encoder is used.
352         // This is not synchronized, but it's okay
353         return result;
354     }
355 
356     /**
357      * {@inheritDoc}
358      */
359     public boolean hasSameAncestor( Path that ) {
360         CheckArg.isNotNull(that, "that");
361         if (that.size() != this.size()) return false;
362         if (this.size() == 1) return true; // both nodes are just under the root
363         for (int i = this.size() - 2; i >= 0; --i) {
364             Path.Segment thisSegment = this.getSegment(i);
365             Path.Segment thatSegment = that.getSegment(i);
366             if (!thisSegment.equals(thatSegment)) return false;
367         }
368         return true;
369     }
370 
371     /**
372      * {@inheritDoc}
373      */
374     public boolean isAncestorOf( Path decendant ) {
375         CheckArg.isNotNull(decendant, "that");
376         if (this == decendant) return false;
377         if (this.size() >= decendant.size()) return false;
378 
379         Iterator<Path.Segment> thisIter = this.iterator();
380         Iterator<Path.Segment> thatIter = decendant.iterator();
381         while (thisIter.hasNext()) {
382             Path.Segment thisSeg = thisIter.next();
383             Path.Segment thatSeg = thatIter.next();
384             if (!thisSeg.equals(thatSeg)) return false;
385         }
386         return true;
387     }
388 
389     /**
390      * {@inheritDoc}
391      * 
392      * @see org.modeshape.graph.property.Path#isAtOrBelow(org.modeshape.graph.property.Path)
393      */
394     public boolean isAtOrBelow( Path other ) {
395         CheckArg.isNotNull(other, "other");
396         if (this == other) return true;
397         if (other.isRoot()) return true;
398         if (other.size() > this.size()) return false;
399         Iterator<Segment> thisIter = iterator();
400         Iterator<Segment> thatIter = other.iterator();
401         while (thisIter.hasNext() && thatIter.hasNext()) {
402             if (!thisIter.next().equals(thatIter.next())) return false;
403         }
404         if (thatIter.hasNext()) return false; // The other still has segments, but this doesn't
405         return true;
406     }
407 
408     /**
409      * {@inheritDoc}
410      * 
411      * @see org.modeshape.graph.property.Path#isAtOrAbove(org.modeshape.graph.property.Path)
412      */
413     public boolean isAtOrAbove( Path other ) {
414         CheckArg.isNotNull(other, "other");
415         if (this == other) return true;
416         if (this.size() > other.size()) return false;
417         Iterator<Segment> thisIter = iterator();
418         Iterator<Segment> thatIter = other.iterator();
419         while (thisIter.hasNext() && thatIter.hasNext()) {
420             if (!thisIter.next().equals(thatIter.next())) return false;
421         }
422         if (thisIter.hasNext()) return false; // This still has segments, but other doesn't
423         return true;
424     }
425 
426     /**
427      * {@inheritDoc}
428      */
429     public boolean isDecendantOf( Path ancestor ) {
430         CheckArg.isNotNull(ancestor, "ancestor");
431         return ancestor.isAncestorOf(this);
432     }
433 
434     /**
435      * {@inheritDoc}
436      */
437     public boolean isSameAs( Path other ) {
438         return other != null && this.compareTo(other) == 0;
439     }
440 
441     /**
442      * {@inheritDoc}
443      */
444     public Iterator<Segment> iterator() {
445         return getSegmentsList().iterator();
446     }
447 
448     /**
449      * {@inheritDoc}
450      * 
451      * @see org.modeshape.graph.property.Path#pathsFromRoot()
452      */
453     public Iterator<Path> pathsFromRoot() {
454         LinkedList<Path> paths = new LinkedList<Path>();
455         Path path = this;
456         while (path != null) {
457             paths.addFirst(path);
458             if (path.isRoot()) break;
459             path = path.getParent();
460         }
461         return paths.iterator();
462     }
463 
464     /**
465      * {@inheritDoc}
466      * 
467      * @see org.modeshape.graph.property.Path#relativeToRoot()
468      */
469     public Path relativeToRoot() {
470         return new BasicPath(getSegmentsList(), false);
471     }
472 
473     /**
474      * {@inheritDoc}
475      */
476     public Path relativeTo( Path startingPath ) {
477         CheckArg.isNotNull(startingPath, "to");
478         if (!this.isAbsolute()) {
479             String msg = GraphI18n.pathIsNotAbsolute.text(this);
480             throw new InvalidPathException(msg);
481         }
482         if (startingPath.isRoot()) {
483             // We just want a relative path containing the same segments ...
484             return relativeToRoot();
485         }
486         if (!startingPath.isAbsolute()) {
487             String msg = GraphI18n.pathIsNotAbsolute.text(startingPath);
488             throw new InvalidPathException(msg);
489         }
490 
491         // Count the number of segments up to the common ancestor (relative path is what remains) ...
492         int lengthOfCommonAncestor = 0;
493         Iterator<Segment> thisIter = this.getNormalizedPath().iterator();
494         Iterator<Segment> toIter = startingPath.getNormalizedPath().iterator();
495         while (thisIter.hasNext() && toIter.hasNext()) {
496             Segment thisSeg = thisIter.next();
497             Segment toSeg = toIter.next();
498             if (thisSeg.equals(toSeg)) {
499                 ++lengthOfCommonAncestor;
500             } else {
501                 break;
502             }
503         }
504         // Create the relative path, starting with parent references to the common ancestor ...
505         int numberOfParentReferences = startingPath.size() - lengthOfCommonAncestor;
506         List<Segment> relativeSegments = new ArrayList<Segment>();
507         for (int i = 0; i != numberOfParentReferences; ++i) {
508             relativeSegments.add(Path.PARENT_SEGMENT);
509         }
510         // Add the segments of this path from the common ancestor ...
511         for (int i = lengthOfCommonAncestor; i < this.size(); ++i) {
512             relativeSegments.add(getSegment(i));
513         }
514         if (relativeSegments.isEmpty()) {
515             relativeSegments.add(Path.SELF_SEGMENT);
516         }
517         return new BasicPath(relativeSegments, false);
518     }
519 
520     /**
521      * {@inheritDoc}
522      */
523     public Path resolve( Path relativePath ) {
524         CheckArg.isNotNull(relativePath, "relative path");
525         if (!this.isAbsolute()) {
526             String msg = GraphI18n.pathIsNotAbsolute.text(this);
527             throw new InvalidPathException(msg);
528         }
529         if (relativePath.isAbsolute()) {
530             String msg = GraphI18n.pathIsNotRelative.text(relativePath);
531             throw new InvalidPathException(msg);
532         }
533         // If the relative path is the self or parent reference ...
534         relativePath = relativePath.getNormalizedPath();
535         if (relativePath.size() == 1) {
536             Segment onlySegment = relativePath.getSegment(0);
537             if (onlySegment.isSelfReference()) return this;
538             if (onlySegment.isParentReference()) return this.getParent();
539         }
540         List<Segment> segments = new ArrayList<Segment>(this.size() + relativePath.size());
541         for (Segment segment : this) {
542             segments.add(segment);
543         }
544         for (Segment segment : relativePath) {
545             segments.add(segment);
546         }
547         return new BasicPath(segments, true).getNormalizedPath();
548     }
549 
550     /**
551      * {@inheritDoc}
552      */
553     public Path resolveAgainst( Path absolutePath ) {
554         CheckArg.isNotNull(absolutePath, "absolute path");
555         return absolutePath.resolve(this);
556     }
557 
558     /**
559      * {@inheritDoc}
560      */
561     public Path subpath( int beginIndex ) {
562         return subpath(beginIndex, size());
563     }
564 
565     /**
566      * {@inheritDoc}
567      */
568     public Path subpath( int beginIndex,
569                          int endIndex ) {
570         CheckArg.isNonNegative(beginIndex, "beginIndex");
571         CheckArg.isNonNegative(endIndex, "endIndex");
572         int size = size();
573         if (beginIndex == 0) {
574             if (endIndex == 0) return RootPath.INSTANCE;
575             if (endIndex == size) return this;
576         }
577         if (beginIndex >= size) {
578             throw new IndexOutOfBoundsException(
579                                                 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToSize.text(beginIndex,
580                                                                                                                        size));
581         }
582         if (beginIndex > endIndex) {
583             throw new IndexOutOfBoundsException(
584                                                 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToEndingIndex.text(beginIndex,
585                                                                                                                               endIndex));
586         }
587         // This reuses the same list, so it's pretty efficient ...
588         return new BasicPath(createSegmentsSubList(beginIndex, endIndex), this.isAbsolute());
589     }
590 
591     protected List<Segment> createSegmentsSubList( int validBeginIndex,
592                                                    int validEndIndex ) {
593         return this.getSegmentsList().subList(validBeginIndex, validEndIndex);
594     }
595 
596     /**
597      * {@inheritDoc}
598      */
599     @Override
600     public int hashCode() {
601         if (hc == 0) {
602             int hashCode = 1;
603             for (Segment segment : this) {
604                 hashCode = 31 * hashCode + segment.hashCode();
605             }
606             hc = hashCode;
607         }
608         return hc;
609     }
610 
611     /**
612      * Method used by {@link AbstractPath#equals(Object)} implementation to quickly get an Iterator over the segments in the
613      * parent.
614      * 
615      * @return the iterator over the segments; never null, but may not have any elements
616      */
617     protected abstract Iterator<Segment> getSegmentsOfParent();
618 
619     /**
620      * {@inheritDoc}
621      */
622     @Override
623     public boolean equals( Object obj ) {
624         if (obj == this) return true;
625         if (obj instanceof Path) {
626             Path that = (Path)obj;
627             // First check whether the paths are roots ...
628             if (this.isRoot()) return that.isRoot();
629             else if (that.isRoot()) return false;
630             // Now check the hash code and size ...
631             if (this.hashCode() != that.hashCode()) return false;
632             if (this.size() != that.size()) return false;
633             // Check the last segments, since these will often differ anyway ...
634             if (!this.getLastSegment().equals(that.getLastSegment())) return false;
635             if (this.size() == 1) return true;
636             // Check the rest of the names ...
637             Iterator<Segment> thisIter = that instanceof AbstractPath ? this.getSegmentsOfParent() : this.iterator();
638             Iterator<Segment> thatIter = that instanceof AbstractPath ? ((AbstractPath)that).getSegmentsOfParent() : that.iterator();
639             while (thisIter.hasNext()) {
640                 Segment thisSegment = thisIter.next();
641                 Segment thatSegment = thatIter.next();
642                 if (!thisSegment.equals(thatSegment)) return false;
643             }
644             return true;
645         }
646         return false;
647     }
648 
649     /**
650      * {@inheritDoc}
651      */
652     public int compareTo( Path that ) {
653         if (this == that) return 0;
654         Iterator<Segment> thisIter = getSegmentsList().iterator();
655         Iterator<Segment> thatIter = that.iterator();
656         while (thisIter.hasNext() && thatIter.hasNext()) {
657             Segment thisSegment = thisIter.next();
658             Segment thatSegment = thatIter.next();
659             int diff = thisSegment.compareTo(thatSegment);
660             if (diff != 0) return diff;
661         }
662         if (thisIter.hasNext()) return 1;
663         if (thatIter.hasNext()) return -1;
664         return 0;
665     }
666 
667     /**
668      * {@inheritDoc}
669      */
670     @Override
671     public String toString() {
672         return getString(Path.NO_OP_ENCODER);
673     }
674 }