001 /*
002 * JBoss DNA (http://www.jboss.org/dna)
003 * See the COPYRIGHT.txt file distributed with this work for information
004 * regarding copyright ownership. Some portions may be licensed
005 * to Red Hat, Inc. under one or more contributor license agreements.
006 * See the AUTHORS.txt file in the distribution for a full listing of
007 * individual contributors.
008 *
009 * JBoss DNA is free software. Unless otherwise indicated, all code in JBoss DNA
010 * is licensed to you under the terms of the GNU Lesser General Public License as
011 * published by the Free Software Foundation; either version 2.1 of
012 * the License, or (at your option) any later version.
013 *
014 * JBoss DNA is distributed in the hope that it will be useful,
015 * but WITHOUT ANY WARRANTY; without even the implied warranty of
016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017 * Lesser General Public License for more details.
018 *
019 * You should have received a copy of the GNU Lesser General Public
020 * License along with this software; if not, write to the Free
021 * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
022 * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
023 */
024 package org.jboss.dna.graph.property.basic;
025
026 import java.util.ArrayList;
027 import java.util.Collections;
028 import java.util.Iterator;
029 import java.util.LinkedList;
030 import java.util.List;
031 import java.util.NoSuchElementException;
032 import net.jcip.annotations.NotThreadSafe;
033 import org.jboss.dna.common.CommonI18n;
034 import org.jboss.dna.common.text.TextEncoder;
035 import org.jboss.dna.common.util.CheckArg;
036 import org.jboss.dna.graph.GraphI18n;
037 import org.jboss.dna.graph.property.InvalidPathException;
038 import org.jboss.dna.graph.property.NamespaceRegistry;
039 import org.jboss.dna.graph.property.Path;
040
041 /**
042 * An abstract foundation for different {@link Path} implementations. This class does not manage any of the {@link Path}'s state,
043 * but it does provide implementations for most of the methods based upon a few abstract methods. For example, any implementaton
044 * that requires the {@link Path.Segment path's segments} are written to use the {@link #iterator()}, since that is likely more
045 * efficient for the majority of implementations.
046 *
047 * @author Randall Hauch
048 */
049 public abstract class AbstractPath implements Path {
050
051 /**
052 * The initial serializable version. Version {@value}
053 */
054 private static final long serialVersionUID = 1L;
055
056 public static final Path SELF_PATH = new BasicPath(Collections.singletonList(Path.SELF_SEGMENT), false);
057
058 protected static Iterator<Path.Segment> EMPTY_PATH_ITERATOR = new Iterator<Segment>() {
059 /**
060 * {@inheritDoc}
061 *
062 * @see java.util.Iterator#hasNext()
063 */
064 public boolean hasNext() {
065 return false;
066 }
067
068 /**
069 * {@inheritDoc}
070 *
071 * @see java.util.Iterator#next()
072 */
073 public Segment next() {
074 throw new NoSuchElementException();
075 }
076
077 /**
078 * {@inheritDoc}
079 *
080 * @see java.util.Iterator#remove()
081 */
082 public void remove() {
083 throw new UnsupportedOperationException();
084 }
085 };
086
087 @NotThreadSafe
088 protected static class SingleIterator<T> implements Iterator<T> {
089 private T value;
090
091 protected SingleIterator( T value ) {
092 this.value = value;
093 }
094
095 /**
096 * {@inheritDoc}
097 *
098 * @see java.util.Iterator#hasNext()
099 */
100 public boolean hasNext() {
101 return value != null;
102 }
103
104 /**
105 * {@inheritDoc}
106 *
107 * @see java.util.Iterator#next()
108 */
109 public T next() {
110 if (value == null) throw new NoSuchElementException();
111 T next = value;
112 value = null;
113 return next;
114 }
115
116 /**
117 * {@inheritDoc}
118 *
119 * @see java.util.Iterator#remove()
120 */
121 public void remove() {
122 throw new UnsupportedOperationException();
123 }
124 }
125
126 private transient int hc = 0;
127
128 protected boolean isNormalized( List<Segment> segments ) {
129 boolean nonParentReference = false;
130 boolean first = isAbsolute(); // only care about first one when it's absolute
131 for (Segment segment : segments) {
132 if (segment.isSelfReference()) return false;
133 if (segment.isParentReference()) {
134 if (nonParentReference || first) return false;
135 } else {
136 nonParentReference = true;
137 }
138 first = false;
139 }
140 return true;
141 }
142
143 /**
144 * {@inheritDoc}
145 *
146 * @see org.jboss.dna.graph.property.Path#getCanonicalPath()
147 */
148 public Path getCanonicalPath() {
149 if (!this.isAbsolute()) {
150 String msg = GraphI18n.pathIsNotAbsolute.text(this);
151 throw new InvalidPathException(msg);
152 }
153 if (this.isNormalized()) return this;
154 return this.getNormalizedPath();
155 }
156
157 /**
158 * {@inheritDoc}
159 */
160 public Path getCommonAncestor( Path that ) {
161 CheckArg.isNotNull(that, "that");
162 if (that.isRoot()) return that;
163 Path normalizedPath = this.getNormalizedPath();
164 int lastIndex = 0;
165 Iterator<Segment> thisIter = normalizedPath.iterator();
166 Iterator<Segment> thatIter = that.getNormalizedPath().iterator();
167 while (thisIter.hasNext() && thatIter.hasNext()) {
168 Segment thisSeg = thisIter.next();
169 Segment thatSeg = thatIter.next();
170 if (thisSeg.equals(thatSeg)) {
171 ++lastIndex;
172 } else {
173 break;
174 }
175 }
176 if (lastIndex == 0) return RootPath.INSTANCE;
177 return normalizedPath.subpath(0, lastIndex);
178 }
179
180 /**
181 * {@inheritDoc}
182 */
183 public Path.Segment getLastSegment() {
184 return this.getSegmentsList().get(size() - 1);
185 }
186
187 /**
188 * {@inheritDoc}
189 *
190 * @see org.jboss.dna.graph.property.Path#getParent()
191 */
192 public Path getParent() {
193 return getAncestor(1);
194 }
195
196 /**
197 * {@inheritDoc}
198 */
199 public Segment getSegment( int index ) {
200 CheckArg.isNonNegative(index, "index");
201 return this.getSegmentsList().get(index);
202 }
203
204 /**
205 * {@inheritDoc}
206 */
207 public Segment[] getSegmentsArray() {
208 // By default, make a new array every time since arrays are mutable, and use the iterator
209 // since that is probably more efficient than creating a list ...
210 Segment[] result = new Path.Segment[size()];
211 int i = 0;
212 for (Segment segment : this) {
213 result[i] = segment;
214 ++i;
215 }
216 return result;
217 }
218
219 /**
220 * {@inheritDoc}
221 */
222 public Path getNormalizedPath() {
223 if (this.isNormalized()) return this;
224 LinkedList<Segment> newSegments = new LinkedList<Segment>();
225 for (Segment segment : this) {
226 if (segment.isSelfReference()) continue;
227 if (segment.isParentReference()) {
228 if (newSegments.isEmpty()) {
229 if (this.isAbsolute()) {
230 throw new InvalidPathException(CommonI18n.pathCannotBeNormalized.text(this));
231 }
232 } else if (!newSegments.getLast().isParentReference()) {
233 newSegments.removeLast();
234 continue;
235 }
236 }
237 newSegments.add(segment);
238 }
239 if (newSegments.isEmpty()) {
240 if (this.isAbsolute()) return RootPath.INSTANCE;
241 // Otherwise relative and it had contained nothing but self references ...
242 return SELF_PATH;
243 }
244 return new BasicPath(newSegments, this.isAbsolute());
245 }
246
247 /**
248 * {@inheritDoc}
249 */
250 public String getString() {
251 return doGetString(null, null, null);
252 }
253
254 /**
255 * {@inheritDoc}
256 */
257 public String getString( TextEncoder encoder ) {
258 return doGetString(null, encoder, null);
259 }
260
261 /**
262 * {@inheritDoc}
263 */
264 public String getString( NamespaceRegistry namespaceRegistry ) {
265 CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
266 return doGetString(namespaceRegistry, null, null);
267 }
268
269 /**
270 * {@inheritDoc}
271 */
272 public String getString( NamespaceRegistry namespaceRegistry,
273 TextEncoder encoder ) {
274 CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
275 return doGetString(namespaceRegistry, encoder, null);
276 }
277
278 /**
279 * {@inheritDoc}
280 *
281 * @see org.jboss.dna.graph.property.Path#getString(org.jboss.dna.graph.property.NamespaceRegistry,
282 * org.jboss.dna.common.text.TextEncoder, org.jboss.dna.common.text.TextEncoder)
283 */
284 public String getString( NamespaceRegistry namespaceRegistry,
285 TextEncoder encoder,
286 TextEncoder delimiterEncoder ) {
287 return doGetString(namespaceRegistry, encoder, delimiterEncoder);
288 }
289
290 /**
291 * Method that creates the string representation. This method works two different ways depending upon whether the namespace
292 * registry is provided.
293 *
294 * @param namespaceRegistry
295 * @param encoder
296 * @param delimiterEncoder
297 * @return this path as a string
298 */
299 protected String doGetString( NamespaceRegistry namespaceRegistry,
300 TextEncoder encoder,
301 TextEncoder delimiterEncoder ) {
302 if (encoder == null) encoder = DEFAULT_ENCODER;
303 final String delimiter = delimiterEncoder != null ? delimiterEncoder.encode(DELIMITER_STR) : DELIMITER_STR;
304
305 // Since the segments are immutable, this code need not be synchronized because concurrent threads
306 // may just compute the same value (with no harm done)
307 StringBuilder sb = new StringBuilder();
308 if (this.isAbsolute()) sb.append(delimiter);
309 boolean first = true;
310 for (Segment segment : this) {
311 if (first) {
312 first = false;
313 } else {
314 sb.append(delimiter);
315 }
316 assert segment != null;
317 sb.append(segment.getString(namespaceRegistry, encoder, delimiterEncoder));
318 }
319 String result = sb.toString();
320 // Save the result to the internal string if this the default encoder is used.
321 // This is not synchronized, but it's okay
322 return result;
323 }
324
325 /**
326 * {@inheritDoc}
327 */
328 public boolean hasSameAncestor( Path that ) {
329 CheckArg.isNotNull(that, "that");
330 if (that.size() != this.size()) return false;
331 if (this.size() == 1) return true; // both nodes are just under the root
332 for (int i = this.size() - 2; i >= 0; --i) {
333 Path.Segment thisSegment = this.getSegment(i);
334 Path.Segment thatSegment = that.getSegment(i);
335 if (!thisSegment.equals(thatSegment)) return false;
336 }
337 return true;
338 }
339
340 /**
341 * {@inheritDoc}
342 */
343 public boolean isAncestorOf( Path decendant ) {
344 CheckArg.isNotNull(decendant, "that");
345 if (this == decendant) return false;
346 if (this.size() >= decendant.size()) return false;
347
348 Iterator<Path.Segment> thisIter = this.iterator();
349 Iterator<Path.Segment> thatIter = decendant.iterator();
350 while (thisIter.hasNext()) {
351 Path.Segment thisSeg = thisIter.next();
352 Path.Segment thatSeg = thatIter.next();
353 if (!thisSeg.equals(thatSeg)) return false;
354 }
355 return true;
356 }
357
358 /**
359 * {@inheritDoc}
360 *
361 * @see org.jboss.dna.graph.property.Path#isAtOrBelow(org.jboss.dna.graph.property.Path)
362 */
363 public boolean isAtOrBelow( Path other ) {
364 CheckArg.isNotNull(other, "other");
365 if (this == other) return true;
366 if (other.isRoot()) return true;
367 if (other.size() > this.size()) return false;
368 Iterator<Segment> thisIter = iterator();
369 Iterator<Segment> thatIter = other.iterator();
370 while (thisIter.hasNext() && thatIter.hasNext()) {
371 if (!thisIter.next().equals(thatIter.next())) return false;
372 }
373 if (thatIter.hasNext()) return false; // The other still has segments, but this doesn't
374 return true;
375 }
376
377 /**
378 * {@inheritDoc}
379 *
380 * @see org.jboss.dna.graph.property.Path#isAtOrAbove(org.jboss.dna.graph.property.Path)
381 */
382 public boolean isAtOrAbove( Path other ) {
383 CheckArg.isNotNull(other, "other");
384 if (this == other) return true;
385 if (this.size() > other.size()) return false;
386 Iterator<Segment> thisIter = iterator();
387 Iterator<Segment> thatIter = other.iterator();
388 while (thisIter.hasNext() && thatIter.hasNext()) {
389 if (!thisIter.next().equals(thatIter.next())) return false;
390 }
391 if (thisIter.hasNext()) return false; // This still has segments, but other doesn't
392 return true;
393 }
394
395 /**
396 * {@inheritDoc}
397 */
398 public boolean isDecendantOf( Path ancestor ) {
399 CheckArg.isNotNull(ancestor, "ancestor");
400 return ancestor.isAncestorOf(this);
401 }
402
403 /**
404 * {@inheritDoc}
405 */
406 public boolean isSameAs( Path other ) {
407 return other != null && this.compareTo(other) == 0;
408 }
409
410 /**
411 * {@inheritDoc}
412 */
413 public Iterator<Segment> iterator() {
414 return getSegmentsList().iterator();
415 }
416
417 /**
418 * {@inheritDoc}
419 *
420 * @see org.jboss.dna.graph.property.Path#pathsFromRoot()
421 */
422 public Iterator<Path> pathsFromRoot() {
423 LinkedList<Path> paths = new LinkedList<Path>();
424 Path path = this;
425 while (path != null) {
426 paths.addFirst(path);
427 if (path.isRoot()) break;
428 path = path.getParent();
429 }
430 return paths.iterator();
431 }
432
433 /**
434 * {@inheritDoc}
435 */
436 public Path relativeTo( Path startingPath ) {
437 CheckArg.isNotNull(startingPath, "to");
438 if (!this.isAbsolute()) {
439 String msg = GraphI18n.pathIsNotAbsolute.text(this);
440 throw new InvalidPathException(msg);
441 }
442 if (!startingPath.isAbsolute()) {
443 String msg = GraphI18n.pathIsNotAbsolute.text(startingPath);
444 throw new InvalidPathException(msg);
445 }
446
447 // Count the number of segments up to the common ancestor (relative path is what remains) ...
448 int lengthOfCommonAncestor = 0;
449 Iterator<Segment> thisIter = this.getNormalizedPath().iterator();
450 Iterator<Segment> toIter = startingPath.getNormalizedPath().iterator();
451 while (thisIter.hasNext() && toIter.hasNext()) {
452 Segment thisSeg = thisIter.next();
453 Segment toSeg = toIter.next();
454 if (thisSeg.equals(toSeg)) {
455 ++lengthOfCommonAncestor;
456 } else {
457 break;
458 }
459 }
460 // Create the relative path, starting with parent references to the common ancestor ...
461 int numberOfParentReferences = startingPath.size() - lengthOfCommonAncestor;
462 List<Segment> relativeSegments = new ArrayList<Segment>();
463 for (int i = 0; i != numberOfParentReferences; ++i) {
464 relativeSegments.add(Path.PARENT_SEGMENT);
465 }
466 // Add the segments of this path from the common ancestor ...
467 for (int i = lengthOfCommonAncestor; i < this.size(); ++i) {
468 relativeSegments.add(getSegment(i));
469 }
470 if (relativeSegments.isEmpty()) {
471 relativeSegments.add(Path.SELF_SEGMENT);
472 }
473 return new BasicPath(relativeSegments, false);
474 }
475
476 /**
477 * {@inheritDoc}
478 */
479 public Path resolve( Path relativePath ) {
480 CheckArg.isNotNull(relativePath, "relative path");
481 if (!this.isAbsolute()) {
482 String msg = GraphI18n.pathIsNotAbsolute.text(this);
483 throw new InvalidPathException(msg);
484 }
485 if (relativePath.isAbsolute()) {
486 String msg = GraphI18n.pathIsNotRelative.text(relativePath);
487 throw new InvalidPathException(msg);
488 }
489 // If the relative path is the self or parent reference ...
490 relativePath = relativePath.getNormalizedPath();
491 if (relativePath.size() == 1) {
492 Segment onlySegment = relativePath.getSegment(0);
493 if (onlySegment.isSelfReference()) return this;
494 if (onlySegment.isParentReference()) return this.getParent();
495 }
496 List<Segment> segments = new ArrayList<Segment>(this.size() + relativePath.size());
497 for (Segment segment : this) {
498 segments.add(segment);
499 }
500 for (Segment segment : relativePath) {
501 segments.add(segment);
502 }
503 return new BasicPath(segments, true).getNormalizedPath();
504 }
505
506 /**
507 * {@inheritDoc}
508 */
509 public Path resolveAgainst( Path absolutePath ) {
510 CheckArg.isNotNull(absolutePath, "absolute path");
511 return absolutePath.resolve(this);
512 }
513
514 /**
515 * {@inheritDoc}
516 */
517 public Path subpath( int beginIndex ) {
518 return subpath(beginIndex, size());
519 }
520
521 /**
522 * {@inheritDoc}
523 */
524 public Path subpath( int beginIndex,
525 int endIndex ) {
526 CheckArg.isNonNegative(beginIndex, "beginIndex");
527 CheckArg.isNonNegative(endIndex, "endIndex");
528 int size = size();
529 if (beginIndex == 0) {
530 if (endIndex == 0) return RootPath.INSTANCE;
531 if (endIndex == size) return this;
532 }
533 if (beginIndex >= size) {
534 throw new IndexOutOfBoundsException(
535 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToSize.text(beginIndex,
536 size));
537 }
538 if (beginIndex > endIndex) {
539 throw new IndexOutOfBoundsException(
540 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToEndingIndex.text(beginIndex,
541 endIndex));
542 }
543 // This reuses the same list, so it's pretty efficient ...
544 return new BasicPath(createSegmentsSubList(beginIndex, endIndex), this.isAbsolute());
545 }
546
547 protected List<Segment> createSegmentsSubList( int validBeginIndex,
548 int validEndIndex ) {
549 return this.getSegmentsList().subList(validBeginIndex, validEndIndex);
550 }
551
552 /**
553 * {@inheritDoc}
554 */
555 @Override
556 public int hashCode() {
557 if (hc == 0) {
558 int hashCode = 1;
559 for (Segment segment : this) {
560 hashCode = 31 * hashCode + segment.hashCode();
561 }
562 hc = hashCode;
563 }
564 return hc;
565 }
566
567 /**
568 * Method used by {@link AbstractPath#equals(Object)} implementation to quickly get an Iterator over the segments in the
569 * parent.
570 *
571 * @return the iterator over the segments; never null, but may not have any elements
572 */
573 protected abstract Iterator<Segment> getSegmentsOfParent();
574
575 /**
576 * {@inheritDoc}
577 */
578 @Override
579 public boolean equals( Object obj ) {
580 if (obj == this) return true;
581 if (obj instanceof Path) {
582 Path that = (Path)obj;
583 // First check whether the paths are roots ...
584 if (this.isRoot()) return that.isRoot();
585 else if (that.isRoot()) return false;
586 // Now check the hash code and size ...
587 if (this.hashCode() != that.hashCode()) return false;
588 if (this.size() != that.size()) return false;
589 // Check the last segments, since these will often differ anyway ...
590 if (!this.getLastSegment().equals(that.getLastSegment())) return false;
591 if (this.size() == 1) return true;
592 // Check the rest of the names ...
593 Iterator<Segment> thisIter = that instanceof AbstractPath ? this.getSegmentsOfParent() : this.iterator();
594 Iterator<Segment> thatIter = that instanceof AbstractPath ? ((AbstractPath)that).getSegmentsOfParent() : that.iterator();
595 while (thisIter.hasNext()) {
596 Segment thisSegment = thisIter.next();
597 Segment thatSegment = thatIter.next();
598 if (!thisSegment.equals(thatSegment)) return false;
599 }
600 return true;
601 }
602 return false;
603 }
604
605 /**
606 * {@inheritDoc}
607 */
608 public int compareTo( Path that ) {
609 if (this == that) return 0;
610 Iterator<Segment> thisIter = getSegmentsList().iterator();
611 Iterator<Segment> thatIter = that.iterator();
612 while (thisIter.hasNext() && thatIter.hasNext()) {
613 Segment thisSegment = thisIter.next();
614 Segment thatSegment = thatIter.next();
615 int diff = thisSegment.compareTo(thatSegment);
616 if (diff != 0) return diff;
617 }
618 if (thisIter.hasNext()) return 1;
619 if (thatIter.hasNext()) return -1;
620 return 0;
621 }
622
623 /**
624 * {@inheritDoc}
625 */
626 @Override
627 public String toString() {
628 return getString(Path.NO_OP_ENCODER);
629 }
630 }