lemon-0.x: comparison lemon/matrix

equal deleted inserted replaced

--1:000000000000
+:09d18a73361d
+/* -*- 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 MatrixColMap : public MapTraits<_MatrixMap> {
+public:
+typedef _MatrixMap MatrixMap;
+typedef typename MatrixMap::SecondKey Key;
+typedef typename MatrixMap::Value Value;
+MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col)
+: matrix(_matrix), col(_col) {}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ReturnValue
+operator[](Key row) {
+return matrix(col, row);
+}
+/// \brief Setter function
+///
+/// Setter function.
+void set(Key row, const Value& val) {
+matrix.set(col, row, val);
+}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ConstReturnValue
+operator[](Key row) const {
+return matrix(col, row);
+}
+private:
+MatrixMap& matrix;
+typename MatrixMap::FirstKey col;
+};
+/// \brief Map for the coloumn view of the matrix
+///
+/// Map for the coloumn view of the matrix.
+template <typename _MatrixMap>
+class ConstMatrixColMap : public MapTraits<_MatrixMap> {
+public:
+typedef _MatrixMap MatrixMap;
+typedef typename MatrixMap::SecondKey Key;
+typedef typename MatrixMap::Value Value;
+ConstMatrixColMap(const MatrixMap& _matrix,
+		      typename MatrixMap::FirstKey _col)
+: matrix(_matrix), col(_col) {}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ConstReturnValue
+operator[](Key row) const {
+return matrix(col, row);
+}
+private:
+const MatrixMap& matrix;
+typename MatrixMap::FirstKey col;
+};
+/// \brief Gives back a coloumn view of the matrix map
+///
+/// Gives back a coloumn view of the matrix map.
+template <typename MatrixMap>
+MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
+				       typename MatrixMap::FirstKey col) {
+return MatrixColMap<MatrixMap>(matrixMap, col);
+}
+template <typename MatrixMap>
+ConstMatrixColMap<MatrixMap>
+matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) {
+return ConstMatrixColMap<MatrixMap>(matrixMap, col);
+}
+/// \brief Map for the row view of the matrix
+///
+/// Map for the row view of the matrix.
+template <typename _MatrixMap>
+class MatrixRowMap : public MapTraits<_MatrixMap> {
+public:
+typedef _MatrixMap MatrixMap;
+typedef typename MatrixMap::FirstKey Key;
+typedef typename MatrixMap::Value Value;
+MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row)
+: matrix(_matrix), row(_row) {}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ReturnValue
+operator[](Key col) {
+return matrix(col, row);
+}
+/// \brief Setter function
+///
+/// Setter function.
+void set(Key col, const Value& val) {
+matrix.set(col, row, val);
+}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ConstReturnValue
+operator[](Key col) const {
+return matrix(col, row);
+}
+private:
+MatrixMap& matrix;
+typename MatrixMap::SecondKey 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::FirstKey Key;
+typedef typename MatrixMap::Value Value;
+ConstMatrixRowMap(const MatrixMap& _matrix,
+		      typename MatrixMap::SecondKey _row)
+: matrix(_matrix), row(_row) {}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+typename MapTraits<MatrixMap>::ConstReturnValue
+operator[](Key col) const {
+return matrix(col, row);
+}
+private:
+const MatrixMap& matrix;
+typename MatrixMap::SecondKey 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::SecondKey row) {
+return MatrixRowMap<MatrixMap>(matrixMap, row);
+}
+template <typename MatrixMap>
+ConstMatrixRowMap<MatrixMap>
+matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) {
+return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
+}
+/// \brief Container for store values for each ordered pair of graph items
+///
+/// This data structure can strore for each pairs 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 pairs 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

changeset 1746	874e4bc21435
child 1751	a2a454f1232d