#ifndef CLUSTER_KEYMAP_HH
# define CLUSTER_KEYMAP_HH

# include "dmem/dnew.hh"

# include "Exception.h"

# include "Symbol.hh"

/** @brief Unknwon entry exception.
 *
 * This exception is thrown by KeyMap if it is unbale
 * to locate an entry with a given key.
 *
 * @author Frederic Py <fpy@mbari.org>
 */
class UnknownKey :public Exception {
public:
  UnknownKey(Symbol const &message)
    :Exception((char *)message.c_str()) {}
  virtual ~UnknownKey() {}

}; // UnknownKey

template<class Ty>
class KeyMap;

template<class Ty>
class KeyIter;

/** @brief Entry for a KeyMap
 *
 * This class is used by KeyMap to store items with
 * their associated key.
 *
 * In fact this class implement a simple linked list
 * which is managed by KeyMap. 
 *
 * @param Ty type of the element.
 * 
 * @author Frederic Py <fpy@mbari.org>
 * @relates KeyMap
 */
template<class Ty>
class KeyEntry {
public:
  /** @brief Key value.
   *
   * This attribute stores the key of this entry.
   *
   * @note The choice of the name is due to the fact
   * that this class was initially based on a std::pair. 
   */
  Symbol const first;
  /** @brief item value.
   *
   * This attribute store the value of this entry.
   *
   * @note The choice of the name is due to the fact
   * that this class was initially based on a std::pair. 
   */
  Ty           second;

private:
  /** @brief Constructor
   *
   * @param key A key value
   * @param val A value
   * @param nxt Following item
   *
   * This constructor is used by KeyMap to insert a new element
   * in its list.
   */
  KeyEntry(Symbol const &key, Ty const &val, KeyEntry<Ty> *nxt)
    :first(key), second(val), m_next(nxt) {}
  /** @brief Destructor.
   *
   * Destroy current instance and all its following elements.
   */
  ~KeyEntry() {
    if( NULL!=m_next )
      delete m_next;
  }

  /** @brief next element.
   *
   * This attribute point to the following element of the list.
   */
  KeyEntry<Ty> *m_next;

  friend class KeyMap<Ty>;
  friend class KeyIter<Ty>;
};

/** @brief KeyMap iterator
 *
 * This class allows user to iterate thrue the elements of a KeyMap
 *
 * @param Ty type of the elements.
 *
 * @author Frederic Py <fpy@mbari.org>
 * @relates KeyMap
 */
template<class Ty>
class KeyIter {
public:
  /** @brief Default constructor
   *
   * Create a new instance that do not point to any KeyMap
   */
  KeyIter()
    :m_pos(NULL) {}
  /** @brief Copy constructor.
   * @param other Another instance.
   *
   * Create a new instance which points to the same element has @e other
   */ 
  KeyIter(KeyIter<Ty> const &other)
    :m_pos(other.m_pos) {}
  /** @brief Destructor 
   */
  ~KeyIter() {}

  /** @brief Copy operator.
   */
  KeyIter &operator= (KeyIter<Ty> const &other) {
    m_pos = other.m_pos;
    return *this;
  }
  /** @brief Equality test
   * @param other Another instance.
   *
   * @retval true if currrent instance points to the same element as @e other
   * @retval false else
   *
   * @sa bool operator!=(KeyIter<Ty> const &) const
   */
  bool operator==(KeyIter<Ty> const &other) const {
    return m_pos==other.m_pos;
  }
  /** @brief Difference test
   * @param other Another instance.
   *
   * @return !operator==(other) 
   *
   * @sa bool operator==(KeyIter<Ty> const &) const
   */
  bool operator!=(KeyIter<Ty> const &other) const {
    return m_pos!=other.m_pos;
  }

  /** @brief pre-increment operator
   *
   * Moves the iterator to the next element if any.
   *
   * @return *this after the operation.
   */
  KeyIter &operator++() {
    if( NULL!=m_pos )
      m_pos = m_pos->m_next;
    return *this;
  }

  /** @brief Access operator.
   *
   * This operator allows to access directly to
   * attributes the pointed element.
   *
   * @note The pointed element is a KeyEntry  
   *
   * @return A pointer to the pointed entry.
   *
   * @sa KeyEntry<Ty> const &operator* () const
   */
  KeyEntry<Ty> const *operator->() const {
    return m_pos;
  }
  /** @brief Dereference operator
   *
   * This operator allows to access directly to
   * the pointed element.
   *
   * @note The pointed element is a KeyEntry  
   *
   * @return A reference to the pointed entry.
   *
   * @sa KeyEntry<Ty> const *operator->() const
   */
  KeyEntry<Ty> const &operator* () const {
    return *m_pos;
  }

private:
  /** @brief Constructor.
   *
   * @param pos An entry.
   *
   * This constructor is used by KeyMap to generate
   * new iterators.
   *
   * @sa KeyMap::begin() const
   * @sa KeyMap::end() const
   */
  KeyIter(KeyEntry<Ty> const *pos)
    :m_pos(pos) {}

  /** @brief Pointed element
   *
   * This is the internal attribute used by KeyIter to navigate
   * thrue KeyMap elements.
   */
  KeyEntry<Ty> const *m_pos;

  friend class KeyMap<Ty>;
}; // KeyIter

/** @brief A simple associative map.
 *
 * This class implements a simple associative map where values can be attached
 * to one particular key.
 *
 * @param Ty type of the values
 *
 * The keys are Symbol and only one value can be attached to one key.
 *
 * @author Frederic Py
 */
template<class Ty>
class KeyMap {
public:
  /** @brief Iterator type for KeyMap
   *
   * This type describes the type used to iterate threw a KeyMap
   */
  typedef KeyIter<Ty> const_iterator;

  /** @brief Default constructor.
   *
   * Create an empty KeyMap
   */
  KeyMap();
  /** @brief Destructor */
  ~KeyMap();

  /** @brief Ad a new entry.
   *
   * @param key A key
   * @param val A value
   * @param overwrite Overwriting flag
   *
   * This method creates a new entry with the key @e key
   * and the value @e val. If an entry @e key already exist
   * if will change its value tyo @e val iff @e overwrite
   * is true.
   *
   * @retval true New entry created
   * @retavl false The entry already exist. If @e overwrite
   * was true the entry value was changed to @e val, otherwise
   * the entry was not modified.
   */
  bool add(Symbol const &key, Ty const &val, 
	   bool overwrite=false);
  /** @brief Entry removal.
   * @param key A key
   *
   * Destroy the entry with key @e key if it exist.
   */
  void remove(Symbol const &key);
  
  /** @brief Check for existence.
   *
   * @param key A key
   *
   * This method check if this instance has an entry with key @e key.
   *
   * @retval true if the entry @e key exist
   * @retval false else
   */
  bool exists(Symbol const &key) const;

  /** @brief Check for emptyness
   *
   * @retval true if this instance has no entry
   * @retval false else
   */
  bool empty() const;

  /** @brief First element.
   *
   * @return The value of the entry with the smallest key of this instance.
   */
  Ty const &front() const;
  
  /** @brief Get one element
   *
   * @param key A key
   *
   * This method looks for the element with key @e key and return its value.
   *
   * @pre The element @e key exist 
   * @return The value aossciated to @e key
   *
   * @throw UnknownKey No element with key @e key found.
   *
   * @sa bool exists(Symbol const &) const
   * @sa Ty const &operator[](Symbol const &) const
   */
  Ty const &get(Symbol const &key) const /* throw(UnknownKey) */;

  Ty &getRef(Symbol const &key) /*throw(UnknownKey)*/; 

  /** @brief Access operator
   *
   * @param key A key
   *
   * This operator looks for the element with key @e key and return its value.
   *
   * @pre The element @e key exist 
   * @return The value associated to @e key
   *
   * @throw UnknownKey No element with key @e key found.
   *
   * @sa bool exists(Symbol const &) const
   * @sa Ty const &get(Symbol const &) const
   */
  Ty const &operator[](Symbol const &key) const {
    return get(key);
  }

  /** @brief Empty the map
   *
   * This method removes all the element of this map.
   *
   * @post The instance is empty
   */
  void clear();
  /** @brief remove firsqt element
   *
   * This method removes the entry of the map with the smallest key
   */
  void pop_front();

  /** @brief First element of the map
   *
   * @return A const_iterator pointing tyo the element of the map with the smallest key
   */
  const_iterator begin() const {
    return const_iterator(m_entries);
  }
  /** @brief End of the map
   *
   * @return A const_iterator pointing to the end of the map
   */
  const_iterator end() const {
    return const_iterator();
  }
  /** @brief Lower bound
   *
   * @param key A key
   *
   * This method looks to the first element of the map whose key
   * is not before @e key.
   *
   * @return A const_iterator pointing to the lower bound of @e key
   *
   * @sa const_iterator upper_bound(Symbol const &) const
   */
  const_iterator lower_bound(Symbol const &key) const;
  /** @brief Upper bound
   *
   * @param key A key
   *
   * This method looks to the first element of the map whose key
   * is after @e key.
   *
   * @return A const_iterator pointing to the upper bound of @e key
   *
   * @sa const_iterator lower_bound(Symbol const &) const
   */
  const_iterator upper_bound(Symbol const &key) const;

private:
  /** @brief Entries list.
   *
   * This attribute store a simple-linked list of all the entries. This
   * list is sorted alphabetically base on key values.
   */
  KeyEntry<Ty> *m_entries;

}; // KeyMap<>

/*
 * class KeyMap<>
 */

// structors :

template<class Ty>
KeyMap<Ty>::KeyMap()
  :m_entries(NULL) {}

template<class Ty>
KeyMap<Ty>::~KeyMap() {
  clear();
}

// modifiers :

template<class Ty>
bool KeyMap<Ty>::add(Symbol const &key, Ty const &val, 
		     bool overwrite) {
  KeyEntry<Ty> **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<Ty>(key, val, *iter);
    return true;
  }
}

template<class Ty>
Ty &KeyMap<Ty>::getRef(Symbol const &key) /*throw(UnknownKey)*/ {
  KeyEntry<Ty> *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;
}

template<class Ty>
void KeyMap<Ty>::remove(Symbol const &key) {
  KeyEntry<Ty> **iter = &m_entries;

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


template<class Ty>
void KeyMap<Ty>::clear() {
  if( NULL!=m_entries ) {
    delete m_entries;
    m_entries = NULL;
  }
}

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

// observers:

template<class Ty>
bool KeyMap<Ty>::empty() const {
  return NULL==m_entries;
}


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

template<class Ty>
KeyMap<Ty>::const_iterator KeyMap<Ty>::lower_bound(Symbol const &key) const {
  const_iterator i = begin();
  const_iterator const endi = end();

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

template<class Ty>
KeyMap<Ty>::const_iterator KeyMap<Ty>::upper_bound(Symbol const &key) const {
  const_iterator i = begin();
  const_iterator const endi = end();

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

template<class Ty>
Ty const &KeyMap<Ty>::front() const {
  return m_entries->second;
}

template<class Ty>
Ty const &KeyMap<Ty>::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;
}



#endif // CLUSTER_KEYMAP_HH