Changeset 674:7733d18de0e8 in lemon-0.x for src/work/deba
- Timestamp:
- 06/04/04 13:52:53 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@911
- Location:
- src/work/deba
- Files:
-
- 1 added
- 3 edited
-
array_map_factory.h (modified) (2 diffs)
-
main.cpp (modified) (1 diff)
-
map_defines.h (added)
-
test_graph.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/work/deba/array_map_factory.h
r627 r674 4 4 #include <memory> 5 5 6 #include "map_base.h"7 6 8 7 #include <iostream> … … 11 10 namespace hugo { 12 11 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 } 15 70 16 71 17 public: 72 Value& operator[](const Key& key) { 73 int id = graph->id(key); 74 return values[id]; 75 } 18 76 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 } 22 86 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 } 29 118 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 }; 121 125 } 122 126 -
src/work/deba/main.cpp
r627 r674 12 12 ListGraph::Node node = g.addNode(); 13 13 } 14 ListGraph::NodeMap Factory::Map<int> map(g, g.node_maps);14 ListGraph::NodeMap<int> map(g); 15 15 for (int i = 0; i < 10; ++i) { 16 16 ListGraph::Node node = g.addNode(); -
src/work/deba/test_graph.h
r627 r674 8 8 #include "invalid.h" 9 9 10 #include "vector_map_factory.h" 10 #include "map_registry.h" 11 #include "array_map_factory.h" 12 13 #include "map_defines.h" 11 14 12 15 namespace hugo { … … 31 34 class SymEdgeIt; 32 35 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 35 41 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 54 42 55 43 int node_id;
Note: See TracChangeset
for help on using the changeset viewer.
