/* -*- C++ -*-

 * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Combinatorial Optimization Research Group, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_MAPS_H

#define LEMON_MAPS_H

///\file

///\brief Miscellaneous property maps

///

///\todo This file has the same name as the concept file in skeletons,

/// and this is not easily detectable in docs...

#include <map>

namespace lemon {

  /// Base class of maps.

  /// Base class of maps.

  /// It provides the necessary <tt>typedef</tt>s required by the map concept.

  template<typename K, typename T>

  class MapBase

  {

  public:

    ///\e

    typedef K KeyType;

    ///\e

    typedef T ValueType;

  };

  /// Null map. (a.k.a. DoNothingMap)

  /// If you have to provide a map only for its type definitions,

  /// or if you have to provide a writable map, but

  /// data written to it will sent to <tt>/dev/null</tt>...

  template<typename K, typename T>

  class NullMap : public MapBase<K,T>

  {

  public:

    /// Gives back a default constructed element.

    T operator[](const K&) const { return T(); }

    /// Absorbs the value.

    void set(const K&, const T&) {}

  };

  /// Constant map.

  /// This is a readable map which assigns a specified value to each key.

  /// In other aspects it is equivalent to the \ref NullMap.

  /// \todo set could be used to set the value.

  template<typename K, typename T>

  class ConstMap : public MapBase<K,T>

  {

    T v;

  public:

    /// Default constructor

    /// The value of the map will be uninitialized. 

    /// (More exactly it will be default constructed.)

    ConstMap() {}

    ///\e

    /// \param _v The initial value of the map.

    ///

    ConstMap(const T &_v) : v(_v) {}

    T operator[](const K&) const { return v; }

    void set(const K&, const T&) {}

    template<typename T1>

    struct rebind {

      typedef ConstMap<K,T1> other;

    };

    template<typename T1>

    ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}

  };

  //to document later

  template<typename T, T v>

  struct Const { };

  //to document later

  template<typename K, typename V, V v>

  class ConstMap<K, Const<V, v> > : public MapBase<K, V>

  {

  public:

    ConstMap() { }

    V operator[](const K&) const { return v; }

    void set(const K&, const V&) { }

  };

  //to document later

  typedef Const<bool, true> True;

  typedef Const<bool, false> False;

  /// \c std::map wrapper

  /// This is essentially a wrapper for \c std::map. With addition that

  /// you can specify a default value different from \c ValueType() .

  ///

  /// \todo Provide allocator parameter...

  template <typename Key, typename T, typename Compare = std::less<Key> >

  class StdMap : public std::map<Key,T,Compare> {

    typedef std::map<Key,T,Compare> parent;

    T v;

    typedef typename parent::value_type PairType;

  public:

    typedef Key KeyType;

    typedef T ValueType;

    typedef T& ReferenceType;

    typedef const T& ConstReferenceType;

    StdMap() : v() {}

    /// Constructor with specified default value

    StdMap(const T& _v) : v(_v) {}

    /// \brief Constructs the map from an appropriate std::map.

    ///

    /// \warning Inefficient: copies the content of \c m !

    StdMap(const parent &m) : parent(m) {}

    /// \brief Constructs the map from an appropriate std::map, and explicitly

    /// specifies a default value.

    ///

    /// \warning Inefficient: copies the content of \c m !

    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}

    template<typename T1, typename Comp1>

    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) { 

      //FIXME; 

    }

    ReferenceType operator[](const Key &k) {

      return insert(PairType(k,v)).first -> second;

    }

    ConstReferenceType operator[](const Key &k) const {

      typename parent::iterator i = lower_bound(k);

      if (i == parent::end() || parent::key_comp()(k, (*i).first))

	return v;

      return (*i).second;

    }

    void set(const Key &k, const T &t) {

      parent::operator[](k) = t;

    }

    /// Changes the default value of the map.

    /// \return Returns the previous default value.

    ///

    /// \warning The value of some keys (which has already been queried, but

    /// the value has been unchanged from the default) may change!

    T setDefault(const T &_v) { T old=v; v=_v; return old; }

    template<typename T1>

    struct rebind {

      typedef StdMap<Key,T1,Compare> other;

    };

  };

}

#endif // LEMON_MAPS_H