yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/YangInstanceIdentifier.java

   1 /*
   2  * Copyright (c) 2014 Cisco Systems, Inc. and others. All rights reserved.
   3  * This program and the accompanying materials are made available under the
   4  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   5  * and is available at http://www.eclipse.org/legal/epl-v10.html
   6  */
   7 package org.opendaylight.yangtools.yang.data.api;
   8
   9 import com.google.common.base.Optional;
  10 import com.google.common.base.Preconditions;
  11 import com.google.common.collect.ImmutableList;
  12 import com.google.common.collect.ImmutableMap;
  13 import com.google.common.collect.ImmutableSet;
  14 import com.google.common.collect.Iterables;
  15 import com.google.common.collect.Lists;
  16 import java.io.IOException;
  17 import java.io.ObjectInputStream;
  18 import java.io.ObjectOutputStream;
  19 import java.io.ObjectStreamException;
  20 import java.io.Serializable;
  21 import java.lang.reflect.Array;
  22 import java.lang.reflect.Field;
  23 import java.util.ArrayList;
  24 import java.util.Arrays;
  25 import java.util.Collections;
  26 import java.util.Iterator;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Map.Entry;
  30 import java.util.Objects;
  31 import java.util.Set;
  32 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  33 import org.opendaylight.yangtools.concepts.Builder;
  34 import org.opendaylight.yangtools.concepts.Immutable;
  35 import org.opendaylight.yangtools.concepts.Path;
  36 import org.opendaylight.yangtools.util.HashCodeBuilder;
  37 import org.opendaylight.yangtools.yang.common.QName;
  38 import org.opendaylight.yangtools.yang.common.QNameModule;
  39 import org.opendaylight.yangtools.yang.data.api.schema.LeafSetEntryNode;
  40
  41 /**
  42  * Unique identifier of a particular node instance in the data tree.
  43  *
  44  * <p>
  45  * Java representation of YANG Built-in type <code>instance-identifier</code>,
  46  * which conceptually is XPath expression minimized to uniquely identify element
  47  * in data tree which conforms to constraints maintained by YANG Model,
  48  * effectively this makes Instance Identifier a path to element in data tree.
  49  * <p>
  50  * Constraints put in YANG specification on instance-identifier allowed it to be
  51  * effectively represented in Java and it's evaluation does not require
  52  * full-blown XPath processor.
  53  * <p>
  54  * <h3>Path Arguments</h3>
  55  * Path to the node represented in instance identifier consists of
  56  * {@link PathArgument} which carries necessary information to uniquely identify
  57  * node on particular level in the subtree.
  58  * <p>
  59  * <ul>
  60  * <li>{@link NodeIdentifier} - Identifier of node, which has cardinality
  61  * <code>0..1</code> in particular subtree in data tree.</li>
  62  * <li>{@link NodeIdentifierWithPredicates} - Identifier of node (list item),
  63  * which has cardinality <code>0..n</code>.</li>
  64  * <li>{@link NodeWithValue} - Identifier of instance <code>leaf</code> node or
  65  * <code>leaf-list</code> node.</li>
  66  * <li>{@link AugmentationIdentifier} - Identifier of instance of
  67  * <code>augmentation</code> node.</li>
  68  * </ul>
  69  *
  70  *
  71  * @see <a href="http://tools.ietf.org/html/rfc6020#section-9.13">RFC6020</a>
  72  */
  73 public final class YangInstanceIdentifier implements Path<YangInstanceIdentifier>, Immutable, Serializable {
  74     @SuppressWarnings("rawtypes")
  75     private static final AtomicReferenceFieldUpdater<YangInstanceIdentifier, ImmutableList> LEGACYPATH_UPDATER =
  76             AtomicReferenceFieldUpdater.newUpdater(YangInstanceIdentifier.class, ImmutableList.class, "legacyPath");
  77     private static final AtomicReferenceFieldUpdater<YangInstanceIdentifier, String> TOSTRINGCACHE_UPDATER =
  78             AtomicReferenceFieldUpdater.newUpdater(YangInstanceIdentifier.class, String.class, "toStringCache");
  79     private static final YangInstanceIdentifier EMPTY = trustedCreate(Collections.<PathArgument>emptyList());
  80     private static final Field PATHARGUMENTS_FIELD;
  81
  82     private static final long serialVersionUID = 3L;
  83     private transient final Iterable<PathArgument> pathArguments;
  84     private final int hash;
  85
  86     private volatile ImmutableList<PathArgument> legacyPath = null;
  87     private transient volatile String toStringCache = null;
  88
  89     static {
  90         final Field f;
  91         try {
  92             f = YangInstanceIdentifier.class.getDeclaredField("pathArguments");
  93         } catch (NoSuchFieldException | SecurityException e) {
  94             throw new ExceptionInInitializerError(e);
  95         }
  96         f.setAccessible(true);
  97
  98         PATHARGUMENTS_FIELD = f;
  99     }
 100
 101     private final ImmutableList<PathArgument> getLegacyPath() {
 102         // Temporary variable saves a volatile read
 103         ImmutableList<PathArgument> ret = legacyPath;
 104         if (ret == null) {
 105             // We could have used a synchronized block, but the window is quite
 106             // small and worst that can happen is duplicate object construction.
 107             ret = ImmutableList.copyOf(pathArguments);
 108             LEGACYPATH_UPDATER.lazySet(this, ret);
 109         }
 110
 111         return ret;
 112     }
 113
 114     /**
 115      * Returns a list of path arguments.
 116      *
 117      * @deprecated Use {@link #getPathArguments()} instead.
 118      * @return Immutable list of path arguments.
 119      */
 120     @Deprecated
 121     public List<PathArgument> getPath() {
 122         return getLegacyPath();
 123     }
 124
 125     /**
 126      * Returns an ordered iteration of path arguments.
 127      *
 128      * @return Immutable iteration of path arguments.
 129      */
 130     public Iterable<PathArgument> getPathArguments() {
 131         return pathArguments;
 132     }
 133
 134     /**
 135      * Returns an iterable of path arguments in reverse order. This is useful
 136      * when walking up a tree organized this way.
 137      *
 138      * @return Immutable iterable of path arguments in reverse order.
 139      */
 140     public Iterable<PathArgument> getReversePathArguments() {
 141         return getLegacyPath().reverse();
 142     }
 143
 144     /**
 145      * Returns the last PathArgument. This is equivalent of iterating
 146      * to the last element of the iterable returned by {@link #getPathArguments()}.
 147      *
 148      * @return The last past argument, or null if there are no PathArguments.
 149      */
 150     public PathArgument getLastPathArgument() {
 151         return Iterables.getFirst(getReversePathArguments(), null);
 152     }
 153
 154     private YangInstanceIdentifier(final Iterable<PathArgument> path, final int hash) {
 155         this.pathArguments = Preconditions.checkNotNull(path, "path must not be null.");
 156         this.hash = hash;
 157     }
 158
 159     private static final YangInstanceIdentifier trustedCreate(final Iterable<PathArgument> path) {
 160         final HashCodeBuilder<PathArgument> hash = new HashCodeBuilder<>();
 161         for (PathArgument a : path) {
 162             hash.addArgument(a);
 163         }
 164
 165         return new YangInstanceIdentifier(path, hash.build());
 166     }
 167
 168     public static final YangInstanceIdentifier create(final Iterable<? extends PathArgument> path) {
 169         if (Iterables.isEmpty(path)) {
 170             return EMPTY;
 171         }
 172
 173         return trustedCreate(ImmutableList.copyOf(path));
 174     }
 175
 176     public static final YangInstanceIdentifier create(final PathArgument... path) {
 177         // We are forcing a copy, since we cannot trust the user
 178         return create(Arrays.asList(path));
 179     }
 180
 181     @Override
 182     public int hashCode() {
 183         /*
 184          * The caching is safe, since the object contract requires
 185          * immutability of the object and all objects referenced from this
 186          * object.
 187          * Used lists, maps are immutable. Path Arguments (elements) are also
 188          * immutable, since the PathArgument contract requires immutability.
 189          */
 190         return hash;
 191     }
 192
 193     @Override
 194     public boolean equals(final Object obj) {
 195         if (this == obj) {
 196             return true;
 197         }
 198         if (obj == null) {
 199             return false;
 200         }
 201         if (getClass() != obj.getClass()) {
 202             return false;
 203         }
 204         YangInstanceIdentifier other = (YangInstanceIdentifier) obj;
 205         if (this.hashCode() != obj.hashCode()) {
 206             return false;
 207         }
 208         return Iterables.elementsEqual(pathArguments, other.pathArguments);
 209     }
 210
 211     /**
 212      * Constructs a new Instance Identifier with new {@link NodeIdentifier} added to the end of path arguments
 213      *
 214      * @param name QName of {@link NodeIdentifier}
 215      * @return Instance Identifier with additional path argument added to the end.
 216      */
 217     public YangInstanceIdentifier node(final QName name) {
 218         return node(new NodeIdentifier(name));
 219     }
 220
 221     /**
 222      *
 223      * Constructs a new Instance Identifier with new {@link PathArgument} added to the end of path arguments
 224      *
 225      * @param arg Path argument which should be added to the end
 226      * @return Instance Identifier with additional path argument added to the end.
 227      */
 228     public YangInstanceIdentifier node(final PathArgument arg) {
 229         return new YangInstanceIdentifier(Iterables.concat(pathArguments, Collections.singleton(arg)), HashCodeBuilder.nextHashCode(hash, arg));
 230     }
 231
 232     /**
 233      * Get the relative path from an ancestor. This method attempts to perform
 234      * the reverse of concatenating a base (ancestor) and a path.
 235      *
 236      * @param ancestor
 237      *            Ancestor against which the relative path should be calculated
 238      * @return This object's relative path from parent, or Optional.absent() if
 239      *         the specified parent is not in fact an ancestor of this object.
 240      */
 241     public Optional<YangInstanceIdentifier> relativeTo(final YangInstanceIdentifier ancestor) {
 242         final Iterator<?> lit = pathArguments.iterator();
 243         final Iterator<?> oit = ancestor.pathArguments.iterator();
 244         int common = 0;
 245
 246         while (oit.hasNext()) {
 247             // Ancestor is not really an ancestor
 248             if (!lit.hasNext() || !lit.next().equals(oit.next())) {
 249                 return Optional.absent();
 250             }
 251
 252             ++common;
 253         }
 254
 255         if (common == 0) {
 256             return Optional.of(this);
 257         }
 258         if (!lit.hasNext()) {
 259             return Optional.of(EMPTY);
 260         }
 261         return Optional.of(trustedCreate(Iterables.skip(pathArguments, common)));
 262     }
 263
 264     private static int hashCode(final Object value) {
 265         if (value == null) {
 266             return 0;
 267         }
 268
 269         if (value.getClass().equals(byte[].class)) {
 270             return Arrays.hashCode((byte[]) value);
 271         }
 272
 273         if (value.getClass().isArray()) {
 274             int hash = 0;
 275             int length = Array.getLength(value);
 276             for (int i = 0; i < length; i++) {
 277                 hash += Objects.hashCode(Array.get(value, i));
 278             }
 279
 280             return hash;
 281         }
 282
 283         return Objects.hashCode(value);
 284     }
 285
 286     // Static factories & helpers
 287
 288     /**
 289      *
 290      * Returns a new InstanceIdentifier with only one path argument of type {@link NodeIdentifier} with supplied QName
 291      *
 292      * @param name QName of first node identifier
 293      * @return Instance Identifier with only one path argument of type {@link NodeIdentifier}
 294      */
 295     public static YangInstanceIdentifier of(final QName name) {
 296         return create(new NodeIdentifier(name));
 297     }
 298
 299     /**
 300      *
 301      * Returns new builder for InstanceIdentifier with empty path arguments.
 302      *
 303      * @return new builder for InstanceIdentifier with empty path arguments.
 304      */
 305     static public InstanceIdentifierBuilder builder() {
 306         return new BuilderImpl();
 307     }
 308
 309     /**
 310      *
 311      * Returns new builder for InstanceIdentifier with path arguments copied from original instance identifier.
 312      *
 313      * @param origin Instace Identifier from which path arguments are copied.
 314      * @return new builder for InstanceIdentifier with path arguments copied from original instance identifier.
 315      */
 316     static public InstanceIdentifierBuilder builder(final YangInstanceIdentifier origin) {
 317         return new BuilderImpl(origin.getPathArguments(), origin.hashCode());
 318     }
 319
 320     /**
 321      * Path argument / component of InstanceIdentifier
 322      *
 323      * Path argument uniquely identifies node in data tree on particular
 324      * level.
 325      * <p>
 326      * This interface itself is used as common parent for actual
 327      * path arguments types and should not be implemented by user code.
 328      * <p>
 329      * Path arguments SHOULD contain only minimum of information
 330      * required to uniquely identify node on particular subtree level.
 331      *
 332      * For actual path arguments types see:
 333      * <ul>
 334      * <li>{@link NodeIdentifier} - Identifier of container or leaf
 335      * <li>{@link NodeIdentifierWithPredicates} - Identifier of list entries, which have key defined
 336      * <li>{@link AugmentationIdentifier} - Identifier of augmentation
 337      * <li>{@link NodeWithValue} - Identifier of leaf-list entry
 338      * </ul>
 339      */
 340     public interface PathArgument extends Comparable<PathArgument>, Immutable, Serializable {
 341         /**
 342          * If applicable returns unique QName of data node as defined in YANG
 343          * Schema.
 344          *
 345          * This method may return null, if the corresponding schema node, does
 346          * not have QName associated, such as in cases of augmentations.
 347          *
 348          * @return Node type
 349          */
 350         QName getNodeType();
 351
 352         /**
 353          * Return the string representation of this object for use in context
 354          * provided by a previous object. This method can be implemented in
 355          * terms of {@link #toString()}, but implementations are encourage to
 356          * reuse any context already emitted by the previous object.
 357          *
 358          * @param previous Previous path argument
 359          * @return String representation
 360          */
 361         String toRelativeString(PathArgument previous);
 362     }
 363
 364     private static abstract class AbstractPathArgument implements PathArgument {
 365         private static final AtomicReferenceFieldUpdater<AbstractPathArgument, Integer> HASH_UPDATER =
 366                 AtomicReferenceFieldUpdater.newUpdater(AbstractPathArgument.class, Integer.class, "hash");
 367         private static final long serialVersionUID = -4546547994250849340L;
 368         private final QName nodeType;
 369         private volatile transient Integer hash = null;
 370
 371         protected AbstractPathArgument(final QName nodeType) {
 372             this.nodeType = Preconditions.checkNotNull(nodeType);
 373         }
 374
 375         @Override
 376         public final QName getNodeType() {
 377             return nodeType;
 378         }
 379
 380         @Override
 381         public int compareTo(final PathArgument o) {
 382             return nodeType.compareTo(o.getNodeType());
 383         }
 384
 385         protected int hashCodeImpl() {
 386             return 31 + getNodeType().hashCode();
 387         }
 388
 389         @Override
 390         public final int hashCode() {
 391             Integer ret = hash;
 392             if (ret == null) {
 393                 ret = hashCodeImpl();
 394                 HASH_UPDATER.lazySet(this, ret);
 395             }
 396
 397             return ret;
 398         }
 399
 400         @Override
 401         public boolean equals(final Object obj) {
 402             if (this == obj) {
 403                 return true;
 404             }
 405             if (obj == null || this.getClass() != obj.getClass()) {
 406                 return false;
 407             }
 408
 409             return getNodeType().equals(((AbstractPathArgument)obj).getNodeType());
 410         }
 411
 412         @Override
 413         public String toString() {
 414             return getNodeType().toString();
 415         }
 416
 417         @Override
 418         public String toRelativeString(final PathArgument previous) {
 419             if (previous instanceof AbstractPathArgument) {
 420                 final QNameModule mod = ((AbstractPathArgument)previous).getNodeType().getModule();
 421                 if (getNodeType().getModule().equals(mod)) {
 422                     return getNodeType().getLocalName();
 423                 }
 424             }
 425
 426             return getNodeType().toString();
 427         }
 428     }
 429
 430     /**
 431      * Fluent Builder of Instance Identifier instances
 432      */
 433     public interface InstanceIdentifierBuilder extends Builder<YangInstanceIdentifier> {
 434         /**
 435          * Adds {@link NodeIdentifier} with supplied QName to path arguments of resulting instance identifier.
 436          *
 437          * @param nodeType QName of {@link NodeIdentifier} which will be added
 438          * @return this builder
 439          */
 440         InstanceIdentifierBuilder node(QName nodeType);
 441
 442         /**
 443          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key values to path arguments of resulting instance identifier.
 444          *
 445          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
 446          * @param keyValues Map of key components and their respective values for {@link NodeIdentifierWithPredicates}
 447          * @return this builder
 448          */
 449         InstanceIdentifierBuilder nodeWithKey(QName nodeType, Map<QName, Object> keyValues);
 450
 451         /**
 452          * Adds {@link NodeIdentifierWithPredicates} with supplied QName and key, value.
 453          *
 454          * @param nodeType QName of {@link NodeIdentifierWithPredicates} which will be added
 455          * @param key QName of key which will be added
 456          * @param value value of key which will be added
 457          * @return this builder
 458          */
 459         InstanceIdentifierBuilder nodeWithKey(QName nodeType, QName key, Object value);
 460
 461         /**
 462          *
 463          * Builds an {@link YangInstanceIdentifier} with path arguments from this builder
 464          *
 465          * @return {@link YangInstanceIdentifier}
 466          */
 467         @Override
 468         YangInstanceIdentifier build();
 469
 470         /*
 471          * @deprecated use #build()
 472          */
 473         @Deprecated
 474         YangInstanceIdentifier toInstance();
 475     }
 476
 477     /**
 478      * Simple path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.ContainerNode} or
 479      * {@link org.opendaylight.yangtools.yang.data.api.schema.LeafNode} leaf in particular subtree.
 480      */
 481     public static final class NodeIdentifier extends AbstractPathArgument {
 482         private static final long serialVersionUID = -2255888212390871347L;
 483
 484         public NodeIdentifier(final QName node) {
 485             super(node);
 486         }
 487     }
 488
 489     /**
 490      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode} leaf
 491      * overall data tree.
 492      */
 493     public static final class NodeIdentifierWithPredicates extends AbstractPathArgument {
 494         private static final long serialVersionUID = -4787195606494761540L;
 495
 496         private final Map<QName, Object> keyValues;
 497
 498         public NodeIdentifierWithPredicates(final QName node, final Map<QName, Object> keyValues) {
 499             super(node);
 500             this.keyValues = ImmutableMap.copyOf(keyValues);
 501         }
 502
 503         public NodeIdentifierWithPredicates(final QName node, final QName key, final Object value) {
 504             this(node, ImmutableMap.of(key, value));
 505         }
 506
 507         public Map<QName, Object> getKeyValues() {
 508             return keyValues;
 509         }
 510
 511         @Override
 512         protected int hashCodeImpl() {
 513             final int prime = 31;
 514             int result = super.hashCodeImpl();
 515             result = prime * result;
 516
 517             for (Entry<QName, Object> entry : keyValues.entrySet()) {
 518                 result += Objects.hashCode(entry.getKey()) + YangInstanceIdentifier.hashCode(entry.getValue());
 519             }
 520             return result;
 521         }
 522
 523         @Override
 524         public boolean equals(final Object obj) {
 525             if (!super.equals(obj)) {
 526                 return false;
 527             }
 528
 529             final Map<QName, Object> otherKeyValues = ((NodeIdentifierWithPredicates) obj).keyValues;
 530             if (keyValues.size() != otherKeyValues.size()) {
 531                 return false;
 532             }
 533
 534             for (Entry<QName, Object> entry : keyValues.entrySet()) {
 535                 if (!otherKeyValues.containsKey(entry.getKey())
 536                         || !Objects.deepEquals(entry.getValue(), otherKeyValues.get(entry.getKey()))) {
 537
 538                     return false;
 539                 }
 540             }
 541
 542             return true;
 543         }
 544
 545         @Override
 546         public String toString() {
 547             return super.toString() + '[' + keyValues + ']';
 548         }
 549
 550         @Override
 551         public String toRelativeString(final PathArgument previous) {
 552             return super.toRelativeString(previous) + '[' + keyValues + ']';
 553         }
 554     }
 555
 556     /**
 557      * Simple path argument identifying a {@link LeafSetEntryNode} leaf
 558      * overall data tree.
 559      */
 560     public static final class NodeWithValue extends AbstractPathArgument {
 561         private static final long serialVersionUID = -3637456085341738431L;
 562
 563         private final Object value;
 564
 565         public NodeWithValue(final QName node, final Object value) {
 566             super(node);
 567             this.value = value;
 568         }
 569
 570         public Object getValue() {
 571             return value;
 572         }
 573
 574         @Override
 575         protected int hashCodeImpl() {
 576             final int prime = 31;
 577             int result = super.hashCodeImpl();
 578             result = prime * result + ((value == null) ? 0 : YangInstanceIdentifier.hashCode(value));
 579             return result;
 580         }
 581
 582         @Override
 583         public boolean equals(final Object obj) {
 584             if (!super.equals(obj)) {
 585                 return false;
 586             }
 587             final NodeWithValue other = (NodeWithValue) obj;
 588             return Objects.deepEquals(value, other.value);
 589         }
 590
 591         @Override
 592         public String toString() {
 593             return super.toString() + '[' + value + ']';
 594         }
 595
 596         @Override
 597         public String toRelativeString(final PathArgument previous) {
 598             return super.toRelativeString(previous) + '[' + value + ']';
 599         }
 600     }
 601
 602     /**
 603      * Composite path argument identifying a {@link org.opendaylight.yangtools.yang.data.api.schema.AugmentationNode} node in
 604      * particular subtree.
 605      *
 606      * Augmentation is uniquely identified by set of all possible child nodes.
 607      * This is possible
 608      * to identify instance of augmentation,
 609      * since RFC6020 states that <code>augment</code> that augment
 610      * statement must not add multiple nodes from same namespace
 611      * / module to the target node.
 612      *
 613      *
 614      * @see <a href="http://tools.ietf.org/html/rfc6020#section-7.15">RFC6020</a>
 615      */
 616     public static final class AugmentationIdentifier implements PathArgument {
 617         private static final long serialVersionUID = -8122335594681936939L;
 618         private final ImmutableSet<QName> childNames;
 619
 620         @Override
 621         public QName getNodeType() {
 622             // This should rather throw exception than return always null
 623             throw new UnsupportedOperationException("Augmentation node has no QName");
 624         }
 625
 626         /**
 627          *
 628          * Construct new augmentation identifier using supplied set of possible
 629          * child nodes
 630          *
 631          * @param childNames
 632          *            Set of possible child nodes.
 633          */
 634         public AugmentationIdentifier(final Set<QName> childNames) {
 635             this.childNames = ImmutableSet.copyOf(childNames);
 636         }
 637
 638         /**
 639          * Returns set of all possible child nodes
 640          *
 641          * @return set of all possible child nodes.
 642          */
 643         public Set<QName> getPossibleChildNames() {
 644             return childNames;
 645         }
 646
 647         @Override
 648         public String toString() {
 649             final StringBuffer sb = new StringBuffer("AugmentationIdentifier{");
 650             sb.append("childNames=").append(childNames).append('}');
 651             return sb.toString();
 652         }
 653
 654         @Override
 655         public String toRelativeString(final PathArgument previous) {
 656             return toString();
 657         }
 658
 659         @Override
 660         public boolean equals(final Object o) {
 661             if (this == o) {
 662                 return true;
 663             }
 664             if (!(o instanceof AugmentationIdentifier)) {
 665                 return false;
 666             }
 667
 668             AugmentationIdentifier that = (AugmentationIdentifier) o;
 669             return childNames.equals(that.childNames);
 670         }
 671
 672         @Override
 673         public int hashCode() {
 674             return childNames.hashCode();
 675         }
 676
 677         @Override
 678         public int compareTo(final PathArgument o) {
 679             if (!(o instanceof AugmentationIdentifier)) {
 680                 return -1;
 681             }
 682             AugmentationIdentifier other = (AugmentationIdentifier) o;
 683             Set<QName> otherChildNames = other.getPossibleChildNames();
 684             int thisSize = childNames.size();
 685             int otherSize = otherChildNames.size();
 686             if (thisSize == otherSize) {
 687                 Iterator<QName> otherIterator = otherChildNames.iterator();
 688                 for (QName name : childNames) {
 689                     int c = name.compareTo(otherIterator.next());
 690                     if (c != 0) {
 691                         return c;
 692                     }
 693                 }
 694                 return 0;
 695             } else if (thisSize < otherSize) {
 696                 return 1;
 697             } else {
 698                 return -1;
 699             }
 700         }
 701     }
 702
 703     private static class BuilderImpl implements InstanceIdentifierBuilder {
 704         private final HashCodeBuilder<PathArgument> hash;
 705         private final List<PathArgument> path;
 706
 707         public BuilderImpl() {
 708             this.hash = new HashCodeBuilder<>();
 709             this.path = new ArrayList<>();
 710         }
 711
 712         public BuilderImpl(final Iterable<PathArgument> prefix, final int hash) {
 713             this.path = Lists.newArrayList(prefix);
 714             this.hash = new HashCodeBuilder<>(hash);
 715         }
 716
 717         @Override
 718         public InstanceIdentifierBuilder node(final QName nodeType) {
 719             final PathArgument arg = new NodeIdentifier(nodeType);
 720             path.add(arg);
 721             hash.addArgument(arg);
 722             return this;
 723         }
 724
 725         @Override
 726         public InstanceIdentifierBuilder nodeWithKey(final QName nodeType, final QName key, final Object value) {
 727             final PathArgument arg = new NodeIdentifierWithPredicates(nodeType, key, value);
 728             path.add(arg);
 729             hash.addArgument(arg);
 730             return this;
 731         }
 732
 733         @Override
 734         public InstanceIdentifierBuilder nodeWithKey(final QName nodeType, final Map<QName, Object> keyValues) {
 735             final PathArgument arg = new NodeIdentifierWithPredicates(nodeType, keyValues);
 736             path.add(arg);
 737             hash.addArgument(arg);
 738             return this;
 739         }
 740
 741         @Override
 742         @Deprecated
 743         public YangInstanceIdentifier toInstance() {
 744             return build();
 745         }
 746
 747         @Override
 748         public YangInstanceIdentifier build() {
 749             return new YangInstanceIdentifier(ImmutableList.copyOf(path), hash.build());
 750         }
 751     }
 752
 753     @Override
 754     public boolean contains(final YangInstanceIdentifier other) {
 755         Preconditions.checkArgument(other != null, "other should not be null");
 756
 757         final Iterator<?> lit = pathArguments.iterator();
 758         final Iterator<?> oit = other.pathArguments.iterator();
 759
 760         while (lit.hasNext()) {
 761             if (!oit.hasNext()) {
 762                 return false;
 763             }
 764
 765             if (!lit.next().equals(oit.next())) {
 766                 return false;
 767             }
 768         }
 769
 770         return true;
 771     }
 772
 773     @Override
 774     public String toString() {
 775         /*
 776          * The toStringCache is safe, since the object contract requires
 777          * immutability of the object and all objects referenced from this
 778          * object.
 779          * Used lists, maps are immutable. Path Arguments (elements) are also
 780          * immutable, since the PathArgument contract requires immutability.
 781          * The cache is thread-safe - if multiple computations occurs at the
 782          * same time, cache will be overwritten with same result.
 783          */
 784         String ret = toStringCache;
 785         if (ret == null) {
 786             final StringBuilder builder = new StringBuilder("/");
 787             PathArgument prev = null;
 788             for (PathArgument argument : getPathArguments()) {
 789                 if (prev != null) {
 790                     builder.append('/');
 791                 }
 792                 builder.append(argument.toRelativeString(prev));
 793                 prev = argument;
 794             }
 795
 796             ret = builder.toString();
 797             TOSTRINGCACHE_UPDATER.lazySet(this, ret);
 798         }
 799         return ret;
 800     }
 801
 802     private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
 803         inputStream.defaultReadObject();
 804
 805         try {
 806             PATHARGUMENTS_FIELD.set(this, legacyPath);
 807         } catch (IllegalArgumentException | IllegalAccessException e) {
 808             throw new IOException(e);
 809         }
 810     }
 811
 812     private Object readResolve() throws ObjectStreamException {
 813         return legacyPath.isEmpty() ? EMPTY : this;
 814     }
 815
 816     private void writeObject(final ObjectOutputStream outputStream) throws IOException {
 817         /*
 818          * This may look strange, but what we are doing here is side-stepping the fact
 819          * that pathArguments is not generally serializable. We are forcing instantiation
 820          * of the legacy path, which is an ImmutableList (thus Serializable) and write
 821          * it out. The read path does the opposite -- it reads the legacyPath and then
 822          * uses invocation API to set the field.
 823          */
 824         getLegacyPath();
 825         outputStream.defaultWriteObject();
 826     }
 827 }