SortedTable Classes

  

  

Figure 3.2: SortedTable Interface

The SortedTable interface (See Figure 3.2) is implemented in the SortedPointerTable class and the SortedObjectTable class.

Each class is a template class representing a sorted table of elements. The elements must implement the SortableObject interface. Since the elements in the table is sorted, any element in the table is accessible via binary searching algorithm.

The constructors initialize the table by another table or just allocate the memory area for the table.

There are four overloaded operators - [key], (index), += element, and -= key or element. When an instance of the SortedTable is named table, table[key] returns the element with the key, table(index) returns the index-th element of the table where the index of the first element is 0. The number of elements in the table is obtained by the accessor getSize().

The statement table += element inserts the element in the table. No two elements with the same key can be inserted in the table. The overloaded operator has two signatures - table -= key and table -= element. The former removes the element with the key from the table, whereas the latter removes the element which has the same identity as the specified element.

The operation removeAll() literally removes all elements in the table.

The remaining two operations - searchByKey() and searchByElement() - should be used carefully. These operations return the index which would be suitable for the element if it were to be inserted. Therefore, these operation may return the next index of that of the last element, which is invalid in the table(index) operator. The element at the returned index may be different from or equal to the specified element.