Creating an Ordered List Using Array

Introduction

The class Array found in darray.h can be used like a list since it has insert and delete functions as well as an iterator. If you want to create an ordered list, you want to make sure you hide the insertItem, insertItemAt and the deleteItemAt functions and override the Find function, or the user could use your ordered list as a list destroying the ordering. You could make the OrderedList class a protected descendent of Array, but this is more complicated than implementing OrderedList that contains an Array.

The Design

First we must decide which functions we will need and then how we will implement the iterator. I felt that in this case only insertItem, deleteItem, find, and the [] operator were necessary. I only allowed [] to be used to retrieve values by returning a value and makeing this a constant operator. The iterator is almost a carbon copy of the array iterator, except that I have to initialize from the _array member item of OrderedList. This means I have to have access to the private member _array in OrderIterator. I accomplished this by making OrderIterator a friend of OrderedList.

template < class Type>
class OrderedList
{
friend OrderIterator< Type>;
public:
	OrderedList(int size=0,int delta=1):_array(size,delta){}
	int insertItem(const Type&); //-1 if fail where if succeed
	Type deleteItem(const Type&); //returns data at deleted node
	int find(const Type&)const; //-1 if not found subscript otherwise
	Type operator [] (int)const; //access to location, but cannot set
private:
	Array< Type> _array;
};

template < class Type>
class OrderIterator
{
public:
	OrderIterator(OrderedList< Type> &t):_array(t._array){init();}
	void init(){_loc = 0;}
	int operator ++(){return _loc++;}
	int operator ++(int){return _loc++;}
	Type operator ()()const{return _array[_loc];}
	Type& operator()(){return _array[_loc];}
	operator int(){return _loc < _array.numberInArray();}
private:
	Array &_array;
	int _loc;
};

The Functions

The OrderedList functions are for the most part straight forward and need little explanation.

template < class Type>
int OrderedList< Type>::insertItem(const Type &x)
{
	int where = 0;
	for (;where < _array.numberInArray();where++)
		if (_array[where]>=x)
      			break;
	_array.insertItemAt(x,where);

}

template < class Type>
Type OrderedList< Type>::deleteItem(const Type &x)
{
	int where = find(x);
	Type rval;
	if(where >=0)
	{
		rval = _array[where];
		_array.deleteItemAt(where);
		return rval;
	}
   return rval;
}

template < class Type>
int OrderedList< Type>::find(const Type &x)const
{
	for (int where =0;where<_array.numberInArray();where++)
		if (_array[where]==x)
			return where;
	return -1;
}

template < class Type>
Type OrderedList< Type>::operator [] (int i)const
{
	return _array[i];
}

Complete Copy

To get a complete copy of the code click here.