VList Java


http://www.keithschwarz.com/interesting/code/?dir=vlist
* An implementation of the List abstraction backed by a VList. The VList is
 * similar to a standard dynamic array implementation, except that the old
 * arrays are chained together to form the implementation, rather than
 * discarded. For example, here is one possible VList holding six elements:
 *
 * <pre>
 *
 *        +------+     +------+     +------+
 *        | next | --} | next | --} | next | -| nil
 *        +------+     +------+     +------+
 * nil |- | prev | {-- | prev | {-- | prev |
 *        +------+     +------+     +------+
 *        |      |     |   2  |     |   0  |
 *        +------+     +------+     +------+
 *        |   5  |     |   1  |
 *        +------+     +------+
 *        |   4  |
 *        +------+
 *        |   3  |
 *        +------+
 *
 * </pre>
 *
 * Each column represents a linked list cell containing a fixed-size array. The
 * size of this array depends on which cell is being referenced. In particular,
 * the nth cell from the end has 2^n elements in it. In this manner, for a
 * uniformly-randomly chosen position, the expected time to look up that element
 * is O(1), though in the worst case it is O(log n). This random access is
 * significantly better than a linked list, though in the worst case is not as
 * good as a dynamic array.
 * <p>
 * Notice that in each array, elements grow up, with the lower-numbered indices
 * of the array holding elements in the array whose positions are higher. This
 * makes it easier to look up individual elements.
 * <p>
 *
 * @author Keith Schwarz (htiek@cs.stanford.edu)
 */

public final class VList<T> extends AbstractList<T> {
  /**
   * A single cell in the VList implementation.
   */

  private static final class VListCell<T> {
    public final T[] mElems;
    public final VListCell<T> mNext;

    /* This field is not mutable because when new elements are added/deleted
     * from the main list, the previous pointer needs to be updated.
     * However, next links never change because the list only grows in one
     * direction.
     */

    public VListCell<T> mPrev;

    /* The number of unused elements in this cell. Alternatively, you can
     * think of this as the index in the array in which the first used
     * element appears. Both interpretations are used in this
     * implementation.
     */

    public int mFreeSpace;

    /**
     * Constructs a new VListCell with the specified number of elements and
     * specified next element.
     *
     * @param numElems
     *            The number of elements this cell should have space for.
     * @param next
     *            The cell in the list of cells that follows this one.
     */

    public VListCell(int numElems, VListCell<T> next) {
      mElems = (T[]) new Object[numElems];
      mNext = next;
      mPrev = null;

      /* Update the next cell to point back to us. */
      if (next != null)
        next.mPrev = this;

      /* We have free space equal to the number of elements. */
      mFreeSpace = numElems;
    }
  }

  /**
   * A utility struct containing information about where an element is in the
   * VList. Methods that need to manipulate individual elements of the list
   * use this struct to communicate where in the list to look for that
   * element.
   */

  private static final class VListLocation<T> {
    public final VListCell<T> mCell;
    public final int mOffset;

    public VListLocation(VListCell<T> cell, int offset) {
      mCell = cell;
      mOffset = offset;
    }
  }

  /* Pointer to the head of the VList, which contains the final elements of
   * the list.
   */

  private VListCell<T> mHead;

  /* Cached total number of elements in the array. */
  private int mSize;

  /**
   * Adds a new element to the end of the array.
   *
   * @param elem
   *            The element to add.
   * @return true
   */

  @Override
  public boolean add(T elem) {
    /* If no free space exists, add a new element to the list. */
    if (mHead == null || mHead.mFreeSpace == 0)
      mHead = new VListCell<T>(mHead == null1 : mHead.mElems.length * 2, mHead);

    /* Prepend this element to the current cell. */
    mHead.mElems[(mHead.mFreeSpace--) - 1] = elem;
    ++mSize;

    /* Success! */
    return true;
  }

  /**
   * Given an absolute offset into the VList, returns an object describing
   * where that object is in the VList.
   *
   * @param index
   *            The index into the VList.
   * @return A VListLocation object holding information about where that
   *         element can be found.
   */

  private VListLocation<T> locateElement(int index) {
    /* Bounds-check. */
    if (index >= size() || index < 0)
      throw new IndexOutOfBoundsException("Position " + index + "; size "
          + size());

    /* Because the list is stored with new elements in front and old
     * elements in back, we'll invert the index so that 0 refers to the
     * final element of the array and size() - 1 refers to the first
     * element.
     */

    index = size() - 1 - index;

    /* Scan across the cells, looking for the first one that can hold our
     * entry. We do this by continuously skipping cells until we find one
     * that can be sure to hold this element.
     *
     * Note that each cell has mElems.length elements, of which mFreeSpace
     * is used. This means that the total number of used elements in each
     * cell is mElems.length - mFreeSpace.
     */

    VListCell<T> curr = mHead;
    while (index >= curr.mElems.length - curr.mFreeSpace) {
      /* Skip past all these elements. */
      index -= curr.mElems.length - curr.mFreeSpace;
      curr = curr.mNext;
    }

    /* We're now in the correct location for what we need to do. The element
     * we want can be found by indexing the proper amount beyond the free
     * space.
     */

    return new VListLocation<T>(curr, index + curr.mFreeSpace);
  }

  /**
   * Scans for the proper location in the cell list for the element, then
   * returns the element at that position.
   *
   * @param index
   *            The index at which to look up the element.
   * @return The element at that position.
   */

  @Override
  public T get(int index) {
    VListLocation<T> where = locateElement(index);

    /* Return the element in the current position of this array. */
    return where.mCell.mElems[where.mOffset];
  }

  /**
   * Returns the cached size.
   *
   * @return The size of the VList.
   */

  @Override
  public int size() {
    return mSize;
  }

  /**
   * Sets an element at a particular position to have a particular value.
   *
   * @param index
   *            The index at which to write a new value.
   * @param value
   *            The value to write at that position.
   * @return The value originally held at that position.
   */

  @Override
  public T set(int index, T value) {
    VListLocation<T> where = locateElement(index);

    /* Cache the element in the current position of this array. */
    T result = where.mCell.mElems[where.mOffset];
    where.mCell.mElems[where.mOffset] = value;
    return result;
  }

  /**
   * Removes the element at the specified position from the VList, returning
   * its value.
   *
   * @param index
   *            The index at which the element should be removed.
   * @return The value held at that position.
   */

  @Override
  public T remove(int index) {
    VListLocation<T> where = locateElement(index);

    /* Cache the value that will be removed. */
    T result = where.mCell.mElems[where.mOffset];

    /* Invoke the helper to do most of the work. */
    removeAtPosition(where);

    return result;
  }

  /**
   * Removes the element at the indicated VListLocation.
   *
   * @param where
   *            The location at which the element should be removed.
   */

  private void removeAtPosition(VListLocation<T> where) {
    /* Scan backward across the blocks after this element, shuffling array
     * elements down a position and copying the last element of the next
     * block over to fill in the top.
     *
     * The variable shuffleTargetPosition indicates the first element of the
     * block that should be overwritten during the shuffle-down. In the
     * first block, this is the position of the element that was
     * overwritten. In all other blocks, it's the last element.
     */

    VListCell<T> curr = where.mCell;
    for (int shuffleTargetPosition = where.mOffset; curr != null
         curr = curr.mPrev, shuffleTargetPosition = (curr == null0 : curr.mElems.length - 1)) {
      /* Shuffle down each element in the current array on top of the
       * target position. Note that in the final block, this may end up
       * copying a whole bunch of null values down. This is more work than
       * necessary, but is harmless and doesn't change the asymptotic
       * runtime (since the last block has size O(n)).
       */

      for (int i = shuffleTargetPosition - 1; i >= 0; --i)
        curr.mElems[i + 1] = curr.mElems[i];

      /* Copy the last element of the next array to the top of this array,
       * unless this is the first block (in which case there is no next
       * array).
       */

      if (curr.mPrev != null)
        curr.mElems[0] = curr.mPrev.mElems[curr.mPrev.mElems.length - 1];
    }

    /* The head just lost an element, so it has some more free space. Null
     * out the lost element and increase the free space.
     */

    ++mHead.mFreeSpace;
    mHead.mElems[mHead.mFreeSpace - 1] = null;

    /* The whole list just lost an element. */
    --mSize;

    /* If the head is entirely free, remove it from the list. */
    if (mHead.mFreeSpace == mHead.mElems.length) {
      mHead = mHead.mNext;

      /* If there is at least one block left, remove the previous block
       * from the linked list.
       */

      if (mHead != null)
        mHead.mPrev = null;
    }
  }

  /**
   * A custom iterator class that traverses the elements of this container in
   * an intelligent way. The normal iterator will call get repeatedly, which
   * is slow because it has to continuously scan for the proper location of
   * the next element. This iterator works by traversing the cells as a proper
   * linked list.
   */

  private final class VListIterator implements Iterator<T> {
    /* The cell and position in that cell that we are about to visit. We
     * maintain the invariant that if there is a next element, mCurrCell is
     * non-null and conversely that if mCurrCell is null, there is no next
     * element.
     */

    private VListCell<T> mCurrCell;
    private int mCurrIndex;

    /* Stores whether we have something to remove (i.e. whether we've called
     * next() without an invervening remove()).
     */

    private boolean mCanRemove;

    /**
     * Constructs a new VListIterator that will traverse the elements of the
     * containing VList.
     */

    public VListIterator() {
      /* Scan to the tail using the "pointer chase" algorithm. When this
       * terminates, prev will hold a pointer to the last element of the
       * list.
       */

      VListCell<T> curr, prev;
      for (curr = mHead, prev = null; curr != null; prev = curr, curr = curr.mNext)
        ;

      /* Set the current cell to the tail. */
      mCurrCell = prev;

      /* If the tail isn't null, it must be a full list of size 1. Set the
       * current index appropriately.
       */

      if (mCurrCell != null)
        mCurrIndex = 0;
    }

    /**
     * As per our invariant, returns whether mCurrCell is non-null.
     */

    @Override
    public boolean hasNext() {
      return mCurrCell != null;
    }

    /**
     * Advances the iterator and returns the element it used to be over.
     */

    @Override
    public T next() {
      /* Bounds-check. */
      if (!hasNext())
        throw new NoSuchElementException();

      /* Cache the return value; we'll be moving off of it soon. */
      T result = mCurrCell.mElems[mCurrIndex];

      /* Back up one step. */
      --mCurrIndex;

      /* If we walked off the end of the buffer, advance to the next
       * element of the list.
       */

      if (mCurrIndex < mCurrCell.mFreeSpace) {
        mCurrCell = mCurrCell.mPrev;

        /* Update the next get location, provided of course that we
         * didn't just walk off the end of the list.
         */

        if (mCurrCell != null)
          mCurrIndex = mCurrCell.mElems.length - 1;
      }

      /* Since there was indeed an element, we can remove it. */
      mCanRemove = true;

      return result;
    }

    /**
     * Removes the last element we visited.
     */

    @Override
    public void remove() {
      /* Check whether there's something to remove. */
      if (!mCanRemove)
        throw new IllegalStateException(
            "remove() without next(), or double remove().");

      /* Clear the flag saying we can do this. */
      mCanRemove = false;

      /* There are several cases to consider. If the current cell is null,
       * we've walked off the end of the array, so we want to remove the
       * very last element. If the current cell isn't null and the cursor
       * is in the middle, remove the previous element and back up a step.
       * If the current cell isn't null and the cursor is at the front,
       * remove the element one step before us and back up a step.
       */


      /* Case 1. */
      if (mCurrCell == null)
        VList.this.remove(size() - 1);
      /* Case 2. */
      else if (mCurrIndex != mCurrCell.mElems.length - 1) {
        /* Back up a step, and remove the element at this position.
         * After the remove completes, the element here should be the
         * next element to visit.
         */

        ++mCurrIndex;
        removeAtPosition(new VListLocation<T>(mCurrCell, mCurrIndex));
      }
      /* Case 3. */
      else {
        /* Back up a step to the top of the previous list. We know that
         * the top will be at position 0, since all internal blocks are
         * completely full. We also know that we aren't at the very
         * front of the list, since if we were, then the call to next()
         * that enabled this call would have pushed us to the next
         * location.
         */

        mCurrCell = mCurrCell.mNext;
        mCurrIndex = 0;
        removeAtPosition(new VListLocation<T>(mCurrCell, mCurrIndex));
      }
    }
  }

  /**
   * Returns a custom iterator rather than the default.
   */

  @Override
  public Iterator<T> iterator() {
    return new VListIterator();
  }
}
http://www.sanfoundry.com/java-program-implement-vlist/
https://en.wikipedia.org/wiki/VList
the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly linked) linked lists.
https://en.wikipedia.org/wiki/Persistent_data_structure
persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts