// UnsortedType.h
// Class is templated.
// Items are in a linked list.

template<class ItemType>
struct NodeType
{
    ItemType info;
    NodeType* next;
};


//Notice that interface is same as the array implementation of UnsortedType.

// Assumption:  ItemType is a type for which the operators "=" and "==" are 
// defined either an appropriate built-in type or a class that overloads 
// these operators.

template <class ItemType>
class UnsortedType   
{
public:
    UnsortedType();		
    ~UnsortedType();   	        

    bool IsFull() const;

    int  LengthIs() const;

    void MakeEmpty();

    void RetrieveItem(ItemType& item, bool& found);
    // Function: Retrieves list element whose key matches item's key (if present).
    // Post: If there is an element someItem whose key matches item's key,
    //       then found = true and item is a copy of someItem; otherwise
    //       found = false and item is unchanged.
    //       List is unchanged.

    void InsertItem(ItemType item);
    // Function: Adds item to list.
    // Pre:  List is not full.
    // Post: item is in list.

    void DeleteItem(ItemType item);
    // Function: Deletes the element whose key matches item's key.
    // Pre:  Key member of item is initialized.
    //       One and only one element in list has a key matching item's key.
    //      DFW: will get rid of above for precondition for homework.
    // Post: No element in list has a key matching item's key.
    //  homework modifies this postcondition.

    void ResetList();
    //Function: Initializes current position for an iteration through the list.
    //Post: Current position is prior to list.

    void GetNextItem(ItemType&);
    // Function: Gets the next element in list.
    // Pre:  Current position is defined.
    //       Element at current position is not last in list.
    // Post: Current position is updated to next position.
    //       item is a copy of element at current position.

private:
    NodeType<ItemType>* listData;    //pointer to front of linked list
    int length;                      //handy-dandy length of the list
    NodeType<ItemType>* currentPos;  //used by iterator
};


#include "UnsortedType.cpp"