Template ≪Class List_entry≫ Class List { Public: // Specifications For The Methods Of The List ADT Go Here. List(); Int Size() Const; Bool Full()

template

class List {

public:

// Specifications for the methods of the list ADT go here.

List();

int size() const;

bool full() const;

bool empty() const;

void clear();

void traverse(void (*visit)(List_entry &));

Error_code retrieve(int position, List_entry &x) const;

Error_code replace(int position, const List_entry &x);

Error_code remove(int position, List_entry &x);

Error_code insert(int position, const List_entry &x);

Error_code double_insert(int position, const List_entry &x1, const List_entry &x2);

// The following methods replace compiler-generated defaults.

~List();

List(const List ©);

List operator =(const List ©);

protected:

// Data members for the linked list implementation now follow.

int count;

Node *head;

// The following auxiliary function is used to locate list positions

Node* set_position(int position) const;

};

template

List::List() {

/**

* Post: The List is initialized to be empty.

*/

count = 0;

head = NULL;

}

template

void List::clear() {

/**

* Post: The List is cleared.

*/

Node *p, *q;

for (p = head; p; p = q) {

q = p->next;

delete p;

}

count = 0;

head = NULL;

}

template

int List::size() const {

/**

* Post: The function returns the number of entries in the List.

*/

return count;

}

template

bool List::empty() const {

/**

* Post: The function returns true or false according as the List is empty or not.

*/

return count =>

}

template

bool List::full() const {

/**

* Post: The function returns 1 or 0 according as the List is full or not.

*/

return false;

}

template

void List::traverse(void (*visit)(List_entry &)) {

/**

* Post: The action specified by function (*visit) has been performed on every

* entry of the List, beginning at position 0 and doing each in turn.

*/

Node *q;

for (q = head; q; q = q->next)

(*visit)(q->entry);

}

template

Error_code List::insert(int position, const List_entry &x) {

/**

* Post: If the List is not full and 0 =>=>

* where n is the number of entries in the List,

* the function succeeds:

* Any entry formerly at

* position and all later entries have their

* position numbers increased by 1, and

* x is inserted at position of the List.

*

* Else:

* The function fails with a diagnostic error code.

*/

if (position count)

return range_err;

Node *new_node, *previous, *following;

if (position > 0) {

previous = set_position(position - 1);

following = previous->next;

}

else following = head;

new_node = new Node(x, following);

if (new_node == NULL)

return overflow;

if (position == 0)

head = new_node;

else

previous->next = new_node;

count++;

return success;

}

template

Error_code List::double_insert(int position, const List_entry &x1, const List_entry &x2) {

/**

* Post: If the List is not full and 0 =>=>

* where n is the number of entries in the List,

* the function succeeds:

* Any entry formerly at

* position and all later entries have their

* position numbers increased by 1, and

* x is inserted at position of the List.

*

* Else:

* The function fails with a diagnostic error code.

*/

}

template

Error_code List::retrieve(int position, List_entry &x) const {

/**

* Post: If the List is not full and 0 =>

* where n is the number of entries in the List,

* the function succeeds:

* The entry in position is copied to x.

* Otherwise the function fails with an error code of range_err.

*/

Node *current;

if (position = count) return range_err;

current = set_position(position);

x = current->entry;

return success;

}

template

Error_code List::replace(int position, const List_entry &x) {

/**

* Post: If 0 =>

* where n is the number of entries in the List,

* the function succeeds:

* The entry in position is replaced by x,

* all other entries remain unchanged.

* Otherwise the function fails with an error code of range_err.

*/

Node *current;

if (position = count) return range_err;

current = set_position(position);

current->entry = x;

return success;

}

template

Error_code List::remove(int position, List_entry &x) {

/**

* Post: If 0 =>

* where n is the number of entries in the List,

* the function succeeds:

* The entry in position is removed

* from the List, and the entries in all later positions

* have their position numbers decreased by 1.

* The parameter x records a copy of

* the entry formerly in position.

* Otherwise the function fails with a diagnostic error code.

*/

Node *prior, *current;

if (count == 0) return fail;

if (position = count) return range_err;

if (position > 0) {

prior = set_position(position - 1);

current = prior->next;

prior->next = current->next;

}

else {

current = head;

head = head->next;

}

x = current->entry;

delete current;

count--;

return success;

}

template

Node *List::set_position(int position) const {

/**

* Pre: position is a valid position in the List;

* 0 =>

* Post: Returns a pointer to the Node in position.

*/

Node *q = head;

for (int i = 0; i next;

return q;

}

template

List::~List() {

/**

* Post: The List is empty: all entries have been removed.

*/

clear();

}

template

List::List(const List ©) {

/**

* Post: The List is initialized to copy the parameter copy.

*/

count = copy.count;

Node *new_node, *old_node = copy.head;

if (old_node == NULL) head = NULL;

else {

new_node = head = new Node(old_node->entry);

while (old_node->next != NULL) {

old_node = old_node->next;

new_node->next = new Node(old_node->entry);

new_node = new_node->next;

}

}

}

template

List List::operator =(const List ©) {

/**

* Post: The List is assigned to copy a parameter

*/

List new_copy(copy);

clear();

count = new_copy.count;

head = new_copy.head;

new_copy.count = 0;

new_copy.head = NULL;

return *this;

}