Package dsa.lab03.solutions

Class CircularDynamicArray<Item>

java.lang.Object
dsa.lab03.solutions.CircularDynamicArray<Item>
Type Parameters:
Item - the item type
All Implemented Interfaces:
Container<Item>, DynamicSequence<Item>, StaticSequence<Item>, Iterable<Item>
public class CircularDynamicArray<Item> extends Object implements DynamicSequence<Item>
A circular dynamic array.

A dynamic sequence implemented using an array with spare capacity and variable start index.

Dynamic operations only rarely reallocate a new array.

Improves on non-circular dynamic arrays' efficiencies with

invalid reference 
#insertFirst(Item)
and DynamicSequence.removeFirst() having (amortised) asymptotic complexity O(1).

  • Constructor Details

    • CircularDynamicArray

      public CircularDynamicArray()
      Construct an empty circular dynamic array.

    • CircularDynamicArray

      public CircularDynamicArray(Iterable<Item> items)
      Construct a circular dynamic array containing the given items.
      Parameters:
      items - the items

    • CircularDynamicArray

      public CircularDynamicArray(Iterable<Item> items, int size) throws IllegalArgumentException
      Construct a circular dynamic array containing the given items more efficiently than CircularDynamicArray(Iterable).
      Parameters:
      items - the items
      size - the number of items
      Throws:
      IllegalArgumentException - if size != n (where n is items's size)

    • CircularDynamicArray

      @SafeVarargs public CircularDynamicArray(Item... items)
      Construct a circular dynamic array containing the given items.
      Parameters:
      items - the items

  • Method Details

    • size

      public int size()
      Description copied from interface: Container
      Get the number of contained items.
      Specified by:
      size in interface Container<Item>
      Returns:
      the size

    • capacity

      public int capacity()
      Get the maximum number of items that can be contained without reallocation.
      Returns:
      the capacity

    • get

      public Item get(int index) throws IndexOutOfBoundsException
      Description copied from interface: StaticSequence
      Get the item at the given index.
      Specified by:
      get in interface StaticSequence<Item>
      Parameters:
      index - the index
      Returns:
      the item that is at that index
      Throws:
      IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)

    • set

      public void set(int index, Item item) throws IndexOutOfBoundsException
      Description copied from interface: StaticSequence
      Set the item at the given index.

      Replaces whatever item was there before.

      Specified by:
      set in interface StaticSequence<Item>
      Parameters:
      index - the index
      item - the new item that should now be at that index
      Throws:
      IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)

    • insert

      public void insert(int index, Item item) throws IndexOutOfBoundsException
      Description copied from interface: DynamicSequence
      Insert the given item at the given index.

      Increments the size, as well as the indices of all items that had the same index or higher.

      Specified by:
      insert in interface DynamicSequence<Item>
      Parameters:
      index - the index
      item - the new item
      Throws:
      IndexOutOfBoundsException - if index < 0 or index > n (where n is the size)

    • remove

      public Item remove(int index) throws IndexOutOfBoundsException
      Description copied from interface: DynamicSequence
      Remove and return the item at the given index.

      Decrements the size, as well as the indices of all items that had the same index or higher.

      Specified by:
      remove in interface DynamicSequence<Item>
      Parameters:
      index - the index
      Returns:
      the item that was at that index
      Throws:
      IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)