SortedArray

When elements must be stored in order for efficient searching and convenient output, and the number of elements is likely to remain relatively stable, SortedArray storage is a good option. SortedArray is a class derived from Array that restricts insertion to ensure that the elements be stored in order. Binary search then reduces search time to $O(\log n)$. SortedArray is the storage medium used for the vertex set of LINK's graphs.

  

Figure 2.12: Arrays and SortedArrays

The methods of SortedArray are listed below. Any Array method not listed or redefined is inherited.

1. Creation

 

SortedArray<Item> a;

Creates an empty dynamic sorted array. A default size of sizeof(Item) * DEFAULT_SIZE (see general.h) is used. O(1)

SortedArray<Item> a( (int) sz);

Creates an dynamic sorted array with a block of space large enough to store sz Items. O(1)

SortedArray<Item> a( (SortedArray<Item>&) a);

Creates an dynamic sorted array with a block of space as large as that of a and initializes it with the elements of a such that order is preserved. O(n)

SortedArray<Item> a( (Container<Item>&) c);

Creates an dynamic array with storage of default size and initializes it with the elements of c. Note that the elements of c may not be stored in order, leading to a worst case running time of O(n²).

2. Operations

SortedArray<Item>& operator= (SortedArray<Item>& a)

Allocate space large enough to hold the elements of a, then copy its contents such that order is preserved.

ContainerNode * insert (Item item)

Insert item into the SortedArray such that order is preserved. If this operation would extend the active range of cells beyond the current allocation, reallocate the Array and recopy the elements. Note: The return type is ContainerNode* so that this method may be called from Container pointers or references. However, since there is no packaging node structure in Array, a NULL pointer is returned. O(n)

ContainerNode * append (Item item)

The same as insert(Item item), except that the new item is added to the empty cell adjacent to the cell in the array's active range of largest index if the operation does not violate the invariant that the elements be stored in order. Otherwise, the new item is inserted in order O(1)

Bool sortedQ () const

Return TRUE. O(1).

int search (Item)

Search for an item in the active range of the array using binary search and return its index if it is found. Return -1 otherwise $O(\log n)$ .

Item min ()

The Container method is redefined to take advantage of the ordered elements. O(1)

Item max ()

The Container method is redefined to take advantage of the ordered elements. O(1)