COIN-OR::LEMON - Graph Library

Changeset 674:7733d18de0e8 in lemon-0.x


Ignore:
Timestamp:
06/04/04 13:52:53 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@911
Message:
 
Location:
src/work/deba
Files:
1 added
3 edited

Legend:

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

    r627 r674  
    44#include <memory>
    55
    6 #include "map_base.h"
    76
    87#include <iostream>
     
    1110namespace hugo {
    1211       
    13         template <typename G, typename K, typename KIt>
    14         class ArrayMapFactory {
     12  template <typename MapRegistry> class ArrayMapFactory {
     13               
     14  public:
     15               
     16    typedef typename MapRegistry::Graph Graph;
     17    typedef typename MapRegistry::Key Key;
     18    typedef typename MapRegistry::KeyIt KeyIt;
     19
     20    typedef typename MapRegistry::MapBase MapBase;
     21               
     22    template <typename V, typename A = std::allocator<V> >
     23      class Map : public MapBase {
     24   
     25        public:
     26
     27        typedef V Value;
     28        typedef A Allocator;
     29
     30       
     31        Map() : values(0), capacity(0) {}
     32                       
     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            }                   
     40          }
     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() {
     67          destroy();
     68          allocator.deallocate(values, capacity);
     69        }
    1570       
    1671       
    17         public:
     72        Value& operator[](const Key& key) {
     73          int id = graph->id(key);
     74          return values[id];
     75        }
    1876               
    19                 typedef G Graph;
    20                 typedef K Key;
    21                 typedef KIt KeyIt;
     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        }
    2286               
    23                 template <typename V, typename A = allocator<V> >
    24                 class Map : public MapBase<G, K, KIt> {
    25                 public:
    26                         typedef V Value;
    27                         typedef typename _Alloc_traits<V, A>::_Alloc_type _Alloc_type;
    28 
     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;
     98            }
     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;
     110          }
     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        }
    29118       
    30                         Map() : values(0), capacity(0) {}
    31                        
    32                         Map(Graph& g, MapRegistry<G, K, KIt>& r)
    33                                 : MapBase<G, K, KIt>(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                                         }                               
    40                                 }
    41                                 if (max_id == -1) {
    42                                         capacity = 0;
    43                                         values = 0;
    44                                         return;
    45                                 }
    46                                 int capacity = 1;
    47                                 while (capacity <= max_id) {
    48                                         capacity <<= 1;
    49                                 }
    50                                 Value* values = reinterpret_cast<Value*>(new char[capacity*sizeof(Value)]);
    51                                 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    52                                         int id = graph->id(it);
    53                                         new(&(values[id])) Value();
    54                                 }                                                               
    55                                 cerr << capacity << endl;       
    56                         }
    57                                
    58                         virtual ~Map() {
    59                                 destroy();
    60                                 delete[] reinterpret_cast<char*>(values);
    61                                 values = 0;
    62                                 capacity = 0;
    63                         }
    64        
    65        
    66                         Value& operator[](const K& key) {
    67                                 int id = graph->id(key);
    68                                 return values[id];
    69                         }
    70                
    71                         const Value& operator[](const K& key) const {
    72                                 int id = graph->id(key);
    73                                 return values[id];
    74                         }
    75        
    76                         const Value& get(const K& key) const {
    77                                 int id = graph->id(key);
    78                                 return values[id];
    79                         }
    80                
    81                         void set(const K& key, const Value& val) {
    82                                 int id = graph->id(key);
    83                                 values[id] = val;
    84                         }
    85                
    86                         void add(const K& key) {
    87                                 cerr << capacity << endl;
    88                                 int id = graph->id(key);
    89                                 if (id >= capacity) {
    90                                         int new_capacity = (capacity == 0 ? 1 : capacity);
    91                                         while (new_capacity <= id) {
    92                                                 new_capacity <<= 1;
    93                                         }
    94                                         Value* new_values = reinterpret_cast<Value*>(new char[new_capacity*sizeof(Value)]);;
    95                                         for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
    96                                                 int jd = graph->id(it);
    97                                                 if (id != jd) {
    98                                                         new(&(new_values[jd])) Value(values[jd]);
    99                                                 }
    100                                         }
    101                                         if (capacity != 0) delete[] reinterpret_cast<char *>(values);
    102                                         values = new_values;
    103                                         capacity = new_capacity;
    104                                 }
    105                                 cerr << id << ' ' << capacity << endl;
    106                                 new(&(values[id])) Value();
    107                         }
    108                
    109                         void erase(const K& key) {
    110                                 int id = graph->id(key);
    111                                 values[id].~Value();
    112                         }
    113        
    114                 private:
    115                         int capacity;
    116                         Value* values;
    117                                                                
    118                 };
    119                
    120         };
     119        private:
     120        int capacity;
     121        Value* values;
     122        Allocator allocator;
     123      };               
     124  };
    121125}
    122126
  • src/work/deba/main.cpp

    r627 r674  
    1212    ListGraph::Node node = g.addNode();
    1313  }
    14   ListGraph::NodeMapFactory::Map<int> map(g, g.node_maps);
     14  ListGraph::NodeMap<int> map(g);
    1515  for (int i = 0; i < 10; ++i) {
    1616    ListGraph::Node node = g.addNode();
  • src/work/deba/test_graph.h

    r627 r674  
    88#include "invalid.h"
    99
    10 #include "vector_map_factory.h"
     10#include "map_registry.h"
     11#include "array_map_factory.h"
     12
     13#include "map_defines.h"
    1114
    1215namespace hugo {
     
    3134    class SymEdgeIt;
    3235   
    33     //    template <typename T> class NodeMap;
    34     //    template <typename T> class EdgeMap;
     36    typedef ListGraph Graph;
     37 
     38    CREATE_MAP_REGISTRIES
     39    CREATE_MAPS(ArrayMapFactory)
     40
    3541  private:
    36     //    template <typename T> friend class NodeMap;
    37     //   template <typename T> friend class EdgeMap;
    38  
    39   private:
    40 
    41  
    42   public:
    43        
    44     typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
    45     typedef VectorMapFactory<NodeMapRegistry> NodeMapFactory;
    46     NodeMapRegistry node_maps;
    47 
    48 
    49 
    50     typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
    51     typedef VectorMapFactory<EdgeMapRegistry> EdgeMapFactory;
    52     EdgeMapRegistry edge_maps;
    53  
    5442
    5543    int node_id;
Note: See TracChangeset for help on using the changeset viewer.