package org.apache.lucene.facet.taxonomy;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Serializable;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * A CategoryPath holds a sequence of string components, specifying the
 * hierarchical name of a category.
 * <P>
 * CategoryPath is designed to reduce the number of object allocations, in two
 * ways: First, it keeps the components internally in two arrays, rather than
 * keeping individual strings. Second, it allows reusing the same CategoryPath
 * object (which can be clear()ed and new components add()ed again) and of
 * add()'s parameter (which can be a reusable object, not just a string).
 * 
 * @lucene.experimental
 */
public class CategoryPath implements Serializable, Cloneable, Comparable<CategoryPath> {

  // A category path is a sequence of string components. It is kept
  // internally as one large character array "chars" with all the string
  // concatenated (without separators), and an array of integers "ends"
  // pointing to the/ end of each component. Both arrays may be larger
  // than actually in use. An additional integer, "ncomponents" specifies
  // how many components are actually set.
  // We use shorts instead of ints for "ends" to save a bit of space. This
  // means that our path lengths are limited to 32767 characters - which
  // should not be a problem in any realistic scenario.
  protected char[] chars;
  protected short[] ends;
  protected short ncomponents;

  /**
   * Return the number of components in the facet path. Note that this is
   * <I>not</I> the number of characters, but the number of components.
   */
  public short length() {
    return ncomponents;
  }

  /**
   * Trim the last components from the path.
   * 
   * @param nTrim
   *            Number of components to trim. If larger than the number of
   *            components this path has, the entire path will be cleared.
   */
  public void trim(int nTrim) {
    if (nTrim >= this.ncomponents) {
      clear();
    } else if (nTrim > 0) {
      this.ncomponents -= nTrim;
    }
  }

  /**
   * Returns the current character capacity of the CategoryPath. The character
   * capacity is the size of the internal buffer used to hold the characters
   * of all the path's components. When a component is added and the capacity
   * is not big enough, the buffer is automatically grown, and capacityChars()
   * increases.
   */
  public int capacityChars() {
    return chars.length;
  }

  /**
   * Returns the current component capacity of the CategoryPath. The component
   * capacity is the maximum number of components that the internal buffer can
   * currently hold. When a component is added beyond this capacity, the
   * buffer is automatically grown, and capacityComponents() increases.
   */
  public int capacityComponents() {
    return ends.length;
  }

  /**
   * Construct a new empty CategoryPath object. CategoryPath objects are meant
   * to be reused, by add()ing components, and later clear()ing, and add()ing
   * components again. The CategoryPath object is created with a buffer
   * pre-allocated for a given number of characters and components, but the
   * buffer will grow as necessary (see {@link #capacityChars()} and
   * {@link #capacityComponents()}).
   */
  public CategoryPath(int capacityChars, int capacityComponents) {
    ncomponents = 0;
    chars = new char[capacityChars];
    ends = new short[capacityComponents];
  }

  /**
   * Create an empty CategoryPath object. Equivalent to the constructor
   * {@link #CategoryPath(int, int)} with the two initial-capacity arguments
   * set to zero.
   */
  public CategoryPath() {
    this(0, 0);
  }

  /**
   * Add the given component to the end of the path.
   * <P>
   * Note that when a String object is passed to this method, a reference to
   * it is not saved (rather, its content is copied), which will lead to that
   * String object being gc'ed. To reduce the number of garbage objects, you
   * can pass a mutable CharBuffer instead of an immutable String to this
   * method.
   */
  public void add(CharSequence component) {
    // Set the new end, increasing the "ends" array sizes if necessary:
    if (ncomponents >= ends.length) {
      short[] newends = new short[(ends.length + 1) * 2];
      System.arraycopy(ends, 0, newends, 0, ends.length);
      ends = newends;
    }
    short prevend = (ncomponents == 0) ? 0 : ends[ncomponents - 1];
    int cmplen = component.length();
    ends[ncomponents] = (short) (prevend + cmplen);

    // Copy the new component's characters, increasing the "chars" array
    // sizes if necessary:
    if (ends[ncomponents] > chars.length) {
      char[] newchars = new char[ends[ncomponents] * 2];
      System.arraycopy(chars, 0, newchars, 0, chars.length);
      chars = newchars;
    }
    for (int i = 0; i < cmplen; i++) {
      chars[prevend++] = component.charAt(i);
    }

    ncomponents++;
  }

  /**
   * Empty the CategoryPath object, so that it has zero components. The
   * capacity of the object (see {@link #capacityChars()} and
   * {@link #capacityComponents()}) is not reduced, so that the object can be
   * reused without frequent reallocations.
   */
  public void clear() {
    ncomponents = 0;
  }

  /**
   * Build a string representation of the path, with its components separated
   * by the given delimiter character. The resulting string is appended to a
   * given Appendable, e.g., a StringBuilder, CharBuffer or Writer.
   * <P>
   * Note that the two cases of zero components and one component with zero
   * length produce indistinguishable results (both of them append nothing).
   * This is normally not a problem, because components should not normally
   * have zero lengths.
   * <P>
   * An IOException can be thrown if the given Appendable's append() throws
   * this exception.
   */
  public void appendTo(Appendable out, char delimiter) throws IOException {
    if (ncomponents == 0) {
      return; // just append nothing...
    }
    for (int i = 0; i < ends[0]; i++) {
      out.append(chars[i]);
    }
    for (int j = 1; j < ncomponents; j++) {
      out.append(delimiter);
      for (int i = ends[j - 1]; i < ends[j]; i++) {
        out.append(chars[i]);
      }
    }
  }

  /**
   * like {@link #appendTo(Appendable, char)}, but takes only a prefix of the
   * path, rather than the whole path.
   * <P>
   * If the given prefix length is negative or bigger than the path's actual
   * length, the whole path is taken.
   */
  public void appendTo(Appendable out, char delimiter, int prefixLen)
      throws IOException {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    if (prefixLen == 0) {
      return; // just append nothing...
    }
    for (int i = 0; i < ends[0]; i++) {
      out.append(chars[i]);
    }
    for (int j = 1; j < prefixLen; j++) {
      out.append(delimiter);
      for (int i = ends[j - 1]; i < ends[j]; i++) {
        out.append(chars[i]);
      }
    }
  }

  /**
   * like {@link #appendTo(Appendable, char)}, but takes only a part of the
   * path, rather than the whole path.
   * <P>
   * <code>start</code> specifies the first component in the subpath, and
   * <code>end</code> is one past the last component. If <code>start</code> is
   * negative, 0 is assumed, and if <code>end</code> is negative or past the
   * end of the path, the path is taken until the end. Otherwise, if
   * <code>end<=start</code>, nothing is appended. Nothing is appended also in
   * the case that the path is empty.
   */
  public void appendTo(Appendable out, char delimiter, int start, int end)
      throws IOException {
    if (start < 0) {
      start = 0;
    }
    if (end < 0 || end > ncomponents) {
      end = ncomponents;
    }
    if (end <= start) {
      return; // just append nothing...
    }
    for (int i = (start == 0 ? 0 : ends[start - 1]); i < ends[start]; i++) {
      out.append(chars[i]);
    }
    for (int j = start + 1; j < end; j++) {
      out.append(delimiter);
      for (int i = ends[j - 1]; i < ends[j]; i++) {
        out.append(chars[i]);
      }
    }
  }

  /**
   * Build a string representation of the path, with its components separated
   * by the given delimiter character. The resulting string is returned as a
   * new String object. To avoid this temporary object creation, consider
   * using {@link #appendTo(Appendable, char)} instead.
   * <P>
   * Note that the two cases of zero components and one component with zero
   * length produce indistinguishable results (both of them return an empty
   * string). This is normally not a problem, because components should not
   * normally have zero lengths.
   */
  public String toString(char delimiter) {
    if (ncomponents == 0) {
      return "";
    }
    StringBuilder sb = new StringBuilder(ends[ncomponents - 1]
        + (ncomponents - 1));
    try {
      this.appendTo(sb, delimiter);
    } catch (IOException e) {
      // can't happen, because StringBuilder.append() never actually
      // throws an exception!
    }
    return sb.toString();
  }

  /**
   * This method, an implementation of the {@link Object#toString()}
   * interface, is to allow simple printing of a CategoryPath, for debugging
   * purposes. When possible, it recommended to avoid using it it, and rather,
   * if you want to output the path with its components separated by a
   * delimiter character, specify the delimiter explicitly, with
   * {@link #toString(char)}.
   */
  @Override
  public String toString() {
    return toString('/');
  }

  /**
   * like {@link #toString(char)}, but takes only a prefix with a given number
   * of components, rather than the whole path.
   * <P>
   * If the given length is negative or bigger than the path's actual length,
   * the whole path is taken.
   */
  public String toString(char delimiter, int prefixLen) {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    if (prefixLen == 0) {
      return "";
    }
    StringBuilder sb = new StringBuilder(ends[prefixLen - 1]
        + (prefixLen - 1));
    try {
      this.appendTo(sb, delimiter, prefixLen);
    } catch (IOException e) {
      // can't happen, because sb.append() never actually throws an
      // exception
    }
    return sb.toString();
  }

  /**
   * like {@link #toString(char)}, but takes only a part of the path, rather
   * than the whole path.
   * <P>
   * <code>start</code> specifies the first component in the subpath, and
   * <code>end</code> is one past the last component. If <code>start</code> is
   * negative, 0 is assumed, and if <code>end</code> is negative or past the
   * end of the path, the path is taken until the end. Otherwise, if
   * <code>end<=start</code>, an empty string is returned. An emptry string is
   * returned also in the case that the path is empty.
   */
  public String toString(char delimiter, int start, int end) {
    if (start < 0) {
      start = 0;
    }
    if (end < 0 || end > ncomponents) {
      end = ncomponents;
    }
    if (end <= start) {
      return "";
    }
    int startchar = (start == 0) ? 0 : ends[start - 1];
    StringBuilder sb = new StringBuilder(ends[end - 1] - startchar
        + (end - start) - 1);
    try {
      this.appendTo(sb, delimiter, start, end);
    } catch (IOException e) {
      // can't happen, because sb.append() never actually throws an
      // exception
    }
    return sb.toString();
  }

  /**
   * Return the i'th component of the path, in a new String object. If there
   * is no i'th component, a null is returned.
   */
  public String getComponent(int i) {
    if (i < 0 || i >= ncomponents) {
      return null;
    }
    if (i == 0) {
      return new String(chars, 0, ends[0]);
    }
    return new String(chars, ends[i - 1], ends[i] - ends[i - 1]);
  }

  /**
   * Return the last component of the path, in a new String object. If the
   * path is empty, a null is returned.
   */
  public String lastComponent() {
    if (ncomponents == 0) {
      return null;
    }
    if (ncomponents == 1) {
      return new String(chars, 0, ends[0]);
    }
    return new String(chars, ends[ncomponents - 2], ends[ncomponents - 1]
        - ends[ncomponents - 2]);
  }

  /**
   * Copies the specified number of components from this category path to the
   * specified character array, with the components separated by a given
   * delimiter character. The array must be large enough to hold the
   * components and separators - the amount of needed space can be calculated
   * with {@link #charsNeededForFullPath()}.
   * <P>
   * This method returns the number of characters written to the array.
   * 
   * @param outputBuffer
   *            The destination character array.
   * @param outputBufferStart
   *            The first location to write in the output array.
   * @param numberOfComponentsToCopy
   *            The number of path components to write to the destination
   *            buffer.
   * @param separatorChar
   *            The separator inserted between every pair of path components
   *            in the output buffer.
   * @see #charsNeededForFullPath()
   */
  public int copyToCharArray(char[] outputBuffer, int outputBufferStart,
      int numberOfComponentsToCopy, char separatorChar) {
    if (numberOfComponentsToCopy == 0) {
      return 0;
    }
    if (numberOfComponentsToCopy < 0
        || numberOfComponentsToCopy > ncomponents) {
      numberOfComponentsToCopy = ncomponents;
    }
    int outputBufferInitialStart = outputBufferStart; // for calculating
                              // chars copied.
    int sourceStart = 0;
    int sourceLength = ends[0];
    for (int component = 0; component < numberOfComponentsToCopy; component++) {
      if (component > 0) {
        sourceStart = ends[component - 1];
        sourceLength = ends[component] - sourceStart;
        outputBuffer[outputBufferStart++] = separatorChar;
      }
      System.arraycopy(chars, sourceStart, outputBuffer,
          outputBufferStart, sourceLength);
      outputBufferStart += sourceLength;
    }
    return outputBufferStart - outputBufferInitialStart;
  }

  /**
   * Returns the number of characters required to represent this entire
   * category path, if written using
   * {@link #copyToCharArray(char[], int, int, char)} or
   * {@link #appendTo(Appendable, char)}. This includes the number of
   * characters in all the components, plus the number of separators between
   * them (each one character in the aforementioned methods).
   */
  public int charsNeededForFullPath() {
    if (ncomponents == 0) {
      return 0;
    }
    return ends[ncomponents - 1] + ncomponents - 1;
  }

  /**
   * Construct a new CategoryPath object, given a single string with
   * components separated by a given delimiter character.
   * <P>
   * The initial capacity of the constructed object will be exactly what is
   * needed to hold the given path. This fact is convenient when creating a
   * temporary object that will not be reused later.
   */
  public CategoryPath(String pathString, char delimiter) {
    if (pathString.length() == 0) {
      ncomponents = 0;
      chars = new char[0];
      ends = new short[0];
      return;
    }

    // This constructor is often used for creating a temporary object
    // (one which will not be reused to hold multiple paths), so we want
    // to do our best to allocate exactly the needed size - not less (to
    // avoid reallocation) and not more (so as not to waste space).
    // To do this, we unfortunately need to make an additional pass on the
    // given string:
    int nparts = 1;
    for (int i = pathString.indexOf(delimiter); i >= 0; i = pathString
        .indexOf(delimiter, i + 1)) {
      nparts++;
    }

    ends = new short[nparts];
    chars = new char[pathString.length() - nparts + 1];
    ncomponents = 0;

    add(pathString, delimiter);
  }

  /**
   * Add the given components to the end of the path. The components are given
   * in a single string, separated by a given delimiter character. If the
   * given string is empty, it is assumed to refer to the root (empty)
   * category, and nothing is added to the path (rather than adding a single
   * empty component).
   * <P>
   * Note that when a String object is passed to this method, a reference to
   * it is not saved (rather, its content is copied), which will lead to that
   * String object being gc'ed. To reduce the number of garbage objects, you
   * can pass a mutable CharBuffer instead of an immutable String to this
   * method.
   */
  public void add(CharSequence pathString, char delimiter) {
    int len = pathString.length();
    if (len == 0) {
      return; // assume root category meant, so add nothing.
    }
    short pos = (ncomponents == 0) ? 0 : ends[ncomponents - 1];
    for (int i = 0; i < len; i++) {
      char c = pathString.charAt(i);
      if (c == delimiter) {
        if (ncomponents >= ends.length) {
          short[] newends = new short[(ends.length + 1) * 2];
          System.arraycopy(ends, 0, newends, 0, ends.length);
          ends = newends;
        }
        ends[ncomponents++] = pos;
      } else {
        if (pos >= chars.length) {
          char[] newchars = new char[(chars.length + 1) * 2];
          System.arraycopy(chars, 0, newchars, 0, chars.length);
          chars = newchars;
        }
        chars[pos++] = c;
      }
    }

    // Don't forget to count the last component!
    if (ncomponents >= ends.length) {
      short[] newends = new short[(ends.length + 1) * 2];
      System.arraycopy(ends, 0, newends, 0, ends.length);
      ends = newends;
    }
    ends[ncomponents++] = pos;
  }

  /**
   * Construct a new CategoryPath object, copying an existing path given as an
   * array of strings.
   * <P>
   * The new object occupies exactly the space it needs, without any spare
   * capacity. This is the expected behavior in the typical use case, where
   * this constructor is used to create a temporary object which is never
   * reused.
   */
  public CategoryPath(CharSequence... components) {
    this.ncomponents = (short) components.length;
    this.ends = new short[ncomponents];
    if (ncomponents > 0) {
      this.ends[0] = (short) components[0].length();
      for (int i = 1; i < ncomponents; i++) {
        this.ends[i] = (short) (this.ends[i - 1] + components[i]
            .length());
      }
      this.chars = new char[this.ends[ncomponents - 1]];
      CharSequence cs = components[0];
      if (cs instanceof String) {
        ((String) cs).getChars(0, cs.length(), this.chars, 0);
      } else {
        for (int j = 0, k = cs.length(); j < k; j++) {
          this.chars[j] = cs.charAt(j);
        }
      }
      for (int i = 1; i < ncomponents; i++) {
        cs = components[i];
        int offset = this.ends[i - 1];
        if (cs instanceof String) {
          ((String) cs).getChars(0, cs.length(), this.chars, offset);
        } else {
          for (int j = 0, k = cs.length(); j < k; j++) {
            this.chars[j + offset] = cs.charAt(j);
          }
        }
      }
    } else {
      this.chars = new char[0];
    }
  }

  /**
   * Construct a new CategoryPath object, copying the path given in an
   * existing CategoryPath object.
   * <P>
   * This copy-constructor is handy when you need to save a reference to a
   * CategoryPath (e.g., when it serves as a key to a hash-table), but cannot
   * save a reference to the original object because its contents can be
   * changed later by the user. Copying the contents into a new object is a
   * solution.
   * <P>
   * This constructor </I>does not</I> copy the capacity (spare buffer size)
   * of the existing CategoryPath. Rather, the new object occupies exactly the
   * space it needs, without any spare. This is the expected behavior in the
   * typical use case outlined in the previous paragraph.
   */
  public CategoryPath(CategoryPath existing) {
    ncomponents = existing.ncomponents;
    if (ncomponents == 0) {
      chars = new char[0];
      ends = new short[0];
      return;
    }

    chars = new char[existing.ends[ncomponents - 1]];
    System.arraycopy(existing.chars, 0, chars, 0, chars.length);
    ends = new short[ncomponents];
    System.arraycopy(existing.ends, 0, ends, 0, ends.length);
  }

  /**
   * Construct a new CategoryPath object, copying a prefix with the given
   * number of components of the path given in an existing CategoryPath
   * object.
   * <P>
   * If the given length is negative or bigger than the given path's actual
   * length, the full path is taken.
   * <P>
   * This constructor is often convenient for creating a temporary object with
   * a path's prefix, but this practice is wasteful, and therefore
   * inadvisable. Rather, the application should be written in a way that
   * allows considering only a prefix of a given path, without needing to make
   * a copy of that path.
   */
  public CategoryPath(CategoryPath existing, int prefixLen) {
    if (prefixLen < 0 || prefixLen > existing.ncomponents) {
      ncomponents = existing.ncomponents;
    } else {
      ncomponents = (short) prefixLen;
    }
    if (ncomponents == 0) {
      chars = new char[0];
      ends = new short[0];
      return;
    }

    chars = new char[existing.ends[ncomponents - 1]];
    System.arraycopy(existing.chars, 0, chars, 0, chars.length);
    ends = new short[ncomponents];
    System.arraycopy(existing.ends, 0, ends, 0, ends.length);
  }

  @Override
  public Object clone() {
    return new CategoryPath(this);
  }

  /**
   * Compare the given CategoryPath to another one. For two category paths to
   * be considered equal, only the path they contain needs to be identical The
   * unused capacity of the objects is not considered in the comparison.
   */
  @Override
  public boolean equals(Object obj) {
    if (obj instanceof CategoryPath) {
      CategoryPath other = (CategoryPath) obj;
      if (other.ncomponents != this.ncomponents) {
        return false;
      }
      // Unfortunately, Arrays.equal() can only compare entire arrays,
      // and in our case we potentially have unused parts of the arrays
      // that must not be compared... I wish that some future version
      // of Java has a offset and length parameter to Arrays.equal
      // (sort of like System.arraycopy()).
      if (ncomponents == 0) {
        return true; // nothing to compare...
      }
      for (int i = 0; i < ncomponents; i++) {
        if (this.ends[i] != other.ends[i]) {
          return false;
        }
      }
      int len = ends[ncomponents - 1]; 
      for (int i = 0; i < len; i++) {
        if (this.chars[i] != other.chars[i]) {
          return false;
        }
      }
      return true;
    }
    return false;
  }

  /**
   * Test whether this object is a descendant of another CategoryPath. This is
   * true if the other CategoryPath is the prefix of this.
   */
  public boolean isDescendantOf(CategoryPath other) {
    if (this.ncomponents < other.ncomponents) {
      return false;
    }
    int j = 0;
    for (int i = 0; i < other.ncomponents; i++) {
      if (ends[i] != other.ends[i]) {
        return false;
      }
      for (; j < ends[i]; j++) {
        if (this.chars[j] != other.chars[j]) {
          return false;
        }
      }
    }
    return true;
  }

  /**
   * Calculate a hashCode for this path, used when a CategoryPath serves as a
   * hash-table key. If two objects are equal(), their hashCodes need to be
   * equal, so like in equal(), hashCode does not consider unused portions of
   * the internal buffers in its calculation.
   * <P>
   * The hash function used is modeled after Java's String.hashCode() - a
   * simple multiplicative hash function with the multiplier 31. The same hash
   * function also appeared in Kernighan & Ritchie's second edition of
   * "The C Programming Language" (1988).
   */
  @Override
  public int hashCode() {
    if (ncomponents == 0) {
      return 0;
    }
    int hash = ncomponents;
    // Unfortunately, Arrays.hashCode() can only calculate a hash code
    // for an entire arrays, and in our case we potentially have unused
    // parts of the arrays that must be ignored, so must use our own loop
    // over the characters. I wish that some future version of Java will
    // add offset and length parameters to Arrays.hashCode (sort of like
    // System.arraycopy()'s parameters).
    for (int i = 0; i < ncomponents; i++) {
      hash = hash * 31 + ends[i];
    }
    int len = ends[ncomponents - 1];
    for (int i = 0; i < len; i++) {
      hash = hash * 31 + chars[i];
    }
    return hash;
  }

  /**
   * Like {@link #hashCode()}, but find the hash function of a prefix with the
   * given number of components, rather than of the entire path.
   */
  public int hashCode(int prefixLen) {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    if (prefixLen == 0) {
      return 0;
    }
    int hash = prefixLen;
    for (int i = 0; i < prefixLen; i++) {
      hash = hash * 31 + ends[i];
    }
    int len = ends[prefixLen - 1];
    for (int i = 0; i < len; i++) {
      hash = hash * 31 + chars[i];
    }
    return hash;
  }

  /**
   * Calculate a 64-bit hash function for this path. Unlike
   * {@link #hashCode()}, this method is not part of the Java standard, and is
   * only used if explicitly called by the user.
   * <P>
   * If two objects are equal(), their hash codes need to be equal, so like in
   * {@link #equals(Object)}, longHashCode does not consider unused portions
   * of the internal buffers in its calculation.
   * <P>
   * The hash function used is a simple multiplicative hash function, with the
   * multiplier 65599. While Java's standard multiplier 31 (used in
   * {@link #hashCode()}) gives a good distribution for ASCII strings, it
   * turns out that for foreign-language strings (with 16-bit characters) it
   * gives too many collisions, and a bigger multiplier produces fewer
   * collisions in this case.
   */
  public long longHashCode() {
    if (ncomponents == 0) {
      return 0;
    }
    long hash = ncomponents;
    for (int i = 0; i < ncomponents; i++) {
      hash = hash * 65599 + ends[i];
    }
    int len = ends[ncomponents - 1];
    for (int i = 0; i < len; i++) {
      hash = hash * 65599 + chars[i];
    }
    return hash;
  }

  /**
   * Like {@link #longHashCode()}, but find the hash function of a prefix with
   * the given number of components, rather than of the entire path.
   */
  public long longHashCode(int prefixLen) {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    if (prefixLen == 0) {
      return 0;
    }
    long hash = prefixLen;
    for (int i = 0; i < prefixLen; i++) {
      hash = hash * 65599 + ends[i];
    }
    int len = ends[prefixLen - 1];
    for (int i = 0; i < len; i++) {
      hash = hash * 65599 + chars[i];
    }
    return hash;
  }

  /**
   * Write out a serialized (as a character sequence) representation of the
   * path to a given Appendable (e.g., a StringBuilder, CharBuffer, Writer, or
   * something similar.
   * <P>
   * This method may throw a IOException if the given Appendable threw this
   * exception while appending.
   */
  public void serializeAppendTo(Appendable out) throws IOException {
    // Note that we use the fact that ncomponents and ends[] are shorts,
    // so we can write them as chars:
    out.append((char) ncomponents);
    if (ncomponents == 0) {
      return;
    }
    for (int i = 0; i < ncomponents; i++) {
      out.append((char) ends[i]);
    }
    int usedchars = ends[ncomponents - 1];
    for (int i = 0; i < usedchars; i++) {
      out.append(chars[i]);
    }
  }

  /**
   * Just like {@link #serializeAppendTo(Appendable)}, but writes only a
   * prefix of the CategoryPath.
   */
  public void serializeAppendTo(int prefixLen, Appendable out)
      throws IOException {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    // Note that we use the fact that ncomponents and ends[] are shorts,
    // so we can write them as chars:
    out.append((char) prefixLen);
    if (prefixLen == 0) {
      return;
    }
    for (int i = 0; i < prefixLen; i++) {
      out.append((char) ends[i]);
    }
    int usedchars = ends[prefixLen - 1];
    for (int i = 0; i < usedchars; i++) {
      out.append(chars[i]);
    }
  }

  /**
   * Set a CategoryPath from a character-sequence representation written by
   * {@link #serializeAppendTo(Appendable)}.
   * <P>
   * Reading starts at the given offset into the given character sequence, and
   * the offset right after the end of this path is returned.
   */
  public int setFromSerialized(CharSequence buffer, int offset) {
    ncomponents = (short) buffer.charAt(offset++);
    if (ncomponents == 0) {
      return offset;
    }

    if (ncomponents >= ends.length) {
      ends = new short[Math.max(ends.length * 2, ncomponents)];
    }
    for (int i = 0; i < ncomponents; i++) {
      ends[i] = (short) buffer.charAt(offset++);
    }

    int usedchars = ends[ncomponents - 1];
    if (usedchars > chars.length) {
      chars = new char[Math.max(chars.length * 2, usedchars)];
    }
    for (int i = 0; i < usedchars; i++) {
      chars[i] = buffer.charAt(offset++);
    }

    return offset;
  }

  /**
   * Check whether the current path is identical to the one serialized (with
   * {@link #serializeAppendTo(Appendable)}) in the given buffer, at the given
   * offset.
   */
  public boolean equalsToSerialized(CharSequence buffer, int offset) {
    int n = (short) buffer.charAt(offset++);
    if (ncomponents != n) {
      return false;
    }
    if (ncomponents == 0) {
      return true;
    }
    for (int i = 0; i < ncomponents; i++) {
      if (ends[i] != (short) buffer.charAt(offset++)) {
        return false;
      }
    }
    int usedchars = ends[ncomponents - 1];
    for (int i = 0; i < usedchars; i++) {
      if (chars[i] != buffer.charAt(offset++)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Just like {@link #equalsToSerialized(CharSequence, int)}, but compare to
   * a prefix of the CategoryPath, instead of the whole CategoryPath.
   */
  public boolean equalsToSerialized(int prefixLen, CharSequence buffer,
      int offset) {
    if (prefixLen < 0 || prefixLen > ncomponents) {
      prefixLen = ncomponents;
    }
    int n = (short) buffer.charAt(offset++);
    if (prefixLen != n) {
      return false;
    }
    if (prefixLen == 0) {
      return true;
    }
    for (int i = 0; i < prefixLen; i++) {
      if (ends[i] != (short) buffer.charAt(offset++)) {
        return false;
      }
    }
    int usedchars = ends[prefixLen - 1];
    for (int i = 0; i < usedchars; i++) {
      if (chars[i] != buffer.charAt(offset++)) {
        return false;
      }
    }
    return true;
  }

  /**
   * This method calculates a hash function of a path that has been written to
   * (using {@link #serializeAppendTo(Appendable)}) a character buffer. It is
   * guaranteed that the value returned is identical to that which
   * {@link #hashCode()} would have produced for the original object before it
   * was serialized.
   */
  public static int hashCodeOfSerialized(CharSequence buffer, int offset) {
    // Note: the algorithm here must be identical to that of hashCode(),
    // in order that they produce identical results!
    int ncomponents = (short) buffer.charAt(offset++);
    if (ncomponents == 0) {
      return 0;
    }
    int hash = ncomponents;
    for (int i = 0; i < ncomponents; i++) {
      hash = hash * 31 + buffer.charAt(offset++);
    }
    int len = buffer.charAt(offset - 1);
    for (int i = 0; i < len; i++) {
      hash = hash * 31 + buffer.charAt(offset++);
    }
    return hash;
  }

  /**
   * Serializes the content of this CategoryPath to a byte stream, using UTF-8
   * encoding to convert characters to bytes, and treating the ends as 16-bit
   * characters. 
   * 
   * @param osw
   *          The output byte stream.
   * @throws IOException
   *           If there are encoding errors.
   */
  // TODO (Facet): consolidate all de/serialize method names to
  // serialize() and unserialize()
  public void serializeToStreamWriter(OutputStreamWriter osw)
      throws IOException {
    osw.write(this.ncomponents);
    if (this.ncomponents <= 0) {
      return;
    }
    for (int j = 0; j < this.ncomponents; j++) {
      osw.write(this.ends[j]);
    }
    osw.write(this.chars, 0, this.ends[this.ncomponents - 1]);
  }

  /**
   * Serializes the content of this CategoryPath to a byte stream, using UTF-8
   * encoding to convert characters to bytes, and treating the ends as 16-bit
   * characters.
   * 
   * @param isr
   *            The input stream.
   * @throws IOException
   *             If there are encoding errors.
   */
  public void deserializeFromStreamReader(InputStreamReader isr)
      throws IOException {
    this.ncomponents = (short) isr.read();
    if (this.ncomponents <= 0) {
      return;
    }
    if (this.ends == null || this.ends.length < this.ncomponents) {
      this.ends = new short[this.ncomponents];
    }
    for (int j = 0; j < this.ncomponents; j++) {
      this.ends[j] = (short) isr.read();
    }
    if (this.chars == null
        || this.ends[this.ncomponents - 1] > chars.length) {
      this.chars = new char[this.ends[this.ncomponents - 1]];
    }
    isr.read(this.chars, 0, this.ends[this.ncomponents - 1]);
  }

  private void writeObject(java.io.ObjectOutputStream out)
  throws IOException {
    OutputStreamWriter osw = new OutputStreamWriter(out, "UTF-8");
    this.serializeToStreamWriter(osw);
    osw.flush();
  }
  
  private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
    InputStreamReader isr = new InputStreamReader(in, "UTF-8");
    this.deserializeFromStreamReader(isr);
  }

  /**
   * Compares this CategoryPath with the other CategoryPath for lexicographic
   * order. 
   * Returns a negative integer, zero, or a positive integer as this
   * CategoryPath lexicographically precedes, equals to, or lexicographically follows 
   * the other CategoryPath.
   */
  public int compareTo(CategoryPath other) {
    int minlength = (this.length() < other.length()) ? this.length() : other.length();
    int ch = 0;
    for (int co = 0 ; co < minlength; co++) {
      if (this.ends[co] <= other.ends[co]) {
        for ( ; ch < this.ends[co] ; ch++) {
          if (this.chars[ch] != other.chars[ch]) {
            return this.chars[ch] - other.chars[ch];
          }
        }
        if (this.ends[co] < other.ends[co]) {
          return -1;
        }
      } else /* this.ends[co] > other.ends[co] */ {
        for ( ; ch < other.ends[co] ; ch++) {
          if (this.chars[ch] != other.chars[ch]) {
            return this.chars[ch] - other.chars[ch];
          }
        }
        return +1;
      }
    }
    // one is a prefix of the other
    return this.length() - other.length();
  }  
}