COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/array_map.h


Ignore:
Timestamp:
10/28/04 00:38:50 (20 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/array_map.h

    r921 r946  
    2121
    2222#include <lemon/map_iterator.h>
    23 #include <lemon/map_bits.h>
    2423
    2524///\ingroup graphmaps
    … …  
    4342   */
    4443
    45   template <typename MapRegistry, typename Value>
    46   class ArrayMap : public MapRegistry::MapBase {
    47 
    48     template <typename MR, typename V> friend class ArrayMap;
    49                
     44  template <typename _Graph,
     45            typename _Item,
     46            typename _ItemIt,
     47            typename _IdMap,
     48            typename _Value>
     49  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
     50
    5051  public:
    5152               
    5253    /// The graph type of the maps.
    53     typedef typename MapRegistry::Graph Graph;
     54    typedef _Graph Graph;
    5455    /// The key type of the maps.
    55     typedef typename MapRegistry::KeyType KeyType;
     56    typedef _Item KeyType;
     57
     58    typedef AlterationObserverRegistry<_Item> Registry;
     59
     60  private:
    5661    /// The iterator to iterate on the keys.
    57     typedef typename MapRegistry::KeyIt KeyIt;
     62    typedef _ItemIt KeyIt;
     63
     64    typedef _IdMap IdMap;
     65
     66    typedef _Value Value;
    5867
    5968    /// The MapBase of the Map which imlements the core regisitry function.
    60     typedef typename MapRegistry::MapBase MapBase;
     69    typedef typename Registry::ObserverBase Parent;
    6170               
    6271   
    … …  
    7887
    7988
     89  private:
    8090    typedef std::allocator<Value> Allocator;
    8191
    82        
     92
     93  public:
     94
    8395    /** Graph and Registry initialized map constructor.
    8496     */
    85     ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
     97    ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
     98      attach(_r);
    8699      allocate_memory();
    87       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    88         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     100      for (KeyIt it(*graph); it != INVALID; ++it) {
     101        int id = IdMap(*graph)[it];
    89102        allocator.construct(&(values[id]), Value());
    90103      }                                                         
    91104    }
    92105
    93     /** Constructor to use default value to initialize the map.
    94      */
    95     ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
    96       : MapBase(g, r) {
     106    /// Constructor to use default value to initialize the map.
     107
     108    /// It constrates a map and initialize all of the the map.
     109
     110    ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
     111      attach(_r);
    97112      allocate_memory();
    98       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    99         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    100         allocator.construct(&(values[id]), v);
     113      for (KeyIt it(*graph); it != INVALID; ++it) {
     114        int id = IdMap(*graph)[it];
     115        allocator.construct(&(values[id]), _v);
    101116      }                                                         
    102117    }
    … …  
    104119    /** Constructor to copy a map of the same map type.
    105120     */
    106     ArrayMap(const ArrayMap& copy) : MapBase(copy) {
     121    ArrayMap(const ArrayMap& copy) {
     122      if (copy.attached()) {
     123        attach(*copy.getRegistry());
     124      }
    107125      capacity = copy.capacity;
    108126      if (capacity == 0) return;
    109127      values = allocator.allocate(capacity);
    110       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    111         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    112         allocator.construct(&(values[id]), copy.values[id]);
    113       }
    114     }
    115 
    116     /** Constructor to copy a map of an other map type.
    117      */
    118     template <typename TT>
    119     ArrayMap(const ArrayMap<MapRegistry, TT>& copy)
    120       : MapBase(copy) {
    121       capacity = copy.capacity;
    122       if (capacity == 0) return;
    123       values = allocator.allocate(capacity);
    124       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    125         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     128      for (KeyIt it(*graph); it != INVALID; ++it) {
     129        int id = IdMap(*graph)[it];
    126130        allocator.construct(&(values[id]), copy.values[id]);
    127131      }
    … …  
    133137      if (&copy == this) return *this;
    134138     
    135       if (MapBase::getGraph() != copy.getGraph()) {
    136         if (capacity != 0) {
    137           MapBase::destroy();
    138           allocator.deallocate(values, capacity);
     139      if (graph != copy.graph) {
     140        if (attached()) {
     141          clear();
     142          detach();
    139143        }
    140 
    141         MapBase::operator=(copy);
     144        if (copy.attached()) {
     145          attach(*copy.getRegistry());
     146        }
    142147        capacity = copy.capacity;
    143148        if (capacity == 0) return *this;
    … …  
    145150      }
    146151
    147       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    148         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     152      for (KeyIt it(*graph); it != INVALID; ++it) {
     153        int id = IdMap(*graph)[it];
    149154        allocator.construct(&(values[id]), copy.values[id]);
    150155      }
    … …  
    153158    }
    154159
    155     /** Assign operator to copy a map of an other map type.
    156      */
    157     template <typename TT>
    158     ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
    159 
    160       if (MapBase::getGraph() != copy.getGraph()) {
    161         if (capacity != 0) {
    162           MapBase::destroy();
    163           allocator.deallocate(values, capacity);
    164         }
    165 
    166         MapBase::operator=(copy);
    167 
    168         capacity = copy.capacity;
    169         if (capacity == 0) return *this;
    170         values = allocator.allocate(capacity);
    171       }
    172 
    173       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    174         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    175         allocator.construct(&(values[id]), copy.values[id]);
    176       }
    177 
    178       return *this;
    179     }
    180                                
    181160    /** The destructor of the map.
    182161     */
    183     virtual ~ArrayMap() {
    184       if (capacity != 0) {
    185         MapBase::destroy();
    186         allocator.deallocate(values, capacity);
     162    virtual ~ArrayMap() {     
     163      if (attached()) {
     164        clear();
     165        detach();
    187166      }
    188167    }
    … …  
    194173     */
    195174    ReferenceType operator[](const KeyType& key) {
    196       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     175      int id = IdMap(*graph)[key];
    197176      return values[id];
    198177    }
    … …  
    203182     */
    204183    ConstReferenceType operator[](const KeyType& key) const {
    205       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     184      int id = IdMap(*graph)[key];
    206185      return values[id];
    207186    }
    … …  
    211190     */
    212191    void set(const KeyType& key, const ValueType& val) {
    213       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    214       values[id] = val;
     192      (*this)[key] = val;
    215193    }
    216194               
    … …  
    218196     */
    219197    void add(const KeyType& key) {
    220       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     198      int id = IdMap(*graph)[key];
    221199      if (id >= capacity) {
    222200        int new_capacity = (capacity == 0 ? 1 : capacity);
    … …  
    224202          new_capacity <<= 1;
    225203        }
    226         Value* new_values = allocator.allocate(new_capacity);;
    227         for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    228           int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     204        Value* new_values = allocator.allocate(new_capacity);
     205        for (KeyIt it(*graph); it != INVALID; ++it) {
     206          int jd = IdMap(*graph)[it];
    229207          if (id != jd) {
    230208            allocator.construct(&(new_values[jd]), values[jd]);
    … …  
    242220     */
    243221    void erase(const KeyType& key) {
    244       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     222      int id = IdMap(*graph)[key];
    245223      allocator.destroy(&(values[id]));
    246224    }
    247225
    248     /** Clear the data structure.
    249      */
     226    void build() {
     227      allocate_memory();
     228      for (KeyIt it(*graph); it != INVALID; ++it) {
     229        int id = IdMap(*graph)[it];
     230        allocator.construct(&(values[id]), Value());
     231      }                                                         
     232    }
     233
    250234    void clear() {     
    251235      if (capacity != 0) {
    252         MapBase::destroy();
     236        for (KeyIt it(*graph); it != INVALID; ++it) {
     237          int id = IdMap(*graph)[it];
     238          allocator.destroy(&(values[id]));
     239        }                                                               
    253240        allocator.deallocate(values, capacity);
    254241        capacity = 0;
    … …  
    256243    }
    257244
    258     /// The stl compatible pair iterator of the map.
    259     typedef MapIterator<ArrayMap> Iterator;
    260     /// The stl compatible const pair iterator of the map.
    261     typedef MapConstIterator<ArrayMap> ConstIterator;
    262 
    263     /** Returns the begin iterator of the map.
    264      */
    265     Iterator begin() {
    266       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    267     }
    268 
    269     /** Returns the end iterator of the map.
    270      */
    271     Iterator end() {
    272       return Iterator(*this, INVALID);
    273     }
    274 
    275     /** Returns the begin ConstIterator of the map.
    276      */
    277     ConstIterator begin() const {
    278       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    279     }
    280 
    281     /** Returns the end const_iterator of the map.
    282      */
    283     ConstIterator end() const {
    284       return ConstIterator(*this, INVALID);
    285     }
    286 
    287     /// The KeySet of the Map.
    288     typedef MapConstKeySet<ArrayMap> ConstKeySet;
    289 
    290     /// KeySet getter function.
    291     ConstKeySet keySet() const {
    292       return ConstKeySet(*this);
    293     }
    294 
    295     /// The ConstValueSet of the Map.
    296     typedef MapConstValueSet<ArrayMap> ConstValueSet;
    297 
    298     /// ConstValueSet getter function.
    299     ConstValueSet valueSet() const {
    300       return ConstValueSet(*this);
    301     }
    302 
    303     /// The ValueSet of the Map.
    304     typedef MapValueSet<ArrayMap> ValueSet;
    305 
    306     /// ValueSet getter function.
    307     ValueSet valueSet() {
    308       return ValueSet(*this);
    309     }
     245//     /// The stl compatible pair iterator of the map.
     246//     typedef MapIterator<ArrayMap> Iterator;
     247//     /// The stl compatible const pair iterator of the map.
     248//     typedef MapConstIterator<ArrayMap> ConstIterator;
     249
     250//     /** Returns the begin iterator of the map.
     251//      */
     252//     Iterator begin() {
     253//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
     254//     }
     255
     256//     /** Returns the end iterator of the map.
     257//      */
     258//     Iterator end() {
     259//       return Iterator(*this, INVALID);
     260//     }
     261
     262//     /** Returns the begin ConstIterator of the map.
     263//      */
     264//     ConstIterator begin() const {
     265//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
     266//     }
     267
     268//     /** Returns the end const_iterator of the map.
     269//      */
     270//     ConstIterator end() const {
     271//       return ConstIterator(*this, INVALID);
     272//     }
     273
     274//     /// The KeySet of the Map.
     275//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
     276
     277//     /// KeySet getter function.
     278//     ConstKeySet keySet() const {
     279//       return ConstKeySet(*this);
     280//     }
     281
     282//     /// The ConstValueSet of the Map.
     283//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
     284
     285//     /// ConstValueSet getter function.
     286//     ConstValueSet valueSet() const {
     287//       return ConstValueSet(*this);
     288//     }
     289
     290//     /// The ValueSet of the Map.
     291//     typedef MapValueSet<ArrayMap> ValueSet;
     292
     293//     /// ValueSet getter function.
     294//     ValueSet valueSet() {
     295//       return ValueSet(*this);
     296//     }
    310297
    311298  private:
    312299     
    313300    void allocate_memory() {
    314       int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
     301      int max_id = IdMap(*graph).maxId();
    315302      if (max_id == -1) {
    316303        capacity = 0;
    … …  
    325312    }     
    326313
     314    const Graph* graph;
    327315    int capacity;
    328316    Value* values;
    … …  
    330318
    331319  public:
    332     // STL  compatibility typedefs.
    333     typedef Iterator iterator;
    334     typedef ConstIterator const_iterator;
    335     typedef typename Iterator::PairValueType value_type;
    336     typedef typename Iterator::KeyType key_type;
    337     typedef typename Iterator::ValueType data_type;
    338     typedef typename Iterator::PairReferenceType reference;
    339     typedef typename Iterator::PairPointerType pointer;
    340     typedef typename ConstIterator::PairReferenceType const_reference;
    341     typedef typename ConstIterator::PairPointerType const_pointer;
    342     typedef int difference_type;               
     320//     // STL  compatibility typedefs.
     321//     typedef Iterator iterator;
     322//     typedef ConstIterator const_iterator;
     323//     typedef typename Iterator::PairValueType value_type;
     324//     typedef typename Iterator::KeyType key_type;
     325//     typedef typename Iterator::ValueType data_type;
     326//     typedef typename Iterator::PairReferenceType reference;
     327//     typedef typename Iterator::PairPointerType pointer;
     328//     typedef typename ConstIterator::PairReferenceType const_reference;
     329//     typedef typename ConstIterator::PairPointerType const_pointer;
     330//     typedef int difference_type;             
    343331  };           
    344332
     333  template <typename _Base>
     334  class ArrayMappableGraphExtender : public _Base {
     335  public:
     336
     337    typedef ArrayMappableGraphExtender<_Base> Graph;
     338    typedef _Base Parent;
     339
     340    typedef typename Parent::Node Node;
     341    typedef typename Parent::NodeIt NodeIt;
     342    typedef typename Parent::NodeIdMap NodeIdMap;
     343    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
     344
     345    typedef typename Parent::Edge Edge;
     346    typedef typename Parent::EdgeIt EdgeIt;
     347    typedef typename Parent::EdgeIdMap EdgeIdMap;
     348    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
     349
     350   
     351
     352    template <typename _Value>
     353    class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
     354    public:
     355      typedef ArrayMappableGraphExtender<_Base> Graph;
     356
     357      typedef typename Graph::Node Node;
     358      typedef typename Graph::NodeIt NodeIt;
     359      typedef typename Graph::NodeIdMap NodeIdMap;
     360
     361      typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
     362
     363      typedef typename Parent::Graph Graph;
     364      typedef typename Parent::Value Value;
     365
     366      NodeMap(const Graph& g)
     367        : Parent(g, g.getNodeObserverRegistry()) {}
     368      NodeMap(const Graph& g, const Value& v)
     369        : Parent(g, g.getNodeObserverRegistry(), v) {}
     370
     371    };
     372
     373    template <typename _Value>
     374    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
     375    public:
     376      typedef ArrayMappableGraphExtender<_Base> Graph;
     377
     378      typedef typename Graph::Edge Edge;
     379      typedef typename Graph::EdgeIt EdgeIt;
     380      typedef typename Graph::EdgeIdMap EdgeIdMap;
     381
     382      typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
     383
     384      typedef typename Parent::Graph Graph;
     385      typedef typename Parent::Value Value;
     386
     387      EdgeMap(const Graph& g)
     388        : Parent(g, g.getEdgeObserverRegistry()) {}
     389      EdgeMap(const Graph& g, const Value& v)
     390        : Parent(g, g.getEdgeObserverRegistry(), v) {}
     391
     392    };
     393   
     394  };
     395
    345396/// @}
    346397
Note: See TracChangeset for help on using the changeset viewer.