Should we offer a set operation?

We have add, contains, indexOf, remove, get, and size. DynamicArray has one more: set(index, value), which overwrites the value at a given index. Should SortedArray offer it too? Let’s try it and see what happens. Start from [1, 4, 7, 9], and have a client call:

sorted.set(1, 100);  // overwrite index 1

The result is [1, 100, 7, 9], which is no longer sorted. The invariant is broken. The client broke it from the outside with one call.

Every method on this class assumes the array is sorted. insertionPoint compares against the middle element and discards half the array based on that comparison. set can move a value to a position where it is no longer sorted relative to its neighbors, and once that happens insertionPoint returns wrong answers, which breaks every other method that relies on it. The client cannot be trusted to use set correctly, so we cannot offer it.

Could we fix it by having set put the value at its sorted position instead of at the given index? Then it is not set anymore. set(1, 100) would have to ignore the 1, and effectively be add with a confusing extra parameter.

So SortedArray does not provide set. The client does not choose the position of an element. The position is determined by the element’s value and the sorted order. A client who wants a different value in the collection calls remove on the old one and add on the new one, and each call puts the array back in sorted order.

The contract determines the operations

Back in the dynamic array chapter I said a data structure is defined by its contract, the promises it makes about its behavior. A SortedArray’s contract includes a promise that the array is always sorted. That promise determines which operations the structure can offer.

  • add and remove are fine. Each one can do its job and still leave the array sorted, as we saw.
  • set is not. Its job is to let the client put a chosen value at a chosen index, and the invariant forbids that.

Compare that with DynamicArray, which makes no promise about order. There, set is harmless, because there is no order for it to violate.