/* -*- C++ -*-

 * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 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/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 AlterationNotifier<_Item>::ObserverBase {

  public:

    typedef typename AlterationNotifier<_Item>::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) 

      : 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) 

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

      Parent::attach(graph.getNotifier(Key()));

    }

    ~DynamicMatrixMap() {

      if (Parent::attached()) {

	Parent::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.

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

      return values[index(graph.id(first), graph.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(graph.id(first), graph.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(graph.id(first), graph.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(graph.id(key) + 1) >= (int)values.size()) {

	values.resize(size(graph.id(key) + 1));	

      }

    }

    virtual void erase(const Key&) {}

    virtual void build() {

      values.resize(size(graph.maxId(Key()) + 1));

    }

    virtual void clear() {

      values.clear();

    }   

  private:

    const Graph& graph;

    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 AlterationNotifier<_Item>::ObserverBase {

  public:

    typedef typename AlterationNotifier<_Item>::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) 

      : 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) 

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

      Parent::attach(graph.getNotifier(Key()));

    }

    ~DynamicSymMatrixMap() {

      if (Parent::attached()) {

	Parent::detach();

      }

    }

    /// \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(graph.id(first), graph.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(graph.id(first), graph.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(graph.id(first), graph.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(graph.id(key) + 1) >= (int)values.size()) {

	values.resize(size(graph.id(key) + 1));	

      }

    }

    virtual void erase(const Key&) {}

    virtual void build() {

      values.resize(size(graph.maxId(Key()) + 1));

    }

    virtual void clear() {

      values.clear();

    }   

  private:

    const Graph& graph;

    std::vector<Value> values;

  };

}

#endif