Task 3: Sets

Look at the Set interface in the set package. It is the Set ADT from the course, with add, remove, contains, and size. A set has no order, so an implementation may reorder its items whenever it likes, even inside contains.

ArraySet, the array-based set from the course, is given. Its contains is a linear search, its add appends at the end, and its remove moves the last item into the gap.

You will write four array-based implementations of Set. Each one also implements Measured, and counts by the same definitions as MeasuredArrayList, with the same two choices from Task 1.

  • MeasuredArraySet is ArraySet with the counting added, the way MeasuredArrayList is ArrayList with the counting added.
  • MeasuredSortedArraySet keeps its items in ascending order. Its contains is a binary search. Its add and remove shift items to keep the order.
  • MeasuredTransposeArraySet works like MeasuredArraySet, except in contains: when it finds an item, it swaps the item with the one just before it, unless the item is already first.
  • MeasuredMoveToFrontArraySet keeps its items in a circular array, the way ArrayDeque does in the deque chapter. Its add appends at the back. When contains finds an item, it moves the item to the front. Its remove keeps the other items in their order.

Use the private helpers each starter class declares, and read the comment above each one: it says what the helper must do.

The lecture notes say move-to-front does not fit an array, since moving an item to the front shifts every item before it. A circular array changes that. Your moveToFront must move whichever are fewer: the items before the target, or the items after it. When they are as many, it moves the items before it. remove must close its gap the same way.

The auto-test checks the order of the items in each array and the counts of each operation, and it calls the private helpers directly.