#include <stdlib.h>

//  A bag is a collection in which an item can appear more than once.
//  This is an implementation of a bag of integers. The operations are
//  a constructor, a destructor, predicates full and empty, and an
//  iterator and a way to reset it, an insertion, a deletion, and a
//  predicate to test if a given integer is in the bag.

//  Data:

//  Basis: X is a bounded bag <=> X is a bag of .
//  Invariant: X never has more than MAX elements in it.

template <class T>
class bagnode {
public:
  T data;
  bagnode * link;
  //  friend class bag<T>;
};

template <class T>
class bag {
  bagnode<T> head;
  bagnode<T> * cursor;

// Operations:

public:

  bag(int max = 20);
//    pre:  None
//    post: An integer bag object is created.

  ~bag(void);
//    pre:  None
//    post: The object is destroyed and its memory recovered.

  int count(void);
//    pre:  None
//    post: result = the number of elements in the object.

  int full(void);
//    pre:  None
//    post: result = 0 if the object is not full, 1 otherwise.

  int empty(void);
//    pre:  None
//    post: result = 0 if the object is not empty, 1 otherwise.

  T * insert(T x);
//    pre:  The object is not full
//    post: x appears once more in the object than it did before the call

  void remove(T x);
//    pre:  None
//    post: if x was in the object before the call, it appears one less time.
//          If it was not in the object before the call, no action is taken.

  int has(T x);
//    pre:  None
//    post: If x is in the object, result = 1, otherwise result = 0.

  T * next(void);
//    pre:  None
//    post: result = a pointer to the next integer in the bag. NULL is 
//          returned if the last integer has already been returned. Calls
//          to next are guaranteed to eventually return all elements in
//          the bag exactly once.

  void resetcursor(void);
//    pre:  None
//    post: The next routine starts fresh from the beginning of the bag.

};

#include"bag.cpp"