Go to the documentation of this file.00001 #ifndef MEGATREE_CACHE_H
00002 #define MEGATREE_CACHE_H
00003
00004 #include <boost/shared_ptr.hpp>
00005 #include <list>
00006 #include <tr1/unordered_map>
00007 #include <megatree/list.h>
00008
00009 namespace megatree
00010 {
00011
00012 template <class K, class T>
00013 class CacheIterator;
00014
00015
00016 template <class K, class T>
00017 class Cache
00018 {
00019 public:
00020
00021
00022 friend class CacheIterator<K, T>;
00023
00024 class Storage
00025 {
00026 public:
00027 Storage(const K& _id, T* _object):
00028 id(_id), object(_object)
00029 {}
00030
00031 K id;
00032 T* object;
00033 };
00034
00035 typedef List<Storage > ObjList;
00036 typedef ListIterator<Storage> ObjListIterator;
00037 typedef std::tr1::unordered_map<K, ObjListIterator> ObjMap;
00038 typedef typename ObjMap::iterator ObjMapIterator;
00039
00040 typedef CacheIterator<K, T> iterator;
00041
00042
00043 bool exists(const K& id)
00044 {
00045 ObjMapIterator hash_it = hash_.find(id);
00046 if (hash_it != hash_.end())
00047 {
00048 return true;
00049 }
00050 return false;
00051 }
00052
00053 iterator iterate()
00054 {
00055 return CacheIterator<K, T>(this, list_.frontIterator());
00056 }
00057 iterator iterateBack()
00058 {
00059 return CacheIterator<K, T>(this, list_.backIterator());
00060 }
00061
00062 void move_back_to_front()
00063 {
00064 list_.moveToFront(list_.getBackPointer());
00065 }
00066
00067
00068 void move_to_front(const K& id)
00069 {
00070
00071 ObjMapIterator hash_it = hash_.find(id);
00072 if (hash_it != hash_.end())
00073 list_.moveToFront(hash_it->second.getNode());
00074 }
00075
00076 void move_to_front(iterator &it)
00077 {
00078 list_.moveToFront(it.getNode());
00079 }
00080
00081
00082 void move_to_back(const K& id)
00083 {
00084
00085 ObjMapIterator hash_it = hash_.find(id);
00086 if (hash_it != hash_.end())
00087 list_.moveToBack(hash_it->second.getNode());
00088 }
00089
00090
00091 iterator find(const K& id)
00092 {
00093 ObjMapIterator hash_it = hash_.find(id);
00094 if (hash_it != hash_.end())
00095 {
00096 return CacheIterator<K, T>(this, hash_it->second);
00097 }
00098 return CacheIterator<K, T>();
00099 }
00100
00101 void erase(iterator &it)
00102 {
00103 hash_.erase(it.id());
00104 list_.erase(it.getNode());
00105 }
00106
00107 #if 0
00108 bool deprecated_find(const K& id, T* & object, bool move_to_front=false)
00109 {
00110
00111 ObjMapIterator hash_it = hash_.find(id);
00112 if (hash_it != hash_.end())
00113 {
00114 if (move_to_front)
00115 list_.moveToFront(hash_it->second.getNode());
00116
00117 object = hash_it->second.get().object;
00118
00119 return true;
00120 }
00121 return false;
00122 }
00123 #endif
00124
00125
00126 void clear()
00127 {
00128 list_.clear();
00129 hash_.clear();
00130 }
00131
00132
00133 void push_back(const K& id, T* object)
00134 {
00135 list_.push_back(Storage(id, object));
00136 hash_.insert(typename std::pair<K, ObjListIterator>(id, list_.backIterator()));
00137 }
00138
00139
00140 void push_front(const K& id, T* object)
00141 {
00142 list_.push_front(Storage(id, object));
00143 hash_.insert(typename std::pair<K, ObjListIterator>(id, list_.frontIterator()));
00144 }
00145
00146 void pop_back()
00147 {
00148 hash_.erase(list_.back().id);
00149 list_.pop_back();
00150 }
00151
00152 size_t size() const
00153 {
00154 return hash_.size();
00155 }
00156
00157 T* front()
00158 {
00159 return list_.front().object;
00160 }
00161
00162 T* back()
00163 {
00164 return list_.back().object;
00165 }
00166
00167
00168 ObjList list_;
00169 ObjMap hash_;
00170
00171
00172 private:
00173 };
00174
00175
00176
00177
00178 template <class K, class T>
00179 class CacheIterator
00180 {
00181 public:
00182
00183
00184 CacheIterator() : b(NULL) {}
00185 CacheIterator(Cache<K, T>* _b):
00186 b(_b),
00187 it(b.list_.frontIterator()){};
00188
00189 CacheIterator(Cache<K, T>* _b, typename Cache<K, T>::ObjListIterator _it):
00190 b(_b),
00191 it(_it){};
00192
00193 CacheIterator(const CacheIterator<K, T> & ci):
00194 b(ci.b),
00195 it(ci.it){};
00196
00197 void operator =(const CacheIterator<K, T> & ci)
00198 {
00199 b = ci.b;
00200 it = ci.it;
00201 }
00202
00203 void next()
00204 {
00205 it.next();
00206 }
00207 void previous()
00208 {
00209 it.previous();
00210 }
00211
00212 T* get()
00213 {
00214 return it.get().object;
00215 }
00216
00217 ListNode<typename Cache<K, T>::Storage>* getNode()
00218 {
00219 return it.getNode();
00220 }
00221
00222 K id()
00223 {
00224 return it.get().id;
00225 }
00226
00227 bool finished()
00228 {
00229 return b == NULL || it.finished();
00230 }
00231
00232 bool operator==(const CacheIterator<K, T> &o) const
00233 {
00234 return b == o.b && it == o.it;
00235 }
00236
00237 private:
00238 Cache<K, T>* b;
00239 typename Cache<K, T>::ObjListIterator it;
00240 };
00241
00242
00243 }
00244
00245 #endif