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
00034 #include <float.h>
00035
00036 #include "mace.h"
00037
00038 #include <map>
00039 #include "mset.h"
00040 #include "XmlRpcCollection.h"
00041 #include "Serializable.h"
00042 #include "Iterator.h"
00043 #include "MaceTypes.h"
00044 #include "RandomUtil.h"
00045 #include "StrUtil.h"
00046 #include "Traits.h"
00047
00048 #ifndef _NEIGHBOR_SET_H
00049 #define _NEIGHBOR_SET_H
00050
00056 namespace mace {
00057
00082 template <class NodeType, uint32_t MaxSize = UINT_MAX>
00083 class NodeCollection : private std::map<MaceKey, NodeType>, public Serializable, public PrintPrintable
00084 {
00085 public:
00086 typedef std::map<MaceKey, NodeType> mapType;
00087 typedef typename mapType::iterator iterator;
00088 typedef typename mapType::const_iterator const_iterator;
00089 typedef typename mapType::reverse_iterator reverse_iterator;
00090 typedef typename mapType::const_reverse_iterator const_reverse_iterator;
00091 typedef typename mapType::size_type size_type;
00092 typedef MapIterator<NodeCollection<NodeType, MaxSize> > map_iterator;
00093 typedef ConstMapIterator<NodeCollection<NodeType, MaxSize> > const_map_iterator;
00094 typedef NodeType mapped_type;
00095
00096 private:
00097
00098 friend class MapIterator<NodeCollection<NodeType, MaxSize> >;
00099 friend class ConstMapIterator<NodeCollection<NodeType, MaxSize> >;
00100
00101 friend int XmlRpcMapDeserialize<NodeCollection<NodeType, MaxSize>, MaceKey, NodeType>(std:: istream& in, NodeCollection<NodeType, MaxSize>& obj);
00102
00103
00104 void erase(iterator i) { myNodeSet.erase(i->first); mapType::erase(i); }
00105
00106
00107
00108
00109
00110 NodeSet myNodeSet;
00111
00112 public:
00113 using mapType::begin;
00114 using mapType::rbegin;
00115 using mapType::end;
00116 using mapType::rend;
00117 using mapType::find;
00118 using mapType::lower_bound;
00119 using mapType::upper_bound;
00120
00122 inline size_t maxSize() const {
00123 return MaxSize;
00124 }
00125
00127 inline size_t maxsize() const {
00128 return MaxSize;
00129 }
00130
00131 NodeCollection() : mapType(), myNodeSet() { }
00132 virtual ~NodeCollection() {}
00133
00135 bool contains(const MaceKey& who) const {
00136
00137 return myNodeSet.contains(who);
00138 }
00140 bool containsKey(const MaceKey& who) const {
00141 return this->contains(who);
00142 }
00143
00144 using mapType::size;
00145 using mapType::empty;
00146
00148 NodeType& get(const MaceKey& who) {
00149 iterator i = mapType::find(who);
00150 if (i == end()) {
00151 ABORT("element not in collection");
00152 }
00153 return i->second;
00154 }
00155
00157 const NodeType& get(const MaceKey& who) const {
00158 const_iterator i = mapType::find(who);
00159 if (i == end()) {
00160 ASSERT(false);
00161 }
00162 return i->second;
00163 }
00164
00166 NodeType& add(const MaceKey& who) {
00167 iterator i = mapType::find(who);
00168 if (i == end() && size() < MaxSize) {
00169 myNodeSet.insert(who);
00170 return (this->operator[](who) = NodeType(who));
00171 }
00172 else if (i == end()) {
00173 ASSERT(false && size() < MaxSize);
00174 }
00175 else {
00176 return (i->second);
00177 }
00178 }
00179
00181 NodeType& add(const NodeType& nbr) {
00182 iterator i = mapType::find(nbr.getId());
00183 if (i == end() && size() < MaxSize) {
00184 myNodeSet.insert(nbr.getId());
00185 return (this->operator[](nbr.getId()) = nbr);
00186 }
00187 else if (i == end()) {
00188 ASSERT(false && size() < MaxSize);
00189 }
00190 else {
00191 return (i->second = nbr);
00192 }
00193 }
00194
00196 void clear() {
00197
00198 if(!myNodeSet.empty()) {
00199 myNodeSet.clear();
00200 mapType::clear();
00201 }
00202 }
00203
00205 size_type erase(const MaceKey& who) {
00206
00207 myNodeSet.erase(who);
00208 return mapType::erase(who);
00209 }
00210
00212 size_type erase(const NodeType& who) {
00213 myNodeSet.erase(who.getId());
00214 return mapType::erase(who.getId());
00215 }
00216
00232 template<typename S>
00233 bool query(S (NodeType::*val)(void), S v) {
00234 for(iterator i=begin(); i!=end(); i++) {
00235 if((i->second.*val)() == v) {
00236 return true;
00237 }
00238 }
00239 return false;
00240 }
00241
00257 template<typename S>
00258 iterator find(S (NodeType::*val)(void), S v) {
00259 for(iterator i=begin(); i!=end(); i++) {
00260 if((i->second.*val)() == v) {
00261 return i;
00262 }
00263 }
00264 return end();
00265 }
00266
00282 template<typename S>
00283 const_iterator find(S (NodeType::*val)(void), S v) const {
00284 for(iterator i=begin(); i!=end(); i++) {
00285 if((i->second.*val)() == v) {
00286 return i;
00287 }
00288 }
00289 return end();
00290 }
00291
00306 template<typename ScoreType>
00307 NodeType& leastScore(ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) {
00308 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00309 return random();
00310 }
00311 ScoreType bestScore = ScoreType();
00312 NodeType *best_entry = NULL;
00313 ASSERT(!empty());
00314 bestScore = (begin()->second.*sc)();
00315 best_entry = &(begin()->second);
00316
00317
00318 for(iterator i=begin(); i!=end(); i++) {
00319
00320
00321 if ((i->second.*sc)() < bestScore) {
00322
00323
00324 bestScore = (i->second.*sc)();
00325 best_entry = &(i->second);
00326 }
00327 }
00328
00329
00330 return *best_entry;
00331 }
00332
00348 template<typename ScoreType, typename Compare>
00349 NodeType& leastScore(const Compare& c, ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) {
00350 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00351 return random();
00352 }
00353 ScoreType bestScore = ScoreType();
00354 NodeType *best_entry = NULL;
00355 ASSERT(!empty());
00356 bestScore = (begin()->second.*sc)();
00357 best_entry = &(begin()->second);
00358
00359
00360 for(iterator i=begin(); i!=end(); i++) {
00361
00362
00363 if (c((i->second.*sc)(),bestScore)) {
00364
00365
00366 bestScore = (i->second.*sc)();
00367 best_entry = &(i->second);
00368 }
00369 }
00370
00371
00372 return *best_entry;
00373 }
00374
00389 template<typename ScoreType>
00390 const NodeType& leastScore(ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) const {
00391 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00392 return random();
00393 }
00394 ScoreType bestScore = ScoreType();
00395 const NodeType *best_entry = NULL;
00396 ASSERT(!empty());
00397 bestScore = (begin()->second.*sc)();
00398 best_entry = &(begin()->second);
00399
00400
00401 for(const_iterator i=begin(); i!=end(); i++) {
00402
00403
00404 if ((i->second.*sc)() < bestScore) {
00405
00406
00407 bestScore = (i->second.*sc)();
00408 best_entry = &(i->second);
00409 }
00410 }
00411
00412
00413 return *best_entry;
00414 }
00415
00431 template<typename ScoreType, typename Compare>
00432 const NodeType& leastScore(const Compare& c, ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) const {
00433 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00434 return random();
00435 }
00436 ScoreType bestScore = ScoreType();
00437 const NodeType *best_entry = NULL;
00438 ASSERT(!empty());
00439 bestScore = (begin()->second.*sc)();
00440 best_entry = &(begin()->second);
00441
00442
00443 for(const_iterator i=begin(); i!=end(); i++) {
00444
00445
00446 if (c((i->second.*sc)(), bestScore)) {
00447
00448
00449 bestScore = (i->second.*sc)();
00450 best_entry = &(i->second);
00451 }
00452 }
00453
00454
00455 return *best_entry;
00456 }
00457
00472 template<typename ScoreType>
00473 NodeType& greatestScore(ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) {
00474 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00475 return random();
00476 }
00477 ScoreType worstScore = ScoreType();
00478 NodeType *worst_entry = NULL;
00479
00480 ASSERT(!empty());
00481 worstScore = (begin()->second.*sc)();
00482 worst_entry = &(begin()->second);
00483
00484 for(iterator i=begin(); i!=end(); i++) {
00485 if ((i->second.*sc)() > worstScore)
00486 {
00487 worstScore = (i->second.*sc)();
00488 worst_entry = &(i->second);
00489 }
00490 }
00491 return *worst_entry;
00492 }
00493
00509 template<typename ScoreType, typename Compare>
00510 NodeType& greatestScore(const Compare& c, ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) {
00511 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00512 return random();
00513 }
00514 ScoreType worstScore = ScoreType();
00515 NodeType *worst_entry = NULL;
00516
00517 ASSERT(!empty());
00518 worstScore = (begin()->second.*sc)();
00519 worst_entry = &(begin()->second);
00520
00521 for(iterator i=begin(); i!=end(); i++) {
00522 if (c(worstScore, (i->second.*sc)()))
00523 {
00524 worstScore = (i->second.*sc)();
00525 worst_entry = &(i->second);
00526 }
00527 }
00528 return *worst_entry;
00529 }
00530
00545 template<typename ScoreType>
00546 const NodeType& greatestScore(ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) const {
00547 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00548 return random();
00549 }
00550 ScoreType worstScore = ScoreType();
00551 const NodeType *worst_entry = NULL;
00552
00553 ASSERT(!empty());
00554 worstScore = (begin()->second.*sc)();
00555 worst_entry = &(begin()->second);
00556
00557 for(const_iterator i=begin(); i!=end(); i++) {
00558 if ((i->second.*sc)() > worstScore)
00559 {
00560 worstScore = (i->second.*sc)();
00561 worst_entry = &(i->second);
00562 }
00563 }
00564 return *worst_entry;
00565 }
00566
00582 template<typename ScoreType, typename Compare>
00583 const NodeType& greatestScore(const Compare& c, ScoreType (NodeType::*sc)(void) const = &NodeType::getScore) const {
00584 if(!mace::KeyTraits<ScoreType>::isDeterministic()) {
00585 return random();
00586 }
00587 ScoreType worstScore = ScoreType();
00588 const NodeType *worst_entry = NULL;
00589
00590 ASSERT(!empty());
00591 worstScore = (begin()->second.*sc)();
00592 worst_entry = &(begin()->second);
00593
00594 for(const_iterator i=begin(); i!=end(); i++) {
00595 if (c(worstScore, (i->second.*sc)()))
00596 {
00597 worstScore = (i->second.*sc)();
00598 worst_entry = &(i->second);
00599 }
00600 }
00601 return *worst_entry;
00602 }
00603
00606 NodeType& random() {
00607 ASSERT(!empty());
00608 size_type i = RandomUtil::randInt(size());
00609 ASSERT(i < size());
00610 iterator j;
00611 for(j=begin(); j!=end() && i > 0; j++, i--);
00612 if(j != end()) {
00613 return j->second;
00614 } else {
00615 ASSERT(false);
00616 }
00617 }
00618
00621 const NodeType& random() const {
00622 ASSERT(!empty());
00623 size_type i = RandomUtil::randInt(size());
00624 ASSERT(i < size());
00625 const_iterator j;
00626 for(j=begin(); j!=end() && i > 0; j++, i--);
00627 if(j != end()) {
00628 return j->second;
00629 } else {
00630 ASSERT(false);
00631 }
00632 }
00633
00635 const NodeSet& nodeSet() const {
00636 return myNodeSet;
00637 }
00638
00640 bool space() const {
00641 return size() < MaxSize;
00642 }
00643
00645 bool full() const {
00646 return size() >= MaxSize;
00647 }
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662
00663
00664
00666 map_iterator mapIterator(const MaceKey* b = NULL, const MaceKey* e = NULL) {
00667 return map_iterator(*this, (b==NULL?begin():mapType::find(*b)), (e==NULL?end():mapType::find(*e)));
00668 }
00670 const_map_iterator mapIterator(const MaceKey* b = NULL, const MaceKey* e = NULL) const {
00671 return const_map_iterator(*this, (b==NULL?begin():mapType::find(*b)), (e==NULL?end():mapType::find(*e)));
00672 }
00673
00674
00675
00676
00677
00678 void serialize(std::string& str) const {
00679 uint32_t s = size();
00680 mace::serialize(str, &s);
00681 for(const_iterator i=mapType::begin(); i!=mapType::end(); i++) {
00682 mace::serialize(str, &(i->second));
00683 }
00684 }
00685
00686 int deserialize(std::istream& in) throw(SerializationException) {
00687 clear();
00688 int position = 0;
00689 int ret = 0;
00690
00691 uint32_t s;
00692
00693 ret = mace::deserialize(in, &s);
00694 if (ret < 0) { return -1; }
00695 else { position += ret; }
00696 ASSERT(s <= MaxSize);
00697
00698 MaceKey m;
00699
00700 for(size_t i=0; i<s; i++) {
00701
00702
00703 int pos = in.tellg();
00704 ret = mace::deserialize(in, &m);
00705 if (ret < 0) { return -1; }
00706 in.seekg(pos, std::ios::beg);
00707 NodeType& t = add(m);
00708 ret = mace::deserialize(in, &t);
00709 if (ret < 0) { return -1; }
00710 }
00711 return position;
00712 }
00713
00714 void serializeXML_RPC(std::string& str) const throw(SerializationException) {
00715 XmlRpcMapSerialize<const_iterator, MaceKey>(str, begin(), end());
00716 }
00717
00718 int deserializeXML_RPC(std::istream& in) throw(SerializationException) {
00719 return XmlRpcMapDeserialize<NodeCollection<NodeType, MaxSize>, MaceKey, NodeType>(in, *this);
00720 }
00721
00723 const std::string& getTypeName() const {
00724 const char* types[] = { "NodeType", "unsigned int MaxSize", 0 };
00725 static const StrUtilNamespace::StdStringList myTypes = StrUtilNamespace::getTypeFromTemplate(__PRETTY_FUNCTION__, types);
00726 return myTypes[0];
00727 }
00728
00729 void print(std::ostream& out) const {
00730 if(mace::PRINT_TYPE_NAMES) {
00731 out << "NodeCollection<" << this->getTypeName() << "," << MaxSize << "> [";
00732 out << " cursize=" << size() << "]";
00733 }
00734 printList(out, setBegin(), setEnd());
00735 }
00736
00737 void printState(std::ostream& out) const {
00738 if(mace::PRINT_TYPE_NAMES) {
00739 out << "NodeCollection<" << this->getTypeName() << "," << MaxSize << "> [";
00740 out << " cursize=" << size() << "]";
00741 }
00742 printListState(out, setBegin(), setEnd());
00743 }
00744
00745 class set_iterator {
00746 private:
00747 iterator iter;
00748 friend class const_set_iterator;
00749 public:
00750
00751 set_iterator(iterator i) : iter(i) { }
00752 set_iterator(const set_iterator& i) : iter(i.iter) { }
00753 NodeType& operator*() { return iter->second; }
00754 set_iterator& operator++() { iter++; return *this; }
00755 void operator++(int) { iter++; }
00756 bool operator==(const set_iterator& right) { return iter == right.iter; }
00757 bool operator!=(const set_iterator& right) { return iter != right.iter; }
00758 };
00759
00760 class const_set_iterator {
00761 private:
00762 const_iterator iter;
00763
00764 public:
00765 const_set_iterator(const_iterator i) : iter(i) { }
00766 const_set_iterator(const const_set_iterator& i) : iter(i.iter) { }
00767 const_set_iterator(const set_iterator& i) : iter(i.iter) { }
00768 const NodeType& operator*() { return iter->second; }
00769 const_set_iterator& operator++() { iter++; return *this; }
00770 void operator++(int) { iter++; }
00771 bool operator==(const const_set_iterator& right) { return iter == right.iter; }
00772 bool operator!=(const const_set_iterator& right) { return iter != right.iter; }
00773 };
00774
00776 set_iterator setBegin() {
00777 return set_iterator(begin());
00778 }
00780 const_set_iterator setBegin() const {
00781 return const_set_iterator(begin());
00782 }
00784 set_iterator setEnd() {
00785 return set_iterator(end());
00786 }
00788 const_set_iterator setEnd() const {
00789 return const_set_iterator(end());
00790 }
00792 set_iterator setFind(const MaceKey& item) {
00793 return set_iterator(this->find(item));
00794 }
00796 const_set_iterator setFind(const MaceKey& item) const {
00797 return set_iterator(this->find(item));
00798 }
00799 };
00800
00803 }
00804
00805 #endif // _NEIGHBOR_SET_H