/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2007

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, 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_MATRIX_MAPS_H

#define LEMON_MATRIX_MAPS_H

#include <vector>

#include <lemon/bits/utility.h>

#include <lemon/bits/invalid.h>

#include <lemon/maps.h>

#include <lemon/concepts/matrix_maps.h>

/// \file

/// \ingroup matrices

/// \brief Maps indexed with pairs of items.

///

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

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

namespace lemon {

  /// \brief Map for the coloumn view of the matrix

  ///

  /// \ingroup matrices

  /// Map for the coloumn view of the matrix.

  ///

  template <typename _MatrixMap>

  class MatrixRowMap : public MatrixMapTraits<_MatrixMap> {

  public:

    typedef _MatrixMap MatrixMap;

    typedef typename MatrixMap::SecondKey Key;

    typedef typename MatrixMap::Value Value;

    /// \brief Constructor of the row map

    ///

    /// Constructor of the row map.

    MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) 

      : matrix(_matrix), row(_row) {}

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ReturnValue

    operator[](Key col) {

      return matrix(row, col);

    }

    /// \brief Setter function

    ///

    /// Setter function.

    void set(Key col, const Value& val) {

      matrix.set(row, col, val);

    }

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ConstReturnValue

    operator[](Key col) const {

      return matrix(row, col);

    }

  private:

    MatrixMap& matrix;

    typename MatrixMap::FirstKey row;

  };

  /// \brief Map for the row view of the matrix

  ///

  /// \ingroup matrices

  /// Map for the row view of the matrix.

  ///

  template <typename _MatrixMap>

  class ConstMatrixRowMap : public MatrixMapTraits<_MatrixMap> {

  public:

    typedef _MatrixMap MatrixMap;

    typedef typename MatrixMap::SecondKey Key;

    typedef typename MatrixMap::Value Value;

    /// \brief Constructor of the row map

    ///

    /// Constructor of the row map.

    ConstMatrixRowMap(const MatrixMap& _matrix, 

		      typename MatrixMap::FirstKey _row) 

      : matrix(_matrix), row(_row) {}

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ConstReturnValue

    operator[](Key col) const {

      return matrix(row, col);

    }

  private:

    const MatrixMap& matrix;

    typename MatrixMap::FirstKey row;

  };

  /// \ingroup matrices

  ///

  /// \brief Gives back a row view of the matrix map

  ///

  /// Gives back a row view of the matrix map.

  ///

  /// \sa MatrixRowMap

  /// \sa ConstMatrixRowMap

  template <typename MatrixMap>

  MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,

				       typename MatrixMap::FirstKey row) {

    return MatrixRowMap<MatrixMap>(matrixMap, row);

  }

  template <typename MatrixMap>

  ConstMatrixRowMap<MatrixMap>

  matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {

    return ConstMatrixRowMap<MatrixMap>(matrixMap, row);

  }

  /// \brief Map for the column view of the matrix

  ///

  /// \ingroup matrices

  /// Map for the column view of the matrix.

  ///

  template <typename _MatrixMap>

  class MatrixColMap : public MatrixMapTraits<_MatrixMap> {

  public:

    typedef _MatrixMap MatrixMap;

    typedef typename MatrixMap::FirstKey Key;

    typedef typename MatrixMap::Value Value;

    /// \brief Constructor of the column map

    ///

    /// Constructor of the column map.

    MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) 

      : matrix(_matrix), col(_col) {}

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ReturnValue

    operator[](Key row) {

      return matrix(row, col);

    }

    /// \brief Setter function

    ///

    /// Setter function.

    void set(Key row, const Value& val) {

      matrix.set(row, col, val);

    }

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ConstReturnValue

    operator[](Key row) const {

      return matrix(row, col);

    }

  private:

    MatrixMap& matrix;

    typename MatrixMap::SecondKey col;

  };

  /// \brief Map for the column view of the matrix

  ///

  /// \ingroup matrices

  /// Map for the column view of the matrix.

  ///

  template <typename _MatrixMap>

  class ConstMatrixColMap : public MatrixMapTraits<_MatrixMap> {

  public:

    typedef _MatrixMap MatrixMap;

    typedef typename MatrixMap::FirstKey Key;

    typedef typename MatrixMap::Value Value;

    /// \brief Constructor of the column map

    ///

    /// Constructor of the column map.

    ConstMatrixColMap(const MatrixMap& _matrix, 

		      typename MatrixMap::SecondKey _col) 

      : matrix(_matrix), col(_col) {}

    /// \brief Subscription operator

    ///

    /// Subscription operator.

    typename MatrixMapTraits<MatrixMap>::ConstReturnValue

    operator[](Key row) const {

      return matrix(row, col);

    }

  private:

    const MatrixMap& matrix;

    typename MatrixMap::SecondKey col;

  };

  /// \ingroup matrices

  ///

  /// \brief Gives back a column view of the matrix map

  ///

  /// Gives back a column view of the matrix map.

  ///

  /// \sa MatrixColMap

  /// \sa ConstMatrixColMap

  template <typename MatrixMap>

  MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,

				       typename MatrixMap::SecondKey col) {

    return MatrixColMap<MatrixMap>(matrixMap, col);

  }

  template <typename MatrixMap>

  ConstMatrixColMap<MatrixMap> 

  matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {

    return ConstMatrixColMap<MatrixMap>(matrixMap, col);

  }

  /// \brief Container for store values for each ordered pair of graph items

  ///

  /// \ingroup matrices

  /// This data structure can strore for each pair of the same item

  /// type a value. It increase the size of the container when the 

  /// associated graph modified, so it updated automaticly whenever

  /// it is needed.

  template <typename _Graph, typename _Item, typename _Value>

  class DynamicMatrixMap 

    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  public:

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase 

    Parent;

    typedef _Graph Graph;

    typedef _Item Key;

    typedef _Item FirstKey;

    typedef _Item SecondKey;

    typedef _Value Value;

    typedef True ReferenceMapTag;

  private:

    typedef std::vector<Value> Container;

  public:

    typedef typename Container::reference Reference;

    typedef typename Container::const_reference ConstReference;

    /// \brief Creates an item matrix for the given graph

    ///

    /// Creates an item matrix for the given graph.

    DynamicMatrixMap(const Graph& _graph) 

      : values(size(_graph.maxId(Key()) + 1)) {

      Parent::attach(_graph.notifier(Key()));

    }

    /// \brief Creates an item matrix for the given graph

    ///

    /// Creates an item matrix for the given graph and assigns for each

    /// pairs of keys the given parameter.

    DynamicMatrixMap(const Graph& _graph, const Value& _val) 

      : values(size(_graph.maxId(Key()) + 1), _val) {

      Parent::attach(_graph.notifier(Key()));

    }

    ///\brief The assignement operator.

    ///

    ///It allow to assign a map to an other.

    DynamicMatrixMap& operator=(const DynamicMatrixMap& _cmap){

      return operator=<DynamicMatrixMap>(_cmap);

    }

    ///\brief Template assignement operator.

    ///

    ///It copy the element of the given map to its own container.  The

    ///type of the two map shall be the same.

    template <typename CMap>

    DynamicMatrixMap& operator=(const CMap& _cmap){

      checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();

      typename Parent::Notifier* notifier = Parent::notifier();

      Key first, second;

      for(notifier->first(first); first != INVALID; 

          notifier->next(first)){

        for(notifier->first(second); second != INVALID; 

            notifier->next(second)){

          set(first, second, _cmap(first, second));

        }

      }

      return *this;

    }

    /// \brief Gives back the value assigned to the \c first - \c second

    /// ordered pair.

    ///

    /// Gives back the value assigned to the \c first - \c second ordered pair.

    ConstReference operator()(const Key& first, const Key& second) const {

      return values[index(Parent::notifier()->id(first), 

                          Parent::notifier()->id(second))];

    }

    /// \brief Gives back the value assigned to the \c first - \c second

    /// ordered pair.

    ///

    /// Gives back the value assigned to the \c first - \c second ordered pair.

    Reference operator()(const Key& first, const Key& second) {

      return values[index(Parent::notifier()->id(first), 

                          Parent::notifier()->id(second))];

    }

    /// \brief Setter function for the matrix map.

    ///

    /// Setter function for the matrix map.

    void set(const Key& first, const Key& second, const Value& val) {

      values[index(Parent::notifier()->id(first), 

                   Parent::notifier()->id(second))] = val;

    }

  protected:

    static int index(int i, int j) {

      if (i < j) {

	return j * j + i;

      } else {

	return i * i + i + j;

      }

    }

    static int size(int s) {

      return s * s;

    }

    virtual void add(const Key& key) {

      if (size(Parent::notifier()->id(key) + 1) >= int(values.size())) {

	values.resize(size(Parent::notifier()->id(key) + 1));	

      }

    }

    virtual void add(const std::vector<Key>& keys) {

      int new_size = 0;

      for (int i = 0; i < int(keys.size()); ++i) {

        if (size(Parent::notifier()->id(keys[i]) + 1) >= new_size) {

          new_size = size(Parent::notifier()->id(keys[i]) + 1);	

        }

      }

      if (new_size > int(values.size())) {

        values.resize(new_size);

      }

    }

    virtual void erase(const Key&) {}

    virtual void erase(const std::vector<Key>&) {}

    virtual void build() {

      values.resize(size(Parent::notifier()->maxId() + 1));

    }

    virtual void clear() {

      values.clear();

    }   

  private:

    std::vector<Value> values;

  };

  /// \brief Container for store values for each unordered pair of graph items

  ///

  /// \ingroup matrices

  /// This data structure can strore for each pair of the same item

  /// type a value. It increase the size of the container when the 

  /// associated graph modified, so it updated automaticly whenever

  /// it is needed. 

  template <typename _Graph, typename _Item, typename _Value>

  class DynamicSymMatrixMap 

    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  public:

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase 

    Parent;

    typedef _Graph Graph;

    typedef _Item Key;

    typedef _Item FirstKey;

    typedef _Item SecondKey;

    typedef _Value Value;

    typedef True ReferenceMapTag;

  private:

    typedef std::vector<Value> Container;

  public:

    typedef typename Container::reference Reference;

    typedef typename Container::const_reference ConstReference;

    /// \brief Creates an item matrix for the given graph

    ///

    /// Creates an item matrix for the given graph.

    DynamicSymMatrixMap(const Graph& _graph) 

      : values(size(_graph.maxId(Key()) + 1)) {

      Parent::attach(_graph.notifier(Key()));

    }

    /// \brief Creates an item matrix for the given graph

    ///

    /// Creates an item matrix for the given graph and assigns for each

    /// pairs of keys the given parameter.

    DynamicSymMatrixMap(const Graph& _graph, const Value& _val) 

      : values(size(_graph.maxId(Key()) + 1), _val) {

      Parent::attach(_graph.notifier(Key()));

    }

    ///\brief The assignement operator.

    ///

    ///It allow to assign a map to an other.

    ///

    DynamicSymMatrixMap& operator=(const DynamicSymMatrixMap& _cmap){

      return operator=<DynamicSymMatrixMap>(_cmap);

    }

    ///\brief Template assignement operator.

    ///

    ///It copy the element of the given map to its own container.  The

    ///type of the two map shall be the same.

    template <typename CMap>

    DynamicSymMatrixMap& operator=(const CMap& _cmap){

      checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();

      typename Parent::Notifier* notifier = Parent::notifier();

      Key first, second;

      for(notifier->first(first); first != INVALID; 

          notifier->next(first)){

        for(notifier->first(second); second != first; 

            notifier->next(second)){

          set(first, second, _cmap(first, second));

        }

        set(first, first, _cmap(first, first));        

      }

      return *this;

    }

    /// \brief Gives back the value assigned to the \c first - \c second

    /// unordered pair.

    ///

    /// Gives back the value assigned to the \c first - \c second unordered 

    /// pair.

    ConstReference operator()(const Key& first, const Key& second) const {

      return values[index(Parent::notifier()->id(first), 

                          Parent::notifier()->id(second))];

    }

    /// \brief Gives back the value assigned to the \c first - \c second

    /// unordered pair.

    ///

    /// Gives back the value assigned to the \c first - \c second unordered 

    /// pair.

    Reference operator()(const Key& first, const Key& second) {

      return values[index(Parent::notifier()->id(first), 

                          Parent::notifier()->id(second))];

    }

    /// \brief Setter function for the matrix map.

    ///

    /// Setter function for the matrix map.

    ///

    void set(const Key& first, const Key& second, const Value& val) {

      values[index(Parent::notifier()->id(first), 

                   Parent::notifier()->id(second))] = val;

    }

  protected:

    static int index(int i, int j) {

      if (i < j) {

	return j * (j + 1) / 2 + i;

      } else {

	return i * (i + 1) / 2 + j;

      }

    }

    static int size(int s) {

      return s * (s + 1) / 2;

    }

    virtual void add(const Key& key) {

      if (size(Parent::notifier()->id(key) + 1) >= int(values.size())) {

	values.resize(size(Parent::notifier()->id(key) + 1));	

      }

    }

    virtual void add(const std::vector<Key>& keys) {

      int new_size = 0;

      for (int i = 0; i < int(keys.size()); ++i) {

        if (size(Parent::notifier()->id(keys[i]) + 1) >= new_size) {

          new_size = size(Parent::notifier()->id(keys[i]) + 1);	

        }

      }

      if (new_size > int(values.size())) {

        values.resize(new_size);

      }

    }

    virtual void erase(const Key&) {}

    virtual void erase(const std::vector<Key>&) {}

    virtual void build() {

      values.resize(size(Parent::notifier()->maxId() + 1));

    }

    virtual void clear() {

      values.clear();

    }   

  private:

    std::vector<Value> values;

  };

  ///\brief Dynamic Asymmetric Matrix Map.

  ///

  ///\ingroup matrices

  ///Dynamic Asymmetric Matrix Map.  Container for store values for each

  ///ordered pair of containers items.  This data structure can store

  ///data with different key types from different container types. It

  ///increases the size of the container if the linked containers

  ///content change, so it is updated automaticly whenever it is

  ///needed.

  ///

  ///This map meet with the concepts::ReferenceMatrixMap<typename K1,

  ///typename K2, typename V, typename R, typename CR> called as

  ///"ReferenceMatrixMap".

  ///

  ///\warning Do not use this map type when the two item sets are

  ///equal or based on the same item set.

  ///

  ///\param _FirstContainer the desired type of first container. It is

  ///ususally a Graph type, but can be any type with alteration

  ///property.

  ///  

  ///\param _FirstContainerItem the nested type of the

  ///FirstContainer. It is usually a graph item as Node, Edge,

  ///etc. This type will be the FirstKey type.

  ///

  ///\param _SecondContainer the desired type of the second

  ///container. It is usualy a Graph type, but can be any type with

  ///alteration property.

  ///

  ///\param _SecondContainerItem the nested type of the

  ///SecondContainer. It is usually a graph item such as Node, Edge,

  ///UEdge, etc. This type will be the SecondKey type.

  ///

  ///\param _Value the type of the strored values in the container.

  ///

  /// \author Janos Nagy

  template <typename _FirstContainer, typename _FirstContainerItem, 

            typename _SecondContainer, typename _SecondContainerItem, 

            typename _Value>

  class DynamicAsymMatrixMap{

  public:

    ///The first key type.

    typedef _FirstContainerItem FirstKey;

    ///The second key type.

    typedef _SecondContainerItem SecondKey;

    ///The value type of the map.

    typedef _Value Value;

    ///Indicates it is a reference map.

    typedef True ReferenceMapTag;

  protected:

    ///\brief Proxy class for the first key type.

    ///

    ///The proxy class belongs to the FirstKey type. It is necessary because

    ///if one want use the same conatainer types and same nested types but on

    ///other instances of containers than due to the type equiality of nested

    ///types it requires a proxy mechanism. 

    class FirstKeyProxy 

      : protected 

    ItemSetTraits<_FirstContainer,_FirstContainerItem>::

    ItemNotifier::ObserverBase 

    {

    public:

      friend class DynamicAsymMatrixMap;

      ///Constructor.

      FirstKeyProxy(DynamicAsymMatrixMap& _map) : _owner(_map) { }

    protected:

      ///\brief Add a new FirstKey to the map.

      ///

      ///It adds a new FirstKey to the map. It is called by the

      ///observer notifier and it is ovverride the add() virtual

      ///member function in the observer base. It will call the

      ///maps addFirstKey() function.

      virtual void add(const FirstKey& _firstKey){

        _owner.addFirstKey(_firstKey);

      }

      ///\brief Add more new FirstKey to the map.

      ///

      ///It adds more new FirstKey to the map. It is called by the

      ///observer notifier and it is ovverride the add() virtual

      ///member function in the observer base. It will call the

      ///map's addFirstKeys() function.

      virtual void add(const std::vector<FirstKey>& _firstKeys){

        _owner.addFirstKeys(_firstKeys);

      }

      ///\brief Erase a FirstKey from the map.

      ///

      ///Erase a FirstKey from the map. It called by the observer

      ///notifier and it overrides the erase() virtual member

      ///function of the observer base. It will call the map's

      ///eraseFirstKey() function.

      virtual void erase(const FirstKey& _firstKey){

        _owner.eraseFirstKey(_firstKey);

      }

      ///\brief Erase more FirstKey from the map.

      ///

      ///Erase more FirstKey from the map. It called by the

      ///observer notifier and it overrides the erase() virtual

      ///member function of the observer base. It will call the

      ///map's eraseFirstKeys() function.

      virtual void erase(const std::vector<FirstKey>& _firstKeys){

        _owner.eraseFirstKeys(_firstKeys);

      }

      ///\brief Builds the map.

      ///

      ///It buildes the map. It called by the observer notifier

      ///and it overrides the build() virtual member function of

      ///the observer base.  It will call the map's build()

      ///function.

      virtual void build() {

        _owner.build();

        //_owner.buildFirst();

      }

      ///\brief Clear the map.

      ///

      ///It erases all items from the map. It called by the

      ///observer notifier and it overrides the clear() virtual

      ///memeber function of the observer base. It will call the

      ///map's clear() function.

      virtual void clear() {

        _owner.clear();

        //_owner.clearFirst();

      }

    private:

      ///The map type for it is linked.

      DynamicAsymMatrixMap& _owner;

    };//END OF FIRSTKEYPROXY

      ///\brief Proxy class for the second key type.

      ///

      ///The proxy class belongs to the SecondKey type. It is

      ///necessary because if one want use the same conatainer types

      ///and same nested types but on other instances of containers

      ///than due to the type equiality of nested types it requires a

      ///proxy mechanism.

    class SecondKeyProxy

      : protected 

    ItemSetTraits<_SecondContainer, _SecondContainerItem>::

    ItemNotifier::ObserverBase {

    public:

      friend class DynamicAsymMatrixMap;

      ///Constructor.

      SecondKeyProxy(DynamicAsymMatrixMap& _map) : _owner(_map) { }

    protected:

      ///\brief Add a new SecondKey to the map.

      ///

      ///It adds a new SecondKey to the map. It is called by the

      ///observer notifier and it is ovverride the add() virtual

      ///member function in the observer base. It will call the

      ///maps addSecondKey() function.

      virtual void add(const SecondKey& _secondKey){

        _owner.addSecondKey(_secondKey);

      }

      ///\brief Add more new SecondKey to the map.

      ///

      ///It adds more new SecondKey to the map. It is called by

      ///the observer notifier and it is ovverride the add()

      ///virtual member function in the observer base. It will

      ///call the maps addSecondKeys() function.

      virtual void add(const std::vector<SecondKey>& _secondKeys){

        _owner.addSecondKeys(_secondKeys);

      }

      ///\brief Erase a SecondKey from the map.

      ///

      ///Erase a SecondKey from the map. It called by the observer

      ///notifier and it overrides the erase() virtual member

      ///function of the observer base. It will call the map's

      ///eraseSecondKey() function.

      virtual void erase(const SecondKey& _secondKey){

        _owner.eraseSecondKey(_secondKey);

      }

      ///\brief Erase more SecondKeys from the map.

      ///

      ///Erase more SecondKey from the map. It called by the

      ///observer notifier and it overrides the erase() virtual

      ///member function of the observer base. It will call the

      ///map's eraseSecondKeys() function.

      virtual void erase(const std::vector<SecondKey>& _secondKeys){

        _owner.eraseSecondKeys(_secondKeys);

      }

      ///\brief Builds the map.

      ///

      ///It buildes the map. It called by the observer notifier

      ///and it overrides the build() virtual member function of

      ///the observer base.  It will call the map's build()

      ///function.

      virtual void build() {

        _owner.build();

      }

      ///\brief Clear the map.

      ///

      ///It erases all items from the map. It called by the

      ///observer notifier and it overrides the clear() virtual

      ///memeber function of the observer base. It will call the

      ///map's clear() function.

      virtual void clear() {

        _owner.clear();

        //_owner.clearFirst();

      }

    private:

      ///The type of map for which it is attached.

      DynamicAsymMatrixMap& _owner;

    };//END OF SECONDKEYPROXY

  private:

    /// \e

    typedef std::vector<Value> Container;

    ///The type of constainer which stores the values of the map.

    typedef std::vector<Container> DContainer;

    ///The std:vector type which contains the data

    DContainer values;

    ///Member for the first proxy class

    FirstKeyProxy _first_key_proxy;

    ///Member for the second proxy class

    SecondKeyProxy _second_key_proxy;

  public:

    ///The refernce type of the map.

    typedef typename Container::reference Reference;

    ///The const reference type of the constainer.

    typedef typename Container::const_reference ConstReference;

    ///\brief Constructor what create the map for the two containers type.

    ///

    ///Creates the matrix map and initialize the values with Value()

    DynamicAsymMatrixMap(const _FirstContainer& _firstContainer, 

                  const _SecondContainer& _secondContainer)

      : values(DContainer(_firstContainer.maxId(FirstKey())+1,

                          Container(_secondContainer.maxId(SecondKey())+1))),

        _first_key_proxy(*this),

        _second_key_proxy(*this)

    {

      _first_key_proxy.attach(_firstContainer.notifier(FirstKey()));

      _second_key_proxy.attach(_secondContainer.notifier(SecondKey()));

    }

    ///\brief Constructor what create the map for the two containers type.

    ///

    ///Creates the matrix map and initialize the values with the given _value

    DynamicAsymMatrixMap(const _FirstContainer& _firstContainer, 

                  const _SecondContainer& _secondContainer, 

                  const Value& _value)

      : values(DContainer(_firstContainer.maxId(FirstKey())+1,

                          Container(_secondContainer.maxId(SecondKey())+1,

                                    _value))),

        _first_key_proxy(*this),

        _second_key_proxy(*this)

    {

      _first_key_proxy.attach(_firstContainer.notifier(FirstKey()));

      _second_key_proxy.attach(_secondContainer.notifier(SecondKey()));

    }

    ///\brief Copy constructor.

    ///

    ///The copy constructor of the map.

    DynamicAsymMatrixMap(const DynamicAsymMatrixMap& _copy) 

      : _first_key_proxy(*this), _second_key_proxy(*this) {

      if(_copy._first_key_proxy.attached() && 

         _copy._second_key_proxy.attached()){

        _first_key_proxy.attach(*_copy._first_key_proxy.notifier());

        _second_key_proxy.attach(*_copy._second_key_proxy.notifier());

        values = _copy.values;

      }

    }

    ///\brief Destructor

    ///

    ///Destructor what detach() from the attached objects.  May this

    ///function is not necessary because the destructor of

    ///ObserverBase do the same.

    ~DynamicAsymMatrixMap() {

      if(_first_key_proxy.attached()){

        _first_key_proxy.detach();

      }

      if(_second_key_proxy.attached()){

        _second_key_proxy.detach();

      }

    }

    ///\brief Gives back the value assigned to the \c first - \c

    ///second ordered pair.

    ///

    ///Gives back the value assigned to the \c first - \c second

    ///ordered pair.

    Reference operator()(const FirstKey& _first, const SecondKey& _second) {

      return values[_first_key_proxy.notifier()->id(_first)]

        [_second_key_proxy.notifier()->id(_second)];

    }

    ///\brief Gives back the value assigned to the \c first - \c

    ///second ordered pair.

    ///

    ///Gives back the value assigned to the \c first - \c second

    ///ordered pair.

    ConstReference operator()(const FirstKey& _first, 

                              const SecondKey& _second) const {

      return values[_first_key_proxy.notifier()->id(_first)]

        [_second_key_proxy.notifier()->id(_second)];

    }

    ///\brief Setter function for this matrix map.

    ///

    ///Setter function for this matrix map.

    void set(const FirstKey& first, const SecondKey& second, 

             const Value& value){

      values[_first_key_proxy.notifier()->id(first)]

        [_second_key_proxy.notifier()->id(second)] = value;

    }

    ///\brief The assignement operator.

    ///

    ///It allow to assign a map to an other. It

    DynamicAsymMatrixMap& operator=(const DynamicAsymMatrixMap& _cmap){

      return operator=<DynamicAsymMatrixMap>(_cmap);

    }

    ///\brief Template assignement operator.

    ///

    ///It copy the element of the given map to its own container.  The

    ///type of the two map shall be the same.

    template <typename CMap>

    DynamicAsymMatrixMap& operator=(const CMap& _cdmap){

      checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();

      const typename FirstKeyProxy::Notifier* notifierFirstKey = 

        _first_key_proxy.notifier();

      const typename SecondKeyProxy::Notifier* notifierSecondKey = 

        _second_key_proxy.notifier();

      FirstKey itemFirst;

      SecondKey itemSecond;

      for(notifierFirstKey->first(itemFirst); itemFirst != INVALID; 

          notifierFirstKey->next(itemFirst)){

        for(notifierSecondKey->first(itemSecond); itemSecond != INVALID; 

            notifierSecondKey->next(itemSecond)){

          set(itemFirst, itemSecond, _cdmap(itemFirst,itemSecond));

        }

      }

      return *this;

    }

  protected:

    ///\brief Add a new FirstKey to the map.

    ///

    ///It adds a new FirstKey to the map. It is called by the observer

    ///class belongs to the FirstKey type.

    void addFirstKey(const FirstKey& firstKey) {

      int size = int(values.size());

      if( _first_key_proxy.notifier()->id(firstKey)+1 >= size ){

        values.resize(_first_key_proxy.notifier()->id(firstKey)+1);

        if( int(values[0].size()) != 0 ){

          int innersize = int(values[0].size());

          for(int i = size; i < int(values.size());++i){

            (values[i]).resize(innersize);

          }

        }else if(_second_key_proxy.notifier()->maxId() >= 0){

          int innersize = _second_key_proxy.notifier()->maxId();

          for(int i = 0; i < int(values.size()); ++i){

            values[0].resize(innersize);

          }

        }

      }

    }

    ///\brief Adds more new FirstKeys to the map.

    ///

    ///It adds more new FirstKeys to the map. It called by the

    ///observer class belongs to the FirstKey type.

    void addFirstKeys(const std::vector<FirstKey>& firstKeys){

      int max = values.size() - 1;

      for(int i = 0; i < int(firstKeys.size()); ++i){

        int id = _first_key_proxy.notifier()->id(firstKeys[i]);

        if(max < id){

          max = id;

        }

      }

      int size = int(values.size());

      if(max >= size){

        values.resize(max + 1);

        if( int(values[0].size()) != 0){

          int innersize = int(values[0].size());

          for(int i = size; i < (max + 1); ++i){

            values[i].resize(innersize);

          }

        }else if(_second_key_proxy.notifier()->maxId() >= 0){

          int innersize = _second_key_proxy.notifier()->maxId();

          for(int i = 0; i < int(values.size()); ++i){

            values[i].resize(innersize);

          }

        }

      }

    }

    ///\brief Add a new SecondKey to the map.

    ///

    ///It adds a new SecondKey to the map. It is called by the

    ///observer class belongs to the SecondKey type.

    void addSecondKey(const SecondKey& secondKey) {

      if(values.size() == 0){

        return;

      }

      int id = _second_key_proxy.notifier()->id(secondKey);

      if(id >= int(values[0].size())){

        for(int i = 0; i < int(values.size());++i){

          values[i].resize(id+1);

        }

      }

    }

    ///\brief Adds more new SecondKeys to the map.

    ///

    ///It adds more new SecondKeys to the map. It called by the

    ///observer class belongs to the SecondKey type.

    void addSecondKeys(const std::vector<SecondKey>& secondKeys){

      if(values.size() == 0){

        return;

      }

      int max = values[0].size();

      for(int i = 0; i < int(secondKeys.size()); ++i){

        int id = _second_key_proxy.notifier()->id(secondKeys[i]);

        if(max < id){

          max = id;

        }