Dictionary.cc

Go to the documentation of this file.

/*
 * Dictionary.cc
 *
 * Smalltalk like class library for C++
 * Growable collection of key-value pairs, 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/Dictionary.h>
#include <stlib/Association.h>
#include <stlib/Array.h>
#include <stlib/KAVIterator.h>
#include <stlib/String.h>
#include <stlib/Visitor.h>

#include <stlib/KeyNotFoundError.h>
#include <stlib/ValueNotFoundError.h>
#include <stlib/SOOBoundsError.h>

Dictionary::Dictionary(int length)
  : Set(length)
{
}

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

/* Accessing protocol */
Object *Dictionary::at(Object *key)
{
    long index;
    Association *obj;

    index = findKeyOrNil(key);
    obj = (Association *) content->at(index);
    if (obj == nil)
        (new KeyNotFoundError(__PRETTY_FUNCTION__, key))->raiseFrom(this);
    return obj->value();
}

Object *Dictionary::at(Object *key, Object *ifAbsentValue)
{
    long index;
    Association *obj;

    index = findKeyOrNil(key);
    obj = (Association *) content->at(index);
    if (obj == nil)
        return ifAbsentValue;
    return obj->value();
}

Object *Dictionary::at(const char *key) {
    return at(new String(key));
}

Object *Dictionary::at(const char* key, const char *ifAbsentValue) {
    return at(new String(key), (ifAbsentValue == nil ? nil : new String(ifAbsentValue)));
}

void Dictionary::put(Object *key, Object *value)
{
    long index;
    Association *element;

    if (key == nil)
        (new SubscriptOutOfBoundsError(__PRETTY_FUNCTION__, 0))->raiseFrom(this);
    index = findKeyOrNil(key);
    element = (Association *) content->at(index);
    if (element == nil) atNewIndexPut(index, new Association(key, value));
                   else element->value(value);
}

void Dictionary::put(const char* key, Object* value) {
    put(new String(key), value);
}

void Dictionary::put(const char* key, const char* value) {
    put(new String(key), new String(value));
}

Object *Dictionary::keyAtValue(Object *value)
{
    for (KeysAndValuesIterator i(this); !i.finished(); i.next()) {
        if (i.value()->isEqual(value))
            return i.key();
    }
    (new ValueNotFoundError(__PRETTY_FUNCTION__, value))->raiseFrom(this);
}

Object *Dictionary::keyAtValue(Object *value, Object *ifAbsentKey)
{
    Object *obj;

    try {
        obj = keyAtValue(value);
    }
    catch (ValueNotFoundError *ex) {
        obj = ifAbsentKey;
    }
    return obj;
}

/* Adding protocol */
void Dictionary::add(Object *assoc)
{
    long index;
    Object *assocKey;
    Association *element;

    if (!assoc->isAssociation() ||
        (assocKey = ((Association *) assoc)->key()) == nil)
        (new SubscriptOutOfBoundsError(__PRETTY_FUNCTION__, 0))->raiseFrom(this);
    index = findKeyOrNil(assocKey);
    element = (Association *) content->at(index);
    if (element == nil) atNewIndexPut(index, assoc);
                   else element->value(((Association *)assoc)->value());
}

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

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

/* Enumeration protocol */
KeysAndValuesIterator *Dictionary::keysAndValuesIterator(void) const
{
    return new KeysAndValuesIterator(this);
}

/* Removing protocol */
Object *Dictionary::remove(Object *)
{
    shouldNotImplement(new String(__PRETTY_FUNCTION__));
    return nil;
}

Object *Dictionary::removeKey(Object *key)
{
    long index;
    Association *element;

    index = findKey(key);
    element = (Association *) content->at(index);
    content->put(index, nil);
    tally = tally - 1;
    fixCollisionsFrom(index);
    return element->value();
}

/* Testing protocol */
bool Dictionary::includes(Object *obj)
{
    return Collection::includes(obj);
}

bool Dictionary::includesKey(Object *key)
{
    return content->at(findKeyOrNil(key)) != nil;
}

/* Visiting protocol */
void Dictionary::visitBy(Visitor *visitor)
{
    visitor->visitDictionary(this);
}

/* Private protocol */
void Dictionary::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)
            noCheckAdd((Association *) i->value());
    }
    delete i;
    delete oldContent;
}

int Dictionary::findKey(Object *key)
{
    int index;

    index = findKeyOrNil(key);
    if (content->at(index) == nil)
        (new KeyNotFoundError(__PRETTY_FUNCTION__, key))->raiseFrom(this);
    return index;
}

int Dictionary::findKeyOrNil(Object *key)
{
    int pass, length = capacity();
    Association *elem;
    int index;

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

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

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

void Dictionary::noCheckAdd(Association *object)
{
    content->put(findKeyOrNil(object->key()), object);
    tally = tally + 1;
}

---