Ordered List Abstract Data Type

The ADT designer writes the ordered list ADT specification:

Each item stored in the ordered list has a key and an info part.

The ordered list sorts its items by ascending key values.

No two items can have the same key value.

Prototype: bool Search( /* in */ int key, /* out */ Info& info );

Purpose: Search the ordered list for an item.

Preconditions:

Postconditions: If the item is found whose stored key == key, then Function value = true and info = item's info.
Otherwise Function value = false.

Prototype: bool Insert( /* in */ int key, /* in */ Info info );

Purpose: Insert a new item into the ordered list at its correct position according to the ordered list's sort order.

Preconditions: The ordered list is not full.

Postconditions: If there was no item in the ordered list whose stored key == key, then the new item has been inserted into the ordered list at its correct position and Function value = true.

Otherwise, the ordered list is unchanged and Function value = false.

Prototype: bool Delete( /* in */ int key );

Purpose: Delete an item from the ordered list.

Preconditions: The ordered list is not empty.

Postconditions: If there was an item in the ordered list whose stored key == key, then it has been deleted from the ordered list and Function value = true.

Otherwise, the ordered list is unchanged and Function value = false.

Prototype: bool IsEmpty() const;

Purpose: Determines if the ordered list is empty.

Preconditions:

Postconditions: Function value = true, if the ordered list is empty, otherwise false.

Prototype: bool IsFull() const;

Purpose: Determines if the ordered list is full.

Preconditions:

Postconditions: Function value = true, if the ordered list is full, otherwise false.

Prototype: int Size() const;

Purpose: Return the size of the ordered list.

Preconditions:

Postconditions: Function value = the number of items in the ordered list.

Prototype: void Reset();

Purpose: Initialize a traversal of the ordered list.

Preconditions: The ordered list is not empty.

Postconditions: The list traversal cursor is positioned on the first item

Prototype: void Advance( /* out */ int& key, /* out */ Info& info );

Purpose: Return the current item, and then advance the list traversal cursor to the next item in the ordered list.

Preconditions: The traversal of the ordered list has been initialized.
There is a current item.
There have been no intervening insertions or deletion into the ordered list since the last traversal reset.

Postconditions: key == the stored key of the current item.
info == the stored info of the current item.

If there is a next item, the list traversal cursor has advanced to it, otherwise the list traversal cursor is undefined.

Header file OrderedList.h

#ifndef ORDERED_LIST_H

#define ORDERED_LIST_H

const int MAX_SIZE_ORDERED_LIST = ...;

const int MAX_LENGTH_NAME = ...;

struct Info

{

char lastname[MAX_LENGTH_NAME+1];

char firstname[MAX_LENGTH_NAME+1];

double salary;

};

class OrderedList

{

public:

OrderedList();

bool Search( /* in */ int key, /* out */ Info& info );

bool Insert( /* in */ int key, /* in */ Info info );

bool Delete( /* in */ int key );

int Size() const;

void Reset();

void Advance( /* out */ int& key, /* out */ Info& info );

bool IsEmpty( void ) const;

bool IsFull( void ) const;

private:

struct Item

{

int key;

Info info;

};

Item items[MAX_SIZE_ORDERED_LIST];

int size;

int current;

};

#endif