Logo Search packages:      
Sourcecode: dasher version File versions

AlphabetMap.cpp

// AlphabetMap.cpp
//
/////////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2002 Iain Murray
//
/////////////////////////////////////////////////////////////////////////////

#include "../Common/Common.h"

#include "AlphabetMap.h"

using namespace Dasher;
using namespace std;

alphabet_map::alphabet_map(unsigned int InitialTableSize)
      : HashTable(InitialTableSize<<1), Undefined(0)
{
      Entries.reserve(InitialTableSize);
}


void alphabet_map::Add(const string& Key, symbol Value)
{
      RecursiveAdd(Key, Value, false);
}


void alphabet_map::RecursiveAdd(const string& Key, symbol Value, bool PrefixFlag)
{
      Entry*& HashEntry = HashTable[Hash(Key)];
      
      // Loop through Entries with the correct Hash value.
      for (Entry* i = HashEntry; i; i=i->Next) {
            if (i->Key==Key) {
                  if (PrefixFlag) {
                        // Just tagging - don't change symbol. Recurse if necessary
                        i->KeyIsPrefix = true;
                        if (Key.size()>1)
                              RecursiveAdd(Key.substr(Key.size()-1), Undefined, true);
                  } else {
                        // Add symbol and leave
                        i->Symbol = Value;
                  }
                  return;
            }
      }
      
      // When hash table gets 1/2 full...
      // (no I haven't optimised when to resize)
      if (Entries.size()<<1 >= HashTable.size()) {
            // Double up all the storage
            HashTable.clear();
            HashTable.resize(Entries.size()<<2);
            Entries.reserve(Entries.size()<<1);
            
            // Rehash as the pointers will all be mangled.
            for (unsigned int j=0; j<Entries.size(); j++) {
                  Entry*& HashEntry2 = HashTable[Hash(Entries[j].Key)];
                  Entries[j].Next = HashEntry2;
                  HashEntry2 = &Entries[j];
            }
            
            // Have to recall this function as the key's hash needs recalculating
            RecursiveAdd(Key, Value, PrefixFlag);
            return;
      }
      
      Entries.push_back(Entry(Key, Value, HashEntry));
      HashEntry = &Entries.back();
}


symbol alphabet_map::Get(const string& Key, bool* KeyIsPrefix) const
{
      // Loop through Entries with the correct Hash value.
      for (Entry* i = HashTable[Hash(Key)]; i; i=i->Next) {
            if (i->Key==Key) {
                  if (KeyIsPrefix!=0)
                        *KeyIsPrefix = i->KeyIsPrefix;
                  return i->Symbol;
            }
      }
      
      if (KeyIsPrefix!=0)
            *KeyIsPrefix = false;
      return Undefined;
}

Generated by  Doxygen 1.6.0   Back to index