CompSci Mon Feb 16th

Specification, Design, and Implementation of RayBag

Overview

  • Discusses the process of specification, design, and implementation, particularly focusing on a container class named ArrayBag.
  • The ArrayBag is a bag of integers with an underlying data structure of an array.
  • An emphasis on test-first design and method specifications.

Specification of ArrayBag

  • Specification process for the ArrayBag includes defining its methods and how they work.
  • Two key fields are specified:
    • data: An array that holds the integers.
    • manyItems: An integer that tracks how many elements in the array are being used.
  • This design allows the use of a partially filled array rather than creating a new array for each add or delete operation.

Class Invariants

  • The invariant of the ArrayBag class defines how fields should be maintained:
    • The number of items (manyItems) must never exceed the length of the array (data.length).
    • For an empty bag, the irrelevant data in the data array does not matter.
    • For a non-empty bag, relevant data is stored from data[0] to data[manyItems - 1], and anything beyond that is irrelevant.

Implementation Stage

  • The final creation of a new class involves writing the code for its methods.
  • Implementation requires adherence to established rules to increase the likelihood of correctness on the first attempt.
  • The method design is iterative, involving bug fixing and continuous improvement, common in object-oriented programming.

ArrayBag Class Fields and Constructors

  • Fields:

    • data: Represents the array holding integers.
    • manyItems: Stores the count of how many valid items are in data.

  • Zero Argument Constructor:

    • Initializes manyItems to zero and sets the default capacity of the bag to 10.
    • Runtime is $O(1)$ (constant time), as the size is fixed and predefined.

  • One Argument Constructor:

    • Accepts an initialCapacity parameter.
    • If initialCapacity is negative, throws an IllegalArgumentException.
    • If valid, creates a new bag with the specified capacity.
    • The runtime complexity is $O(n)$ with respect to n, where n is the initialCapacity, as it requires time proportional to the capacity to create the array.

Method Details

Add Method
  • Signature: public void add(int element)
  • Functionality:
    • Checks if the bag is full (manyItems == data.length).
    • If full, calls ensureCapacity(manyItems * 2 + 1) to expand the capacity.
    • Adds the element to the next available spot in the data array and increments manyItems.
  • Runtime Complexity:
    • Primarily depends on the ensureCapacity method. If not full and elements are added, this is $O(1)$ for operations.
    • Worst-case for ensureCapacity is $O(n)$ due to necessary copying of elements.
EnsureCapacity Method
  • Signature: public void ensureCapacity(int minimumCapacity)
  • Functionality:
    • Checks if data.length < minimumCapacity.
    • If so, a new array is created with size minimumCapacity, and the current data is copied to it.
  • Runtime Complexity:
    • Time to create a new array is $O(n)$ for n elements. The copy operation also tends to scale linearly with manyItems at worst case.
AddAll Method
  • Signature: public void addAll(ArrayBag addend)
  • Functionality:
    • Calls ensureCapacity for the sum of manyItems and addend.manyItems.
    • Copies all elements from the addend bag to the current bag's data array.
  • Runtime Complexity:
    • Approaches $O(total items)$ combining current items and added items due to array copying.
CountOccurrences Method
  • Signature: public int countOccurrences(int target)
  • Functionality:
    • Iterates over all valid items in the bag and counts how many times target appears.
  • Runtime Complexity:
    • The for-loop runs manyItems times, leading to a complexity of $O(manyItems)$.
Remove Method
  • Signature: public boolean remove(int target)
  • Functionality:
    • Searches for target; if found, replaces it with the current last item (to maintain order and optimize performance).
    • Decreases manyItems regardless of the position of target found.
  • Runtime Complexity:
    • Search complexity is $O(manyItems)$, while the deletion operation is $O(1)$ due to direct index manipulations.
TrimToSize Method
  • Signature: public void trimToSize()
  • Functionality:
    • Resizes the underlying array to the current number of items if it differs from capacity.
    • Uses array copying to create a new smaller array if necessary.
  • Runtime Complexity:
    • Similar to ensureCapacity, depends on current manyItems, hence $O(manyItems)$.
Union Method (Static)
  • Signature: public static ArrayBag union(ArrayBag b1, ArrayBag b2)
  • Functionality:
    • Combines elements from two bags into a new ArrayBag, preserving all items.
  • Runtime Complexity:
    • Overall is $O(b1.capacity + b2.capacity + b1.manyItems + b2.manyItems)$, as both capacities and current sizes contribute to the resource requirements.

Summary

  • The ArrayBag class provides a robust structure for a bag of integers, supporting operations like adding, removing, and combining bags efficiently with a focus on maintaining invariants and optimizing performance through careful capacity management.
  • Runtime analysis is crucial for understanding the efficiency of different methods in this implementation.