deba@1720: /* -*- C++ -*-
deba@1720:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1720:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1720:  *
deba@1720:  * Permission to use, modify and distribute this software is granted
deba@1720:  * provided that this copyright notice appears in all copies. For
deba@1720:  * precise terms see the accompanying LICENSE file.
deba@1720:  *
deba@1720:  * This software is provided "AS IS" with no warranty of any kind,
deba@1720:  * express or implied, and with no claim as to its suitability for any
deba@1720:  * purpose.
deba@1720:  *
deba@1720:  */
deba@1720: 
deba@1720: #ifndef LEMON_MATRIX_MAPS_H
deba@1720: #define LEMON_MATRIX_MAPS_H
deba@1720: 
deba@1720: 
deba@1720: #include <vector>
deba@1993: #include <lemon/bits/utility.h>
alpar@2088: #include <lemon/bits/invalid.h>
deba@1720: #include <lemon/maps.h>
deba@1720: 
alpar@2260: #include <lemon/concepts/matrix_maps.h>
deba@1720: 
deba@1720: /// \file
alpar@2072: /// \ingroup matrices
deba@1720: /// \brief Maps indexed with pairs of items.
deba@1720: ///
alpar@2260: /// \todo This file has the same name as the concept file in concepts/,
deba@1720: ///  and this is not easily detectable in docs...
deba@1720: namespace lemon {
deba@1720: 
deba@1720:   /// \brief Map for the coloumn view of the matrix
deba@1720:   ///
alpar@2072:   /// \ingroup matrices
deba@1720:   /// Map for the coloumn view of the matrix.
alpar@2072:   ///
deba@1720:   template <typename _MatrixMap>
deba@2039:   class MatrixRowMap : public MatrixMapTraits<_MatrixMap> {
deba@1720:   public:
deba@1720:     typedef _MatrixMap MatrixMap;
deba@1720:     typedef typename MatrixMap::SecondKey Key;
deba@1720:     typedef typename MatrixMap::Value Value;
deba@1720: 
deba@1720: 
deba@2084:     /// \brief Constructor of the row map
deba@2084:     ///
deba@2084:     /// Constructor of the row map.
deba@1751:     MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) 
deba@1720:       : matrix(_matrix), row(_row) {}
deba@1720: 
deba@1720:     /// \brief Subscription operator
deba@1720:     ///
deba@1720:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ReturnValue
deba@1720:     operator[](Key col) {
deba@1751:       return matrix(row, col);
deba@1720:     }
deba@1720: 
deba@1720:     /// \brief Setter function
deba@1720:     ///
deba@1720:     /// Setter function.
deba@1720:     void set(Key col, const Value& val) {
deba@1751:       matrix.set(row, col, val);
deba@1720:     }
deba@1720:       
deba@1720:     /// \brief Subscription operator
deba@1720:     ///
deba@1720:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ConstReturnValue
deba@1720:     operator[](Key col) const {
deba@1751:       return matrix(row, col);
deba@1720:     }
deba@1720: 
deba@1720:   private:
deba@1720:     MatrixMap& matrix;
deba@1751:     typename MatrixMap::FirstKey row;
deba@1720:   };
deba@1720: 
deba@1720:   /// \brief Map for the row view of the matrix
deba@1720:   ///
alpar@2072:   /// \ingroup matrices
deba@1720:   /// Map for the row view of the matrix.
alpar@2072:   ///
deba@1720:   template <typename _MatrixMap>
deba@2039:   class ConstMatrixRowMap : public MatrixMapTraits<_MatrixMap> {
deba@1720:   public:
deba@1720:     typedef _MatrixMap MatrixMap;
deba@1751:     typedef typename MatrixMap::SecondKey Key;
deba@1720:     typedef typename MatrixMap::Value Value;
deba@1720: 
deba@1751: 
deba@2084:     /// \brief Constructor of the row map
deba@2084:     ///
deba@2084:     /// Constructor of the row map.
deba@1720:     ConstMatrixRowMap(const MatrixMap& _matrix, 
deba@1751: 		      typename MatrixMap::FirstKey _row) 
deba@1720:       : matrix(_matrix), row(_row) {}
deba@1720: 
deba@1720:     /// \brief Subscription operator
deba@1720:     ///
deba@1720:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ConstReturnValue
deba@1720:     operator[](Key col) const {
deba@1751:       return matrix(row, col);
deba@1720:     }
deba@1720: 
deba@1720:   private:
deba@1720:     const MatrixMap& matrix;
deba@1751:     typename MatrixMap::FirstKey row;
deba@1720:   };
deba@1720: 
deba@2084:   /// \ingroup matrices
deba@2084:   ///
deba@1720:   /// \brief Gives back a row view of the matrix map
deba@1720:   ///
deba@1720:   /// Gives back a row view of the matrix map.
alpar@2072:   ///
deba@2084:   /// \sa MatrixRowMap
deba@2084:   /// \sa ConstMatrixRowMap
deba@1720:   template <typename MatrixMap>
deba@1720:   MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
deba@1751: 				       typename MatrixMap::FirstKey row) {
deba@1720:     return MatrixRowMap<MatrixMap>(matrixMap, row);
deba@1720:   }
deba@1720: 
deba@1720:   template <typename MatrixMap>
deba@1751:   ConstMatrixRowMap<MatrixMap>
deba@1751:   matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {
deba@1720:     return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
deba@1720:   }
deba@1720: 
alpar@2072:   /// \brief Map for the column view of the matrix
deba@1751:   ///
alpar@2072:   /// \ingroup matrices
alpar@2072:   /// Map for the column view of the matrix.
alpar@2072:   ///
deba@1751:   template <typename _MatrixMap>
deba@2039:   class MatrixColMap : public MatrixMapTraits<_MatrixMap> {
deba@1751:   public:
deba@1751:     typedef _MatrixMap MatrixMap;
deba@1751:     typedef typename MatrixMap::FirstKey Key;
deba@1751:     typedef typename MatrixMap::Value Value;
deba@1751: 
deba@2084:     /// \brief Constructor of the column map
deba@2084:     ///
deba@2084:     /// Constructor of the column map.
deba@1751:     MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) 
deba@1751:       : matrix(_matrix), col(_col) {}
deba@1751: 
deba@1751:     /// \brief Subscription operator
deba@1751:     ///
deba@1751:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ReturnValue
deba@1751:     operator[](Key row) {
deba@1751:       return matrix(row, col);
deba@1751:     }
deba@1751: 
deba@1751:     /// \brief Setter function
deba@1751:     ///
deba@1751:     /// Setter function.
deba@1751:     void set(Key row, const Value& val) {
deba@1751:       matrix.set(row, col, val);
deba@1751:     }
deba@1751:       
deba@1751:     /// \brief Subscription operator
deba@1751:     ///
deba@1751:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ConstReturnValue
deba@1751:     operator[](Key row) const {
deba@1751:       return matrix(row, col);
deba@1751:     }
deba@1751: 
deba@1751:   private:
deba@1751:     MatrixMap& matrix;
deba@1751:     typename MatrixMap::SecondKey col;
deba@1751:   };
deba@1751: 
alpar@2072:   /// \brief Map for the column view of the matrix
deba@1751:   ///
alpar@2072:   /// \ingroup matrices
alpar@2072:   /// Map for the column view of the matrix.
alpar@2072:   ///
deba@1751:   template <typename _MatrixMap>
deba@2039:   class ConstMatrixColMap : public MatrixMapTraits<_MatrixMap> {
deba@1751:   public:
deba@1751:     typedef _MatrixMap MatrixMap;
deba@1751:     typedef typename MatrixMap::FirstKey Key;
deba@1751:     typedef typename MatrixMap::Value Value;
deba@1751: 
deba@2084:     /// \brief Constructor of the column map
deba@2084:     ///
deba@2084:     /// Constructor of the column map.
deba@1751:     ConstMatrixColMap(const MatrixMap& _matrix, 
deba@1751: 		      typename MatrixMap::SecondKey _col) 
deba@1751:       : matrix(_matrix), col(_col) {}
deba@1751: 
deba@1751:     /// \brief Subscription operator
deba@1751:     ///
deba@1751:     /// Subscription operator.
deba@2039:     typename MatrixMapTraits<MatrixMap>::ConstReturnValue
deba@1751:     operator[](Key row) const {
deba@1751:       return matrix(row, col);
deba@1751:     }
deba@1751: 
deba@1751:   private:
deba@1751:     const MatrixMap& matrix;
deba@1751:     typename MatrixMap::SecondKey col;
deba@1751:   };
deba@1751: 
deba@2084:   /// \ingroup matrices
deba@2084:   ///
alpar@2072:   /// \brief Gives back a column view of the matrix map
deba@1751:   ///
alpar@2072:   /// Gives back a column view of the matrix map.
alpar@2072:   ///
deba@2084:   /// \sa MatrixColMap
deba@2084:   /// \sa ConstMatrixColMap
deba@1751:   template <typename MatrixMap>
deba@1751:   MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
deba@1751: 				       typename MatrixMap::SecondKey col) {
deba@1751:     return MatrixColMap<MatrixMap>(matrixMap, col);
deba@1751:   }
deba@1751: 
deba@1751:   template <typename MatrixMap>
deba@1751:   ConstMatrixColMap<MatrixMap> 
deba@1751:   matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {
deba@1751:     return ConstMatrixColMap<MatrixMap>(matrixMap, col);
deba@1751:   }
deba@1751: 
deba@1720:   /// \brief Container for store values for each ordered pair of graph items
deba@1720:   ///
alpar@2072:   /// \ingroup matrices
alpar@1757:   /// This data structure can strore for each pair of the same item
deba@1720:   /// type a value. It increase the size of the container when the 
deba@1720:   /// associated graph modified, so it updated automaticly whenever
deba@1720:   /// it is needed.
deba@1720:   template <typename _Graph, typename _Item, typename _Value>
deba@1720:   class DynamicMatrixMap 
deba@1999:     : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
deba@1720:   public:
deba@1999:     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase 
deba@1999:     Parent;
deba@1720: 
deba@1720:     typedef _Graph Graph;
deba@1720:     typedef _Item Key;
deba@1720: 
deba@1720:     typedef _Item FirstKey;
deba@1720:     typedef _Item SecondKey;
deba@1720:     typedef _Value Value;
deba@1720: 
deba@1720:     typedef True ReferenceMapTag;
deba@1720: 
deba@1720:   private:
deba@1720: 		
deba@1720:     typedef std::vector<Value> Container;
deba@1720: 
deba@1720:   public:
deba@1720: 
deba@1720:     typedef typename Container::reference Reference;
deba@1720:     typedef typename Container::const_reference ConstReference;
deba@1720: 
deba@1720:     /// \brief Creates an item matrix for the given graph
deba@1720:     ///
deba@1720:     /// Creates an item matrix for the given graph.
deba@1720:     DynamicMatrixMap(const Graph& _graph) 
deba@1999:       : values(size(_graph.maxId(Key()) + 1)) {
deba@2384:       Parent::attach(_graph.notifier(Key()));
deba@1720:     }
deba@1720: 
deba@1720:     /// \brief Creates an item matrix for the given graph
deba@1720:     ///
deba@1720:     /// Creates an item matrix for the given graph and assigns for each
deba@1720:     /// pairs of keys the given parameter.
deba@1720:     DynamicMatrixMap(const Graph& _graph, const Value& _val) 
deba@1999:       : values(size(_graph.maxId(Key()) + 1), _val) {
deba@2384:       Parent::attach(_graph.notifier(Key()));
deba@1720:     }
deba@1720: 
deba@2039:     ///\brief The assignement operator.
deba@2039:     ///
deba@2039:     ///It allow to assign a map to an other.
deba@2039:     DynamicMatrixMap& operator=(const DynamicMatrixMap& _cmap){
deba@2039:       return operator=<DynamicMatrixMap>(_cmap);
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Template assignement operator.
deba@2039:     ///
deba@2039:     ///It copy the element of the given map to its own container.  The
deba@2039:     ///type of the two map shall be the same.
deba@2039:     template <typename CMap>
deba@2039:     DynamicMatrixMap& operator=(const CMap& _cmap){
alpar@2260:       checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();
deba@2384:       typename Parent::Notifier* notifier = Parent::notifier();
deba@2039:       Key first, second;
deba@2039:       for(notifier->first(first); first != INVALID; 
deba@2039:           notifier->next(first)){
deba@2039:         for(notifier->first(second); second != INVALID; 
deba@2039:             notifier->next(second)){
deba@2039:           set(first, second, _cmap(first, second));
deba@2039:         }
deba@2039:       }
deba@2039:       return *this;
deba@2039:     }
deba@2039: 
deba@1720:     /// \brief Gives back the value assigned to the \c first - \c second
deba@1720:     /// ordered pair.
deba@1720:     ///
deba@1720:     /// Gives back the value assigned to the \c first - \c second ordered pair.
deba@1720:     ConstReference operator()(const Key& first, const Key& second) const {
deba@2384:       return values[index(Parent::notifier()->id(first), 
deba@2384:                           Parent::notifier()->id(second))];
deba@1720:     }
deba@1720:     
deba@1720:     /// \brief Gives back the value assigned to the \c first - \c second
deba@1720:     /// ordered pair.
deba@1720:     ///
deba@1720:     /// Gives back the value assigned to the \c first - \c second ordered pair.
deba@1720:     Reference operator()(const Key& first, const Key& second) {
deba@2384:       return values[index(Parent::notifier()->id(first), 
deba@2384:                           Parent::notifier()->id(second))];
deba@1720:     }
deba@1720: 
deba@1720:     /// \brief Setter function for the matrix map.
deba@1720:     ///
deba@1720:     /// Setter function for the matrix map.
deba@1720:     void set(const Key& first, const Key& second, const Value& val) {
deba@2384:       values[index(Parent::notifier()->id(first), 
deba@2384:                    Parent::notifier()->id(second))] = val;
deba@1720:     }
deba@1720: 
deba@1720:   protected:
deba@1720: 
deba@1720:     static int index(int i, int j) {
deba@1720:       if (i < j) {
deba@1720: 	return j * j + i;
deba@1720:       } else {
deba@1720: 	return i * i + i + j;
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@1720:     static int size(int s) {
deba@1720:       return s * s;
deba@1720:     }
deba@1720: 
deba@1720:     virtual void add(const Key& key) {
deba@2386:       if (size(Parent::notifier()->id(key) + 1) >= int(values.size())) {
deba@2384: 	values.resize(size(Parent::notifier()->id(key) + 1));	
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@2305:     virtual void add(const std::vector<Key>& keys) {
deba@2305:       int new_size = 0;
deba@2386:       for (int i = 0; i < int(keys.size()); ++i) {
deba@2384:         if (size(Parent::notifier()->id(keys[i]) + 1) >= new_size) {
deba@2384:           new_size = size(Parent::notifier()->id(keys[i]) + 1);	
deba@2305:         }
deba@2305:       }
deba@2386:       if (new_size > int(values.size())) {
deba@2305:         values.resize(new_size);
deba@2305:       }
deba@2305:     }
deba@2305: 
deba@1720:     virtual void erase(const Key&) {}
deba@1720: 
deba@2305:     virtual void erase(const std::vector<Key>&) {}
deba@2305: 
deba@1720:     virtual void build() {
deba@2384:       values.resize(size(Parent::notifier()->maxId() + 1));
deba@1720:     }
deba@1720: 
deba@1720:     virtual void clear() {
deba@1720:       values.clear();
deba@1720:     }   
deba@1720:     
deba@1720:   private:
deba@1720:     std::vector<Value> values;
deba@1720:   };
deba@1720: 
deba@1720:   /// \brief Container for store values for each unordered pair of graph items
deba@1720:   ///
alpar@2072:   /// \ingroup matrices
alpar@1757:   /// This data structure can strore for each pair of the same item
deba@1720:   /// type a value. It increase the size of the container when the 
deba@1720:   /// associated graph modified, so it updated automaticly whenever
deba@1720:   /// it is needed. 
deba@1720:   template <typename _Graph, typename _Item, typename _Value>
deba@1720:   class DynamicSymMatrixMap 
deba@1999:     : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
deba@1720:   public:
deba@1999:     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase 
deba@1999:     Parent;
deba@1720: 
deba@1720:     typedef _Graph Graph;
deba@1720:     typedef _Item Key;
deba@1720: 
deba@1720:     typedef _Item FirstKey;
deba@1720:     typedef _Item SecondKey;
deba@1720:     typedef _Value Value;
deba@1720: 
deba@1720:     typedef True ReferenceMapTag;
deba@1720: 
deba@1720:   private:
deba@1720: 		
deba@1720:     typedef std::vector<Value> Container;
deba@1720: 
deba@1720:   public:
deba@1720: 
deba@1720:     typedef typename Container::reference Reference;
deba@1720:     typedef typename Container::const_reference ConstReference;
deba@1720: 
deba@1720:     /// \brief Creates an item matrix for the given graph
deba@1720:     ///
deba@1720:     /// Creates an item matrix for the given graph.
deba@1720:     DynamicSymMatrixMap(const Graph& _graph) 
deba@1999:       : values(size(_graph.maxId(Key()) + 1)) {
deba@2384:       Parent::attach(_graph.notifier(Key()));
deba@1720:     }
deba@1720: 
deba@1720:     /// \brief Creates an item matrix for the given graph
deba@1720:     ///
deba@1720:     /// Creates an item matrix for the given graph and assigns for each
deba@1720:     /// pairs of keys the given parameter.
deba@1720:     DynamicSymMatrixMap(const Graph& _graph, const Value& _val) 
deba@1999:       : values(size(_graph.maxId(Key()) + 1), _val) {
deba@2384:       Parent::attach(_graph.notifier(Key()));
deba@1720:     }
deba@1720: 
deba@2039: 
deba@2039:     ///\brief The assignement operator.
deba@2039:     ///
deba@2039:     ///It allow to assign a map to an other.
alpar@2072:     ///
deba@2039:     DynamicSymMatrixMap& operator=(const DynamicSymMatrixMap& _cmap){
deba@2039:       return operator=<DynamicSymMatrixMap>(_cmap);
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Template assignement operator.
deba@2039:     ///
deba@2039:     ///It copy the element of the given map to its own container.  The
deba@2039:     ///type of the two map shall be the same.
deba@2039:     template <typename CMap>
deba@2039:     DynamicSymMatrixMap& operator=(const CMap& _cmap){
alpar@2260:       checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();
deba@2384:       typename Parent::Notifier* notifier = Parent::notifier();
deba@2039:       Key first, second;
deba@2039:       for(notifier->first(first); first != INVALID; 
deba@2039:           notifier->next(first)){
deba@2039:         for(notifier->first(second); second != first; 
deba@2039:             notifier->next(second)){
deba@2039:           set(first, second, _cmap(first, second));
deba@2039:         }
deba@2039:         set(first, first, _cmap(first, first));        
deba@2039:       }
deba@2039:       return *this;
deba@2039:     }
deba@2039: 
deba@1720:     /// \brief Gives back the value assigned to the \c first - \c second
deba@1720:     /// unordered pair.
deba@1720:     ///
deba@1720:     /// Gives back the value assigned to the \c first - \c second unordered 
deba@1720:     /// pair.
deba@1720:     ConstReference operator()(const Key& first, const Key& second) const {
deba@2384:       return values[index(Parent::notifier()->id(first), 
deba@2384:                           Parent::notifier()->id(second))];
deba@1720:     }
deba@1720:     
deba@1720:     /// \brief Gives back the value assigned to the \c first - \c second
deba@1720:     /// unordered pair.
deba@1720:     ///
deba@1720:     /// Gives back the value assigned to the \c first - \c second unordered 
deba@1720:     /// pair.
deba@1720:     Reference operator()(const Key& first, const Key& second) {
deba@2384:       return values[index(Parent::notifier()->id(first), 
deba@2384:                           Parent::notifier()->id(second))];
deba@1720:     }
deba@1720: 
deba@1720:     /// \brief Setter function for the matrix map.
deba@1720:     ///
deba@1720:     /// Setter function for the matrix map.
alpar@2072:     ///
deba@1720:     void set(const Key& first, const Key& second, const Value& val) {
deba@2384:       values[index(Parent::notifier()->id(first), 
deba@2384:                    Parent::notifier()->id(second))] = val;
deba@1720:     }
deba@1720: 
deba@1720:   protected:
deba@1720: 
deba@1720:     static int index(int i, int j) {
deba@1720:       if (i < j) {
deba@1720: 	return j * (j + 1) / 2 + i;
deba@1720:       } else {
deba@1720: 	return i * (i + 1) / 2 + j;
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@1720:     static int size(int s) {
deba@1720:       return s * (s + 1) / 2;
deba@1720:     }
deba@1720: 
deba@1720:     virtual void add(const Key& key) {
deba@2386:       if (size(Parent::notifier()->id(key) + 1) >= int(values.size())) {
deba@2384: 	values.resize(size(Parent::notifier()->id(key) + 1));	
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@2305:     virtual void add(const std::vector<Key>& keys) {
deba@2305:       int new_size = 0;
deba@2386:       for (int i = 0; i < int(keys.size()); ++i) {
deba@2384:         if (size(Parent::notifier()->id(keys[i]) + 1) >= new_size) {
deba@2384:           new_size = size(Parent::notifier()->id(keys[i]) + 1);	
deba@2305:         }
deba@2305:       }
deba@2386:       if (new_size > int(values.size())) {
deba@2305:         values.resize(new_size);
deba@2305:       }
deba@2305:     }
deba@2305: 
deba@1720:     virtual void erase(const Key&) {}
deba@1720: 
deba@2305:     virtual void erase(const std::vector<Key>&) {}
deba@2305: 
deba@1720:     virtual void build() {
deba@2384:       values.resize(size(Parent::notifier()->maxId() + 1));
deba@1720:     }
deba@1720: 
deba@1720:     virtual void clear() {
deba@1720:       values.clear();
deba@1720:     }   
deba@1720:     
deba@1720:   private:
deba@1720:     std::vector<Value> values;
deba@1720:   };
deba@2039:   
deba@2039:   ///\brief Dynamic Asymmetric Matrix Map.
deba@2039:   ///
alpar@2072:   ///\ingroup matrices
deba@2039:   ///Dynamic Asymmetric Matrix Map.  Container for store values for each
deba@2039:   ///ordered pair of containers items.  This data structure can store
deba@2039:   ///data with different key types from different container types. It
deba@2039:   ///increases the size of the container if the linked containers
deba@2039:   ///content change, so it is updated automaticly whenever it is
deba@2039:   ///needed.
deba@2039:   ///
alpar@2260:   ///This map meet with the concepts::ReferenceMatrixMap<typename K1,
deba@2039:   ///typename K2, typename V, typename R, typename CR> called as
deba@2039:   ///"ReferenceMatrixMap".
deba@2039:   ///
deba@2376:   ///\warning Do not use this map type when the two item sets are
deba@2376:   ///equal or based on the same item set.
deba@2376:   ///
deba@2039:   ///\param _FirstContainer the desired type of first container. It is
deba@2039:   ///ususally a Graph type, but can be any type with alteration
deba@2039:   ///property.
deba@2039:   ///  
deba@2039:   ///\param _FirstContainerItem the nested type of the
deba@2039:   ///FirstContainer. It is usually a graph item as Node, Edge,
deba@2039:   ///etc. This type will be the FirstKey type.
deba@2039:   ///
deba@2039:   ///\param _SecondContainer the desired type of the second
deba@2039:   ///container. It is usualy a Graph type, but can be any type with
deba@2039:   ///alteration property.
deba@2039:   ///
deba@2039:   ///\param _SecondContainerItem the nested type of the
deba@2039:   ///SecondContainer. It is usually a graph item such as Node, Edge,
deba@2039:   ///UEdge, etc. This type will be the SecondKey type.
deba@2039:   ///
deba@2039:   ///\param _Value the type of the strored values in the container.
deba@2039:   ///
deba@2039:   /// \author Janos Nagy
deba@2039:   template <typename _FirstContainer, typename _FirstContainerItem, 
deba@2039:             typename _SecondContainer, typename _SecondContainerItem, 
deba@2039:             typename _Value>
deba@2039:   class DynamicAsymMatrixMap{
deba@2039:   public:
deba@2039: 
deba@2039:     ///The first key type.
deba@2039:     typedef _FirstContainerItem FirstKey;
deba@2039:       
deba@2039:     ///The second key type.
deba@2039:     typedef _SecondContainerItem SecondKey;
deba@2039:       
deba@2039:     ///The value type of the map.
deba@2039:     typedef _Value Value;
deba@2039:       
deba@2039:     ///Indicates it is a reference map.
deba@2039:     typedef True ReferenceMapTag;
deba@2039:     
deba@2039:   protected:
deba@2039:       
deba@2039:     ///\brief Proxy class for the first key type.
deba@2039:     ///
deba@2039:     ///The proxy class belongs to the FirstKey type. It is necessary because
deba@2039:     ///if one want use the same conatainer types and same nested types but on
deba@2039:     ///other instances of containers than due to the type equiality of nested
deba@2039:     ///types it requires a proxy mechanism. 
deba@2039:     class FirstKeyProxy 
deba@2039:       : protected 
deba@2039:     ItemSetTraits<_FirstContainer,_FirstContainerItem>::
deba@2039:     ItemNotifier::ObserverBase 
deba@2039:     {
deba@2039:         
deba@2039:     public:
deba@2039: 
deba@2039:       friend class DynamicAsymMatrixMap;
deba@2039:           
deba@2039:       ///Constructor.
deba@2039:       FirstKeyProxy(DynamicAsymMatrixMap& _map) : _owner(_map) { }
deba@2039:     protected:
deba@2039: 
deba@2039:       ///\brief Add a new FirstKey to the map.
deba@2039:       ///
deba@2039:       ///It adds a new FirstKey to the map. It is called by the
deba@2039:       ///observer notifier and it is ovverride the add() virtual
deba@2039:       ///member function in the observer base. It will call the
deba@2039:       ///maps addFirstKey() function.
deba@2039:       virtual void add(const FirstKey& _firstKey){
deba@2039:         _owner.addFirstKey(_firstKey);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Add more new FirstKey to the map.
deba@2039:       ///
deba@2039:       ///It adds more new FirstKey to the map. It is called by the
deba@2039:       ///observer notifier and it is ovverride the add() virtual
deba@2039:       ///member function in the observer base. It will call the
deba@2039:       ///map's addFirstKeys() function.
deba@2039:       virtual void add(const std::vector<FirstKey>& _firstKeys){
deba@2039:         _owner.addFirstKeys(_firstKeys);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Erase a FirstKey from the map.
deba@2039:       ///
deba@2039:       ///Erase a FirstKey from the map. It called by the observer
deba@2039:       ///notifier and it overrides the erase() virtual member
deba@2039:       ///function of the observer base. It will call the map's
deba@2039:       ///eraseFirstKey() function.
deba@2039:       virtual void erase(const FirstKey& _firstKey){
deba@2039:         _owner.eraseFirstKey(_firstKey);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Erase more FirstKey from the map.
deba@2039:       ///
deba@2039:       ///Erase more FirstKey from the map. It called by the
deba@2039:       ///observer notifier and it overrides the erase() virtual
deba@2039:       ///member function of the observer base. It will call the
deba@2039:       ///map's eraseFirstKeys() function.
deba@2039:       virtual void erase(const std::vector<FirstKey>& _firstKeys){
deba@2039:         _owner.eraseFirstKeys(_firstKeys);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Builds the map.
deba@2039:       ///
deba@2039:       ///It buildes the map. It called by the observer notifier
deba@2039:       ///and it overrides the build() virtual member function of
deba@2039:       ///the observer base.  It will call the map's build()
deba@2039:       ///function.
deba@2039:       virtual void build() {
deba@2039:         _owner.build();
deba@2039:         //_owner.buildFirst();
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Clear the map.
deba@2039:       ///
deba@2039:       ///It erases all items from the map. It called by the
deba@2039:       ///observer notifier and it overrides the clear() virtual
deba@2039:       ///memeber function of the observer base. It will call the
deba@2039:       ///map's clear() function.
deba@2039:       virtual void clear() {
deba@2039:         _owner.clear();
deba@2039:         //_owner.clearFirst();
deba@2039:       }
deba@2039:     private:
deba@2039:           
deba@2039:       ///The map type for it is linked.
deba@2039:       DynamicAsymMatrixMap& _owner;
alpar@2072:     };//END OF FIRSTKEYPROXY
deba@2039:       
deba@2039:       ///\brief Proxy class for the second key type.
deba@2039:       ///
ladanyi@2047:       ///The proxy class belongs to the SecondKey type. It is
deba@2039:       ///necessary because if one want use the same conatainer types
deba@2039:       ///and same nested types but on other instances of containers
deba@2039:       ///than due to the type equiality of nested types it requires a
deba@2039:       ///proxy mechanism.
deba@2039:     class SecondKeyProxy
deba@2039:       : protected 
deba@2039:     ItemSetTraits<_SecondContainer, _SecondContainerItem>::
deba@2039:     ItemNotifier::ObserverBase {
deba@2039:         
deba@2039:     public:
deba@2039: 
deba@2039:       friend class DynamicAsymMatrixMap;
deba@2039:       ///Constructor.
deba@2039:       SecondKeyProxy(DynamicAsymMatrixMap& _map) : _owner(_map) { }
deba@2039: 
deba@2039:     protected:
deba@2039:           
deba@2039:       ///\brief Add a new SecondKey to the map.
deba@2039:       ///
deba@2039:       ///It adds a new SecondKey to the map. It is called by the
deba@2039:       ///observer notifier and it is ovverride the add() virtual
deba@2039:       ///member function in the observer base. It will call the
deba@2039:       ///maps addSecondKey() function.
deba@2039:       virtual void add(const SecondKey& _secondKey){
deba@2039:         _owner.addSecondKey(_secondKey);
deba@2039:       }
deba@2039:     
deba@2039:       ///\brief Add more new SecondKey to the map.
deba@2039:       ///
deba@2039:       ///It adds more new SecondKey to the map. It is called by
deba@2039:       ///the observer notifier and it is ovverride the add()
deba@2039:       ///virtual member function in the observer base. It will
deba@2039:       ///call the maps addSecondKeys() function.
deba@2039:       virtual void add(const std::vector<SecondKey>& _secondKeys){
deba@2039:         _owner.addSecondKeys(_secondKeys);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Erase a SecondKey from the map.
deba@2039:       ///
deba@2039:       ///Erase a SecondKey from the map. It called by the observer
deba@2039:       ///notifier and it overrides the erase() virtual member
deba@2039:       ///function of the observer base. It will call the map's
deba@2039:       ///eraseSecondKey() function.
deba@2039:       virtual void erase(const SecondKey& _secondKey){
deba@2039:         _owner.eraseSecondKey(_secondKey);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Erase more SecondKeys from the map.
deba@2039:       ///
deba@2039:       ///Erase more SecondKey from the map. It called by the
deba@2039:       ///observer notifier and it overrides the erase() virtual
deba@2039:       ///member function of the observer base. It will call the
deba@2039:       ///map's eraseSecondKeys() function.
deba@2039:       virtual void erase(const std::vector<SecondKey>& _secondKeys){
deba@2039:         _owner.eraseSecondKeys(_secondKeys);
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Builds the map.
deba@2039:       ///
deba@2039:       ///It buildes the map. It called by the observer notifier
deba@2039:       ///and it overrides the build() virtual member function of
deba@2039:       ///the observer base.  It will call the map's build()
deba@2039:       ///function.
deba@2039:       virtual void build() {
deba@2039:         _owner.build();
deba@2039:       }
deba@2039:           
deba@2039:       ///\brief Clear the map.
deba@2039:       ///
deba@2039:       ///It erases all items from the map. It called by the
deba@2039:       ///observer notifier and it overrides the clear() virtual
deba@2039:       ///memeber function of the observer base. It will call the
deba@2039:       ///map's clear() function.
deba@2039:       virtual void clear() {
deba@2039:         _owner.clear();
deba@2039:         //_owner.clearFirst();
deba@2039:       }
deba@2039:     private:
deba@2039:           
deba@2039:       ///The type of map for which it is attached.
deba@2039:       DynamicAsymMatrixMap& _owner;
alpar@2072:     };//END OF SECONDKEYPROXY
deba@2039:       
deba@2039:   private:
deba@2039:     
deba@2039:     /// \e
deba@2039:     typedef std::vector<Value> Container;
deba@2039:       
deba@2039:     ///The type of constainer which stores the values of the map.
deba@2039:     typedef std::vector<Container> DContainer;
deba@2039: 
deba@2039:     ///The std:vector type which contains the data
deba@2039:     DContainer values;
deba@2039:       
deba@2039:     ///Member for the first proxy class
deba@2039:     FirstKeyProxy _first_key_proxy;
deba@2039:       
deba@2039:     ///Member for the second proxy class
deba@2039:     SecondKeyProxy _second_key_proxy;
deba@2039: 
deba@2039:   public:
deba@2039:     
deba@2039:     ///The refernce type of the map.
deba@2039:     typedef typename Container::reference Reference;
deba@2039:       
deba@2039:     ///The const reference type of the constainer.
deba@2039:     typedef typename Container::const_reference ConstReference;
deba@2039: 
deba@2039:     ///\brief Constructor what create the map for the two containers type.
deba@2039:     ///
deba@2039:     ///Creates the matrix map and initialize the values with Value()
deba@2039:     DynamicAsymMatrixMap(const _FirstContainer& _firstContainer, 
deba@2039:                   const _SecondContainer& _secondContainer)
deba@2039:       : values(DContainer(_firstContainer.maxId(FirstKey())+1,
deba@2039:                           Container(_secondContainer.maxId(SecondKey())+1))),
deba@2039:         _first_key_proxy(*this),
deba@2039:         _second_key_proxy(*this)
deba@2039:     {
deba@2384:       _first_key_proxy.attach(_firstContainer.notifier(FirstKey()));
deba@2384:       _second_key_proxy.attach(_secondContainer.notifier(SecondKey()));
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Constructor what create the map for the two containers type.
deba@2039:     ///
deba@2039:     ///Creates the matrix map and initialize the values with the given _value
deba@2039:     DynamicAsymMatrixMap(const _FirstContainer& _firstContainer, 
deba@2039:                   const _SecondContainer& _secondContainer, 
deba@2039:                   const Value& _value)
deba@2039:       : values(DContainer(_firstContainer.maxId(FirstKey())+1,
deba@2039:                           Container(_secondContainer.maxId(SecondKey())+1,
deba@2039:                                     _value))),
deba@2039:         _first_key_proxy(*this),
deba@2039:         _second_key_proxy(*this)
deba@2039:     {
deba@2384:       _first_key_proxy.attach(_firstContainer.notifier(FirstKey()));
deba@2384:       _second_key_proxy.attach(_secondContainer.notifier(SecondKey()));
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Copy constructor.
deba@2039:     ///
deba@2039:     ///The copy constructor of the map.
deba@2039:     DynamicAsymMatrixMap(const DynamicAsymMatrixMap& _copy) 
deba@2039:       : _first_key_proxy(*this), _second_key_proxy(*this) {
deba@2039:       if(_copy._first_key_proxy.attached() && 
deba@2039:          _copy._second_key_proxy.attached()){
deba@2384:         _first_key_proxy.attach(*_copy._first_key_proxy.notifier());
deba@2384:         _second_key_proxy.attach(*_copy._second_key_proxy.notifier());
deba@2039:         values = _copy.values;
deba@2039:       }
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Destructor
deba@2039:     ///
deba@2039:     ///Destructor what detach() from the attached objects.  May this
deba@2039:     ///function is not necessary because the destructor of
deba@2039:     ///ObserverBase do the same.
deba@2039:     ~DynamicAsymMatrixMap() {
deba@2039:       if(_first_key_proxy.attached()){
deba@2039:         _first_key_proxy.detach();
deba@2039:       }
deba@2039:       if(_second_key_proxy.attached()){
deba@2039:         _second_key_proxy.detach();
deba@2039:       }
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Gives back the value assigned to the \c first - \c
deba@2039:     ///second ordered pair.
deba@2039:     ///
deba@2039:     ///Gives back the value assigned to the \c first - \c second
deba@2039:     ///ordered pair.
deba@2039:     Reference operator()(const FirstKey& _first, const SecondKey& _second) {
deba@2384:       return values[_first_key_proxy.notifier()->id(_first)]
deba@2384:         [_second_key_proxy.notifier()->id(_second)];
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Gives back the value assigned to the \c first - \c
deba@2039:     ///second ordered pair.
deba@2039:     ///
deba@2039:     ///Gives back the value assigned to the \c first - \c second
deba@2039:     ///ordered pair.
deba@2039:     ConstReference operator()(const FirstKey& _first, 
deba@2039:                               const SecondKey& _second) const {
deba@2384:       return values[_first_key_proxy.notifier()->id(_first)]
deba@2384:         [_second_key_proxy.notifier()->id(_second)];
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Setter function for this matrix map.
deba@2039:     ///
deba@2039:     ///Setter function for this matrix map.
deba@2039:     void set(const FirstKey& first, const SecondKey& second, 
deba@2039:              const Value& value){
deba@2384:       values[_first_key_proxy.notifier()->id(first)]
deba@2384:         [_second_key_proxy.notifier()->id(second)] = value;
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief The assignement operator.
deba@2039:     ///
deba@2039:     ///It allow to assign a map to an other. It
deba@2039:     DynamicAsymMatrixMap& operator=(const DynamicAsymMatrixMap& _cmap){
deba@2039:       return operator=<DynamicAsymMatrixMap>(_cmap);
deba@2039:     }
deba@2039:       
deba@2039:     ///\brief Template assignement operator.
deba@2039:     ///
deba@2039:     ///It copy the element of the given map to its own container.  The
deba@2039:     ///type of the two map shall be the same.
deba@2039:     template <typename CMap>
deba@2039:     DynamicAsymMatrixMap& operator=(const CMap& _cdmap){
alpar@2260:       checkConcept<concepts::ReadMatrixMap<FirstKey, SecondKey, Value>, CMap>();
deba@2039:       const typename FirstKeyProxy::Notifier* notifierFirstKey = 
deba@2384:         _first_key_proxy.notifier();
deba@2039:       const typename SecondKeyProxy::Notifier* notifierSecondKey = 
deba@2384:         _second_key_proxy.notifier();
deba@2039:       FirstKey itemFirst;
deba@2039:       SecondKey itemSecond;
deba@2039:       for(notifierFirstKey->first(itemFirst); itemFirst != INVALID; 
deba@2039:           notifierFirstKey->next(itemFirst)){
deba@2039:         for(notifierSecondKey->first(itemSecond); itemSecond != INVALID; 
deba@2039:             notifierSecondKey->next(itemSecond)){
deba@2039:           set(itemFirst, itemSecond, _cdmap(itemFirst,itemSecond));
deba@2039:         }
deba@2039:       }
deba@2039:       return *this;
deba@2039:     }
deba@2039:       
deba@2039:   protected:
deba@2039:     
deba@2039:     ///\brief Add a new FirstKey to the map.
deba@2039:     ///
deba@2039:     ///It adds a new FirstKey to the map. It is called by the observer
deba@2039:     ///class belongs to the FirstKey type.
deba@2039:     void addFirstKey(const FirstKey& firstKey) {
deba@2386:       int size = int(values.size());
deba@2384:       if( _first_key_proxy.notifier()->id(firstKey)+1 >= size ){
deba@2384:         values.resize(_first_key_proxy.notifier()->id(firstKey)+1);
deba@2386:         if( int(values[0].size()) != 0 ){
deba@2386:           int innersize = int(values[0].size());
deba@2386:           for(int i = size; i < int(values.size());++i){
deba@2039:             (values[i]).resize(innersize);
deba@2039:           }
deba@2384:         }else if(_second_key_proxy.notifier()->maxId() >= 0){
deba@2384:           int innersize = _second_key_proxy.notifier()->maxId();
deba@2386:           for(int i = 0; i < int(values.size()); ++i){
deba@2039:             values[0].resize(innersize);
deba@2039:           }
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Adds more new FirstKeys to the map.
deba@2039:     ///
deba@2039:     ///It adds more new FirstKeys to the map. It called by the
deba@2039:     ///observer class belongs to the FirstKey type.
deba@2039:     void addFirstKeys(const std::vector<FirstKey>& firstKeys){
deba@2039:       int max = values.size() - 1;
deba@2386:       for(int i = 0; i < int(firstKeys.size()); ++i){
deba@2384:         int id = _first_key_proxy.notifier()->id(firstKeys[i]);
deba@2039:         if(max < id){
deba@2039:           max = id;
deba@2039:         }
deba@2039:       }
deba@2386:       int size = int(values.size());
deba@2039:       if(max >= size){
deba@2039:         values.resize(max + 1);
deba@2386:         if( int(values[0].size()) != 0){
deba@2386:           int innersize = int(values[0].size());
deba@2386:           for(int i = size; i < (max + 1); ++i){
deba@2039:             values[i].resize(innersize);
deba@2039:           }
deba@2384:         }else if(_second_key_proxy.notifier()->maxId() >= 0){
deba@2384:           int innersize = _second_key_proxy.notifier()->maxId();
deba@2386:           for(int i = 0; i < int(values.size()); ++i){
deba@2039:             values[i].resize(innersize);
deba@2039:           }
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Add a new SecondKey to the map.
deba@2039:     ///
deba@2039:     ///It adds a new SecondKey to the map. It is called by the
deba@2039:     ///observer class belongs to the SecondKey type.
deba@2039:     void addSecondKey(const SecondKey& secondKey) {
deba@2039:       if(values.size() == 0){
deba@2039:         return;
deba@2039:       }
deba@2384:       int id = _second_key_proxy.notifier()->id(secondKey);
deba@2386:       if(id >= int(values[0].size())){
deba@2386:         for(int i = 0; i < int(values.size());++i){
deba@2039:           values[i].resize(id+1);
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039:         
deba@2039:     ///\brief Adds more new SecondKeys to the map.
deba@2039:     ///
deba@2039:     ///It adds more new SecondKeys to the map. It called by the
deba@2039:     ///observer class belongs to the SecondKey type.
deba@2039:     void addSecondKeys(const std::vector<SecondKey>& secondKeys){
deba@2039:       if(values.size() == 0){
deba@2039:         return;
deba@2039:       }
deba@2039:       int max = values[0].size();
deba@2386:       for(int i = 0; i < int(secondKeys.size()); ++i){
deba@2384:         int id = _second_key_proxy.notifier()->id(secondKeys[i]);
deba@2039:         if(max < id){
deba@2039:           max = id;
deba@2039:         }
deba@2039:       }
deba@2386:       if(max > int(values[0].size())){
deba@2386:         for(int i = 0; i < int(values.size()); ++i){
deba@2039:           values[i].resize(max + 1);
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039:     
deba@2039:     ///\brief Erase a FirstKey from the map.
deba@2039:     ///
deba@2039:     ///Erase a FirstKey from the map. It called by the observer
deba@2039:     ///class belongs to the FirstKey type.
deba@2039:     void eraseFirstKey(const FirstKey& first) {
deba@2384:       int id = _first_key_proxy.notifier()->id(first);
deba@2386:       for(int i = 0; i < int(values[id].size()); ++i){
deba@2039:         values[id][i] = Value();
deba@2039:       }
deba@2039:     }
deba@2039:         
deba@2039:     ///\brief Erase more FirstKey from the map.
deba@2039:     ///
deba@2039:     ///Erase more FirstKey from the map. It called by the observer
deba@2039:     ///class belongs to the FirstKey type.
deba@2039:     void eraseFirstKeys(const std::vector<FirstKey>& firstKeys) {
deba@2386:       for(int j = 0; j < int(firstKeys.size()); ++j){
deba@2384:         int id = _first_key_proxy.notifier()->id(firstKeys[j]);
deba@2386:         for(int i = 0; i < int(values[id].size()); ++i){
deba@2039:           values[id][i] = Value();
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Erase a SecondKey from the map.
deba@2039:     ///
deba@2039:     ///Erase a SecondKey from the map. It called by the observer class
deba@2039:     ///belongs to the SecondKey type.
deba@2039:     void eraseSecondKey(const SecondKey& second) {
deba@2039:       if(values.size() == 0){
deba@2039:         return;
deba@2039:       }
deba@2384:       int id = _second_key_proxy.notifier()->id(second);
deba@2386:       for(int i = 0; i < int(values.size()); ++i){
deba@2039:         values[i][id] = Value();
deba@2039:       }
deba@2039:     }
deba@2039:         
deba@2039:     ///\brief Erase more SecondKey from the map.
deba@2039:     ///
deba@2039:     ///Erase more SecondKey from the map. It called by the observer
deba@2039:     ///class belongs to the SecondKey type.
deba@2039:     void eraseSecondKeys(const std::vector<SecondKey>& secondKeys) {
deba@2039:       if(values.size() == 0){
deba@2039:         return;
deba@2039:       }
deba@2386:       for(int j = 0; j < int(secondKeys.size()); ++j){
deba@2384:         int id = _second_key_proxy.notifier()->id(secondKeys[j]);
deba@2386:         for(int i = 0; i < int(values.size()); ++i){
deba@2039:           values[i][id] = Value();
deba@2039:         }
deba@2039:       }
deba@2039:     }
deba@2039: 
deba@2039:     ///\brief Builds the map.
deba@2039:     ///
deba@2039:     ///It buildes the map. It is called by the observer class belongs
deba@2039:     ///to the FirstKey or SecondKey type.
deba@2039:     void build() {
deba@2384:       values.resize(_first_key_proxy.notifier()->maxId());
deba@2386:       for(int i = 0; i< int(values.size()); ++i){
deba@2384:         values[i].resize(_second_key_proxy.notifier()->maxId());
deba@2039:       }
deba@2039:     }
deba@2039:     
deba@2039:     ///\brief Clear the map.
deba@2039:     ///
deba@2039:     ///It erases all items from the map. It is called by the observer class
deba@2039:     ///belongs to the FirstKey or SecondKey type.
deba@2039:     void clear() {
deba@2386:       for(int i = 0; i < int(values.size()); ++i) {
deba@2039:         values[i].clear();
deba@2039:       }
deba@2039:       values.clear();
deba@2039:     }
deba@2039:  
deba@2039:   };
deba@2039: 
deba@2039: 
deba@1720: 
deba@1720: }
deba@1720: 
deba@1720: #endif