source: lemon-0.x/lemon/matrix_maps.h @ 1757:bd4199049036

/* -*- 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