deba@1810: /* -*- C++ -*-
deba@1810:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1810:  *
deba@1810:  * Permission to use, modify and distribute this software is granted
deba@1810:  * provided that this copyright notice appears in all copies. For
deba@1810:  * precise terms see the accompanying LICENSE file.
deba@1810:  *
deba@1810:  * This software is provided "AS IS" with no warranty of any kind,
deba@1810:  * express or implied, and with no claim as to its suitability for any
deba@1810:  * purpose.
deba@1810:  *
deba@1810:  */
deba@1810: 
deba@1810: #ifndef LEMON_BITS_MAP_EXTENDER_H
deba@1810: #define LEMON_BITS_MAP_EXTENDER_H
deba@1810: 
deba@1810: #include <iterator>
deba@1810: 
deba@1993: #include <lemon/bits/traits.h>
deba@1810: 
deba@2031: #include <lemon/concept_check.h>
alpar@2260: #include <lemon/concepts/maps.h>
deba@2031: 
deba@1810: ///\file
deba@1810: ///\brief Extenders for iterable maps.
deba@1810: 
deba@1810: namespace lemon {
deba@1810: 
deba@1996:   /// \ingroup graphbits
deba@1999:   /// 
deba@1999:   /// \brief Extender for maps
deba@1810:   template <typename _Map>
deba@1999:   class MapExtender : public _Map {
deba@1810:   public:
deba@1810: 
deba@1810:     typedef _Map Parent;
deba@1999:     typedef MapExtender Map;
deba@1810: 
deba@1810: 
alpar@1854:     typedef typename Parent::Graph Graph;
alpar@1854:     typedef typename Parent::Key Item;
deba@1810: 
alpar@1854:     typedef typename Parent::Key Key;
alpar@1854:     typedef typename Parent::Value Value;
deba@1810: 
deba@1810:     class MapIt;
deba@1810:     class ConstMapIt;
deba@1810: 
deba@1810:     friend class MapIt;
deba@1810:     friend class ConstMapIt;
deba@1810: 
deba@1810:   public:
deba@1810: 
deba@1999:     MapExtender(const Graph& graph) 
deba@1999:       : Parent(graph) {}
deba@1810: 
deba@1999:     MapExtender(const Graph& graph, const Value& value) 
deba@1810:       : Parent(graph, value) {}
deba@1810: 
deba@2031:     MapExtender& operator=(const MapExtender& cmap) {
deba@2031:       return operator=<MapExtender>(cmap);
deba@2031:     }
deba@2031: 
deba@2031:     template <typename CMap>
deba@2031:     MapExtender& operator=(const CMap& cmap) {
deba@2031:       Parent::operator=(cmap);
deba@2031:       return *this;
deba@2031:     } 
deba@1810: 
deba@1999:     class MapIt : public Item {
deba@1810:     public:
deba@1810:       
deba@1999:       typedef Item Parent;
deba@1810:       typedef typename Map::Value Value;
deba@1810:       
deba@1999:       MapIt() {}
deba@1999: 
deba@1999:       MapIt(Invalid i) : Parent(i) { }
deba@1999: 
deba@1999:       explicit MapIt(Map& _map) : map(_map) {
deba@2384:         map.notifier()->first(*this);
deba@1999:       }
deba@1999: 
deba@1999:       MapIt(const Map& _map, const Item& item) 
deba@1999: 	: Parent(item), map(_map) {}
deba@1999: 
deba@1999:       MapIt& operator++() { 
deba@2384: 	map.notifier()->next(*this);
deba@1999: 	return *this; 
deba@1999:       }
deba@1810:       
deba@1810:       typename MapTraits<Map>::ConstReturnValue operator*() const {
deba@1810: 	return map[*this];
deba@1810:       }
deba@1810: 
deba@1810:       typename MapTraits<Map>::ReturnValue operator*() {
deba@1810: 	return map[*this];
deba@1810:       }
deba@1810:       
deba@1810:       void set(const Value& value) {
deba@1810: 	map.set(*this, value);
deba@1810:       }
deba@1810:       
deba@1810:     protected:
deba@1810:       Map& map;
deba@1810:       
deba@1810:     };
deba@1810: 
deba@1999:     class ConstMapIt : public Item {
deba@1810:     public:
deba@1810: 
deba@1999:       typedef Item Parent;
deba@1810: 
deba@1810:       typedef typename Map::Value Value;
deba@1999:       
deba@1999:       ConstMapIt() {}
deba@1810: 
deba@1999:       ConstMapIt(Invalid i) : Parent(i) { }
deba@1999: 
deba@1999:       explicit ConstMapIt(Map& _map) : map(_map) {
deba@2384:         map.notifier()->first(*this);
deba@1999:       }
deba@1999: 
deba@1999:       ConstMapIt(const Map& _map, const Item& item) 
deba@1999: 	: Parent(item), map(_map) {}
deba@1999: 
deba@1999:       ConstMapIt& operator++() { 
deba@2384: 	map.notifier()->next(*this);
deba@1999: 	return *this; 
deba@1999:       }
deba@1810: 
deba@1810:       typename MapTraits<Map>::ConstReturnValue operator*() const {
deba@1810: 	return map[*this];
deba@1810:       }
deba@1999: 
deba@1810:     protected:
deba@1810:       const Map& map;
deba@1810:     };
deba@1810: 
deba@2031:     class ItemIt : public Item {
deba@1810:     public:
deba@1810:       
deba@1999:       typedef Item Parent;
deba@1999:       
deba@1999:       ItemIt() {}
deba@1810: 
deba@1999:       ItemIt(Invalid i) : Parent(i) { }
deba@1999: 
deba@1999:       explicit ItemIt(Map& _map) : map(_map) {
deba@2384:         map.notifier()->first(*this);
deba@1999:       }
deba@1999: 
deba@1999:       ItemIt(const Map& _map, const Item& item) 
deba@1999: 	: Parent(item), map(_map) {}
deba@1999: 
deba@1999:       ItemIt& operator++() { 
deba@2384: 	map.notifier()->next(*this);
deba@1999: 	return *this; 
deba@1999:       }
deba@1999: 
deba@1999:     protected:
deba@1999:       const Map& map;
deba@1810:       
deba@1810:     };
deba@1810:   };
deba@1810: 
deba@2031:   /// \ingroup graphbits
deba@2031:   /// 
deba@2031:   /// \brief Extender for maps which use a subset of the items.
deba@2031:   template <typename _Graph, typename _Map>
deba@2031:   class SubMapExtender : public _Map {
deba@2031:   public:
deba@2031: 
deba@2031:     typedef _Map Parent;
deba@2031:     typedef SubMapExtender Map;
deba@2031: 
deba@2031:     typedef _Graph Graph;
deba@2031: 
deba@2031:     typedef typename Parent::Key Item;
deba@2031: 
deba@2031:     typedef typename Parent::Key Key;
deba@2031:     typedef typename Parent::Value Value;
deba@2031: 
deba@2031:     class MapIt;
deba@2031:     class ConstMapIt;
deba@2031: 
deba@2031:     friend class MapIt;
deba@2031:     friend class ConstMapIt;
deba@2031: 
deba@2031:   public:
deba@2031: 
deba@2031:     SubMapExtender(const Graph& _graph) 
deba@2031:       : Parent(_graph), graph(_graph) {}
deba@2031: 
deba@2031:     SubMapExtender(const Graph& _graph, const Value& _value) 
deba@2031:       : Parent(_graph, _value), graph(_graph) {}
deba@2031: 
deba@2031:     SubMapExtender& operator=(const SubMapExtender& cmap) {
deba@2031:       return operator=<MapExtender>(cmap);
deba@2031:     }
deba@2031: 
deba@2031:     template <typename CMap>
deba@2031:     SubMapExtender& operator=(const CMap& cmap) {
alpar@2260:       checkConcept<concepts::ReadMap<Key, Value>, CMap>();
deba@2031:       Item it;
deba@2031:       for (graph.first(it); it != INVALID; graph.next(it)) {
deba@2031:         Parent::set(it, cmap[it]);
deba@2031:       }
deba@2031:       return *this;
deba@2031:     } 
deba@2031: 
deba@2031:     class MapIt : public Item {
deba@2031:     public:
deba@2031:       
deba@2031:       typedef Item Parent;
deba@2031:       typedef typename Map::Value Value;
deba@2031:       
deba@2031:       MapIt() {}
deba@2031: 
deba@2031:       MapIt(Invalid i) : Parent(i) { }
deba@2031: 
deba@2031:       explicit MapIt(Map& _map) : map(_map) {
deba@2031:         map.graph.first(*this);
deba@2031:       }
deba@2031: 
deba@2031:       MapIt(const Map& _map, const Item& item) 
deba@2031: 	: Parent(item), map(_map) {}
deba@2031: 
deba@2031:       MapIt& operator++() { 
deba@2031: 	map.graph.next(*this);
deba@2031: 	return *this; 
deba@2031:       }
deba@2031:       
deba@2031:       typename MapTraits<Map>::ConstReturnValue operator*() const {
deba@2031: 	return map[*this];
deba@2031:       }
deba@2031: 
deba@2031:       typename MapTraits<Map>::ReturnValue operator*() {
deba@2031: 	return map[*this];
deba@2031:       }
deba@2031:       
deba@2031:       void set(const Value& value) {
deba@2031: 	map.set(*this, value);
deba@2031:       }
deba@2031:       
deba@2031:     protected:
deba@2031:       Map& map;
deba@2031:       
deba@2031:     };
deba@2031: 
deba@2031:     class ConstMapIt : public Item {
deba@2031:     public:
deba@2031: 
deba@2031:       typedef Item Parent;
deba@2031: 
deba@2031:       typedef typename Map::Value Value;
deba@2031:       
deba@2031:       ConstMapIt() {}
deba@2031: 
deba@2031:       ConstMapIt(Invalid i) : Parent(i) { }
deba@2031: 
deba@2031:       explicit ConstMapIt(Map& _map) : map(_map) {
deba@2031:         map.graph.first(*this);
deba@2031:       }
deba@2031: 
deba@2031:       ConstMapIt(const Map& _map, const Item& item) 
deba@2031: 	: Parent(item), map(_map) {}
deba@2031: 
deba@2031:       ConstMapIt& operator++() { 
deba@2031: 	map.graph.next(*this);
deba@2031: 	return *this; 
deba@2031:       }
deba@2031: 
deba@2031:       typename MapTraits<Map>::ConstReturnValue operator*() const {
deba@2031: 	return map[*this];
deba@2031:       }
deba@2031: 
deba@2031:     protected:
deba@2031:       const Map& map;
deba@2031:     };
deba@2031: 
deba@2031:     class ItemIt : public Item {
deba@2031:     public:
deba@2031:       
deba@2031:       typedef Item Parent;
deba@2031:       
deba@2031:       ItemIt() {}
deba@2031: 
deba@2031:       ItemIt(Invalid i) : Parent(i) { }
deba@2031: 
deba@2031:       explicit ItemIt(Map& _map) : map(_map) {
deba@2031:         map.graph.first(*this);
deba@2031:       }
deba@2031: 
deba@2031:       ItemIt(const Map& _map, const Item& item) 
deba@2031: 	: Parent(item), map(_map) {}
deba@2031: 
deba@2031:       ItemIt& operator++() { 
deba@2031: 	map.graph.next(*this);
deba@2031: 	return *this; 
deba@2031:       }
deba@2031: 
deba@2031:     protected:
deba@2031:       const Map& map;
deba@2031:       
deba@2031:     };
deba@2031:     
deba@2031:   private:
deba@2031: 
deba@2031:     const Graph& graph;
deba@2031:     
deba@2031:   };
deba@2031: 
deba@1810: }
deba@1810: 
deba@1810: #endif