content: /* Alloy Analyzer 4 -- Copyright (c) 2006-2009, Felix Chang
   *
   * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
   * (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
   * merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
   * furnished to do so, subject to the following conditions:
   *
   * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
   *
   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
   * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
   * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
   * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   */
  
  package edu.mit.csail.sdg.alloy4;
  
  import java.io.Serializable;
  import java.util.AbstractList;
  
  /**
   * Immutable; implements a list where it is combine them; null values are NOT
   * allowed.
   */
  
  public final class JoinableList<E> extends AbstractList<E> implements Serializable {
  
      /** This ensures the class can be serialized reliably. */
      private static final long     serialVersionUID = 0;
  
      /**
       * The number of items stored in this list.
       * <p>
       * <b>Invariant:</b> count == (pre!=null ? pre.count : 0) + (item!=null ? 1 : 0)
       * + (post!=null ? post.count : 0)
       */
      private final int             count;
  
      /** The list of items before "this.item"; may be null. */
      private final JoinableList<E> pre;
  
      /** The list of items after "this.item"; may be null. */
      private final JoinableList<E> post;
  
      /** If nonnull, it stores an item. */
      private final E               item;
  
      /** Construct a JoinableList object. */
      private JoinableList(int count, JoinableList<E> pre, E item, JoinableList<E> post) {
          this.count = count;
          this.pre = pre;
          this.item = item;
          this.post = post;
      }
  
      /** Construct an empty list. */
      public JoinableList() {
          this(0, null, null, null);
      }
  
      /**
       * Construct a list containing a single item, or return an empty list if
       * item==null.
       */
      public JoinableList(E item) {
          this((item != null ? 1 : 0), null, item, null);
      }
  
      /**
       * Returns a list that represents the concatenation of this list and that list.
       */
      public JoinableList<E> make(JoinableList<E> that) {
          if (that == null || that.count == 0)
              return this;
          else if (count == 0)
              return that;
          int sum = count + that.count;
          if (sum < count)
              throw new OutOfMemoryError(); // integer overflow
          if (post != null)
              return new JoinableList<E>(sum, this, null, that);
          else
              return new JoinableList<E>(sum, pre, item, that);
      }
  
      /**
       * Returns a list that represents the result of appending newItem onto this
       * list; if newItem==null we return this list as-is.
       */
      public JoinableList<E> make(E newItem) {
          if (newItem == null)
              return this;
          int sum = count + 1; // integer overflow
          if (sum < 1)
              throw new OutOfMemoryError();
          if (post != null)
              return new JoinableList<E>(sum, this, newItem, null);
          if (item != null)
              return new JoinableList<E>(sum, pre, item, new JoinableList<E>(newItem));
          return new JoinableList<E>(sum, pre, newItem, null);
      }
  
      /**
       * If the list if nonempty, arbitrarily return one of the item, otherwise throw
       * ArrayIndexOutOfBoundsException.
       */
      public E pick() {
          if (item != null)
              return item;
          else
              return get(0);
      }
  
      /**
       * Return the i-th element
       *
       * @throws ArrayIndexOutOfBoundsException if the given index doesn't exist
       */
      @Override
      public E get(int i) {
          if (i < 0 || i >= count)
              throw new ArrayIndexOutOfBoundsException();
          JoinableList<E> x = this;
          while (true) {
              int pre = (x.pre == null) ? 0 : x.pre.count;
              if (i < pre) {
                  x = x.pre;
                  continue;
              }
              if (x.item == null) {
                  i = i - pre;
                  x = x.post;
              } else if (i != pre) {
                  i = i - pre - 1;
                  x = x.post;
              } else
                  return x.item;
          }
      }
  
      /** Returns the number of elements in this list. */
      @Override
      public int size() {
          return count;
      }
  }
  