InfoMagic Source Code 1993 July/THE_SOURCE_CODE_CD_ROM.iso/gnu/nihcl-3.0/lib/Bag.c

C/C++ Source or Header | 1990-05-19 | 5.3 KB | 253 lines

/* Bag.c -- implementation of a Set of Objects with possible duplicates

    THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
    "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
    AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
    CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
    PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
    RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.

Author:
    K. E. Gorlen
    Bg. 12A, Rm. 2033
    Computer Systems Laboratory
    Division of Computer Research and Technology
    National Institutes of Health
    Bethesda, Maryland 20892
    Phone: [phone]
    uucp: uunet!nih-csl!kgorlen
    Internet: [e-mail]
    September, 1985

Function:

A Bag is like a Set, except Bags can contain multiple occurrences of
equal objects.  Bags are implemented by using a Dictionary to associate
each object in the Bag with its number of occurrences.

$Log:    Bag.c,v $
 * Revision 3.0  90/05/20  00:19:06  kgorlen
 * Release for 1st edition.
 *
*/

#include "Bag.h"
#include "AssocInt.h"
#include "Integer.h"
#include "nihclIO.h"

#define    THIS    Bag
#define    BASE    Collection
#define BASE_CLASSES BASE::desc()
#define MEMBER_CLASSES Dictionary::desc()
#define VIRTUAL_BASE_CLASSES

DEFINE_CLASS(Bag,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/Bag.c,v 3.0 90/05/20 00:19:06 kgorlen Rel $",NULL,NULL);

extern const int NIHCL_REMOVEERR;

Bag::Bag(unsigned size) : contents(size)
{
    count = 0;
}

Bag::Bag(const Bag& b) : contents(b.contents)
{
    count = b.count;
    Object* a;
    Iterator i(contents);
    while (a = i++) contents.at(i.index-1) = a->shallowCopy();
}

Bag::~Bag()
{
    DO(contents,AssocInt,a) delete a; OD;
}

void Bag::operator=(const Bag& b)
{
    if (this == &b) return;
    DO(contents,AssocInt,a) delete a; OD;
    contents = b.contents;
    count = b.count;
    Object* a;
    Iterator i(contents);
    while (a = i++) contents.at(i.index-1) = a->shallowCopy();
}

void Bag::reSize(unsigned newSize)
{
    contents.reSize(newSize);
}

Object* Bag::addWithOccurrences(Object& ob, unsigned n)
{
    AssocInt* a = (AssocInt*)contents.assocAt(ob);
    Object* o = &ob;
    if (a == 0) {
            a = new AssocInt(ob,n);
        contents.add(*a);
    }
    else {
        Integer& i = *Integer::castdown(a->value());
        o = a->key();
        i.value(i.value()+n);
    }
    count += n;
    return o;
}

Object* Bag::add(Object& ob)
{
    return addWithOccurrences(ob,1);
}

Object*& Bag::at(int i)                    { return contents.at(i); }

const Object *const& Bag::at(int i) const    { return contents.at(i); }

unsigned Bag::capacity() const { return contents.capacity(); }

void Bag::deepenShallowCopy()
{
    BASE::deepenShallowCopy();
    contents.deepenShallowCopy();
}

Object* Bag::doNext(Iterator& pos) const
{
    const AssocInt* a;
    while (YES) {
        if (pos.num == 0) {
            a = AssocInt::castdown(contents.doNext(pos));
            if (a == NULL) return NULL;
        }
        else a = AssocInt::castdown(contents.at(pos.index-1));
        if (pos.num++ < (Integer::castdown(a->value()))->value())
            return a->key();
        pos.num = 0;
    }
}

void Bag::dumpOn(ostream& strm) const
{
    strm << className() << '[';
    DO(contents,AssocInt,a) a->dumpOn(strm); OD
    strm << "]\n";
}

Object* Bag::remove(const Object& ob)
{
    AssocInt* a = (AssocInt*)contents.assocAt(ob);
    Object* rob = 0;        // return NULL until last occurrence removed
    if (a == 0) setError(NIHCL_REMOVEERR,DEFAULT,this,className(),ob.className(),&ob);
    Integer* i = Integer::castdown(a->value());
    unsigned n = (unsigned)(i->value());
    if (--n == 0) {
        rob = a->key();
        delete AssocInt::castdown(contents.remove(*a));
    }
    else i->value(n);
    --count;
    return rob;
}

void Bag::removeAll()
{
    DO(contents,AssocInt,a) delete a; OD;
    contents.removeAll();
    count = 0;
}

bool Bag::operator==(const Bag& b) const
{
    return count==b.count && contents==b.contents;
}

unsigned Bag::hash() const    { return count^contents.hash(); }

bool Bag::isEqual(const Object& p) const
{
    return p.isSpecies(classDesc) && *this==castdown(p);
}

const Class* Bag::species() const { return &classDesc; }

unsigned Bag::occurrencesOf(const Object& ob) const
{
    AssocInt* a = (AssocInt*)contents.assocAt(ob);
    if (a == 0) return 0;
    else return (Integer::castdown(a->value()))->value();
}

unsigned Bag::size() const    { return count; }

Bag Collection::asBag() const
{
    Bag cltn(MAX(size(),DEFAULT_CAPACITY));
    addContentsTo(cltn);
    return cltn;
}

static unsigned bag_capacity;

Bag::Bag(OIOin& strm)
:
#ifdef MI
    Object(strm),
#endif
    BASE(strm),
    contents((strm >> bag_capacity, bag_capacity))
{
    count = 0;
    unsigned i,n;
    strm >> n;        // read bag size
    while (n--) {
        strm >> i;
        addWithOccurrences(*Object::readFrom(strm),i);
    }
}

void Bag::storer(OIOout& strm) const
{
    BASE::storer(strm);
    strm << contents.capacity() << contents.size();
    DO(contents,AssocInt,a)
        strm << (Integer::castdown(a->value()))->value();
        (a->key())->storeOn(strm);
    OD
}

Bag::Bag(OIOifd& fd)
:
#ifdef MI
    Object(fd),
#endif
    BASE(fd),
    contents((fd >> bag_capacity, bag_capacity))
{
    count = 0;
    unsigned i,n;
    fd >> n;
    while ( n-- ) {
        fd >> i;
        addWithOccurrences(*Object::readFrom(fd),i);
    }
}

void Bag::storer(OIOofd& fd) const
{
    BASE::storer(fd);
    fd << contents.capacity() << contents.size();
    DO(contents,AssocInt,a)
        fd << (Integer::castdown(a->value()))->value();
        (a->key())->storeOn(fd);
    OD
}

int Bag::compare(const Object&) const
{
    shouldNotImplement("compare");
    return 0;
}