COIN-OR::LEMON - Graph Library

Changeset 703:32f280a5ed7d in lemon-0.x for src/work/deba


Ignore:
Timestamp:
07/15/04 14:15:58 (20 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@954
Message:
 
Location:
src/work/deba
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • src/work/deba/array_map_factory.h

    r702 r703  
     1// -*- c++ -*-
    12#ifndef ARRAY_MAP_H
    23#define ARRAY_MAP_H
     
    45#include <memory>
    56
    6 
    7 #include <iostream>
    8 using namespace std;
     7#include "extended_pair.h"
    98
    109namespace hugo {
     
    2019    typedef typename MapRegistry::MapBase MapBase;
    2120               
    22     template <typename V, typename A = std::allocator<V> > class Map : public MapBase {
     21    template <typename V, typename A = std::allocator<V> >
     22    class Map : public MapBase {
    2323   
    2424      public:
     
    3131                       
    3232      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
    33         int max_id = -1;
    34         for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    35           int id = getGraph()->id(it);
    36           if (id > max_id) {
    37             max_id = id;
    38           }                     
    39         }
    40         if (max_id == -1) {
    41           capacity = 0;
    42           values = 0;
    43           return;
    44         }
    45         capacity = 1;
    46         while (capacity <= max_id) {
    47           capacity <<= 1;
    48         }
    49         values = allocator.allocate(capacity);
     33        allocate_memory();
    5034        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    5135          int id = getGraph()->id(it);
     
    5539
    5640      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
    57         int max_id = -1;
    58         for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    59           int id = getGraph()->id(it);
    60           if (id > max_id) {
    61             max_id = id;
    62           }                     
    63         }
    64         if (max_id == -1) {
    65           capacity = 0;
    66           values = 0;
    67           return;
    68         }
    69         capacity = 1;
    70         while (capacity <= max_id) {
    71           capacity <<= 1;
    72         }
    73         values = allocator.allocate(capacity);
     41        allocate_memory();
    7442        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    7543          int id = getGraph()->id(it);
     
    8856      }
    8957
    90       template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
     58      template <typename CMap> Map(const CMap& copy)
     59        : capacity(0), values(0), MapBase(copy) {
    9160        if (getGraph()) {
    92           init();
     61          allocate_memory();
    9362          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    9463            set(it, copy[it]);
     
    11887        this->MapBase::operator=(copy);
    11988        if (getGraph()) {
    120           init();
     89          allocate_memory();
    12190          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    12291            set(it, copy[it]);
     
    12493        }
    12594      }
    126 
    127        
    12895                               
    12996      virtual ~Map() {
     
    182149      }
    183150       
    184       /** Compatible iterator with the stl maps' iterators.
    185        *  It iterates on pairs of a key and a value.
    186        */
    187151      class iterator {
    188152        friend class Map;
    189153        friend class const_iterator;
    190         private:
     154      private:
    191155
    192156        /** Private constructor to initalize the the iterators returned
     
    195159        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
    196160
    197         public:
     161      public:
    198162
    199163        /** Default constructor.
    200164         */
    201165        iterator() {}
     166
     167        typedef extended_pair<const Key&, const Key&,
     168                              Value&, Value&> Reference;
    202169
    203170        /** Dereference operator for map.
    204171         */     
    205         std::pair<const Key, Value> operator*() {
    206           return std::pair<const Key, Value>(it, (*map)[it]);
    207         }
     172        Reference operator*() {
     173          return Reference(it, (*map)[it]);
     174        }
     175
     176        class Pointer {
     177          friend class iterator;
     178        private:
     179          Reference data;
     180          Pointer(const Key& key, Value& val) : data(key, val) {}
     181        public:
     182          Reference* operator->() {return &data;}
     183        };
    208184
    209185        /** Arrow operator for map.
    210186         */     
    211         std::pair<const Key, Value>* operator->() {
    212           static std::pair<const Key, Value> tmp = operator*();
    213           return &tmp;
     187        Pointer operator->() {
     188          return Pointer(it, ((*map)[it]));
    214189        }
    215190
     
    240215          return !(*this == p_it);
    241216        }
    242        
    243         private:
     217
     218       
     219      private:
    244220        Map* map;
    245221        KeyIt it;
     
    261237        friend class Map;
    262238        friend class iterator;
    263         private:
     239      private:
    264240
    265241        /** Private constructor to initalize the the iterators returned
    266242         *  by the begin() and end().
    267243         */
    268         const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
    269 
    270         public:
     244        const_iterator (const Map& pmap, const KeyIt& pit)
     245          : map(&pmap), it(pit) {}
     246
     247      public:
    271248
    272249        /** Default constructor.
     
    276253        /** Constructor to convert iterator to const_iterator.
    277254         */
    278         const_iterator(iterator p_it) {
    279           it = p_it.it;
    280         }
     255        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
    281256     
     257        typedef extended_pair<const Key&, const Key&,
     258          const Value&, const Value&> Reference;
     259
    282260        /** Dereference operator for map.
    283261         */     
    284         std::pair<const Key, const Value> operator*() const {
    285           return std::pair<const Key, const Value>(it, (*map)[it]);
    286         }
     262        Reference operator*() {
     263          return Reference(it, (*map)[it]);
     264        }
     265
     266
     267        class Pointer {
     268          friend class const_iterator;
     269        private:
     270          Reference data;
     271          Pointer(const Key& key, const Value& val) : data(key, val) {}
     272        public:
     273          Reference* operator->() {return &data;}
     274        };
    287275
    288276        /** Arrow operator for map.
    289277         */     
    290         std::pair<const Key, const Value>* operator->() const {
    291           static std::pair<const Key, const Value> tmp = operator*();
    292           return &tmp;
     278        Pointer operator->() {
     279          return Pointer(it, ((*map)[it]));
    293280        }
    294281
     
    320307        }
    321308       
    322         private:
     309
     310      private:
    323311        const Map* map;
    324312        KeyIt it;
     
    337325      }
    338326
    339       private:
     327    private:
     328     
     329      void allocate_memory() {
     330        int max_id = -1;
     331        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     332          int id = getGraph()->id(it);
     333          if (id > max_id) {
     334            max_id = id;
     335          }                     
     336        }
     337        if (max_id == -1) {
     338          capacity = 0;
     339          values = 0;
     340          return;
     341        }
     342        capacity = 1;
     343        while (capacity <= max_id) {
     344          capacity <<= 1;
     345        }
     346        values = allocator.allocate(capacity); 
     347      }     
    340348      int capacity;
    341349      Value* values;
  • src/work/deba/extended_pair.h

    r702 r703  
     1// -*- c++ -*-
    12#ifndef EXTENDED_PAIR_H
    23#define EXTENDED_PAIR_H
     
    78  typedef T2 second_type;
    89
     10  extended_pair() : first(), second() {}
     11
    912  extended_pair(A1 f, A2 s) : first(f), second(s) {}
     13
     14  template <class Pair>
     15  extended_pair(const Pair& pair) : first(pair.first), second(pair.second) {}
    1016
    1117  T1 first;
     
    1319};
    1420
     21template <typename T1, typename T2,
     22          typename LA1, typename LA2, typename RA1, typename RA2>
     23bool operator==(const extended_pair<T1, LA1, T2, LA2>& left,
     24                const extended_pair<T1, RA1, T2, RA2>& right) {
     25  return left.first == right.first && left.second == right.second;
     26}
     27
     28template <typename T1, typename T2,
     29          typename LA1, typename LA2, typename RA1, typename RA2>
     30bool operator!=(const extended_pair<T1, LA1, T2, LA2>& left,
     31                const extended_pair<T1, RA1, T2, RA2>& right) {
     32  return  !(left == right);
     33}
     34
     35template <typename T1, typename T2,
     36          typename LA1, typename LA2, typename RA1, typename RA2>
     37bool operator<(const extended_pair<T1, LA1, T2, LA2>& left,
     38                const extended_pair<T1, RA1, T2, RA2>& right) {
     39  if (left.first == right.first) return left.second == right.second;
     40  return left.first < right.first;
     41}
     42
     43template <typename T1, typename T2,
     44          typename LA1, typename LA2, typename RA1, typename RA2>
     45bool operator>(const extended_pair<T1, LA1, T2, LA2>& left,
     46                const extended_pair<T1, RA1, T2, RA2>& right) {
     47  return right < left;
     48}
     49
     50template <typename T1, typename T2,
     51          typename LA1, typename LA2, typename RA1, typename RA2>
     52bool operator<=(const extended_pair<T1, LA1, T2, LA2>& left,
     53                const extended_pair<T1, RA1, T2, RA2>& right) {
     54  return !(right > left);
     55}
     56
     57template <typename T1, typename T2,
     58          typename LA1, typename LA2, typename RA1, typename RA2>
     59bool operator>=(const extended_pair<T1, LA1, T2, LA2>& left,
     60                const extended_pair<T1, RA1, T2, RA2>& right) {
     61  return !(right < left);
     62}
     63
     64
    1565#endif
  • src/work/deba/list_graph.h

    r702 r703  
    1313#include "invalid.h"
    1414
    15 #include "vector_map_factory.h"
     15#include "array_map_factory.h"
    1616#include "map_registry.h"
    1717
     
    7777   
    7878    CREATE_MAP_REGISTRIES;
    79     CREATE_MAPS(VectorMapFactory);
     79    CREATE_MAPS(ArrayMapFactory);
    8080  public:
    8181
  • src/work/deba/main.cpp

    r702 r703  
     1// -*- c++ -*-
    12#include <iostream>
    23#include <cstdlib>
     
    56using namespace std;
    67using namespace hugo;
     8
    79
    810
     
    2325  for (pit = map.begin(); pit != map.end(); ++pit) {
    2426    cout << g.id(pit->first) << ' ' << pit->second << endl;
    25   }
    26   /*
    27   ListGraph::NodeMap<double> ot_map = map;
    28   for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
    29     ot_map[it] *= 2.1;
    30     cout << ot_map[it] << endl;
    31   }
    32   ot_map = map;
    33   for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
    34     ot_map[it] *= 3.1;
    35     cout << ot_map[it] << endl;
    36     }*/
     27    (*pit).second = g.id(pit->first);
     28    cout << g.id((*pit).first) << ' ' << (*pit).second << endl;
     29  } 
     30  const ListGraph::NodeMap<int> const_map = map;
     31  ListGraph::NodeMap<int>::const_iterator cit;
     32  for (cit = const_map.begin(); cit != const_map.end(); ++cit) {
     33    cerr << g.id(cit->first) << ' ' << cit->second << endl;
     34    cerr << g.id((*cit).first) << ' ' << (*cit).second << endl;
     35  } 
    3736  return 0;
    3837}
  • src/work/deba/map_defines.h

    r701 r703  
    5454NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
    5555NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
    56 NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
     56NodeMap(const NodeMap& copy) \
     57  : Factory::Map<V>(static_cast<const Factory::Map<V>&>(copy)) {} \
    5758template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
    5859NodeMap& operator=(const NodeMap& copy) { \
    59   this->Factory::Map<V>::operator=(copy); \
     60  this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
    6061  return *this; \
    6162} \
     
    7980EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
    8081EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
    81 EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
     82EdgeMap(const EdgeMap& copy) \
     83  : Factory::Map<V>(static_cast<Factory::Map<V>&>(copy)) {} \
    8284template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
    8385EdgeMap& operator=(const EdgeMap& copy) { \
    84   this->Factory::Map<V>::operator=(copy); \
     86  this->Factory::Map<V>::operator=(static_cast<Factory::Map<V>&>(copy)); \
    8587  return *this; \
    8688} \
  • src/work/deba/map_registry.h

    r701 r703  
    9292      const Graph* getGraph() const { return graph; }
    9393       
    94     private:
    95                
    96       const Graph* graph;
     94    protected:
     95               
     96      const Graph* graph;     
    9797      Registry* registry;
    9898
  • src/work/deba/vector_map_factory.h

    r702 r703  
     1// -*- c++ -*-
    12#ifndef VECTOR_MAP_H
    23#define VECTOR_MAP_H
    34
    45#include <vector>
    5 #include <iostream>
    66
    77#include "extended_pair.h"
     
    5656       */
    5757      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
    58         init();
    5958        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    60           set(it, v);
     59          int id = getGraph->id(it);
     60          if (id >= container.size) {
     61            container.resize(id + 1);
     62          }
     63          set(it, v);
    6164        }
    6265      }
     
    6669      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
    6770        if (getGraph()) {
    68           init();
    6971          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     72            int id = getGraph->id(it);
     73            if (id >= container.size) {
     74              container.resize(id + 1);
     75            }
    7076            set(it, copy[it]);
    7177          }
     
    8187        this->MapBase::operator=(copy);
    8288        if (getGraph()) {
    83           init();
    8489          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     90            int id = getGraph->id(it);
     91            if (id >= container.size) {
     92              container.resize(id + 1);
     93            }
    8594            set(it, copy[it]);
    8695          }
     
    91100       */
    92101      virtual ~Map() {
    93         destroy();
    94102      }
    95103               
     
    152160        iterator() {}
    153161
     162        typedef extended_pair<const Key&, const Key&,
     163                              Value&, Value&> Reference;
     164
    154165        /** Dereference operator for map.
    155166         */     
    156         std::pair<const Key, Value> operator*() {
    157           return std::pair<const Key, Value>(it, (*map)[it]);
    158         }
    159 
     167        Reference operator*() {
     168          return Reference(it, (*map)[it]);
     169        }
    160170
    161171        class Pointer {
    162172          friend class iterator;
    163173        private:
    164           typedef extended_pair<const Key&, const Key&, Value&, Value&> Pair;
    165           Pair data;
     174          Reference data;
    166175          Pointer(const Key& key, Value& val) : data(key, val) {}
    167176        public:
    168           Pair* operator->() {return &data;}
     177          Reference* operator->() {return &data;}
    169178        };
    170179
     
    228237         *  by the begin() and end().
    229238         */
    230         const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
     239        const_iterator (const Map& pmap, const KeyIt& pit)
     240          : map(&pmap), it(pit) {}
    231241
    232242      public:
     
    238248        /** Constructor to convert iterator to const_iterator.
    239249         */
    240         const_iterator(iterator p_it) {
    241           it = p_it.it;
    242         }
     250        const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
    243251     
     252        typedef extended_pair<const Key&, const Key&,
     253          const Value&, const Value&> Reference;
     254
    244255        /** Dereference operator for map.
    245256         */     
    246         std::pair<const Key, const Value> operator*() const {
    247           return std::pair<const Key, const Value>(it, (*map)[it]);
    248         }
     257        Reference operator*() {
     258          return Reference(it, (*map)[it]);
     259        }
     260
    249261
    250262        class Pointer {
    251263          friend class const_iterator;
    252264        private:
    253           typedef extended_pair<const Key&, const Key&, const Value&, const Value&> Pair;
    254           Pair data;
     265          Reference data;
    255266          Pointer(const Key& key, const Value& val) : data(key, val) {}
    256267        public:
    257           Pair* operator->() {return &data;}
     268          Reference* operator->() {return &data;}
    258269        };
     270
    259271        /** Arrow operator for map.
    260272         */     
    261         Pointer operator->() const {
    262           return Pointer(it, (*map)[it]);
     273        Pointer operator->() {
     274          return Pointer(it, ((*map)[it]));
    263275        }
    264276
Note: See TracChangeset for help on using the changeset viewer.