diff -r 9588dcef6793 -r 655d8e78454d src/lemon/map_utils.h --- a/src/lemon/map_utils.h Wed May 04 13:07:10 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,311 +0,0 @@ -/* -*- C++ -*- - * src/lemon/map_utils.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. - * - */ - - -///\ingroup mutils -///\file -///\brief Map utilities. - -#ifndef LEMON_MAP_UTILS_H -#define LEMON_MAP_UTILS_H - -#include -#include - -#include - -namespace lemon { - - /// \addtogroup mutils - /// @{ - - - template - struct ReferenceMapTraits { - typedef typename Map::Value Value; - typedef typename Map::Value& Reference; - typedef const typename Map::Value& ConstReference; - typedef typename Map::Value* Pointer; - typedef const typename Map::Value* ConstPointer; - }; - - template - struct ReferenceMapTraits< - Map, - typename enable_if::type - > { - typedef typename Map::Value Value; - typedef typename Map::Reference Reference; - typedef typename Map::ConstReference ConstReference; - typedef typename Map::Pointer Pointer; - typedef typename Map::ConstPointer ConstPointer; - }; - - /// \brief General inversable map type. - - /// This type provides simple inversable map functions. - /// The InversableMap wraps an arbitrary ReadWriteMap - /// and if a key is setted to a new value then store it - /// in the inverse map. - /// \param _Graph The graph type. - /// \param _Map The map to extend with inversable functionality. - template < - typename _Graph, - typename _Item, - typename _Value, - typename _Map - = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> - > - class InversableMap : protected _Map { - - public: - - typedef _Map Map; - typedef _Graph Graph; - /// The key type of InversableMap (Node, Edge, UndirEdge). - typedef typename _Map::Key Key; - /// The value type of the InversableMap. - typedef typename _Map::Value Value; - - typedef std::map InverseMap; - - typedef typename _Map::ConstReference ConstReference; - - /// \brief Constructor. - /// - /// Construct a new InversableMap for the graph. - /// - InversableMap(const Graph& graph) : Map(graph) {} - - /// \brief The setter function of the map. - /// - - void set(const Key& key, const Value& val) { - Value oldval = Map::operator[](key); - typename InverseMap::iterator it = invMap.find(oldval); - if (it != invMap.end() && it->second == key) { - invMap.erase(it); - } - invMap.insert(make_pair(val, key)); - Map::set(key, val); - } - - /// \brief The getter function of the map. - /// - /// It gives back the value associated with the key. - ConstReference operator[](const Key& key) const { - return Map::operator[](key); - } - - /// \brief Add a new key to the map. - /// - /// Add a new key to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const Key& key) { - Map::add(key); - } - - /// \brief Erase the key from the map. - /// - /// Erase the key to the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Key& key) { - Value val = Map::operator[](key); - typename InverseMap::iterator it = invMap.find(val); - if (it != invMap.end() && it->second == key) { - invMap.erase(it); - } - Map::erase(key); - } - - /// \brief Clear the keys from the map and inverse map. - /// - /// Clear the keys from the map and inverse map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - invMap.clear(); - Map::clear(); - } - - /// \brief It gives back the just readeable inverse map. - /// - /// It gives back the just readeable inverse map. - const InverseMap& inverse() const { - return invMap; - } - - - private: - InverseMap invMap; - }; - - - - /// \brief Provides a mutable, continous and unique descriptor for each - /// item in the graph. - /// - /// The DescriptorMap class provides a mutable, continous and immutable - /// mapping for each item in the graph. - /// - /// \param _Graph The graph class the \c DescriptorMap belongs to. - /// \param _Item The Item is the Key of the Map. It may be Node, Edge or - /// UndirEdge. - /// \param _Map A ReadWriteMap mapping from the item type to integer. - - template < - typename _Graph, - typename _Item, - typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map - > - class DescriptorMap : protected _Map { - - typedef _Item Item; - typedef _Map Map; - - public: - /// The graph class of DescriptorMap. - typedef _Graph Graph; - - /// The key type of DescriptorMap (Node, Edge, UndirEdge). - typedef typename _Map::Key Key; - /// The value type of DescriptorMap. - typedef typename _Map::Value Value; - - typedef std::vector InverseMap; - - /// \brief Constructor. - /// - /// Constructor for creating descriptor map. - DescriptorMap(const Graph& _graph) : Map(_graph) { - build(); - } - - /// \brief Add a new key to the map. - /// - /// Add a new key to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const Item& item) { - Map::add(item); - Map::set(item, invMap.size()); - invMap.push_back(item); - } - - /// \brief Erase the key from the map. - /// - /// Erase the key to the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Item& item) { - Map::set(invMap.back(), Map::operator[](item)); - invMap[Map::operator[](item)] = invMap.back(); - Map::erase(item); - } - - /// \brief Build the unique map. - /// - /// Build the unique map. It is called by the - /// \c AlterationNotifier. - virtual void build() { - Map::build(); - Item it; - const typename Map::Graph* graph = Map::getGraph(); - for (graph->first(it); it != INVALID; graph->next(it)) { - Map::set(it, invMap.size()); - invMap.push_back(it); - } - } - - /// \brief Clear the keys from the map. - /// - /// Clear the keys from the map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - invMap.clear(); - Map::clear(); - } - - /// \brief Gives back the \e descriptor of the item. - /// - /// Gives back the mutable and unique \e descriptor of the map. - int operator[](const Item& item) const { - return Map::operator[](item); - } - - /// \brief Gives back the inverse of the map. - /// - /// Gives back the inverse of the map. - const InverseMap inverse() const { - return invMap; - } - - private: - std::vector invMap; - }; - - /// Provides an immutable and unique id for each item in the graph. - - /// The IdMap class provides an unique and immutable mapping for each item - /// in the graph. - /// - template - class IdMap { - public: - typedef _Graph Graph; - typedef int Value; - typedef _Item Item; - typedef _Item Key; - - /// \brief The class represents the inverse of the map. - /// - /// The class represents the inverse of the map. - /// \see inverse() - class InverseMap { - public: - /// \brief Constructor. - /// - /// Constructor for creating an id-to-item map. - InverseMap(const Graph& _graph) : graph(&_graph) {} - /// \brief Gives back the given item from its id. - /// - /// Gives back the given item from its id. - /// - Item operator[](int id) const { return graph->fromId(id, Item());} - private: - const Graph* graph; - }; - - /// \brief Constructor. - /// - /// Constructor for creating id map. - IdMap(const Graph& _graph) : graph(&_graph) {} - - /// \brief Gives back the \e id of the item. - /// - /// Gives back the immutable and unique \e id of the map. - int operator[](const Item& item) const { return graph->id(item);} - - /// \brief Gives back the inverse of the map. - /// - /// Gives back the inverse of the map. - InverseMap inverse() const { return InverseMap(*graph);} - - private: - const Graph* graph; - - }; - -} - -#endif