COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
07/14/04 23:16:10 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@953
Message:
 
File:
1 edited

Legend:

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

    r674 r702  
    2020    typedef typename MapRegistry::MapBase MapBase;
    2121               
    22     template <typename V, typename A = std::allocator<V> >
    23       class Map : public MapBase {
     22    template <typename V, typename A = std::allocator<V> > class Map : public MapBase {
    2423   
    25         public:
    26 
    27         typedef V Value;
    28         typedef A Allocator;
    29 
    30        
    31         Map() : values(0), capacity(0) {}
     24      public:
     25
     26      typedef V Value;
     27      typedef A Allocator;
     28
     29       
     30      Map() : values(0), capacity(0) {}
    3231                       
    33         Map(Graph& g, MapRegistry& r) : MapBase(g, r) {
    34           int max_id = -1;
    35           for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    36             int id = graph->id(it);
    37             if (id > max_id) {
    38               max_id = id;
    39             }                   
     32      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);
     50        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     51          int id = getGraph()->id(it);
     52          allocator.construct(&(values[id]), Value());
     53        }                                                               
     54      }
     55
     56      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);
     74        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     75          int id = getGraph()->id(it);
     76          allocator.construct(&(values[id]), v);
     77        }                                                               
     78      }
     79
     80      Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
     81        capacity = copy.capacity;
     82        if (capacity == 0) return;
     83        values = allocator.allocate(capacity);
     84        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     85          int id = getGraph()->id(it);
     86          allocator.construct(&(values[id]), copy.values[id]);
     87        }
     88      }
     89
     90      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
     91        if (getGraph()) {
     92          init();
     93          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     94            set(it, copy[it]);
    4095          }
    41           if (max_id == -1) {
    42             capacity = 0;
    43             values = 0;
    44             return;
    45           }
    46           capacity = 1;
    47           while (capacity <= max_id) {
    48             capacity <<= 1;
    49           }
    50           values = allocator.allocate(capacity);
    51           for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    52             int id = graph->id(it);
    53             allocator.construct(&(values[id]), Value());
    54           }                                                             
    55         }
    56 
    57         Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
    58           capacity = copy.capacity;
    59           values = allocator.allocate(capacity);
    60           for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    61             int id = graph->id(it);
    62             allocator.construct(&(values[id]), copy.values[id]);
    63           }
    64         }
    65                                
    66         virtual ~Map() {
     96        }
     97      }
     98
     99      Map& operator=(const Map& copy) {
     100        if (&copy == this) return;
     101        if (capacity != 0) {
    67102          destroy();
    68103          allocator.deallocate(values, capacity);
    69104        }
    70        
    71        
    72         Value& operator[](const Key& key) {
    73           int id = graph->id(key);
    74           return values[id];
     105        capacity = copy.capacity;
     106        if (capacity == 0) return;
     107        values = allocator.allocate(capacity);
     108        for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     109          int id = getGraph()->id(it);
     110          allocator.construct(&(values[id]), copy.values[id]);
     111        }
     112      }
     113
     114      template <typename CMap> Map& operator=(const CMap& copy) {
     115        if (getGraph()) {
     116          destroy();
    75117        }
    76                
    77         const Value& operator[](const Key& key) const {
    78           int id = graph->id(key);
    79           return values[id];
    80         }
    81        
    82         const Value& get(const Key& key) const {
    83           int id = graph->id(key);
    84           return values[id];
    85         }
    86                
    87         void set(const Key& key, const Value& val) {
    88           int id = graph->id(key);
    89           values[id] = val;
    90         }
    91                
    92         void add(const Key& key) {
    93           int id = graph->id(key);
    94           if (id >= capacity) {
    95             int new_capacity = (capacity == 0 ? 1 : capacity);
    96             while (new_capacity <= id) {
    97               new_capacity <<= 1;
     118        this->MapBase::operator=(copy);
     119        if (getGraph()) {
     120          init();
     121          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     122            set(it, copy[it]);
     123          }
     124        }
     125      }
     126
     127       
     128                               
     129      virtual ~Map() {
     130        if (capacity != 0) {
     131          destroy();
     132          allocator.deallocate(values, capacity);
     133        }
     134      }
     135       
     136       
     137      Value& operator[](const Key& key) {
     138        int id = getGraph()->id(key);
     139        return values[id];
     140      }
     141               
     142      const Value& operator[](const Key& key) const {
     143        int id = getGraph()->id(key);
     144        return values[id];
     145      }
     146       
     147      const Value& get(const Key& key) const {
     148        int id = getGraph()->id(key);
     149        return values[id];
     150      }
     151               
     152      void set(const Key& key, const Value& val) {
     153        int id = getGraph()->id(key);
     154        values[id] = val;
     155      }
     156               
     157      void add(const Key& key) {
     158        int id = getGraph()->id(key);
     159        if (id >= capacity) {
     160          int new_capacity = (capacity == 0 ? 1 : capacity);
     161          while (new_capacity <= id) {
     162            new_capacity <<= 1;
     163          }
     164          Value* new_values = allocator.allocate(new_capacity);;
     165          for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
     166            int jd = getGraph()->id(it);
     167            if (id != jd) {
     168              allocator.construct(&(new_values[jd]), values[jd]);
     169              allocator.destroy(&(values[jd]));
    98170            }
    99             Value* new_values = allocator.allocate(new_capacity);;
    100             for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    101               int jd = graph->id(it);
    102               if (id != jd) {
    103                 allocator.construct(&(new_values[jd]), values[jd]);
    104                 allocator.destroy(&(values[jd]));
    105               }
    106             }
    107             if (capacity != 0) allocator.deallocate(values, capacity);
    108             values = new_values;
    109             capacity = new_capacity;
    110171          }
    111           allocator.construct(&(values[id]), Value());
    112         }
    113                
    114         void erase(const Key& key) {
    115           int id = graph->id(key);
    116           allocator.destroy(&(values[id]));
    117         }
    118        
     172          if (capacity != 0) allocator.deallocate(values, capacity);
     173          values = new_values;
     174          capacity = new_capacity;
     175        }
     176        allocator.construct(&(values[id]), Value());
     177      }
     178               
     179      void erase(const Key& key) {
     180        int id = getGraph()->id(key);
     181        allocator.destroy(&(values[id]));
     182      }
     183       
     184      /** Compatible iterator with the stl maps' iterators.
     185       *  It iterates on pairs of a key and a value.
     186       */
     187      class iterator {
     188        friend class Map;
     189        friend class const_iterator;
    119190        private:
    120         int capacity;
    121         Value* values;
    122         Allocator allocator;
    123       };               
     191
     192        /** Private constructor to initalize the the iterators returned
     193         *  by the begin() and end().
     194         */
     195        iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
     196
     197        public:
     198
     199        /** Default constructor.
     200         */
     201        iterator() {}
     202
     203        /** Dereference operator for map.
     204         */     
     205        std::pair<const Key, Value> operator*() {
     206          return std::pair<const Key, Value>(it, (*map)[it]);
     207        }
     208
     209        /** Arrow operator for map.
     210         */     
     211        std::pair<const Key, Value>* operator->() {
     212          static std::pair<const Key, Value> tmp = operator*();
     213          return &tmp;
     214        }
     215
     216        /** The pre increment operator of the map.
     217         */
     218        iterator& operator++() {
     219          map->getGraph()->next(it);
     220          return *this;
     221        }
     222
     223        /** The post increment operator of the map.
     224         */
     225        iterator operator++(int) {
     226          iterator tmp(it);
     227          map.getGraph()->next(it);
     228          return tmp;
     229        }
     230
     231        /** The equality operator of the map.
     232         */
     233        bool operator==(const_iterator p_it) {
     234          return p_it.it == it;
     235        }
     236       
     237        /** The not-equality operator of the map.
     238         */
     239        bool operator!=(const_iterator p_it) {
     240          return !(*this == p_it);
     241        }
     242       
     243        private:
     244        Map* map;
     245        KeyIt it;
     246      };
     247
     248      /** Returns the begin iterator of the map.
     249       */
     250      iterator begin() {
     251        return iterator(*this, KeyIt(*getGraph()));
     252      }
     253
     254      /** Returns the end iterator of the map.
     255       */
     256      iterator end() {
     257        return iterator(*this, INVALID);
     258      }
     259
     260      class const_iterator {
     261        friend class Map;
     262        friend class iterator;
     263        private:
     264
     265        /** Private constructor to initalize the the iterators returned
     266         *  by the begin() and end().
     267         */
     268        const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
     269
     270        public:
     271
     272        /** Default constructor.
     273         */
     274        const_iterator() {}
     275
     276        /** Constructor to convert iterator to const_iterator.
     277         */
     278        const_iterator(iterator p_it) {
     279          it = p_it.it;
     280        }
     281     
     282        /** Dereference operator for map.
     283         */     
     284        std::pair<const Key, const Value> operator*() const {
     285          return std::pair<const Key, const Value>(it, (*map)[it]);
     286        }
     287
     288        /** Arrow operator for map.
     289         */     
     290        std::pair<const Key, const Value>* operator->() const {
     291          static std::pair<const Key, const Value> tmp = operator*();
     292          return &tmp;
     293        }
     294
     295        /** The pre increment operator of the map.
     296         */
     297        const_iterator& operator++() {
     298          map->getGraph()->next(it);
     299          return *this;
     300        }
     301
     302        /** The post increment operator of the map.
     303         */
     304        const_iterator operator++(int) {
     305          const_iterator tmp(it);
     306          map->getGraph()->next(it);
     307          return tmp;
     308        }
     309
     310        /** The equality operator of the map.
     311         */
     312        bool operator==(const_iterator p_it) {
     313          return p_it.it == it;
     314        }
     315       
     316        /** The not-equality operator of the map.
     317         */
     318        bool operator!=(const_iterator p_it) {
     319          return !(*this == p_it);
     320        }
     321       
     322        private:
     323        const Map* map;
     324        KeyIt it;
     325      };
     326
     327      /** Returns the begin const_iterator of the map.
     328       */
     329      const_iterator begin() const {
     330        return const_iterator(*this, KeyIt(*getGraph()));
     331      }
     332
     333      /** Returns the end const_iterator of the map.
     334       */
     335      const_iterator end() const {
     336        return const_iterator(*this, INVALID);
     337      }
     338
     339      private:
     340      int capacity;
     341      Value* values;
     342      Allocator allocator;
     343    };         
    124344  };
    125345}
Note: See TracChangeset for help on using the changeset viewer.