The Simons     Component Library

           

---

Bag.h

//
//  SCL : Simons Component Library
//
//
//  Filename:   Bag.h
//  Contents:   Bag class
//  Author:     Anthony J H Simons
//  Revised:    22 November 2005

// This software is distributed free in the hope that others will
// find it useful.  However, it comes WITHOUT ANY WARRANTY.  No
// liability can be accepted for software failure, merchantability
// or fitness for a particular purpose.  You can redistribute this
// software in its original form, or in a modified form, provided
// that this disclaimer is retained in the file banner.

#ifndef SCL_BAG
#define SCL_BAG

#include "Unordered.h"          // Include my superclass type
#include "BagID.h"              // Include my pointer type

#include "EntryID.h"            // Depend on the pointer type


class Bag : public Unordered {
private:
        Natural alloc;                  // capacity of table
        Natural slots;                  // used hash table slots
        Natural items;                  // count of elements
        struct Link {
                ObjectID item;
                Link* next;
                Link(ObjectID& o, Link* n) : item(o), next(n) {}
        } **block;
        struct Memo {
                Integer index;          // index of item-rank
                Integer slot;           // place in hash table
                Link* link;             // referenced link
                Memo() : index(0), slot(0), link(0) {}
        } *memo;
        enum Constants { OFFSET = 3 };
        Integer locate(ObjectID) const;
        Void expand();                  // expand hash table
        Void compact(Integer);          // rehash after remove
        Void memoSeek(Integer) const;   // find ith element
        Void memoReset() const;         // find 0th element
protected:
        Bag(const Bag&);
        Void deepAdd(EntryID);
        Void deepRemove(EntryID);
public:
        Bag();
        virtual ~Bag();
        Bag(CollectionID);
        virtual ObjectID clone() const;
        virtual Natural size() const;
        virtual Boolean has(ObjectID) const;
        virtual Natural count(ObjectID) const;
        virtual ObjectID find(ObjectID) const;
        virtual ObjectID item(Integer) const;
        virtual Void add(ObjectID);
        virtual Void remove(ObjectID);
        Void clear(ObjectID);
};



inline BagID::BagID() {}

inline BagID::~BagID() {}

inline BagID::BagID(const Null* null) :
        UnorderedID(null) {}
        
inline BagID::BagID(const Bag* bag) :
        UnorderedID(bag) {}
        
inline BagID::BagID(const BagID& pointer) :
        UnorderedID(pointer) {}
        
inline BagID& BagID::operator=(const Bag* bag) {
        assign(bag);
        return *this;
}

inline BagID& BagID::operator=(const BagID& pointer) {
        assign(pointer);
        return *this;
}


#endif

---