/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2006

  * 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.getNotifier(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.getNotifier(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::getNotifier();

       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::getNotifier()->id(first), 

                           Parent::getNotifier()->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::getNotifier()->id(first), 

                           Parent::getNotifier()->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::getNotifier()->id(first), 

                    Parent::getNotifier()->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::getNotifier()->id(key) + 1) >= (int)values.size()) {

 	values.resize(size(Parent::getNotifier()->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::getNotifier()->id(keys[i]) + 1) >= new_size) {

           new_size = size(Parent::getNotifier()->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::getNotifier()->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.getNotifier(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.getNotifier(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::getNotifier();

       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::getNotifier()->id(first), 

                           Parent::getNotifier()->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::getNotifier()->id(first), 

                           Parent::getNotifier()->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::getNotifier()->id(first), 

                    Parent::getNotifier()->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::getNotifier()->id(key) + 1) >= (int)values.size()) {

 	values.resize(size(Parent::getNotifier()->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::getNotifier()->id(keys[i]) + 1) >= new_size) {

           new_size = size(Parent::getNotifier()->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::getNotifier()->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".

   ///

   ///\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.getNotifier(FirstKey()));

       _second_key_proxy.attach(_secondContainer.getNotifier(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.getNotifier(FirstKey()));

       _second_key_proxy.attach(_secondContainer.getNotifier(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.getNotifier());

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

         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.getNotifier()->id(_first)]

         [_second_key_proxy.getNotifier()->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.getNotifier()->id(_first)]

         [_second_key_proxy.getNotifier()->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.getNotifier()->id(first)]

         [_second_key_proxy.getNotifier()->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.getNotifier();

       const typename SecondKeyProxy::Notifier* notifierSecondKey = 

         _second_key_proxy.getNotifier();

       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.getNotifier()->id(firstKey)+1 >= size ){

         values.resize(_first_key_proxy.getNotifier()->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.getNotifier()->maxId() >= 0){

           int innersize = _second_key_proxy.getNotifier()->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.getNotifier()->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.getNotifier()->maxId() >= 0){

           int innersize = _second_key_proxy.getNotifier()->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.getNotifier()->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.getNotifier()->id(secondKeys[i]);

         if(max < id){

           max = id;

         }

       }

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

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

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

         }

       }

     }

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

     ///

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

     ///class belongs to the FirstKey type.

     void eraseFirstKey(const FirstKey& first) {

       int id = _first_key_proxy.getNotifier()->id(first);

       for(int i = 0; i != (int)values[id].size(); ++i){

         values[id][i] = Value();

       }

     }

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

     ///

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

     ///class belongs to the FirstKey type.

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

       for(int j = 0; j != (int)firstKeys.size(); ++j){

         int id = _first_key_proxy.getNotifier()->id(firstKeys[j]);

         for(int i = 0; i != (int)values[id].size(); ++i){

           values[id][i] = Value();

         }

       }

     }

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

     ///

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

     ///belongs to the SecondKey type.

     void eraseSecondKey(const SecondKey& second) {

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

         return;

       }

       int id = _second_key_proxy.getNotifier()->id(second);

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

         values[i][id] = Value();

       }

     }

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

     ///

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

     ///class belongs to the SecondKey type.

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

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

         return;

       }

       for(int j = 0; j != (int)secondKeys.size(); ++j){

         int id = _second_key_proxy.getNotifier()->id(secondKeys[j]);

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

           values[i][id] = Value();

         }

       }

     }

     ///\brief Builds the map.

     ///

     ///It buildes the map. It is called by the observer class belongs

     ///to the FirstKey or SecondKey type.

     void build() {

       values.resize(_first_key_proxy.getNotifier()->maxId());

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

         values[i].resize(_second_key_proxy.getNotifier()->maxId());

       }

     }

     ///\brief Clear the map.

     ///

     ///It erases all items from the map. It is called by the observer class

     ///belongs to the FirstKey or SecondKey type.

     void clear() {

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

         values[i].clear();

       }

       values.clear();

     }

   };

 }

 #endif