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