diff -r f59038affc7e -r a1500fed2270 src/work/deba/map_utils.h --- a/src/work/deba/map_utils.h Mon Feb 07 15:40:34 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,276 +0,0 @@ -/* -*- C++ -*- - * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - -#include - - -namespace lemon { - - /// \addtogroup mutils - /// @{ - - /// \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 _Map - > - class InversableMap : protected _Map { - - public: - typedef _Graph Graph; - - typedef _Map Map; - /// 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. - /// - /// It sets the map and the inverse map to given key-value pair. - 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 - > - 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; - for (getGraph()->first(it); it != INVALID; getGraph()->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: - 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; - - /// \brief The class represents the inverse of the map. - /// - /// The class represents the inverse of the map. - /// \see inverse() - class InverseMap { - protected: - InverseMap(const Graph& _graph) : graph(_graph) {} - public: - /// \brief Gives back the given item by its id. - /// - /// Gives back the given item by its id. - /// - Item operator[](int id) const { return graph->fromId(id, Item());} - private: - 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; - - }; - - - -} -