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#getCanonicalPath()
148      */
149     public Path getCanonicalPath() {
150         if (!this.isAbsolute()) {
151             String msg = GraphI18n.pathIsNotAbsolute.text(this);
152             throw new InvalidPathException(msg);
153         }
154         if (this.isNormalized()) return this;
155         return this.getNormalizedPath();
156     }
157 
158     /**
159      * {@inheritDoc}
160      */
161     public Path getCommonAncestor( Path that ) {
162         CheckArg.isNotNull(that, "that");
163         if (that.isRoot()) return that;
164         Path normalizedPath = this.getNormalizedPath();
165         int lastIndex = 0;
166         Iterator<Segment> thisIter = normalizedPath.iterator();
167         Iterator<Segment> thatIter = that.getNormalizedPath().iterator();
168         while (thisIter.hasNext() && thatIter.hasNext()) {
169             Segment thisSeg = thisIter.next();
170             Segment thatSeg = thatIter.next();
171             if (thisSeg.equals(thatSeg)) {
172                 ++lastIndex;
173             } else {
174                 break;
175             }
176         }
177         if (lastIndex == 0) return RootPath.INSTANCE;
178         return normalizedPath.subpath(0, lastIndex);
179     }
180 
181     /**
182      * {@inheritDoc}
183      */
184     public Path.Segment getLastSegment() {
185         return this.getSegmentsList().get(size() - 1);
186     }
187 
188     /**
189      * {@inheritDoc}
190      * 
191      * @see org.modeshape.graph.property.Path#endsWith(org.modeshape.graph.property.Name)
192      */
193     public boolean endsWith( Name nameOfLastSegment ) {
194         Segment segment = getLastSegment();
195         return segment != null && segment.getName().equals(nameOfLastSegment) && !segment.hasIndex();
196     }
197 
198     /**
199      * {@inheritDoc}
200      * 
201      * @see org.modeshape.graph.property.Path#endsWith(org.modeshape.graph.property.Name, int)
202      */
203     public boolean endsWith( Name nameOfLastSegment,
204                              int snsIndex ) {
205         Segment segment = getLastSegment();
206         return segment != null && segment.getName().equals(nameOfLastSegment) && segment.getIndex() == snsIndex;
207     }
208 
209     /**
210      * {@inheritDoc}
211      * 
212      * @see org.modeshape.graph.property.Path#getParent()
213      */
214     public Path getParent() {
215         return getAncestor(1);
216     }
217 
218     /**
219      * {@inheritDoc}
220      */
221     public Segment getSegment( int index ) {
222         CheckArg.isNonNegative(index, "index");
223         return this.getSegmentsList().get(index);
224     }
225 
226     /**
227      * {@inheritDoc}
228      */
229     public Segment[] getSegmentsArray() {
230         // By default, make a new array every time since arrays are mutable, and use the iterator
231         // since that is probably more efficient than creating a list ...
232         Segment[] result = new Path.Segment[size()];
233         int i = 0;
234         for (Segment segment : this) {
235             result[i] = segment;
236             ++i;
237         }
238         return result;
239     }
240 
241     /**
242      * {@inheritDoc}
243      */
244     public Path getNormalizedPath() {
245         if (this.isNormalized()) return this;
246         LinkedList<Segment> newSegments = new LinkedList<Segment>();
247         for (Segment segment : this) {
248             if (segment.isSelfReference()) continue;
249             if (segment.isParentReference()) {
250                 if (newSegments.isEmpty()) {
251                     if (this.isAbsolute()) {
252                         throw new InvalidPathException(CommonI18n.pathCannotBeNormalized.text(this));
253                     }
254                 } else if (!newSegments.getLast().isParentReference()) {
255                     newSegments.removeLast();
256                     continue;
257                 }
258             }
259             newSegments.add(segment);
260         }
261         if (newSegments.isEmpty()) {
262             if (this.isAbsolute()) return RootPath.INSTANCE;
263             // Otherwise relative and it had contained nothing but self references ...
264             return SELF_PATH;
265         }
266         return new BasicPath(newSegments, this.isAbsolute());
267     }
268 
269     /**
270      * {@inheritDoc}
271      */
272     public String getString() {
273         return doGetString(null, null, null);
274     }
275 
276     /**
277      * {@inheritDoc}
278      */
279     public String getString( TextEncoder encoder ) {
280         return doGetString(null, encoder, null);
281     }
282 
283     /**
284      * {@inheritDoc}
285      */
286     public String getString( NamespaceRegistry namespaceRegistry ) {
287         CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
288         return doGetString(namespaceRegistry, null, null);
289     }
290 
291     /**
292      * {@inheritDoc}
293      */
294     public String getString( NamespaceRegistry namespaceRegistry,
295                              TextEncoder encoder ) {
296         CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
297         return doGetString(namespaceRegistry, encoder, null);
298     }
299 
300     /**
301      * {@inheritDoc}
302      * 
303      * @see org.modeshape.graph.property.Path#getString(org.modeshape.graph.property.NamespaceRegistry,
304      *      org.modeshape.common.text.TextEncoder, org.modeshape.common.text.TextEncoder)
305      */
306     public String getString( NamespaceRegistry namespaceRegistry,
307                              TextEncoder encoder,
308                              TextEncoder delimiterEncoder ) {
309         return doGetString(namespaceRegistry, encoder, delimiterEncoder);
310     }
311 
312     /**
313      * Method that creates the string representation. This method works two different ways depending upon whether the namespace
314      * registry is provided.
315      * 
316      * @param namespaceRegistry
317      * @param encoder
318      * @param delimiterEncoder
319      * @return this path as a string
320      */
321     protected String doGetString( NamespaceRegistry namespaceRegistry,
322                                   TextEncoder encoder,
323                                   TextEncoder delimiterEncoder ) {
324         if (encoder == null) encoder = DEFAULT_ENCODER;
325         final String delimiter = delimiterEncoder != null ? delimiterEncoder.encode(DELIMITER_STR) : DELIMITER_STR;
326 
327         // Since the segments are immutable, this code need not be synchronized because concurrent threads
328         // may just compute the same value (with no harm done)
329         StringBuilder sb = new StringBuilder();
330         if (this.isAbsolute()) sb.append(delimiter);
331         boolean first = true;
332         for (Segment segment : this) {
333             if (first) {
334                 first = false;
335             } else {
336                 sb.append(delimiter);
337             }
338             assert segment != null;
339             sb.append(segment.getString(namespaceRegistry, encoder, delimiterEncoder));
340         }
341         String result = sb.toString();
342         // Save the result to the internal string if this the default encoder is used.
343         // This is not synchronized, but it's okay
344         return result;
345     }
346 
347     /**
348      * {@inheritDoc}
349      */
350     public boolean hasSameAncestor( Path that ) {
351         CheckArg.isNotNull(that, "that");
352         if (that.size() != this.size()) return false;
353         if (this.size() == 1) return true; // both nodes are just under the root
354         for (int i = this.size() - 2; i >= 0; --i) {
355             Path.Segment thisSegment = this.getSegment(i);
356             Path.Segment thatSegment = that.getSegment(i);
357             if (!thisSegment.equals(thatSegment)) return false;
358         }
359         return true;
360     }
361 
362     /**
363      * {@inheritDoc}
364      */
365     public boolean isAncestorOf( Path decendant ) {
366         CheckArg.isNotNull(decendant, "that");
367         if (this == decendant) return false;
368         if (this.size() >= decendant.size()) return false;
369 
370         Iterator<Path.Segment> thisIter = this.iterator();
371         Iterator<Path.Segment> thatIter = decendant.iterator();
372         while (thisIter.hasNext()) {
373             Path.Segment thisSeg = thisIter.next();
374             Path.Segment thatSeg = thatIter.next();
375             if (!thisSeg.equals(thatSeg)) return false;
376         }
377         return true;
378     }
379 
380     /**
381      * {@inheritDoc}
382      * 
383      * @see org.modeshape.graph.property.Path#isAtOrBelow(org.modeshape.graph.property.Path)
384      */
385     public boolean isAtOrBelow( Path other ) {
386         CheckArg.isNotNull(other, "other");
387         if (this == other) return true;
388         if (other.isRoot()) return true;
389         if (other.size() > this.size()) return false;
390         Iterator<Segment> thisIter = iterator();
391         Iterator<Segment> thatIter = other.iterator();
392         while (thisIter.hasNext() && thatIter.hasNext()) {
393             if (!thisIter.next().equals(thatIter.next())) return false;
394         }
395         if (thatIter.hasNext()) return false; // The other still has segments, but this doesn't
396         return true;
397     }
398 
399     /**
400      * {@inheritDoc}
401      * 
402      * @see org.modeshape.graph.property.Path#isAtOrAbove(org.modeshape.graph.property.Path)
403      */
404     public boolean isAtOrAbove( Path other ) {
405         CheckArg.isNotNull(other, "other");
406         if (this == other) return true;
407         if (this.size() > other.size()) return false;
408         Iterator<Segment> thisIter = iterator();
409         Iterator<Segment> thatIter = other.iterator();
410         while (thisIter.hasNext() && thatIter.hasNext()) {
411             if (!thisIter.next().equals(thatIter.next())) return false;
412         }
413         if (thisIter.hasNext()) return false; // This still has segments, but other doesn't
414         return true;
415     }
416 
417     /**
418      * {@inheritDoc}
419      */
420     public boolean isDecendantOf( Path ancestor ) {
421         CheckArg.isNotNull(ancestor, "ancestor");
422         return ancestor.isAncestorOf(this);
423     }
424 
425     /**
426      * {@inheritDoc}
427      */
428     public boolean isSameAs( Path other ) {
429         return other != null && this.compareTo(other) == 0;
430     }
431 
432     /**
433      * {@inheritDoc}
434      */
435     public Iterator<Segment> iterator() {
436         return getSegmentsList().iterator();
437     }
438 
439     /**
440      * {@inheritDoc}
441      * 
442      * @see org.modeshape.graph.property.Path#pathsFromRoot()
443      */
444     public Iterator<Path> pathsFromRoot() {
445         LinkedList<Path> paths = new LinkedList<Path>();
446         Path path = this;
447         while (path != null) {
448             paths.addFirst(path);
449             if (path.isRoot()) break;
450             path = path.getParent();
451         }
452         return paths.iterator();
453     }
454 
455     /**
456      * {@inheritDoc}
457      * 
458      * @see org.modeshape.graph.property.Path#relativeToRoot()
459      */
460     public Path relativeToRoot() {
461         return new BasicPath(getSegmentsList(), false);
462     }
463 
464     /**
465      * {@inheritDoc}
466      */
467     public Path relativeTo( Path startingPath ) {
468         CheckArg.isNotNull(startingPath, "to");
469         if (!this.isAbsolute()) {
470             String msg = GraphI18n.pathIsNotAbsolute.text(this);
471             throw new InvalidPathException(msg);
472         }
473         if (startingPath.isRoot()) {
474             // We just want a relative path containing the same segments ...
475             return relativeToRoot();
476         }
477         if (!startingPath.isAbsolute()) {
478             String msg = GraphI18n.pathIsNotAbsolute.text(startingPath);
479             throw new InvalidPathException(msg);
480         }
481 
482         // Count the number of segments up to the common ancestor (relative path is what remains) ...
483         int lengthOfCommonAncestor = 0;
484         Iterator<Segment> thisIter = this.getNormalizedPath().iterator();
485         Iterator<Segment> toIter = startingPath.getNormalizedPath().iterator();
486         while (thisIter.hasNext() && toIter.hasNext()) {
487             Segment thisSeg = thisIter.next();
488             Segment toSeg = toIter.next();
489             if (thisSeg.equals(toSeg)) {
490                 ++lengthOfCommonAncestor;
491             } else {
492                 break;
493             }
494         }
495         // Create the relative path, starting with parent references to the common ancestor ...
496         int numberOfParentReferences = startingPath.size() - lengthOfCommonAncestor;
497         List<Segment> relativeSegments = new ArrayList<Segment>();
498         for (int i = 0; i != numberOfParentReferences; ++i) {
499             relativeSegments.add(Path.PARENT_SEGMENT);
500         }
501         // Add the segments of this path from the common ancestor ...
502         for (int i = lengthOfCommonAncestor; i < this.size(); ++i) {
503             relativeSegments.add(getSegment(i));
504         }
505         if (relativeSegments.isEmpty()) {
506             relativeSegments.add(Path.SELF_SEGMENT);
507         }
508         return new BasicPath(relativeSegments, false);
509     }
510 
511     /**
512      * {@inheritDoc}
513      */
514     public Path resolve( Path relativePath ) {
515         CheckArg.isNotNull(relativePath, "relative path");
516         if (!this.isAbsolute()) {
517             String msg = GraphI18n.pathIsNotAbsolute.text(this);
518             throw new InvalidPathException(msg);
519         }
520         if (relativePath.isAbsolute()) {
521             String msg = GraphI18n.pathIsNotRelative.text(relativePath);
522             throw new InvalidPathException(msg);
523         }
524         // If the relative path is the self or parent reference ...
525         relativePath = relativePath.getNormalizedPath();
526         if (relativePath.size() == 1) {
527             Segment onlySegment = relativePath.getSegment(0);
528             if (onlySegment.isSelfReference()) return this;
529             if (onlySegment.isParentReference()) return this.getParent();
530         }
531         List<Segment> segments = new ArrayList<Segment>(this.size() + relativePath.size());
532         for (Segment segment : this) {
533             segments.add(segment);
534         }
535         for (Segment segment : relativePath) {
536             segments.add(segment);
537         }
538         return new BasicPath(segments, true).getNormalizedPath();
539     }
540 
541     /**
542      * {@inheritDoc}
543      */
544     public Path resolveAgainst( Path absolutePath ) {
545         CheckArg.isNotNull(absolutePath, "absolute path");
546         return absolutePath.resolve(this);
547     }
548 
549     /**
550      * {@inheritDoc}
551      */
552     public Path subpath( int beginIndex ) {
553         return subpath(beginIndex, size());
554     }
555 
556     /**
557      * {@inheritDoc}
558      */
559     public Path subpath( int beginIndex,
560                          int endIndex ) {
561         CheckArg.isNonNegative(beginIndex, "beginIndex");
562         CheckArg.isNonNegative(endIndex, "endIndex");
563         int size = size();
564         if (beginIndex == 0) {
565             if (endIndex == 0) return RootPath.INSTANCE;
566             if (endIndex == size) return this;
567         }
568         if (beginIndex >= size) {
569             throw new IndexOutOfBoundsException(
570                                                 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToSize.text(beginIndex,
571                                                                                                                        size));
572         }
573         if (beginIndex > endIndex) {
574             throw new IndexOutOfBoundsException(
575                                                 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToEndingIndex.text(beginIndex,
576                                                                                                                               endIndex));
577         }
578         // This reuses the same list, so it's pretty efficient ...
579         return new BasicPath(createSegmentsSubList(beginIndex, endIndex), this.isAbsolute());
580     }
581 
582     protected List<Segment> createSegmentsSubList( int validBeginIndex,
583                                                    int validEndIndex ) {
584         return this.getSegmentsList().subList(validBeginIndex, validEndIndex);
585     }
586 
587     /**
588      * {@inheritDoc}
589      */
590     @Override
591     public int hashCode() {
592         if (hc == 0) {
593             int hashCode = 1;
594             for (Segment segment : this) {
595                 hashCode = 31 * hashCode + segment.hashCode();
596             }
597             hc = hashCode;
598         }
599         return hc;
600     }
601 
602     /**
603      * Method used by {@link AbstractPath#equals(Object)} implementation to quickly get an Iterator over the segments in the
604      * parent.
605      * 
606      * @return the iterator over the segments; never null, but may not have any elements
607      */
608     protected abstract Iterator<Segment> getSegmentsOfParent();
609 
610     /**
611      * {@inheritDoc}
612      */
613     @Override
614     public boolean equals( Object obj ) {
615         if (obj == this) return true;
616         if (obj instanceof Path) {
617             Path that = (Path)obj;
618             // First check whether the paths are roots ...
619             if (this.isRoot()) return that.isRoot();
620             else if (that.isRoot()) return false;
621             // Now check the hash code and size ...
622             if (this.hashCode() != that.hashCode()) return false;
623             if (this.size() != that.size()) return false;
624             // Check the last segments, since these will often differ anyway ...
625             if (!this.getLastSegment().equals(that.getLastSegment())) return false;
626             if (this.size() == 1) return true;
627             // Check the rest of the names ...
628             Iterator<Segment> thisIter = that instanceof AbstractPath ? this.getSegmentsOfParent() : this.iterator();
629             Iterator<Segment> thatIter = that instanceof AbstractPath ? ((AbstractPath)that).getSegmentsOfParent() : that.iterator();
630             while (thisIter.hasNext()) {
631                 Segment thisSegment = thisIter.next();
632                 Segment thatSegment = thatIter.next();
633                 if (!thisSegment.equals(thatSegment)) return false;
634             }
635             return true;
636         }
637         return false;
638     }
639 
640     /**
641      * {@inheritDoc}
642      */
643     public int compareTo( Path that ) {
644         if (this == that) return 0;
645         Iterator<Segment> thisIter = getSegmentsList().iterator();
646         Iterator<Segment> thatIter = that.iterator();
647         while (thisIter.hasNext() && thatIter.hasNext()) {
648             Segment thisSegment = thisIter.next();
649             Segment thatSegment = thatIter.next();
650             int diff = thisSegment.compareTo(thatSegment);
651             if (diff != 0) return diff;
652         }
653         if (thisIter.hasNext()) return 1;
654         if (thatIter.hasNext()) return -1;
655         return 0;
656     }
657 
658     /**
659      * {@inheritDoc}
660      */
661     @Override
662     public String toString() {
663         return getString(Path.NO_OP_ENCODER);
664     }
665 }