/* -*- 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/maps.h>

 /// \file

 /// \ingroup maps

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

 ///

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

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

 namespace lemon {

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

   ///

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

   template <typename _MatrixMap>

   class MatrixRowMap : public MapTraits<_MatrixMap> {

   public:

     typedef _MatrixMap MatrixMap;

     typedef typename MatrixMap::SecondKey Key;

     typedef typename MatrixMap::Value Value;

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

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

     /// \brief Subscription operator

     ///

     /// Subscription operator.

     typename MapTraits<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 MapTraits<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

   ///

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

   template <typename _MatrixMap>

   class ConstMatrixRowMap : public MapTraits<_MatrixMap> {

   public:

     typedef _MatrixMap MatrixMap;

     typedef typename MatrixMap::SecondKey Key;

     typedef typename MatrixMap::Value Value;

     ConstMatrixRowMap(const MatrixMap& _matrix, 

 		      typename MatrixMap::FirstKey _row) 

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

     /// \brief Subscription operator

     ///

     /// Subscription operator.

     typename MapTraits<MatrixMap>::ConstReturnValue

     operator[](Key col) const {

       return matrix(row, col);

     }

   private:

     const MatrixMap& matrix;

     typename MatrixMap::FirstKey row;

   };

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

   ///

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

   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 row view of the matrix

   ///

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

   template <typename _MatrixMap>

   class MatrixColMap : public MapTraits<_MatrixMap> {

   public:

     typedef _MatrixMap MatrixMap;

     typedef typename MatrixMap::FirstKey Key;

     typedef typename MatrixMap::Value Value;

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

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

     /// \brief Subscription operator

     ///

     /// Subscription operator.

     typename MapTraits<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 MapTraits<MatrixMap>::ConstReturnValue

     operator[](Key row) const {

       return matrix(row, col);

     }

   private:

     MatrixMap& matrix;

     typename MatrixMap::SecondKey col;

   };

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

   ///

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

   template <typename _MatrixMap>

   class ConstMatrixColMap : public MapTraits<_MatrixMap> {

   public:

     typedef _MatrixMap MatrixMap;

     typedef typename MatrixMap::FirstKey Key;

     typedef typename MatrixMap::Value Value;

     ConstMatrixColMap(const MatrixMap& _matrix, 

 		      typename MatrixMap::SecondKey _col) 

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

     /// \brief Subscription operator

     ///

     /// Subscription operator.

     typename MapTraits<MatrixMap>::ConstReturnValue

     operator[](Key row) const {

       return matrix(row, col);

     }

   private:

     const MatrixMap& matrix;

     typename MatrixMap::SecondKey col;

   };

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

   ///

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

   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

   ///

   /// 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 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 erase(const 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

   ///

   /// 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 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 erase(const Key&) {}

     virtual void build() {

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

     }

     virtual void clear() {

       values.clear();

     }   

   private:

     std::vector<Value> values;

   };

 }

 #endif