Set

A set is an iterable collection of unique elements. It has no particular order.

Operations include: has O(n) insert O(n) remove O(n) size O(1) find O(n)

Implementable with a linked list or with an array.

Efficiency

We can use a heuristic that moves the target of the search to the head of the list, so it can be found faster next time.

"Move to front heuristic" speeds up the linear search performance if the target is likely to be searched again.

• For arrays, a common strategy is "transpose sequential search" heruistic.

Iterator

A set iterator should iterate over the elements from head to tail in a LinkSet and from index 0 to numElements-1 in an ArraySet because a set is an unordered collection. The client shall not expect the iteration is done in any particular order.

What happens if you structurally modfiy a data structure while iterating over it.

• A structural modification is any operation that adds or deletes elements or explicitly resizes the data structure.
• In general, the results of the iteration are undefined under a structural modification.
• Suppose we assume the last element of the array will be swapped with the element to be removed. We would end iteration by not visiting the last element before removal.

In Java's Collection Frameowrk, it is prohibited for one thread to modify a Collection while another thread is iterating over it. Or else, ConcurrentModificationException will be thrown.

To make an iteration "fail-fast", we need to be able to tell that the data structure has been modified since the iteration started.

• use a version number in the data structure class to achieve this. It will start at 0 and modify whenever a structural modification is performed. Each iterator will remember what number it was created for and check for modifications by comparing version numbers. Raise an exception if there is a mismatch.

Ordered Set

An ordered-set is an iterable collection of ordered unqiue elements. The elements are expected to be iterated over in order, based on their values

public interface OrderedSet<T extends Comparable<T>> extends Set<T> {
}

• must use bounded generics to ensure that elements are comparable.

With an underlying linked list, the operations are the same as if it was an unordered set because we cannot do better than a Linear Search. Everything is still O(n)

With an underlying array, we can use binary searc, so find and has will cost O(lg n). insert and remove operations will remain linear since we must shift elements to preserve order.

Set-theoretical Operations.

Two sets can be "added" together. The union of A and B is denoted by $A \cup B$.

The intersection, denoted by $A \cap B$, is the set of elements that are members of both A and B.

The set difference of A and B, denoted by $A-B$, is the set of all elements that are in A, but not B.

Operations can be defined in the OrderedSetADT:

OrderedSet<T> union(OrderedSet<T> other);
OrderedSet<T> intersect(OrderedSet<T> other);
OrderedSet<T> subtract(OrderedSet<T> other);