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