#include <stdlib.h>

//  A bag is a collection in which an item can appear more than once.
//  This is an implementation of a bag. 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 data is in the bag.

//  Data:

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

template <class T, int max, T empty, T deleted>
class bag {
  T * data;
  int size;
  int cursor;

// Operations:

public:

  bag(void);
//    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.

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

  void remove(T x, int h);
//    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, int h);
//    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 object in the bag. NULL is 
//          returned if the last object has already been returned. Calls
//          to next are guaranteed to eventually return all elements in
//          the bag exactly once. No inserts or removes may be done between
//          subsequent calls to next.

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

};

#include "bag_array_dhash.cpp"