deba@1720: /* -*- C++ -*-
deba@1720:  * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
deba@1720:  *
alpar@1875:  * Copyright (C) 2006 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@1720: #include <lemon/utility.h>
deba@1720: #include <lemon/maps.h>
deba@1720: 
deba@1720: 
deba@1720: /// \file
deba@1720: /// \ingroup maps
deba@1720: /// \brief Maps indexed with pairs of items.
deba@1720: ///
deba@1720: /// \todo This file has the same name as the concept file in concept/,
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:   ///
deba@1720:   /// Map for the coloumn view of the matrix.
deba@1720:   template <typename _MatrixMap>
deba@1751:   class MatrixRowMap : public MapTraits<_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@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@1720:     typename MapTraits<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@1720:     typename MapTraits<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:   ///
deba@1720:   /// Map for the row view of the matrix.
deba@1720:   template <typename _MatrixMap>
deba@1720:   class ConstMatrixRowMap : public MapTraits<_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@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@1720:     typename MapTraits<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@1720:   /// \brief Gives back a row view of the matrix map
deba@1720:   ///
deba@1720:   /// Gives back a row view of the matrix map.
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: 
deba@1751:   /// \brief Map for the row view of the matrix
deba@1751:   ///
deba@1751:   /// Map for the row view of the matrix.
deba@1751:   template <typename _MatrixMap>
deba@1751:   class MatrixColMap : public MapTraits<_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@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@1751:     typename MapTraits<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@1751:     typename MapTraits<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: 
deba@1751:   /// \brief Map for the col view of the matrix
deba@1751:   ///
deba@1751:   /// Map for the col view of the matrix.
deba@1751:   template <typename _MatrixMap>
deba@1751:   class ConstMatrixColMap : public MapTraits<_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@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@1751:     typename MapTraits<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@1751:   /// \brief Gives back a col view of the matrix map
deba@1751:   ///
deba@1751:   /// Gives back a col view of the matrix map.
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@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@1720:     : protected AlterationNotifier<_Item>::ObserverBase {
deba@1720:   public:
deba@1720:     typedef typename AlterationNotifier<_Item>::ObserverBase 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@1720:       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
deba@1720:       Parent::attach(graph.getNotifier(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@1720:       : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
deba@1720:       Parent::attach(graph.getNotifier(Key()));
deba@1720:     }
deba@1720: 
deba@1720:     ~DynamicMatrixMap() {
deba@1720:       if (Parent::attached()) {
deba@1720: 	Parent::detach();
deba@1720:       }
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:     ConstReference operator()(const Key& first, const Key& second) const {
deba@1720:       return values[index(graph.id(first), graph.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@1720:       return values[index(graph.id(first), graph.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@1720:       values[index(graph.id(first), graph.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@1720:       if (size(graph.id(key) + 1) >= (int)values.size()) {
deba@1720: 	values.resize(size(graph.id(key) + 1));	
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@1720:     virtual void erase(const Key&) {}
deba@1720: 
deba@1720:     virtual void build() {
deba@1720:       values.resize(size(graph.maxId(Key()) + 1));
deba@1720:     }
deba@1720: 
deba@1720:     virtual void clear() {
deba@1720:       values.clear();
deba@1720:     }   
deba@1720:     
deba@1720:   private:
deba@1720:     const Graph& graph;
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@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@1720:     : protected AlterationNotifier<_Item>::ObserverBase {
deba@1720:   public:
deba@1720:     typedef typename AlterationNotifier<_Item>::ObserverBase 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@1720:       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
deba@1720:       Parent::attach(graph.getNotifier(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@1720:       : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
deba@1720:       Parent::attach(graph.getNotifier(Key()));
deba@1720:     }
deba@1720: 
deba@1720:     ~DynamicSymMatrixMap() {
deba@1720:       if (Parent::attached()) {
deba@1720: 	Parent::detach();
deba@1720:       }
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:     ConstReference operator()(const Key& first, const Key& second) const {
deba@1720:       return values[index(graph.id(first), graph.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@1720:       return values[index(graph.id(first), graph.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@1720:       values[index(graph.id(first), graph.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@1720:       if (size(graph.id(key) + 1) >= (int)values.size()) {
deba@1720: 	values.resize(size(graph.id(key) + 1));	
deba@1720:       }
deba@1720:     }
deba@1720: 
deba@1720:     virtual void erase(const Key&) {}
deba@1720: 
deba@1720:     virtual void build() {
deba@1720:       values.resize(size(graph.maxId(Key()) + 1));
deba@1720:     }
deba@1720: 
deba@1720:     virtual void clear() {
deba@1720:       values.clear();
deba@1720:     }   
deba@1720:     
deba@1720:   private:
deba@1720:     const Graph& graph;
deba@1720:     std::vector<Value> values;
deba@1720:   };
deba@1720: 
deba@1720: }
deba@1720: 
deba@1720: #endif