#include "KeyMap.hh"

/*
 * class KeyMap<>
 */

// structors :

KeyMap::KeyMap()
  :m_entries(NULL) {}

KeyMap::~KeyMap() {
  clear();
}

// modifiers :

bool KeyMap::add(Symbol const &key, void *val, 
		 bool overwrite) {
  KeyEntry **iter = &m_entries;

  while( NULL!=*iter && (*iter)->first<key )
    iter = &((*iter)->m_next);
  if( NULL!=*iter && (*iter)->first==key ) {
    if( overwrite )
      (*iter)->second = val;
    return false;
  } else {
    *iter = new KeyEntry(key, val, *iter);
    return true;
  }
}

void *&KeyMap::getRef(Symbol const &key) /*throw(UnknownKey)*/ {
  KeyEntry *iter = m_entries;

  while( NULL!=iter && iter->first<key )
    iter = iter->m_next;
  if( NULL==iter || key<iter->first )
    throw UnknownKey("getRef() : Unknown key "+key);
  return iter->second;
}

void KeyMap::remove(Symbol const &key) {
  KeyEntry **iter = &m_entries;

  while( NULL!=*iter && (*iter)->first<key )
    iter = &((*iter)->m_next);  
  if( NULL!=*iter && (*iter)->first==key ) {
    KeyEntry *to_del = *iter;
    *iter = to_del->m_next;
    to_del->m_next = NULL;
    delete to_del;
  }
}


void KeyMap::clear() {
  if( NULL!=m_entries ) {
    delete m_entries;
    m_entries = NULL;
  }
}

void KeyMap::pop_front() {
  if( !empty() ) {
    KeyEntry *to_del = m_entries;
    m_entries = m_entries->m_next;
    to_del->m_next = NULL;
    delete to_del;
  }
}

// observers:

bool KeyMap::empty() const {
  return NULL==m_entries;
}


bool KeyMap::exists(Symbol const &key) const {
  const_iterator i = lower_bound(key);
  return end()!=i && i->first==key;
}

KeyMap::const_iterator KeyMap::lower_bound(Symbol const &key) const {
  const_iterator i = begin();
  const_iterator const endi = end();

  for( ; endi!=i && i->first<key; ++i );
  return i;
}

KeyMap::const_iterator KeyMap::upper_bound(Symbol const &key) const {
  const_iterator i = begin();
  const_iterator const endi = end();

  for( ; endi!=i && !(key<i->first); ++i );
  return i;
}

void *KeyMap::front() const {
  return m_entries->second;
}

void *KeyMap::get(Symbol const &key) const /* throw(UnknownKey) */ {
  const_iterator pos = lower_bound(key);

  if( end()==pos || key<pos->first )
    throw UnknownKey("Unknown key "+key);
  return pos->second;
}