BDict.h

Go to the documentation of this file.

/*******************************************************************************
 *  BDict.h BEAM Dictionary class
 *          T.Barnaby,  BEAM Ltd,   2008-05-21
 *  Copyright (c) 2012 All Right Reserved, Beam Ltd, http://www.beam.ltd.uk
 *******************************************************************************
 */
#ifndef BDict_H
#define BDict_H 1

#include <BNameValue.h>

template <class Type> class BDictItem {
public:
            BDictItem(BString k = "", Type v = Type()) : key(k), value(v){}
    BString     key;
    Type        value;
    
//  BDictItem<Type> operator=(BDictItem<Type>& item){ key = item.key; value = item.value; return *this; }
};

template <class Type> class BDict : public BList<BDictItem<Type> > {
public:
    typedef BIter   iterator;
    
            BDict(int hashSize = 100);
            BDict(const BDict<Type>& dict);

    int     hasKey(const BString& k) const;
    BString     key(const BIter& i) const;
    void        clear();
    void        insert(BIter& i, const BDictItem<Type>& item);
    void        append(const BDictItem<Type>& item);
    void        append(const BDict<Type>& dict);
    void        del(const BString& k);
    void        del(BIter& i);
    BIter       find(const BString& k) const;

    Type&       operator[](const BString& i);
    const Type& operator[](const BString& i) const;
    Type&       operator[](const BIter& i);
    const Type& operator[](const BIter& i) const;
    Type&       operator[](int i);
    const Type& operator[](int i) const;
    BDict<Type> operator+(const BDict<Type>& dict) const;
    BDict<Type>&    operator=(const BDict<Type>& dict);
    
    void        hashPrint();
private:
    void            hashAdd(const BString& k, BIter iter);
    void            hashDelete(const BString& k, BIter iter);
    int         hashFind(const BString& k, BIter& iter) const;

    int         ohashSize;
    BArray<BList<BIter> >   ohashLists;
};

typedef BDict<BString>  BDictString;

void toBString(const BDictString& v, BString& s);
void fromBString(const BString& s, BDictString& v);
BString bdictStringToString(const BDictString& dict);   

template <class Type> BDict<Type>::BDict(int hashSize){
    ohashSize = hashSize;
    ohashLists.resize(ohashSize);
}

template <class Type> BDict<Type>::BDict(const BDict<Type>& dict) : BList<BDictItem<Type> >(){
    ohashSize = dict.ohashSize;
    ohashLists.resize(ohashSize);
    this->append(dict);
}

template <class Type> int BDict<Type>::hasKey(const BString& k) const {
    BIter   i = this->find(k);
    return !this->isEnd(i);
}

template <class Type> BString BDict<Type>::key(const BIter& i) const {
    return this->get(i).key;
}

template <class Type> void BDict<Type>::clear(){
    BUInt   i;
    
    BList<BDictItem<Type> >::clear();
    for(i = 0; i < ohashLists.size(); i++){
        ohashLists[i].clear();
    }
}

template <class Type> void BDict<Type>::insert(BIter& i, const BDictItem<Type>& item){
    BList<BDictItem<Type> >::insert(i, item);
    hashAdd(item.key, i);
}

template <class Type> void BDict<Type>::append(const BDictItem<Type>& item){
    BList<BDictItem<Type> >::append(item);
}

template <class Type> void BDict<Type>::append(const BDict<Type>& dict){
    BList<BDictItem<Type> >::append(dict);
}

template <class Type> void BDict<Type>::del(const BString& k){
    BIter   i = find(k);
    
    if(!this->isEnd(i)){
        hashDelete(k, i);
        BList<BDictItem<Type> >::del(i);
    }
}

template <class Type> void BDict<Type>::del(BIter& i){
    BList<BDictItem<Type> >::del(i);
}

template <class Type> BIter BDict<Type>::find(const BString& k) const {
    BIter   i;

#ifdef ZAP
    for(this->start(i); !this->isEnd(i); this->next(i)){
        if(this->get(i).key == k)
            return i;
    }
    return this->onodes;
#else
    if(hashFind(k, i))
        return i;
    else
        return this->onodes;
#endif
}

template <class Type> Type& BDict<Type>::operator[](const BString& k) {
    BIter   i = this->find(k);
    
    if(this->isEnd(i)){
        this->append(BDictItem<Type>(k));
        i = this->end();
    }

    return this->get(i).value;
}

template <class Type> const Type& BDict<Type>::operator[](const BString& k) const {
    BIter   i = this->find(k);
    
    if(this->isEnd(i)){
        fprintf(stderr, "BDict over range\n");
        exit(1);
    }

    return this->get(i).value;
}

template <class Type> Type& BDict<Type>::operator[](const BIter& i) {
    return this->get(i).value;
}

template <class Type> const Type& BDict<Type>::operator[](const BIter& i) const {
    return this->get(i).value;
}

template <class Type> Type& BDict<Type>::operator[](int i) {
    return BList<BDictItem<Type> >::operator[](i).value;
}

template <class Type> const Type& BDict<Type>::operator[](int i) const {
    return BList<BDictItem<Type> >::operator[](i).value;
}

template <class Type> BDict<Type> BDict<Type>::operator+(const BDict<Type>& dict) const {
    BDict<Type> r = *this;
    BIter       i;

    for(dict.start(i); !dict.isEnd(i); dict.next(i)){
        r.append(this->get(i));
    }
    return r;
}

template <class Type> BDict<Type>& BDict<Type>::operator=(const BDict<Type>& dict){
    BIter   i;
    
    if(this != &dict){
        this->clear();
        for(dict.start(i); !dict.isEnd(i); dict.next(i)){
            append(this->get(i));
        }
    }
    
    return *this;
}

template <class Type> void BDict<Type>::hashAdd(const BString& k, BIter iter){
    BUInt   pos;
    
    pos = k.hash() % ohashSize;
    ohashLists[pos].append(iter);
}

template <class Type> void BDict<Type>::hashDelete(const BString& k, BIter iter){
    BUInt   pos;
    BIter   i;
    
    pos = k.hash() % ohashSize;
    for(ohashLists[pos].start(i); !ohashLists[pos].isEnd(i); ohashLists[pos].next(i)){
        if(ohashLists[pos][i] == iter){
            ohashLists[pos].del(i);
            break;
        }
    }
}

template <class Type> int BDict<Type>::hashFind(const BString& k, BIter& iter) const {
    BUInt   pos;
    BIter   i;
    
    pos = k.hash() % ohashSize;
    for(ohashLists[pos].start(i); !ohashLists[pos].isEnd(i); ohashLists[pos].next(i)){
        if(key(ohashLists[pos][i]) == k){
            iter = ohashLists[pos][i];
            return 1;
        }
    }
    return 0;
}

template <class Type> void BDict<Type>::hashPrint(){
    BUInt   i;
    BUInt   n = 0;
    
    for(i = 0; i < ohashLists.size(); i++){
        n += ohashLists[i].number();
//      printf("Number: %d: %d\n", i, ohashLists[i].number());
    }
    printf("ListSize: %d HashSize: %d\n", BList<BDictItem<Type> >::number(), n);
}

#endif