00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include "mhash_map.h"
00034 #include "RandomUtil.h"
00035 #include "Log.h"
00036
00042 #ifndef CANDIDATE_MAP_H
00043 #define CANDIDATE_MAP_H 1
00044
00045 namespace mace {
00046
00071 template<class Key, class Data, class HashFcn = __gnu_cxx::hash<Key>, class EqualKey = std::equal_to<Key>, class Alloc = std::allocator<Data> >
00072 class CandidateMap : public mace::hash_map<Key, Data, SerializeMap<Key, Data>, HashFcn, EqualKey, Alloc> {
00073
00074 public:
00075 typedef typename mace::hash_map<Key, Data, SerializeMap<Key, Data>, HashFcn, EqualKey, Alloc> base_hash_map;
00076 typedef typename base_hash_map::iterator iterator;
00077
00078 CandidateMap() : base_hash_map(), maxSize((size_t)-1), n(0) {
00079 }
00080
00081 CandidateMap(size_t s) : base_hash_map(), maxSize(s), n(0) {
00082 }
00083
00084 virtual ~CandidateMap() { }
00085
00087 virtual void setMaxSize(size_t size) {
00088 maxSize = size;
00089 }
00090
00092 void reset() {
00093 n = 0;
00094 }
00095
00097 size_t aggregateCount() {
00098 if (n < this->size()) {
00099 n = this->size();
00100 }
00101 return n;
00102 }
00103
00105 void compact(CandidateMap<Key, Data, HashFcn, EqualKey, Alloc> cs) {
00106 base_hash_map tmp;
00107
00108 n += cs.size();
00109
00110
00111 while (this->size() > maxSize) {
00112 randErase();
00113 }
00114
00115 while (cs.size() > cs.maxSize) {
00116 cs.randErase();
00117 }
00118
00119
00120 if (n < this->size()) {
00121 n = this->size();
00122 }
00123
00124 if (cs.n < cs.size()) {
00125 cs.n = cs.size();
00126 }
00127
00128 size_t accum = 0;
00129 std::pair<Key, Data> v;
00130 int baseweight = n;
00131 int weight = cs.n;
00132
00133 size_t total = this->size() + cs.size();
00134 if (total > maxSize) {
00135 total = maxSize;
00136 }
00137
00138 while (accum < total) {
00139 bool rnd = RandomUtil::randInt(2, baseweight, weight);
00140
00141 if (cs.empty() || (!this->empty() && !rnd)) {
00142
00143 if (this->empty()) {
00144 break;
00145 }
00146 v = randErase();
00147 baseweight--;
00148 }
00149 else {
00150 v = cs.randErase();
00151 weight--;
00152 }
00153
00154 if (tmp.find(v.first) == tmp.end()) {
00155 accum++;
00156 }
00157 tmp[v.first] = v.second;
00158 }
00159
00160 this->clear();
00161
00162 for (iterator i = tmp.begin();
00163 i != tmp.end(); i++) {
00164 operator[](i->first) = i->second;
00165 }
00166 }
00167
00168 void serialize(std::string &s) const throw(SerializationException) {
00169 base_hash_map::serialize(s);
00170 mace::serialize(s, &maxSize);
00171 mace::serialize(s, &n);
00172 }
00173
00174 int deserialize(std::istream& in) throw(SerializationException) {
00175 unsigned offset = base_hash_map::deserialize(in);
00176 offset += mace::deserialize(in, &maxSize);
00177 offset += mace::deserialize(in, &n);
00178 return offset;
00179 }
00180
00181 private:
00183 std::pair<Key, Data> randErase() {
00184 size_t pos = RandomUtil::randInt(this->size());
00185 iterator i = this->begin();
00186 for (size_t count = 0; count < pos; count++, i++);
00187 std::pair<Key, Data> p = *i;
00188 erase(i);
00189 return p;
00190 }
00191
00192 private:
00193 size_t maxSize;
00194
00195
00196 size_t n;
00197 };
00198
00201 }
00202 #endif // CANDIDATE_MAP_H