alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_MAP_ITERATOR_H alpar@921: #define LEMON_MAP_ITERATOR_H deba@822: deba@844: #include deba@844: alpar@921: #include deba@822: deba@830: ///\ingroup graphmaps deba@830: ///\file deba@830: ///\brief Iterators on the maps. deba@830: alpar@921: namespace lemon { deba@822: deba@830: /// \addtogroup graphmaps deba@830: /// @{ deba@830: deba@830: /** The base class all of the map iterators. deba@830: * The class defines the typedefs of the iterators, deba@830: * simple step functions and equality operators. deba@830: */ deba@822: deba@822: template deba@830: class MapIteratorBase { deba@822: deba@830: public: deba@844: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@830: /// The value type of the iterator. deba@830: typedef typename Map::ValueType ValueType; deba@830: /// The reference type of the iterator. deba@830: typedef typename Map::ReferenceType ReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::PointerType PointerType; deba@830: deba@830: /// The const value type of the iterator. deba@830: typedef typename Map::ConstValueType ConstValueType; deba@830: /// The const reference type of the iterator. deba@830: typedef typename Map::ConstReferenceType ConstReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::ConstPointerType ConstPointerType; deba@830: deba@830: protected: deba@830: deba@830: KeyIt it; deba@830: deba@830: /// Default constructor. deba@830: MapIteratorBase() {} deba@830: deba@830: /// KeyIt initialized MapIteratorBase constructor. deba@830: MapIteratorBase(const KeyIt pit) : it(pit) {} deba@830: deba@830: public: deba@830: deba@830: /// Stepping forward in the map. deba@830: void increment() { deba@830: ++it; deba@830: } deba@830: deba@830: /// The equality operator of the map. deba@830: bool operator==(const MapIteratorBase& pit) const { deba@830: return pit.it == it; deba@830: } deba@830: deba@830: /// The not-equality operator of the map. deba@830: bool operator!=(const MapIteratorBase& pit) const { deba@830: return !(*this == pit); deba@830: } deba@830: }; deba@830: deba@830: template class MapConstIterator; deba@822: deba@822: /** Compatible iterator with the stl maps' iterators. deba@830: * It iterates on pairs of a key and a value. deba@822: */ deba@822: template deba@830: class MapIterator : public MapIteratorBase { deba@830: deba@822: friend class MapConstIterator; deba@822: deba@844: deba@822: public: deba@822: deba@844: /// The iterator base class. deba@844: typedef MapIteratorBase Base; deba@844: deba@822: /// The key type of the iterator. deba@822: typedef typename Map::KeyType KeyType; deba@822: /// The iterator to iterate on the keys. deba@822: typedef typename Map::KeyIt KeyIt; deba@822: deba@822: /// The value type of the iterator. deba@822: typedef typename Map::ValueType ValueType; deba@822: /// The reference type of the iterator. deba@822: typedef typename Map::ReferenceType ReferenceType; deba@822: /// The pointer type of the iterator. deba@822: typedef typename Map::PointerType PointerType; deba@822: deba@822: /// The const value type of the iterator. deba@822: typedef typename Map::ConstValueType ConstValueType; deba@822: /// The const reference type of the iterator. deba@822: typedef typename Map::ConstReferenceType ConstReferenceType; deba@822: /// The pointer type of the iterator. deba@822: typedef typename Map::ConstPointerType ConstPointerType; deba@822: deba@822: public: deba@822: deba@844: /// The value type of the iterator. deba@844: typedef extended_pair PairValueType; deba@844: deba@830: /// The reference type of the iterator. deba@822: typedef extended_pair PairReferenceType; deba@822: deba@830: /// Default constructor. deba@830: MapIterator() {} deba@830: deba@830: /// Constructor to initalize the iterators returned deba@830: /// by the begin() and end(). deba@844: MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {} deba@830: deba@830: /// Dereference operator for the iterator. deba@822: PairReferenceType operator*() { deba@844: return PairReferenceType(Base::it, (*map)[Base::it]); deba@822: } deba@822: deba@830: /// The pointer type of the iterator. deba@822: class PairPointerType { deba@822: friend class MapIterator; deba@822: private: deba@822: PairReferenceType data; deba@822: PairPointerType(const KeyType& key, ReferenceType val) deba@822: : data(key, val) {} deba@822: public: deba@822: PairReferenceType* operator->() {return &data;} deba@822: }; deba@822: deba@830: /// Arrow operator for the iterator. deba@822: PairPointerType operator->() { deba@844: return PairPointerType(Base::it, ((*map)[Base::it])); deba@822: } deba@830: deba@830: /// The pre increment operator of the iterator. deba@822: MapIterator& operator++() { deba@844: Base::increment(); deba@822: return *this; deba@822: } deba@822: deba@830: /// The post increment operator of the iterator. deba@822: MapIterator operator++(int) { deba@844: MapIterator tmp(*this); deba@844: Base::increment(); deba@822: return tmp; deba@822: } deba@822: deba@822: private: deba@822: Map* map; deba@844: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef std::forward_iterator_tag iterator_category; deba@844: typedef int difference_type; deba@844: typedef PairValueType value_type; deba@844: typedef PairReferenceType reference; deba@844: typedef PairPointerType pointer; deba@822: }; deba@822: deba@822: /** Compatible iterator with the stl maps' iterators. deba@822: * It iterates on pairs of a key and a value. deba@822: */ deba@822: template deba@830: class MapConstIterator : public MapIteratorBase { deba@830: deba@822: public: deba@822: deba@844: /// The iterator base class. deba@844: typedef MapIteratorBase Base; deba@844: deba@822: /// The key type of the iterator. deba@822: typedef typename Map::KeyType KeyType; deba@822: /// The iterator to iterate on the keys. deba@822: typedef typename Map::KeyIt KeyIt; deba@822: deba@822: /// The value type of the iterator. deba@822: typedef typename Map::ValueType ValueType; deba@822: /// The reference type of the iterator. deba@822: typedef typename Map::ReferenceType ReferenceType; deba@822: /// The pointer type of the iterator. deba@822: typedef typename Map::PointerType PointerType; deba@822: deba@822: /// The const value type of the iterator. deba@822: typedef typename Map::ConstValueType ConstValueType; deba@822: /// The const reference type of the iterator. deba@822: typedef typename Map::ConstReferenceType ConstReferenceType; deba@822: /// The pointer type of the iterator. deba@822: typedef typename Map::ConstPointerType ConstPointerType; deba@822: deba@822: public: deba@822: deba@830: /// Default constructor. deba@822: MapConstIterator() {} deba@822: deba@830: /// Constructor to initalize the the iterators returned deba@830: /// by the begin() and end(). deba@830: MapConstIterator(const Map& pmap, const KeyIt& pit) deba@844: : Base(pit), map(&pmap) {} deba@830: deba@830: /// Constructor to create const iterator from a non const. deba@830: MapConstIterator(const MapIterator& pit) { deba@844: Base::it = pit.Base::it; deba@830: map = pit.map; deba@830: } deba@830: deba@844: /// The value type of the iterator. deba@844: typedef extended_pair PairValueType; deba@844: deba@830: /// The reference type of map. deba@822: typedef extended_pair PairReferenceType; deba@822: deba@830: /// Dereference operator for the iterator. deba@822: PairReferenceType operator*() { deba@844: return PairReferenceType(Base::it, (*map)[Base::it]); deba@822: } deba@822: deba@830: /// The pointer type of the iterator. deba@822: class PairPointerType { deba@822: friend class MapConstIterator; deba@822: private: deba@822: PairReferenceType data; deba@822: PairPointerType(const KeyType& key, ConstReferenceType val) deba@822: : data(key, val) {} deba@822: public: deba@822: PairReferenceType* operator->() {return &data;} deba@822: }; deba@822: deba@830: /// Arrow operator for the iterator. deba@822: PairPointerType operator->() { deba@844: return PairPointerType(Base::it, (*map)[Base::it]); deba@822: } deba@822: deba@830: /// The pre increment operator of the iterator. deba@822: MapConstIterator& operator++() { deba@844: Base::increment(); deba@822: return *this; deba@822: } deba@822: deba@830: /// The post increment operator of the iterator. deba@822: MapConstIterator operator++(int) { deba@844: MapConstIterator tmp(*this); deba@844: Base::increment(); deba@822: return tmp; deba@822: } deba@822: deba@830: private: deba@830: const Map* map; deba@844: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef std::input_iterator_tag iterator_category; deba@844: typedef int difference_type; deba@844: typedef PairValueType value_type; deba@844: typedef PairReferenceType reference; deba@844: typedef PairPointerType pointer; deba@830: }; deba@830: deba@830: /** The class makes the KeyIt to an stl compatible iterator deba@830: * with dereferencing operator. deba@830: */ deba@830: template deba@830: class MapKeyIterator : public MapIteratorBase { deba@830: deba@830: public: deba@830: deba@844: /// The iterator base class. deba@844: typedef MapIteratorBase Base; deba@844: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@830: public: deba@830: deba@830: /// Default constructor. deba@830: MapKeyIterator() {} deba@830: deba@830: /// KeyIt initialized iterator. deba@844: MapKeyIterator(const KeyIt& pit) : Base(pit) {} deba@830: deba@830: /// The pre increment operator of the iterator. deba@830: MapKeyIterator& operator++() { deba@844: Base::increment(); deba@830: return *this; deba@822: } deba@822: deba@830: /// The post increment operator of the iterator. deba@830: MapKeyIterator operator++(int) { deba@830: MapKeyIterator tmp(*this); deba@844: Base::increment(); deba@830: return tmp; deba@822: } deba@830: deba@830: /// The dereferencing operator of the iterator. deba@830: KeyType operator*() const { deba@844: return static_cast(Base::it); deba@822: } deba@844: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef std::input_iterator_tag iterator_category; deba@844: typedef int difference_type; deba@844: typedef KeyType value_type; deba@844: typedef const KeyType& reference; deba@844: typedef const KeyType* pointer; deba@830: }; deba@830: deba@830: template class MapConstValueIterator; deba@830: deba@844: /** MapValueIterator creates an stl compatible iterator deba@844: * for the values. deba@844: */ deba@830: template deba@830: class MapValueIterator : public MapIteratorBase { deba@830: deba@830: friend class MapConstValueIterator; deba@830: deba@830: public: deba@830: deba@844: /// The iterator base class. deba@844: typedef MapIteratorBase Base; deba@844: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@830: deba@830: /// The value type of the iterator. deba@830: typedef typename Map::ValueType ValueType; deba@830: /// The reference type of the iterator. deba@830: typedef typename Map::ReferenceType ReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::PointerType PointerType; deba@830: deba@830: /// The const value type of the iterator. deba@830: typedef typename Map::ConstValueType ConstValueType; deba@830: /// The const reference type of the iterator. deba@830: typedef typename Map::ConstReferenceType ConstReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::ConstPointerType ConstPointerType; deba@830: deba@822: private: deba@830: deba@830: Map* map; deba@830: deba@830: public: deba@830: deba@830: /// Default constructor. deba@830: MapValueIterator() {} deba@830: deba@830: /// Map and KeyIt initialized iterator. deba@830: MapValueIterator(Map& pmap, const KeyIt& pit) deba@844: : Base(pit), map(&pmap) {} deba@830: deba@830: deba@830: /// The pre increment operator of the iterator. deba@830: MapValueIterator& operator++() { deba@844: Base::increment(); deba@830: return *this; deba@830: } deba@830: deba@830: /// The post increment operator of the iterator. deba@830: MapValueIterator operator++(int) { deba@830: MapValueIterator tmp(*this); deba@844: Base::increment(); deba@830: return tmp; deba@830: } deba@830: deba@830: /// The dereferencing operator of the iterator. deba@830: ReferenceType operator*() const { deba@844: return (*map)[Base::it]; deba@830: } deba@830: deba@830: /// The arrow operator of the iterator. deba@830: PointerType operator->() const { deba@830: return &(operator*()); deba@830: } deba@830: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef std::forward_iterator_tag iterator_category; deba@844: typedef int difference_type; deba@844: typedef ValueType value_type; deba@844: typedef ReferenceType reference; deba@844: typedef PointerType pointer; deba@830: }; deba@830: deba@844: /** MapValueIterator creates an stl compatible iterator deba@844: * for the const values. deba@844: */ deba@830: deba@830: template deba@830: class MapConstValueIterator : public MapIteratorBase { deba@830: deba@830: public: deba@830: deba@844: /// The iterator base class. deba@844: typedef MapIteratorBase Base; deba@844: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@830: /// The value type of the iterator. deba@830: typedef typename Map::ValueType ValueType; deba@830: /// The reference type of the iterator. deba@830: typedef typename Map::ReferenceType ReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::PointerType PointerType; deba@830: deba@830: /// The const value type of the iterator. deba@830: typedef typename Map::ConstValueType ConstValueType; deba@830: /// The const reference type of the iterator. deba@830: typedef typename Map::ConstReferenceType ConstReferenceType; deba@830: /// The pointer type of the iterator. deba@830: typedef typename Map::ConstPointerType ConstPointerType; deba@830: deba@830: private: deba@830: deba@822: const Map* map; deba@830: deba@830: public: deba@830: deba@830: /// Default constructor. deba@830: MapConstValueIterator() {} deba@830: deba@830: /// Constructor to create const iterator from a non const. deba@830: MapConstValueIterator(const MapValueIterator& pit) { deba@844: Base::it = pit.Base::it; deba@830: map = pit.map; deba@830: } deba@830: deba@830: /// Map and KeyIt initialized iterator. deba@830: MapConstValueIterator(const Map& pmap, const KeyIt& pit) deba@844: : Base(pit), map(&pmap) {} deba@830: deba@830: /// The pre increment operator of the iterator. deba@830: MapConstValueIterator& operator++() { deba@844: Base::increment(); deba@830: return *this; deba@830: } deba@830: deba@830: /// The post increment operator of the iterator. deba@830: MapConstValueIterator operator++(int) { deba@830: MapConstValueIterator tmp(*this); deba@844: Base::increment(); deba@830: return tmp; deba@830: } deba@830: deba@830: /// The dereferencing operator of the iterator. deba@830: ConstReferenceType operator*() const { deba@844: return (*map)[Base::it]; deba@830: } deba@830: deba@830: /// The arrow operator of the iterator. deba@830: ConstPointerType operator->() const { deba@830: return &(operator*()); deba@830: } deba@830: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef std::input_iterator_tag iterator_category; deba@844: typedef int difference_type; deba@844: typedef ValueType value_type; deba@844: typedef ConstReferenceType reference; deba@844: typedef ConstPointerType pointer; deba@822: }; deba@822: deba@830: deba@830: /** This class makes from a map an iteratable set deba@830: * which contains all the keys of the map. deba@830: */ deba@830: template deba@830: class MapConstKeySet { deba@830: deba@830: const Map* map; deba@830: deba@830: public: deba@830: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@844: deba@844: /// The value type of the iterator. deba@844: typedef typename Map::ValueType ValueType; deba@844: /// The reference type of the iterator. deba@844: typedef typename Map::ReferenceType ReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::PointerType PointerType; deba@844: deba@844: /// The const value type of the iterator. deba@844: typedef typename Map::ConstValueType ConstValueType; deba@844: /// The const reference type of the iterator. deba@844: typedef typename Map::ConstReferenceType ConstReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::ConstPointerType ConstPointerType; deba@844: deba@830: /// The map initialized const key set. deba@830: MapConstKeySet(const Map& pmap) : map(&pmap) {} deba@830: deba@830: /// The const iterator of the set. deba@830: typedef MapKeyIterator ConstIterator; deba@830: deba@830: /// It gives back the const iterator pointed to the first element. deba@830: ConstIterator begin() const { deba@830: return ConstIterator(KeyIt(*map->getGraph())); deba@830: } deba@830: deba@830: /// It gives back the const iterator pointed to the first ivalid element. deba@830: ConstIterator end() const { deba@830: return ConstIterator(KeyIt(INVALID)); deba@830: } deba@844: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef ValueType value_type; deba@844: typedef ConstIterator const_iterator; deba@844: typedef ConstReferenceType const_reference; deba@844: typedef ConstPointerType const_pointer; deba@844: typedef int difference_type; deba@830: }; deba@830: deba@830: /** This class makes from a map an iteratable set deba@830: * which contains all the values of the map. deba@830: * The values cannot be modified. deba@830: */ deba@830: template deba@830: class MapConstValueSet { deba@830: deba@830: const Map* map; deba@830: deba@830: public: deba@830: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@844: deba@844: /// The value type of the iterator. deba@844: typedef typename Map::ValueType ValueType; deba@844: /// The reference type of the iterator. deba@844: typedef typename Map::ReferenceType ReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::PointerType PointerType; deba@844: deba@844: /// The const value type of the iterator. deba@844: typedef typename Map::ConstValueType ConstValueType; deba@844: /// The const reference type of the iterator. deba@844: typedef typename Map::ConstReferenceType ConstReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::ConstPointerType ConstPointerType; deba@844: deba@830: /// The map initialized const value set. deba@830: MapConstValueSet(const Map& pmap) : map(&pmap) {} deba@830: deba@830: /// The const iterator of the set. deba@830: typedef MapConstValueIterator ConstIterator; deba@830: deba@830: /// It gives back the const iterator pointed to the first element. deba@830: ConstIterator begin() const { deba@830: return ConstIterator(*map, KeyIt(*map->getGraph())); deba@830: } deba@830: deba@830: /// It gives back the const iterator pointed to the first invalid element. deba@830: ConstIterator end() const { deba@830: return ConstIterator(*map, KeyIt(INVALID)); deba@830: } deba@844: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef ValueType value_type; deba@844: typedef ConstIterator const_iterator; deba@844: typedef ConstReferenceType const_reference; deba@844: typedef ConstPointerType const_pointer; deba@844: typedef int difference_type; deba@830: }; deba@830: deba@830: deba@830: /** This class makes from a map an iteratable set deba@830: * which contains all the values of the map. deba@830: * The values can be modified. deba@830: */ deba@830: template deba@830: class MapValueSet { deba@830: deba@830: Map* map; deba@830: deba@830: public: deba@830: deba@830: /// The key type of the iterator. deba@830: typedef typename Map::KeyType KeyType; deba@830: /// The iterator to iterate on the keys. deba@830: typedef typename Map::KeyIt KeyIt; deba@830: deba@844: deba@844: /// The value type of the iterator. deba@844: typedef typename Map::ValueType ValueType; deba@844: /// The reference type of the iterator. deba@844: typedef typename Map::ReferenceType ReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::PointerType PointerType; deba@844: deba@844: /// The const value type of the iterator. deba@844: typedef typename Map::ConstValueType ConstValueType; deba@844: /// The const reference type of the iterator. deba@844: typedef typename Map::ConstReferenceType ConstReferenceType; deba@844: /// The pointer type of the iterator. deba@844: typedef typename Map::ConstPointerType ConstPointerType; deba@844: deba@830: /// The map initialized value set. deba@830: MapValueSet(Map& pmap) : map(&pmap) {} deba@830: deba@830: /// The const iterator of the set. deba@830: typedef MapConstValueIterator ConstIterator; deba@830: deba@830: /// It gives back the const iterator pointed to the first element. deba@830: ConstIterator begin() const { deba@830: return ConstIterator(*map, KeyIt(*map->getGraph())); deba@830: } deba@830: deba@830: /// It gives back the const iterator pointed to the first invalid element. deba@830: ConstIterator end() const { deba@830: return ConstIterator(*map, KeyIt(INVALID)); deba@830: } deba@830: deba@830: /// The iterator of the set. deba@830: typedef MapValueIterator Iterator; deba@830: deba@830: /// It gives back the iterator pointed to the first element. deba@830: Iterator begin() { deba@830: return Iterator(*map, KeyIt(*map->getGraph())); deba@830: } deba@830: deba@830: /// It gives back the iterator pointed to the first invalid element. deba@830: Iterator end() { deba@830: return Iterator(*map, KeyIt(INVALID)); deba@830: } deba@830: deba@844: public: deba@844: // STL compatibility typedefs. deba@844: typedef ValueType value_type; deba@844: typedef Iterator iterator; deba@844: typedef ConstIterator const_iterator; deba@844: typedef ReferenceType reference; deba@844: typedef ConstReferenceType const_reference; deba@844: typedef PointerType pointer; deba@844: typedef ConstPointerType const_pointer; deba@844: typedef int difference_type; deba@844: deba@830: }; deba@830: deba@830: /// @} deba@830: deba@822: } deba@822: deba@822: #endif