Set.cc

Go to the documentation of this file.

/*
 * Set.cc
 *
 * Smalltalk like class library for C++
 * Growable collection, not index-accessible.
 *
 * Copyright (c) 2003 Milan Cermak
 */
/*
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include <stlib/Set.h>
#include <stlib/Array.h>
#include <stlib/Iterator.h>
#include <stlib/String.h>
#include <stlib/NotFoundError.h>

/* public methods */

Set::Set(int length)
{
    content = new Array(length);
    tally = 0;
}

Set::~Set(void)
{
    delete content;
}

/* Copying protocol */
Set::Set(Set &origin)
{
    tally = origin.tally;
    content = (Array *) origin.content->copy();
}

/* Class-accessing protocol */
String *Set::className(void) const
{
    return new String("Set");
}

/* Accessing protocol */
long Set::capacity(void) const
{
    return content->size();
}

long Set::size(void) const
{
    return tally;
}

Object *Set::any(void)
{
    return content->any();
}

/* Adding protocol */
void Set::add(Object *obj)
{
    int index;

    if (obj == nil) return;
    index = findElementOrNil(obj);
    if (isEmptyAt(index))
        atNewIndexPut(index, obj);
}

/* Converting protocol */
Set *Set::asSet(void)
{
    return this;
}

/* Copying protocol */
Object *Set::copy(void)
{
    return new Set(*this);
}

Object *Set::copyEmpty(long size)
{
    return new Set(size);
}

/* Removing protocol */
Object *Set::remove(Object *obj)
{
    int index;

    index = findElementOrNil(obj);
    if (isEmptyAt(index)) {
        (new NotFoundError(__PRETTY_FUNCTION__, obj))->raiseFrom(this);
    } else {
        content->put(index, nil);
        tally = tally - 1;
        fixCollisionsFrom(index);
    }
    return obj;
}

/* Testing protocol */
bool Set::includes(Object *obj)
{
    return !isEmptyAt(findElementOrNil(obj));
}

/* protected methods */
/* Enumeration protocol */
Object *Set::privNextForIterator(CollectionIterator *iter) const
{
    Object *obj;
    long index = iter->position();

    for (; index < capacity(); index += 1) {
        if ((obj = content->at(index)) != nil) {
            iter->position(index);
            return obj;
        }
    }
    iter->position(index);
    return nil;
}

/* Private protocol */
void Set::atNewIndexPut(int index, Object *obj)
{
    content->put(index, obj);
    tally = tally + 1;
    fullCheck();
}

void Set::changeCapacity(long newCapacity)
{
    Array *oldContent;
    Iterator *i;

    oldContent = content;
    content = new Array(newCapacity);
    tally = 0;
    for (i = oldContent->iterator(); !i->finished(); i->next()) {
        if (i->value() != nil)
            add(i->value());
    }
    delete i;
    delete oldContent;
}

int Set::findElementOrNil(Object *obj)
{
    int pass, length = capacity();
    Object *elem;
    int index;

    index = obj->hash() % length;
    /* Unfortunately, result of modulo can be negative */
    if (index < 0) index = length + index;
    pass = 1;
    while ((elem = content->at(index)) != nil && !elem->isEqual(obj)) {
        index++;
        if (index >= length) {
            index = 0;
            pass++;
            if (pass > 2) {
                grow();
                return findElementOrNil(obj);
            }
        }
    }
    return index;
}

void Set::fixCollisionsFrom(int oldIndex)
{
    int length, nextIndex;
    Object *nextObject = nil;

    length = capacity();
    nextIndex = oldIndex;
    do {
        if (nextIndex != oldIndex) {
            content->put(nextIndex, nextObject);
            content->put(oldIndex, nil);
        }
        oldIndex = (oldIndex + 1) % length;
        nextObject = content->at(oldIndex);
        if (nextObject != nil)
            nextIndex = findElementOrNil(nextObject);
    } while (nextObject != nil);
}

void Set::fullCheck(void)
{
    int sizePlusOne, cap;

    cap = capacity();
    sizePlusOne = size() + 1;
    if (sizePlusOne >= cap || cap - sizePlusOne < (cap >> 2))
        grow();
}

void Set::grow(void)
{
    changeCapacity(capacity() + growSize());
}

bool Set::isEmptyAt(int index)
{
    return content->at(index) == nil;
}

Object *Set::privAtIndex(int index)
{
    return content->at(index);
}

---