Package cs2110

Class ArraySeq<T>

java.lang.Object
cs2110.ArraySeq<T>
All Implemented Interfaces:
Seq<T>, Iterable<T>
public class ArraySeq<T> extends Object implements Seq<T>
A sequence of non-null elements of type `T` implemented using a dynamically resized array. The array begins with some initial capacity and doubles in size whenever adding an element would cause the sequence to exceed its capacity.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private class 
    ArraySeq.ArraySeqIterator
    A private inner class that acts as an iterator over an ArraySeq.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private T[]
    contents
    Backing storage of this sequence.
    private static final int
    INITIAL_CAPACITY
    The initial capacity of the backing storage for new instances of `ArraySeq`.
    private int
    size
    Number of elements in the sequence.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ArraySeq()
    Create an empty list.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    append(T elem)
    Add element `elem` to the end of this list.
    boolean
    contains(T elem)
    Return whether this list contains an element equal to `elem` (according to `equals()`).
    boolean
    equals(Object other)
    Return whether this and `other` are `ArraySeq`s containing the same elements in the same order.
    private int
    firstIndexOf(T elem)
    Return the smallest index i such that `contents[i].equals(elem)`, or -1 if this sequence does not contain `elem`.
    T
    get(int index)
    Return the element at index `index` in this list.
    int
    hashCode()
    Returns a hash code value for the object.
    void
    insertBefore(T elem, T successor)
    Insert element `elem` into the list just before the first occurrence of element `successor`.
    Iterator<T>
    iterator()
    Return an iterator over the elements of this list (in sequence order).
    void
    prepend(T elem)
    Insert element `elem` at the beginning of this list.
    boolean
    remove(T elem)
    Remove the first occurrence of element `elem` (if any) from this list.
    private void
    resizeIfNeeded()
    If our backing storage is full, replace it with an array that is twice as large while preserving its contents.
    int
    size()
    Return the number of elements in this list.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Field Details

    • INITIAL_CAPACITY

      private static final int INITIAL_CAPACITY
      The initial capacity of the backing storage for new instances of `ArraySeq`.
      See Also:

    • contents

      private T[] contents
      Backing storage of this sequence. Indices 0..size-1 are non-null while indices size..contents.length are null. Length must be at least 1.

    • size

      private int size
      Number of elements in the sequence. Must be non-negative and at most `contents.length`

  • Constructor Details

    • ArraySeq

      public ArraySeq()
      Create an empty list.

  • Method Details

    • size

      public int size()
      Description copied from interface: Seq
      Return the number of elements in this list.
      Specified by:
      size in interface Seq<T>

    • get

      public T get(int index)
      Description copied from interface: Seq
      Return the element at index `index` in this list. The index of the first element is 0. Requires 0 <= index < size(). Will not return null.
      Specified by:
      get in interface Seq<T>

    • resizeIfNeeded

      private void resizeIfNeeded()
      If our backing storage is full, replace it with an array that is twice as large while preserving its contents. Otherwise, do nothing.

    • prepend

      public void prepend(T elem)
      Description copied from interface: Seq
      Insert element `elem` at the beginning of this list. Example: if the list is [8, 7, 4], prepend(2) would change the list to [2, 8, 7, 4]. Requires `elem` is not null.
      Specified by:
      prepend in interface Seq<T>

    • append

      public void append(T elem)
      Description copied from interface: Seq
      Add element `elem` to the end of this list. Example: if the list is [8, 7, 4], append(2) would change the list to [8, 7, 4, 2]. Requires `elem` is not null.
      Specified by:
      append in interface Seq<T>

    • firstIndexOf

      private int firstIndexOf(T elem)
      Return the smallest index i such that `contents[i].equals(elem)`, or -1 if this sequence does not contain `elem`.

    • contains

      public boolean contains(T elem)
      Description copied from interface: Seq
      Return whether this list contains an element equal to `elem` (according to `equals()`). Requires `elem` is not null.
      Specified by:
      contains in interface Seq<T>

    • insertBefore

      public void insertBefore(T elem, T successor)
      Description copied from interface: Seq
      Insert element `elem` into the list just before the first occurrence of element `successor`. Requires that `successor` is contained in the list and that `elem` and `successor` are not null.

      Example: If the list is [3, 8, 2], then insertBefore(1, 8) would change the list to [3, 1, 8, 2].

      Specified by:
      insertBefore in interface Seq<T>

    • remove

      public boolean remove(T elem)
      Description copied from interface: Seq
      Remove the first occurrence of element `elem` (if any) from this list. Return whether the list changed. Requires `elem` is not null.
      Specified by:
      remove in interface Seq<T>

    • equals

      public boolean equals(Object other)
      Return whether this and `other` are `ArraySeq`s containing the same elements in the same order. Two elements `e1` and `e2` are "the same" if `e1.equals(e2)`. Note that `ArraySeq` is mutable, so equivalence between two objects may change over time. See `Object.equals()` for additional guarantees.
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Returns a hash code value for the object. See `Object.hashCode()` for additional guarantees.
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • iterator

      public Iterator<T> iterator()
      Return an iterator over the elements of this list (in sequence order). By implementing `Iterable`, clients can use Java's "enhanced for-loops" to iterate over the elements of the list.
      Specified by:
      iterator in interface Iterable<T>