1 #ifndef __LOUT_CONTAINER_HH_ 2 #define __LOUT_CONTAINER_HH_ 3 4 #include "object.hh" 5 6 namespace lout { 7 8 /** 9 * \brief This namespace contains a framework for container classes, which 10 * members are instances of object::Object. 11 * 12 * A common problem in languages without garbage collection is, where the 13 * children belong to, and so, who is responsible to delete them (instantiation 14 * is always done by the caller). This information is here told to the 15 * collections, each container has a constructor with the parameter 16 * "ownerOfObjects" (HashTable has two such parameters, for keys and values). 17 * 18 * \sa container::untyped, container::typed 19 */ 20 namespace container { 21 22 /** 23 * \brief The container classes defined here contain instances of 24 * object::Object. 25 * 26 * Different sub-classes may be mixed, and you have to care about casting, 27 * there is no type-safety. 28 */ 29 namespace untyped { 30 31 /** 32 * \brief ... 33 */ 34 class Collection0: public object::Object 35 { 36 friend class Iterator; 37 38 protected: 39 /** 40 * \brief The base class for all iterators, as created by 41 * container::untyped::Collection::createIterator. 42 */ 43 class AbstractIterator: public object::Object 44 { 45 private: 46 int refcount; 47 48 public: AbstractIterator()49 AbstractIterator() { refcount = 1; } 50 ref()51 void ref () { refcount++; } unref()52 void unref () { refcount--; if (refcount == 0) delete this; } 53 54 virtual bool hasNext () = 0; 55 virtual Object *getNext () = 0; 56 }; 57 58 protected: 59 virtual AbstractIterator* createIterator() = 0; 60 }; 61 62 /** 63 * \brief This is a small wrapper for AbstractIterator, which may be used 64 * directly, not as a pointer, to makes memory management simpler. 65 */ 66 class Iterator 67 { 68 friend class Collection; 69 70 private: 71 Collection0::AbstractIterator *impl; 72 73 // Should not instantiated directly. Iterator(Collection0::AbstractIterator * impl)74 inline Iterator(Collection0::AbstractIterator *impl) { this->impl = impl; } 75 76 public: 77 Iterator(); 78 Iterator(const Iterator &it2); 79 Iterator(Iterator &it2); 80 ~Iterator(); 81 Iterator &operator=(const Iterator &it2); 82 Iterator &operator=(Iterator &it2); 83 hasNext()84 inline bool hasNext() { return impl->hasNext(); } getNext()85 inline object::Object *getNext() { return impl->getNext(); } 86 }; 87 88 /** 89 * \brief Abstract base class for all container objects in container::untyped. 90 */ 91 class Collection: public Collection0 92 { 93 public: 94 void intoStringBuffer(misc::StringBuffer *sb); iterator()95 inline Iterator iterator() { Iterator it(createIterator()); return it; } 96 }; 97 98 99 /** 100 * \brief Container, which is implemented by an array, which is 101 * dynamically resized. 102 */ 103 class Vector: public Collection 104 { 105 friend class VectorIterator; 106 107 private: 108 object::Object **array; 109 int numAlloc, numElements; 110 bool ownerOfObjects; 111 112 class VectorIterator: public AbstractIterator 113 { 114 private: 115 Vector *vector; 116 int index; 117 118 public: VectorIterator(Vector * vector)119 VectorIterator(Vector *vector) { this->vector = vector; index = -1; } 120 bool hasNext(); 121 Object *getNext(); 122 }; 123 124 protected: 125 AbstractIterator* createIterator(); 126 127 public: 128 Vector(int initSize, bool ownerOfObjects); 129 ~Vector(); 130 131 void put(object::Object *newElement, int newPos = -1); 132 void insert(object::Object *newElement, int pos); 133 134 /** 135 * \brief Insert into an already sorted vector. 136 * 137 * Notice that insertion is not very efficient, unless the position 138 * is rather at the end. 139 */ insertSorted(object::Object * newElement)140 inline void insertSorted(object::Object *newElement) 141 { insert (newElement, bsearch (newElement, false)); } 142 143 void remove(int pos); get(int pos) const144 inline object::Object *get(int pos) const 145 { return (pos >= 0 && pos < numElements) ? array[pos] : NULL; } size()146 inline int size() { return numElements; } 147 void clear(); 148 void sort(); 149 int bsearch(Object *key, bool mustExist); 150 }; 151 152 153 /** 154 * \brief A single-linked list. 155 */ 156 class List: public Collection 157 { 158 friend class ListIterator; 159 160 private: 161 struct Node 162 { 163 public: 164 object::Object *object; 165 Node *next; 166 }; 167 168 class ListIterator: public AbstractIterator 169 { 170 private: 171 List::Node *current; 172 public: ListIterator(List::Node * node)173 ListIterator(List::Node *node) { current = node; } 174 bool hasNext(); 175 Object *getNext(); 176 }; 177 178 Node *first, *last; 179 bool ownerOfObjects; 180 int numElements; 181 182 bool remove0(object::Object *element, bool compare, bool doNotDeleteAtAll); 183 184 protected: 185 AbstractIterator* createIterator(); 186 187 public: 188 List(bool ownerOfObjects); 189 ~List(); 190 191 void clear(); 192 void append(object::Object *element); removeRef(object::Object * element)193 inline bool removeRef(object::Object *element) 194 { return remove0(element, false, false); } remove(object::Object * element)195 inline bool remove(object::Object *element) 196 { return remove0(element, true, false); } detachRef(object::Object * element)197 inline bool detachRef(object::Object *element) 198 { return remove0(element, false, true); } size() const199 inline int size() const { return numElements; } isEmpty() const200 inline bool isEmpty() const { return numElements == 0; } getFirst() const201 inline object::Object *getFirst() const { return first->object; } getLast() const202 inline object::Object *getLast() const { return last->object; } 203 }; 204 205 206 /** 207 * \brief A hash set. 208 */ 209 class HashSet: public Collection 210 { 211 friend class HashSetIterator; 212 213 protected: 214 struct Node 215 { 216 object::Object *object; 217 Node *next; 218 }; 219 220 Node **table; 221 int tableSize; 222 bool ownerOfObjects; 223 calcHashValue(object::Object * object) const224 inline int calcHashValue(object::Object *object) const 225 { 226 return abs(object->hashValue()) % tableSize; 227 } 228 229 virtual Node *createNode(); 230 virtual void clearNode(Node *node); 231 232 Node *findNode(object::Object *object) const; 233 Node *insertNode(object::Object *object); 234 235 AbstractIterator* createIterator(); 236 237 private: 238 class HashSetIterator: public Collection0::AbstractIterator 239 { 240 private: 241 HashSet *set; 242 HashSet::Node *node; 243 int pos; 244 245 void gotoNext(); 246 247 public: 248 HashSetIterator(HashSet *set); 249 bool hasNext(); 250 Object *getNext(); 251 }; 252 253 public: 254 HashSet(bool ownerOfObjects, int tableSize = 251); 255 ~HashSet(); 256 257 void put (object::Object *object); 258 bool contains (object::Object *key) const; 259 bool remove (object::Object *key); 260 //Object *getReference (object::Object *object); 261 }; 262 263 /** 264 * \brief A hash table. 265 */ 266 class HashTable: public HashSet 267 { 268 private: 269 bool ownerOfValues; 270 271 struct KeyValuePair: public Node 272 { 273 object::Object *value; 274 }; 275 276 protected: 277 Node *createNode(); 278 void clearNode(Node *node); 279 280 public: 281 HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251); 282 ~HashTable(); 283 284 void intoStringBuffer(misc::StringBuffer *sb); 285 286 void put (object::Object *key, object::Object *value); 287 object::Object *get (object::Object *key) const; 288 }; 289 290 /** 291 * \brief A stack (LIFO). 292 * 293 * Note that the iterator returns all elements in the reversed order they have 294 * been put on the stack. 295 */ 296 class Stack: public Collection 297 { 298 friend class StackIterator; 299 300 private: 301 class Node 302 { 303 public: 304 object::Object *object; 305 Node *prev; 306 }; 307 308 class StackIterator: public AbstractIterator 309 { 310 private: 311 Stack::Node *current; 312 public: StackIterator(Stack::Node * node)313 StackIterator(Stack::Node *node) { current = node; } 314 bool hasNext(); 315 Object *getNext(); 316 }; 317 318 Node *bottom, *top; 319 bool ownerOfObjects; 320 int numElements; 321 322 protected: 323 AbstractIterator* createIterator(); 324 325 public: 326 Stack (bool ownerOfObjects); 327 ~Stack(); 328 329 void push (object::Object *object); 330 void pushUnder (object::Object *object); getTop() const331 inline object::Object *getTop () const { return top ? top->object : NULL; } 332 void pop (); size() const333 inline int size() const { return numElements; } 334 }; 335 336 } // namespace untyped 337 338 /** 339 * \brief This namespace provides thin wrappers, implemented as C++ templates, 340 * to gain type-safety. 341 * 342 * Notice, that nevertheless, all objects still have to be instances of 343 * object::Object. 344 */ 345 namespace typed { 346 347 template <class T> class Collection; 348 349 /** 350 * \brief Typed version of container::untyped::Iterator. 351 */ 352 template <class T> class Iterator 353 { 354 friend class Collection<T>; 355 356 private: 357 untyped::Iterator base; 358 359 public: Iterator()360 inline Iterator() { } Iterator(const Iterator<T> & it2)361 inline Iterator(const Iterator<T> &it2) { this->base = it2.base; } Iterator(Iterator<T> & it2)362 inline Iterator(Iterator<T> &it2) { this->base = it2.base; } ~Iterator()363 ~Iterator() { } operator =(const Iterator<T> & it2)364 inline Iterator &operator=(const Iterator<T> &it2) 365 { this->base = it2.base; return *this; } operator =(Iterator<T> & it2)366 inline Iterator &operator=(Iterator<T> &it2) 367 { this->base = it2.base; return *this; } 368 hasNext()369 inline bool hasNext() { return this->base.hasNext(); } getNext()370 inline T *getNext() { return (T*)this->base.getNext(); } 371 }; 372 373 /** 374 * \brief Abstract base class template for all container objects in 375 * container::typed. 376 * 377 * Actually, a wrapper for container::untyped::Collection. 378 */ 379 template <class T> class Collection: public object::Object 380 { 381 protected: 382 untyped::Collection *base; 383 384 public: Collection()385 Collection () { this->base = NULL; } ~Collection()386 ~Collection () { if (this->base) delete this->base; } 387 intoStringBuffer(misc::StringBuffer * sb)388 void intoStringBuffer(misc::StringBuffer *sb) 389 { this->base->intoStringBuffer(sb); } 390 iterator()391 inline Iterator<T> iterator() { 392 Iterator<T> it; it.base = this->base->iterator(); return it; } 393 }; 394 395 396 /** 397 * \brief Typed version of container::untyped::Vector. 398 */ 399 template <class T> class Vector: public Collection <T> 400 { 401 public: Vector(int initSize,bool ownerOfObjects)402 inline Vector(int initSize, bool ownerOfObjects) { 403 this->base = new untyped::Vector(initSize, ownerOfObjects); } 404 put(T * newElement,int newPos=-1)405 inline void put(T *newElement, int newPos = -1) 406 { ((untyped::Vector*)this->base)->put(newElement, newPos); } insert(T * newElement,int pos)407 inline void insert(T *newElement, int pos) 408 { ((untyped::Vector*)this->base)->insert(newElement, pos); } insertSorted(T * newElement)409 inline void insertSorted(T *newElement) 410 { ((untyped::Vector*)this->base)->insertSorted(newElement); } remove(int pos)411 inline void remove(int pos) { ((untyped::Vector*)this->base)->remove(pos); } get(int pos) const412 inline T *get(int pos) const 413 { return (T*)((untyped::Vector*)this->base)->get(pos); } size() const414 inline int size() const { return ((untyped::Vector*)this->base)->size(); } clear()415 inline void clear() { ((untyped::Vector*)this->base)->clear(); } sort()416 inline void sort() { ((untyped::Vector*)this->base)->sort(); } bsearch(T * key,bool mustExist)417 inline int bsearch(T *key, bool mustExist) 418 { return ((untyped::Vector*)this->base)->bsearch(key, mustExist); } 419 }; 420 421 422 /** 423 * \brief Typed version of container::untyped::List. 424 */ 425 template <class T> class List: public Collection <T> 426 { 427 public: List(bool ownerOfObjects)428 inline List(bool ownerOfObjects) 429 { this->base = new untyped::List(ownerOfObjects); } 430 clear()431 inline void clear() { ((untyped::List*)this->base)->clear(); } append(T * element)432 inline void append(T *element) 433 { ((untyped::List*)this->base)->append(element); } removeRef(T * element)434 inline bool removeRef(T *element) { 435 return ((untyped::List*)this->base)->removeRef(element); } remove(T * element)436 inline bool remove(T *element) { 437 return ((untyped::List*)this->base)->remove(element); } detachRef(T * element)438 inline bool detachRef(T *element) { 439 return ((untyped::List*)this->base)->detachRef(element); } 440 size() const441 inline int size() const { return ((untyped::List*)this->base)->size(); } isEmpty() const442 inline bool isEmpty() const 443 { return ((untyped::List*)this->base)->isEmpty(); } getFirst() const444 inline T *getFirst() const 445 { return (T*)((untyped::List*)this->base)->getFirst(); } getLast() const446 inline T *getLast() const 447 { return (T*)((untyped::List*)this->base)->getLast(); } 448 }; 449 450 /** 451 * \brief Typed version of container::untyped::HashSet. 452 */ 453 template <class T> class HashSet: public Collection <T> 454 { 455 protected: HashSet()456 inline HashSet() { } 457 458 public: HashSet(bool owner,int tableSize=251)459 inline HashSet(bool owner, int tableSize = 251) 460 { this->base = new untyped::HashSet(owner, tableSize); } 461 put(T * object)462 inline void put(T *object) 463 { return ((untyped::HashSet*)this->base)->put(object); } contains(T * object) const464 inline bool contains(T *object) const 465 { return ((untyped::HashSet*)this->base)->contains(object); } remove(T * object)466 inline bool remove(T *object) 467 { return ((untyped::HashSet*)this->base)->remove(object); } 468 //inline T *getReference(T *object) 469 //{ return (T*)((untyped::HashSet*)this->base)->getReference(object); } 470 }; 471 472 /** 473 * \brief Typed version of container::untyped::HashTable. 474 */ 475 template <class K, class V> class HashTable: public HashSet <K> 476 { 477 public: HashTable(bool ownerOfKeys,bool ownerOfValues,int tableSize=251)478 inline HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251) 479 { this->base = new untyped::HashTable(ownerOfKeys, ownerOfValues, 480 tableSize); } 481 put(K * key,V * value)482 inline void put(K *key, V *value) 483 { return ((untyped::HashTable*)this->base)->put(key, value); } get(K * key) const484 inline V *get(K *key) const 485 { return (V*)((untyped::HashTable*)this->base)->get(key); } 486 }; 487 488 /** 489 * \brief Typed version of container::untyped::Stack. 490 */ 491 template <class T> class Stack: public Collection <T> 492 { 493 public: Stack(bool ownerOfObjects)494 inline Stack (bool ownerOfObjects) 495 { this->base = new untyped::Stack (ownerOfObjects); } 496 push(T * object)497 inline void push (T *object) { 498 ((untyped::Stack*)this->base)->push (object); } pushUnder(T * object)499 inline void pushUnder (T *object) 500 { ((untyped::Stack*)this->base)->pushUnder (object); } getTop() const501 inline T *getTop () const 502 { return (T*)((untyped::Stack*)this->base)->getTop (); } pop()503 inline void pop () { ((untyped::Stack*)this->base)->pop (); } size() const504 inline int size() const { return ((untyped::Stack*)this->base)->size(); } 505 }; 506 507 } // namespace untyped 508 509 } // namespace container 510 511 } // namespace lout 512 513 #endif // __LOUT_CONTAINER_HH_ 514