// $Id: Bag.h,v 1.3 1995/04/23 20:07:15 leavens Exp leavens $

#ifndef Bag_h
#define Bag_h

#include "bool.h"

typedef long int ItemType;

class Bag {

    // ABSTRACTLY: a set of pairs of the form (item: ItemType, count: int)
    // (See HR page 428 for operations on tuples used below.)

    // CLASSINV: If x and y are distinct elements,
    // then item(x) and item(y) are not equal.
    // Also, if x is an element, then count(x) >= 0.

public:
    Bag(int hashTableSize);
        // PRE: hashTableSize > 0
        // MODIFIES: self
        // POST: the set is empty
        // NOTE: hashTableSize is used to tell the implementation how big
        // of a hash table to allocate.  It's best if this is a prime.

    Bag(const Bag& oth);
        // MODIFIES: self
        // POST: makes the state of self be the same as the state of oth

    ~Bag();
        // MODIFIES: self
        // POST: any dynamically allocated memory is returned.

    Bag& operator = (const Bag& oth);
        // MODIFIES: self
        // POST: IF self is a different object than oth (this != &oth),
        //       THEN makes the state of self be the same as the state of oth

    void AddNTimes( ItemType it, int N );
        // PRE: N > 0
        // MODIFIES: self
        // POST: IF there is an element x in self<entry>
        // such that item(x) = it,
        // THEN self == (self<entry> - {x}) UNION {(item(x), count(x)+N)}
        // ELSE self == self<entry> UNION {(it, N)}

    void DeleteNTimes( ItemType it, int N );
        // PRE: N > 0
        // MODIFIES: self
        // POST: IF there is an element x in self<entry>
        // such that item(x) = it,
        // THEN self == (self<entry> - {x})
        //                   UNION {(item(x), MAX(count(x)-N, 0)}
        // ELSE self == self<entry>

    int Count( ItemType it ) const;
        // POST: IF there is an element x in self<entry>
        // such that item(x) = it,
        // THEN FCTVAL == count(x) ELSE FCTVAL == 0

    int Size() const;
        // POST: FCTVAL is the sum of count(x), for all elements x in self

    ItemType Least() const;
        // PRE: self is not empty
        // POST: FCTVAL is the least (in the < ordering on ItemType)
        // element of self.

#include "Bag.pri"
};
#endif