1 /* ScummVM - Graphic Adventure Engine 2 * 3 * ScummVM is the legal property of its developers, whose names 4 * are too numerous to list here. Please refer to the COPYRIGHT 5 * file distributed with this source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 #ifndef ULTIMA_STD_CONTAINERS_H 24 #define ULTIMA_STD_CONTAINERS_H 25 26 #include "common/algorithm.h" 27 #include "common/array.h" 28 #include "common/hashmap.h" 29 #include "common/hash-str.h" 30 #include "common/list.h" 31 #include "common/queue.h" 32 #include "common/stack.h" 33 34 namespace Ultima { 35 namespace Std { 36 37 template<class T1, class T2> 38 struct pair { 39 T1 first; 40 T2 second; 41 pairpair42 pair() { 43 } pairpair44 pair(T1 first_, T2 second_) : first(first_), second(second_) { 45 } 46 }; 47 48 template<class T> 49 class vector : public Common::Array<T> { 50 public: 51 struct reverse_iterator { 52 private: 53 vector<T> *_owner; 54 int _index; 55 public: reverse_iteratorreverse_iterator56 reverse_iterator(vector<T> *owner, int index) : _owner(owner), _index(index) {} reverse_iteratorreverse_iterator57 reverse_iterator() : _owner(0), _index(-1) {} 58 59 T &operator*() { return (*_owner)[_index]; } 60 61 reverse_iterator &operator++() { 62 --_index; 63 return *this; 64 } 65 66 bool operator==(const reverse_iterator &rhs) { 67 return _owner == rhs._owner && _index == rhs._index; 68 } 69 bool operator!=(const reverse_iterator &rhs) { 70 return !operator==(rhs); 71 } 72 }; 73 74 struct const_reverse_iterator { 75 private: 76 const vector<T> *_owner; 77 int _index; 78 public: const_reverse_iteratorconst_reverse_iterator79 const_reverse_iterator(const vector<T> *owner, int index) : _owner(owner), _index(index) { 80 } const_reverse_iteratorconst_reverse_iterator81 const_reverse_iterator() : _owner(0), _index(-1) { 82 } 83 84 const T operator*() const { 85 return (*_owner)[_index]; 86 } 87 88 const_reverse_iterator &operator++() { 89 --_index; 90 return *this; 91 } 92 93 bool operator==(const const_reverse_iterator &rhs) { 94 return _owner == rhs._owner && _index == rhs._index; 95 } 96 bool operator!=(const const_reverse_iterator &rhs) { 97 return !operator==(rhs); 98 } 99 }; 100 public: 101 typedef T reference; 102 typedef const T const_reference; 103 vector()104 vector() : Common::Array<T>() {} vector(size_t newSize)105 vector(size_t newSize) : Common::Array<T>() { 106 Common::Array<T>::resize(newSize); 107 } vector(size_t newSize,const T elem)108 vector(size_t newSize, const T elem) { 109 resize(newSize, elem); 110 } 111 erase(typename Common::Array<T>::iterator pos)112 typename Common::Array<T>::iterator erase(typename Common::Array<T>::iterator pos) { 113 return Common::Array<T>::erase(pos); 114 } 115 erase(typename Common::Array<T>::iterator first,typename Common::Array<T>::iterator last)116 typename Common::Array<T>::iterator erase(typename Common::Array<T>::iterator first, 117 typename Common::Array<T>::iterator last) { 118 Common::copy(last, this->_storage + this->_size, first); 119 120 int count = (last - first); 121 this->_size -= count; 122 123 // We also need to destroy the objects beyond the new size 124 for (uint idx = this->_size; idx < (this->_size + count); ++idx) 125 this->_storage[idx].~T(); 126 127 return first; 128 } 129 swap(vector & arr)130 void swap(vector &arr) { 131 SWAP(this->_capacity, arr._capacity); 132 SWAP(this->_size, arr._size); 133 SWAP(this->_storage, arr._storage); 134 } 135 rbegin()136 reverse_iterator rbegin() { 137 return reverse_iterator(this, (int)Common::Array<T>::size() - 1); 138 } rend()139 reverse_iterator rend() { 140 return reverse_iterator(this, -1); 141 } rbegin()142 const_reverse_iterator rbegin() const { 143 return const_reverse_iterator(this, (int)Common::Array<T>::size() - 1); 144 } rend()145 const_reverse_iterator rend() const { 146 return const_reverse_iterator(this, -1); 147 } 148 pop_front()149 void pop_front() { 150 Common::Array<T>::remove_at(0); 151 } 152 resize(size_t newSize)153 void resize(size_t newSize) { 154 Common::Array<T>::resize(newSize); 155 } resize(size_t newSize,const T elem)156 void resize(size_t newSize, const T elem) { 157 size_t oldSize = Common::Array<T>::size(); 158 resize(newSize); 159 for (size_t idx = oldSize; idx < newSize; ++idx) 160 this->operator[](idx) = elem; 161 } 162 at(size_t index)163 T at(size_t index) const { 164 return (*this)[index]; 165 } 166 }; 167 168 template<class T> 169 class set { 170 struct Comparitor { operatorComparitor171 bool operator()(const T &a, const T &b) const { 172 return a == b; 173 } 174 }; 175 176 class Items : public Common::Array<T> { 177 public: swap(Items & arr)178 void swap(Items &arr) { 179 SWAP(this->_capacity, arr._capacity); 180 SWAP(this->_size, arr._size); 181 SWAP(this->_storage, arr._storage); 182 } 183 }; 184 private: 185 Items _items; 186 Comparitor _comparitor; 187 public: 188 typedef T *iterator; 189 typedef const T *const_iterator; 190 begin()191 iterator begin() { return _items.begin(); } end()192 iterator end() { return _items.end(); } begin()193 const_iterator begin() const { return _items.begin(); } end()194 const_iterator end() const { return _items.end(); } 195 196 /** 197 * Clear the set 198 */ clear()199 void clear() { 200 _items.clear(); 201 } 202 203 /** 204 * Inserts a new item 205 */ insert(T val)206 void insert(T val) { 207 _items.push_back(val); 208 Common::sort(begin(), end(), _comparitor); 209 } 210 211 /** 212 * Inserts a range of items 213 */ insert(iterator first,iterator last)214 void insert(iterator first, iterator last) { 215 for (; first != last; ++first) 216 _items.push_back(*first); 217 Common::sort(begin(), end(), _comparitor); 218 } 219 220 /** 221 * Swaps a set 222 */ swap(set<T> & arr)223 void swap(set<T> &arr) { 224 _items.swap(arr); 225 } 226 227 /** 228 * Find an item 229 */ find(const T item)230 iterator find(const T item) { 231 iterator it = begin(); 232 for (; it != end() && *it != item; ++it) {} 233 return it; 234 } find(const T item)235 const_iterator find(const T item) const { 236 const_iterator it = begin(); 237 for (; it != end() && *it != item; ++it) { 238 } 239 return it; 240 } 241 }; 242 243 struct PointerHash { 244 Common::Hash<const char *> hash; 245 operatorPointerHash246 uint operator()(const void *ptr) const { 247 Common::String str = Common::String::format("%p", ptr); 248 return hash.operator()(str.c_str()); 249 } 250 }; 251 252 template<class Key, class Val, class HashFunc = Common::Hash<Key>, 253 class EqualFunc = Common::EqualTo<Key> > 254 class map : public Common::HashMap<Key, Val, HashFunc, EqualFunc> { 255 public: insert(Std::pair<Key,Val> elem)256 void insert(Std::pair<Key, Val> elem) { 257 this->operator[](elem.first) = elem.second; 258 } 259 }; 260 261 template<class VAL> 262 class deque : public Common::List<VAL> { 263 public: 264 VAL operator[](uint index) { 265 for (typename Common::List<VAL>::iterator it = this->begin(); 266 it != this->end(); ++it, --index) { 267 if (index == 0) 268 return *it; 269 } 270 271 error("Invalid index"); 272 } 273 }; 274 275 template<class T> 276 class list : public Common::List<T> { 277 public: 278 struct reverse_iterator { 279 private: 280 typename Common::List<T>::iterator _it; 281 public: reverse_iteratorreverse_iterator282 reverse_iterator(typename Common::List<T>::iterator it) : _it(it) {} reverse_iteratorreverse_iterator283 reverse_iterator() {} 284 285 T operator*() const { return *_it; } 286 287 reverse_iterator &operator++() { 288 --_it; 289 return *this; 290 } 291 292 bool operator==(const reverse_iterator &rhs) { return _it == rhs._it; } 293 bool operator!=(const reverse_iterator &rhs) { return _it != rhs._it; } 294 }; 295 public: insert(typename Common::List<T>::iterator pos,const T & element)296 typename Common::List<T>::iterator insert(typename Common::List<T>::iterator pos, 297 const T &element) { 298 Common::List<T>::insert(pos, element); 299 return pos; 300 } 301 rbegin()302 reverse_iterator rbegin() { 303 return reverse_iterator(Common::List<T>::reverse_begin()); 304 } rend()305 reverse_iterator rend() { 306 return reverse_iterator(Common::List<T>::end()); 307 } 308 }; 309 310 template<class VAL> 311 class stack : public Common::Stack<VAL> { 312 }; 313 314 /** 315 * Queue ordered by a provided priority function 316 * NOTE: Unlike in the C std library, we have to provde a comparitor that sorts 317 * the array so that the smallest priority comes last 318 */ 319 template <class _Ty, class _Container, class _Pr> 320 class priority_queue { 321 public: priority_queue()322 priority_queue() : c(), comp() {} 323 priority_queue(const _Pr & _Pred)324 explicit priority_queue(const _Pr &_Pred) : c(), comp(_Pred) {} 325 priority_queue(const _Pr & _Pred,const _Container & _Cont)326 priority_queue(const _Pr &_Pred, const _Container &_Cont) : c(_Cont), comp(_Pred) { 327 make_heap(c.begin(), c.end(), comp); 328 } 329 330 template <class _InIt> priority_queue(_InIt _First,_InIt _Last,const _Pr & _Pred,const _Container & _Cont)331 priority_queue(_InIt _First, _InIt _Last, const _Pr &_Pred, const _Container &_Cont) : c(_Cont), comp(_Pred) { 332 c.insert(c.end(), _First, _Last); 333 make_heap(c.begin(), c.end(), comp); 334 } 335 336 template <class _InIt> priority_queue(_InIt _First,_InIt _Last)337 priority_queue(_InIt _First, _InIt _Last) : c(_First, _Last), comp() { 338 make_heap(c.begin(), c.end(), comp); 339 } 340 341 template <class _InIt> priority_queue(_InIt _First,_InIt _Last,const _Pr & _Pred)342 priority_queue(_InIt _First, _InIt _Last, const _Pr &_Pred) : c(_First, _Last), comp(_Pred) { 343 make_heap(c.begin(), c.end(), comp); 344 } 345 empty()346 bool empty() const { 347 return c.empty(); 348 } 349 size()350 size_t size() const { 351 return c.size(); 352 } 353 top()354 typename _Container::const_reference top() const { 355 return c.back(); 356 } 357 push(const typename _Container::value_type & _Val)358 void push(const typename _Container::value_type &_Val) { 359 c.push_back(_Val); 360 Common::sort(c.begin(), c.end(), comp); 361 } 362 pop()363 void pop() { 364 c.pop_back(); 365 } 366 swap(priority_queue & _Right)367 void swap(priority_queue &_Right) { 368 SWAP(c, _Right.c); 369 SWAP(comp, _Right.comp); 370 } 371 372 protected: 373 _Container c; 374 _Pr comp; 375 }; 376 377 } // End of namespace Std 378 } // End of namespace Ultima 379 380 #endif 381