1.1 --- a/src/hugo/vector_map.h Wed Sep 29 14:12:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,243 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/hugo/vector_map.h - Part of HUGOlib, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef HUGO_VECTOR_MAP_H
1.21 -#define HUGO_VECTOR_MAP_H
1.22 -
1.23 -#include <vector>
1.24 -
1.25 -#include <hugo/map_iterator.h>
1.26 -#include <hugo/map_bits.h>
1.27 -
1.28 -///\ingroup graphmaps
1.29 -///\file
1.30 -///\brief Vector based graph maps.
1.31 -
1.32 -namespace hugo {
1.33 -
1.34 - /// \addtogroup graphmaps
1.35 - /// @{
1.36 -
1.37 - /** The ArrayMap template class is graph map structure what
1.38 - * automatically updates the map when a key is added to or erased from
1.39 - * the map. This map factory uses the allocators to implement
1.40 - * the container functionality. This map factory
1.41 - * uses the std::vector to implement the container function.
1.42 - *
1.43 - * The template parameter is the MapRegistry that the maps
1.44 - * will belong to and the ValueType.
1.45 - *
1.46 - * \todo It should use a faster initialization using the maxNodeId() or
1.47 - * maxEdgeId() function of the graph instead of iterating through each
1.48 - * edge/node.
1.49 - */
1.50 -
1.51 - template <typename MapRegistry, typename Value>
1.52 - class VectorMap : public MapRegistry::MapBase {
1.53 - template <typename MR, typename T> friend class VectorMap;
1.54 - public:
1.55 -
1.56 - /// The graph type of the maps.
1.57 - typedef typename MapRegistry::Graph Graph;
1.58 - /// The key type of the maps.
1.59 - typedef typename MapRegistry::KeyType KeyType;
1.60 - /// The iterator to iterate on the keys.
1.61 - typedef typename MapRegistry::KeyIt KeyIt;
1.62 -
1.63 - /// The map type.
1.64 - typedef VectorMap Map;
1.65 - /// The MapBase of the Map which implements the core regisitry function.
1.66 - typedef typename MapRegistry::MapBase MapBase;
1.67 -
1.68 - private:
1.69 -
1.70 - /// The container type of the map.
1.71 - typedef std::vector<Value> Container;
1.72 -
1.73 - public:
1.74 -
1.75 -
1.76 - /// The value type of the map.
1.77 - typedef Value ValueType;
1.78 - /// The reference type of the map;
1.79 - typedef typename Container::reference ReferenceType;
1.80 - /// The pointer type of the map;
1.81 - typedef typename Container::pointer PointerType;
1.82 -
1.83 - /// The const value type of the map.
1.84 - typedef const Value ConstValueType;
1.85 - /// The const reference type of the map;
1.86 - typedef typename Container::const_reference ConstReferenceType;
1.87 - /// The pointer type of the map;
1.88 - typedef typename Container::const_pointer ConstPointerType;
1.89 -
1.90 - /** Graph and Registry initialized map constructor.
1.91 - */
1.92 - VectorMap(const Graph& g, MapRegistry& r)
1.93 - : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
1.94 -
1.95 - /** Constructor to use default value to initialize the map.
1.96 - */
1.97 - VectorMap(const Graph& g, MapRegistry& r, const Value& v)
1.98 - : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
1.99 -
1.100 - /** Assign operator to copy a map of an other map type.
1.101 - */
1.102 - template <typename TT>
1.103 - VectorMap(const VectorMap<MapRegistry, TT>& c)
1.104 - : MapBase(c), container(c.container.size()) {
1.105 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.106 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.107 - container[id] = c.container[id];
1.108 - }
1.109 - }
1.110 -
1.111 - /** Assign operator to copy a map of an other map type.
1.112 - */
1.113 - template <typename TT>
1.114 - VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
1.115 - if (MapBase::getGraph() != c.getGraph()) {
1.116 - MapBase::operator=(c);
1.117 - container.resize(c.container.size());
1.118 - }
1.119 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.120 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.121 - container[id] = c.container[id];
1.122 - }
1.123 - return *this;
1.124 - }
1.125 - /**
1.126 - * The subscript operator. The map can be subscripted by the
1.127 - * actual keys of the graph.
1.128 - */
1.129 - ReferenceType operator[](const KeyType& key) {
1.130 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.131 - return container[id];
1.132 - }
1.133 -
1.134 - /**
1.135 - * The const subscript operator. The map can be subscripted by the
1.136 - * actual keys of the graph.
1.137 - */
1.138 - ConstReferenceType operator[](const KeyType& key) const {
1.139 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.140 - return container[id];
1.141 - }
1.142 -
1.143 - /** Setter function of the map. Equivalent with map[key] = val.
1.144 - * This is a compatibility feature with the not dereferable maps.
1.145 - */
1.146 - void set(const KeyType& key, const ValueType& val) {
1.147 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.148 - container[id] = val;
1.149 - }
1.150 -
1.151 - /** Add a new key to the map. It called by the map registry.
1.152 - */
1.153 - void add(const KeyType& key) {
1.154 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.155 - if (id >= (int)container.size()) {
1.156 - container.resize(id + 1);
1.157 - }
1.158 - }
1.159 -
1.160 - /** Erase a key from the map. It called by the map registry.
1.161 - */
1.162 - void erase(const KeyType& key) {}
1.163 -
1.164 - /** Clear the data structure.
1.165 - */
1.166 - void clear() {
1.167 - container.clear();
1.168 - }
1.169 -
1.170 - /// The stl compatible pair iterator of the map.
1.171 - typedef MapIterator<VectorMap> Iterator;
1.172 - /// The stl compatible const pair iterator of the map.
1.173 - typedef MapConstIterator<VectorMap> ConstIterator;
1.174 -
1.175 - /** Returns the begin iterator of the map.
1.176 - */
1.177 - Iterator begin() {
1.178 - return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.179 - }
1.180 -
1.181 - /** Returns the end iterator of the map.
1.182 - */
1.183 - Iterator end() {
1.184 - return Iterator(*this, INVALID);
1.185 - }
1.186 -
1.187 - /** Returns the begin ConstIterator of the map.
1.188 - */
1.189 - ConstIterator begin() const {
1.190 - return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.191 - }
1.192 -
1.193 - /** Returns the end const_iterator of the map.
1.194 - */
1.195 - ConstIterator end() const {
1.196 - return ConstIterator(*this, INVALID);
1.197 - }
1.198 -
1.199 - /// The KeySet of the Map.
1.200 - typedef MapConstKeySet<VectorMap> ConstKeySet;
1.201 -
1.202 - /// KeySet getter function.
1.203 - ConstKeySet keySet() const {
1.204 - return ConstKeySet(*this);
1.205 - }
1.206 -
1.207 - /// The ConstValueSet of the Map.
1.208 - typedef MapConstValueSet<VectorMap> ConstValueSet;
1.209 -
1.210 - /// ConstValueSet getter function.
1.211 - ConstValueSet valueSet() const {
1.212 - return ConstValueSet(*this);
1.213 - }
1.214 -
1.215 - /// The ValueSet of the Map.
1.216 - typedef MapValueSet<VectorMap> ValueSet;
1.217 -
1.218 - /// ValueSet getter function.
1.219 - ValueSet valueSet() {
1.220 - return ValueSet(*this);
1.221 - }
1.222 -
1.223 -
1.224 - private:
1.225 -
1.226 - Container container;
1.227 -
1.228 - public:
1.229 - // STL compatibility typedefs.
1.230 - typedef Iterator iterator;
1.231 - typedef ConstIterator const_iterator;
1.232 - typedef typename Iterator::PairValueType value_type;
1.233 - typedef typename Iterator::KeyType key_type;
1.234 - typedef typename Iterator::ValueType data_type;
1.235 - typedef typename Iterator::PairReferenceType reference;
1.236 - typedef typename Iterator::PairPointerType pointer;
1.237 - typedef typename ConstIterator::PairReferenceType const_reference;
1.238 - typedef typename ConstIterator::PairPointerType const_pointer;
1.239 - typedef int difference_type;
1.240 - };
1.241 -
1.242 - /// @}
1.243 -
1.244 -}
1.245 -
1.246 -#endif