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 SELF_PATH = new BasicPath(Collections.singletonList(Path.SELF_SEGMENT), false);
057
058 private final List<Segment> segments;
059 private final boolean absolute;
060 private final boolean normalized;
061 private transient String path;
062
063 /**
064 * @param segments the segments
065 * @param absolute true if this path is absolute, or false otherwise
066 */
067 public BasicPath( List<Segment> segments,
068 boolean absolute ) {
069 CheckArg.isNotNull(segments, "segments");
070 this.segments = segments.isEmpty() ? EMPTY_SEGMENTS : Collections.unmodifiableList(segments);
071 this.absolute = absolute;
072 this.normalized = isNormalized(this.segments);
073 }
074
075 protected boolean isNormalized( List<Segment> segments ) {
076 for (Segment segment : segments) {
077 if (segment.isSelfReference() || segment.isParentReference()) return false;
078 }
079 return true;
080 }
081
082 /**
083 * {@inheritDoc}
084 */
085 public Path getParent() {
086 if (this.isRoot()) return null;
087 if (this.segments.size() == 1) return ROOT;
088 return subpath(0, this.segments.size() - 1);
089 }
090
091 /**
092 * {@inheritDoc}
093 */
094 public Path getAncestor( int degree ) {
095 CheckArg.isNonNegative(degree, "degree");
096 if (degree == 0) return this;
097 if (this.isRoot()) return null;
098 int endIndex = this.segments.size() - degree;
099 if (endIndex < 0) {
100 String msg = GraphI18n.pathAncestorDegreeIsInvalid.text(this.getString(), Inflector.getInstance().ordinalize(degree));
101 throw new InvalidPathException(msg);
102 }
103 return subpath(0, endIndex);
104 }
105
106 /**
107 * {@inheritDoc}
108 */
109 public Path getCanonicalPath() {
110 if (!this.isAbsolute()) {
111 String msg = GraphI18n.pathIsNotAbsolute.text(this);
112 throw new InvalidPathException(msg);
113 }
114 if (this.isNormalized()) return this;
115 return this.getNormalizedPath();
116 }
117
118 /**
119 * {@inheritDoc}
120 */
121 public Path getCommonAncestor( Path that ) {
122 if (that == null) return null;
123 if (this.isRoot() || that.isRoot()) return ROOT;
124 Path normalizedPath = this.getNormalizedPath();
125 int lastIndex = 0;
126 Iterator<Segment> thisIter = normalizedPath.iterator();
127 Iterator<Segment> thatIter = that.getNormalizedPath().iterator();
128 while (thisIter.hasNext() && thatIter.hasNext()) {
129 Segment thisSeg = thisIter.next();
130 Segment thatSeg = thatIter.next();
131 if (thisSeg.equals(thatSeg)) {
132 ++lastIndex;
133 } else {
134 break;
135 }
136 }
137 if (lastIndex == 0) return ROOT;
138 return normalizedPath.subpath(0, lastIndex);
139 }
140
141 /**
142 * {@inheritDoc}
143 */
144 public Path.Segment getLastSegment() {
145 if (this.isRoot()) return null;
146 return this.segments.get(size() - 1);
147 }
148
149 /**
150 * {@inheritDoc}
151 */
152 public Path getNormalizedPath() {
153 if (this.isNormalized()) return this; // ROOT is normalized already
154 LinkedList<Segment> newSegments = new LinkedList<Segment>();
155 for (Segment segment : segments) {
156 if (segment.isSelfReference()) continue;
157 if (segment.isParentReference()) {
158 if (newSegments.isEmpty()) {
159 if (this.isAbsolute()) {
160 throw new InvalidPathException(CommonI18n.pathCannotBeNormalized.text(this));
161 }
162 } else if (!newSegments.getLast().isParentReference()) {
163 newSegments.removeLast();
164 continue;
165 }
166 }
167 newSegments.add(segment);
168 }
169 if (newSegments.isEmpty()) {
170 if (this.isAbsolute()) return ROOT;
171 // Otherwise relative and it had contained nothing but self references ...
172 return SELF_PATH;
173 }
174 return new BasicPath(newSegments, this.isAbsolute());
175 }
176
177 /**
178 * {@inheritDoc}
179 */
180 public Segment getSegment( int index ) {
181 return this.segments.get(index);
182 }
183
184 /**
185 * {@inheritDoc}
186 */
187 public Segment[] getSegmentsArray() {
188 return this.segments.toArray(new Path.Segment[this.segments.size()]);
189 }
190
191 /**
192 * {@inheritDoc}
193 */
194 public List<Segment> getSegmentsList() {
195 return this.segments;
196 }
197
198 /**
199 * {@inheritDoc}
200 */
201 public String getString() {
202 return doGetString(null, DEFAULT_ENCODER);
203 }
204
205 /**
206 * {@inheritDoc}
207 */
208 public String getString( TextEncoder encoder ) {
209 return doGetString(null, encoder);
210 }
211
212 /**
213 * {@inheritDoc}
214 */
215 public String getString( NamespaceRegistry namespaceRegistry ) {
216 CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
217 return doGetString(namespaceRegistry, null);
218 }
219
220 /**
221 * {@inheritDoc}
222 */
223 public String getString( NamespaceRegistry namespaceRegistry,
224 TextEncoder encoder ) {
225 CheckArg.isNotNull(namespaceRegistry, "namespaceRegistry");
226 return doGetString(namespaceRegistry, encoder);
227 }
228
229 /**
230 * Method that creates the string representation. This method works two different ways depending upon whether the namespace
231 * registry is provided.
232 *
233 * @param namespaceRegistry
234 * @param encoder
235 * @return this path as a string
236 */
237 protected String doGetString( NamespaceRegistry namespaceRegistry,
238 TextEncoder encoder ) {
239 if (encoder == null) encoder = DEFAULT_ENCODER;
240 if (encoder == DEFAULT_ENCODER && this.path != null) return this.path;
241
242 // Since the segments are immutable, this code need not be synchronized because concurrent threads
243 // may just compute the same value (with no harm done)
244 StringBuilder sb = new StringBuilder();
245 if (this.isAbsolute()) sb.append(DELIMITER);
246 boolean first = true;
247 for (Segment segment : this.segments) {
248 if (first) {
249 first = false;
250 } else {
251 sb.append(DELIMITER);
252 }
253 assert segment != null;
254 if (namespaceRegistry != null) {
255 sb.append(segment.getString(namespaceRegistry, encoder));
256 } else {
257 sb.append(segment.getString(encoder));
258 }
259 }
260 String result = sb.toString();
261 // Save the result to the internal string if this the default encoder is used.
262 // This is not synchronized, but it's okay
263 if (encoder == DEFAULT_ENCODER && this.path == null) this.path = result;
264 return result;
265 }
266
267 /**
268 * {@inheritDoc}
269 */
270 public boolean hasSameAncestor( Path that ) {
271 if (that == null) return false;
272 if (that.size() != this.size()) return false;
273 if (this.size() == 1) return false;
274 for (int i = this.size() - 2; i < 0; --i) {
275 Path.Segment thisSegment = this.getSegment(i);
276 Path.Segment thatSegment = that.getSegment(i);
277 if (!thisSegment.equals(thatSegment)) return false;
278 }
279 return true;
280 }
281
282 /**
283 * {@inheritDoc}
284 */
285 public boolean isAbsolute() {
286 return this.absolute;
287 }
288
289 /**
290 * {@inheritDoc}
291 */
292 public boolean isAncestorOf( Path decendant ) {
293 if (decendant == null) return false;
294 if (this == decendant) return false;
295 if (this.size() >= decendant.size()) return false;
296
297 Iterator<Path.Segment> thisIter = this.iterator();
298 Iterator<Path.Segment> thatIter = decendant.iterator();
299 while (thisIter.hasNext()) {
300 Path.Segment thisSeg = thisIter.next();
301 Path.Segment thatSeg = thatIter.next();
302 if (!thisSeg.equals(thatSeg)) return false;
303 }
304 return true;
305 }
306
307 /**
308 * {@inheritDoc}
309 *
310 * @see org.jboss.dna.graph.properties.Path#isAtOrBelow(org.jboss.dna.graph.properties.Path)
311 */
312 public boolean isAtOrBelow( Path other ) {
313 if (other == null) return false;
314 if (this == other) return true;
315 Iterator<Segment> thisIter = this.segments.iterator();
316 Iterator<Segment> thatIter = other.iterator();
317 while (thisIter.hasNext() && thatIter.hasNext()) {
318 if (!thisIter.next().equals(thatIter.next())) return false;
319 }
320 if (thatIter.hasNext()) return false; // The other still has segments, but this doesn't
321 return true;
322 }
323
324 /**
325 * {@inheritDoc}
326 *
327 * @see org.jboss.dna.graph.properties.Path#isAtOrAbove(org.jboss.dna.graph.properties.Path)
328 */
329 public boolean isAtOrAbove( Path other ) {
330 if (other == null) return false;
331 if (this == other) return true;
332 Iterator<Segment> thisIter = this.segments.iterator();
333 Iterator<Segment> thatIter = other.iterator();
334 while (thisIter.hasNext() && thatIter.hasNext()) {
335 if (!thisIter.next().equals(thatIter.next())) return false;
336 }
337 if (thisIter.hasNext()) return false; // This still has segments, but other doesn't
338 return true;
339 }
340
341 /**
342 * {@inheritDoc}
343 */
344 public boolean isDecendantOf( Path ancestor ) {
345 if (ancestor == null) return false;
346 return ancestor.isAncestorOf(this);
347 }
348
349 /**
350 * {@inheritDoc}
351 */
352 public boolean isNormalized() {
353 return this.normalized;
354 }
355
356 /**
357 * {@inheritDoc}
358 */
359 public boolean isRoot() {
360 return this == ROOT || this.segments.isEmpty();
361 }
362
363 /**
364 * {@inheritDoc}
365 */
366 public boolean isSameAs( Path other ) {
367 return other != null && this.compareTo(other) == 0;
368 }
369
370 /**
371 * {@inheritDoc}
372 */
373 public Iterator<Segment> iterator() {
374 return this.segments.iterator();
375 }
376
377 /**
378 * {@inheritDoc}
379 */
380 public Path relativeTo( Path startingPath ) {
381 CheckArg.isNotNull(startingPath, "to");
382 if (!this.isAbsolute()) {
383 String msg = GraphI18n.pathIsNotAbsolute.text(this);
384 throw new InvalidPathException(msg);
385 }
386 if (!startingPath.isAbsolute()) {
387 String msg = GraphI18n.pathIsNotAbsolute.text(startingPath);
388 throw new InvalidPathException(msg);
389 }
390
391 // Count the number of segments up to the common ancestor (relative path is what remains) ...
392 int lengthOfCommonAncestor = 0;
393 Iterator<Segment> thisIter = this.getNormalizedPath().iterator();
394 Iterator<Segment> toIter = startingPath.getNormalizedPath().iterator();
395 while (thisIter.hasNext() && toIter.hasNext()) {
396 Segment thisSeg = thisIter.next();
397 Segment toSeg = toIter.next();
398 if (thisSeg.equals(toSeg)) {
399 ++lengthOfCommonAncestor;
400 } else {
401 break;
402 }
403 }
404 // Create the relative path, starting with parent references to the common ancestor ...
405 int numberOfParentReferences = startingPath.size() - lengthOfCommonAncestor;
406 List<Segment> relativeSegments = new ArrayList<Segment>();
407 for (int i = 0; i != numberOfParentReferences; ++i) {
408 relativeSegments.add(Path.PARENT_SEGMENT);
409 }
410 // Add the segments of this path from the common ancestor ...
411 for (int i = lengthOfCommonAncestor; i < this.size(); ++i) {
412 relativeSegments.add(this.segments.get(i));
413 }
414 if (relativeSegments.isEmpty()) {
415 relativeSegments.add(Path.SELF_SEGMENT);
416 }
417 return new BasicPath(relativeSegments, false);
418 }
419
420 /**
421 * {@inheritDoc}
422 */
423 public Path resolve( Path relativePath ) {
424 CheckArg.isNotNull(relativePath, "relative path");
425 if (!this.isAbsolute()) {
426 String msg = GraphI18n.pathIsAlreadyAbsolute.text(this.path);
427 throw new InvalidPathException(msg);
428 }
429 if (relativePath.isAbsolute()) {
430 String msg = GraphI18n.pathIsNotRelative.text(relativePath);
431 throw new InvalidPathException(msg);
432 }
433 // If the relative path is the self or parent reference ...
434 relativePath = relativePath.getNormalizedPath();
435 if (relativePath.size() == 1) {
436 Segment onlySegment = relativePath.getSegment(0);
437 if (onlySegment.isSelfReference()) return this;
438 if (onlySegment.isParentReference()) return this.getParent();
439 }
440 List<Segment> segments = new ArrayList<Segment>(this.size() + relativePath.size());
441 segments.addAll(this.segments);
442 segments.addAll(relativePath.getSegmentsList());
443 return new BasicPath(segments, true).getNormalizedPath();
444 }
445
446 /**
447 * {@inheritDoc}
448 */
449 public Path resolveAgainst( Path absolutePath ) {
450 CheckArg.isNotNull(absolutePath, "absolute path");
451 return absolutePath.resolve(this);
452 }
453
454 /**
455 * {@inheritDoc}
456 */
457 public int size() {
458 return this.segments.size();
459 }
460
461 /**
462 * {@inheritDoc}
463 */
464 public Path subpath( int beginIndex ) {
465 if (beginIndex == 0) return this;
466 int size = size();
467 if (beginIndex >= size) {
468 throw new IndexOutOfBoundsException(GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToSize.text(beginIndex,
469 size));
470 }
471 if (size == 0) return ROOT;
472 return new BasicPath(this.segments.subList(beginIndex, size), this.isAbsolute());
473 }
474
475 /**
476 * {@inheritDoc}
477 */
478 public Path subpath( int beginIndex,
479 int endIndex ) {
480 int size = size();
481 if (beginIndex == 0) {
482 if (endIndex == 0) return ROOT;
483 if (endIndex == size) return this;
484 }
485 if (beginIndex >= size) {
486 throw new IndexOutOfBoundsException(GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToSize.text(beginIndex,
487 size));
488 }
489 if (beginIndex > endIndex) {
490 throw new IndexOutOfBoundsException(
491 GraphI18n.unableToCreateSubpathBeginIndexGreaterThanOrEqualToEndingIndex.text(beginIndex,
492 endIndex));
493 }
494 // This reuses the same list, so it's pretty efficient ...
495 return new BasicPath(this.segments.subList(beginIndex, endIndex), this.isAbsolute());
496 }
497
498 /**
499 * {@inheritDoc}
500 */
501 @Override
502 public int hashCode() {
503 return this.segments.hashCode();
504 }
505
506 /**
507 * {@inheritDoc}
508 */
509 @Override
510 public boolean equals( Object obj ) {
511 if (obj == this) return true;
512 if (obj instanceof Path) {
513 Path that = (Path)obj;
514 return this.segments.equals(that.getSegmentsList());
515 }
516 return false;
517 }
518
519 /**
520 * {@inheritDoc}
521 */
522 public int compareTo( Path that ) {
523 if (this == that) return 0;
524 Iterator<Segment> thisIter = this.segments.iterator();
525 Iterator<Segment> thatIter = that.iterator();
526 while (thisIter.hasNext() && thatIter.hasNext()) {
527 Segment thisSegment = thisIter.next();
528 Segment thatSegment = thatIter.next();
529 int diff = thisSegment.compareTo(thatSegment);
530 if (diff != 0) return diff;
531 }
532 if (thisIter.hasNext()) return 1;
533 if (thatIter.hasNext()) return -1;
534 return 0;
535 }
536
537 /**
538 * {@inheritDoc}
539 */
540 @Override
541 public String toString() {
542 return getString(Path.URL_ENCODER);
543 }
544
545 }