Dillo v3.1.1-14-g8f67d6e0
Loading...
Searching...
No Matches
container.hh
Go to the documentation of this file.
1/*
2 * Dillo Widget
3 *
4 * Copyright 2005-2007 Sebastian Geerken <sgeerken@dillo.org>
5 * Copyright 2024 Rodrigo Arias Mallo <rodarima@gmail.com>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 3 of the License, or
10 * (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, see <http://www.gnu.org/licenses/>.
19 */
20
21#ifndef __LOUT_CONTAINER_HH_
22#define __LOUT_CONTAINER_HH_
23
24#include "object.hh"
25
26namespace lout {
27
40namespace container {
41
49namespace untyped {
50
55{
56 friend class Iterator;
57
58protected:
64 {
65 private:
67
68 public:
70
71 void ref () { refcount++; }
72 void unref () { refcount--; if (refcount == 0) delete this; }
73
74 virtual bool hasNext () = 0;
75 virtual Object *getNext () = 0;
76 };
77
78protected:
80};
81
87{
88 friend class Collection;
89
90private:
92
93 // Should not instantiated directly.
95
96public:
97 Iterator();
98 Iterator(const Iterator &it2);
99 Iterator(Iterator &it2);
100 ~Iterator();
101 Iterator &operator=(const Iterator &it2);
103
104 inline bool hasNext() { return impl->hasNext(); }
105 inline object::Object *getNext() { return impl->getNext(); }
106};
107
112{
113public:
115 inline Iterator iterator() { Iterator it(createIterator()); return it; }
116 virtual int size() = 0;
117};
118
119
124class Vector: public Collection
125{
126 friend class VectorIterator;
127
128private:
132
134 {
135 private:
137 int index;
138
139 public:
140 VectorIterator(Vector *vector) { this->vector = vector; index = -1; }
141 bool hasNext();
142 Object *getNext();
143 };
144
145protected:
146 AbstractIterator* createIterator();
147
148public:
149 Vector(int initSize, bool ownerOfObjects);
150 ~Vector();
151
152 int size();
153
154 void put(object::Object *newElement, int newPos = -1);
155 void insert(object::Object *newElement, int pos);
156
163 inline int insertSorted(object::Object *newElement,
164 object::Comparator *comparator =
166 { int pos = bsearch (newElement, false, comparator);
167 insert (newElement, pos); return pos; }
168
169 void remove(int pos);
170 inline object::Object *get(int pos) const
171 { return (pos >= 0 && pos < numElements) ? array[pos] : NULL; }
172 void clear();
174 int bsearch(Object *key, bool mustExist, int start, int end,
176 inline int bsearch(Object *key, bool mustExist,
177 object::Comparator *comparator =
179 { return bsearch (key, mustExist, 0, size () - 1, comparator); }
180};
181
182
186class List: public Collection
187{
188 friend class ListIterator;
189
190private:
191 struct Node
192 {
193 public:
196 };
197
199 {
200 private:
202 public:
203 ListIterator(List::Node *node) { current = node; }
204 bool hasNext();
205 Object *getNext();
206 };
207
211
212 bool remove0(object::Object *element, bool compare, bool doNotDeleteAtAll);
213
214protected:
216
217public:
218 List(bool ownerOfObjects);
219 ~List();
220
221 bool equals(Object *other);
222 int hashValue();
223
224 int size ();
225
226 void clear();
227 void append(object::Object *element);
228 bool insertBefore(object::Object *beforeThis, object::Object *neew);
229 inline bool removeRef(object::Object *element)
230 { return remove0(element, false, false); }
231 inline bool remove(object::Object *element)
232 { return remove0(element, true, false); }
233 inline bool detachRef(object::Object *element)
234 { return remove0(element, false, true); }
235 inline int size() const { return numElements; }
236 inline bool isEmpty() const { return numElements == 0; }
237 inline object::Object *getFirst() const { return first->object; }
238 inline object::Object *getLast() const { return last->object; }
239};
240
241
245class HashSet: public Collection
246{
247 friend class HashSetIterator;
248
249protected:
250 struct Node
251 {
254 virtual ~Node() = default;
255 };
256
260
261 inline int calcHashValue(object::Object *object) const
262 {
263 return abs(object->hashValue()) % tableSize;
264 }
265
266 virtual Node *createNode();
267 virtual void clearNode(Node *node);
268
269 Node *findNode(object::Object *object) const;
270 Node *insertNode(object::Object *object);
271
272 AbstractIterator* createIterator();
273
274private:
276 {
277 private:
280 int pos;
281
282 void gotoNext();
283
284 public:
286 bool hasNext();
287 Object *getNext();
288 };
289
290public:
291 HashSet(bool ownerOfObjects, int tableSize = 251);
292 ~HashSet();
293
294 int size ();
295
296 void put (object::Object *object);
297 bool contains (object::Object *key) const;
298 bool remove (object::Object *key);
299 //Object *getReference (object::Object *object);
300};
301
305class HashTable: public HashSet
306{
307private:
309
310 struct KeyValuePair: public Node
311 {
313 };
314
315protected:
316 Node *createNode();
317 void clearNode(Node *node);
318
319public:
320 HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251);
321 ~HashTable();
322
324
325 void put (object::Object *key, object::Object *value);
326 object::Object *get (object::Object *key) const;
327};
328
336class Stack: public Collection
337{
338 friend class StackIterator;
339
340private:
341 class Node
342 {
343 public:
346 };
347
349 {
350 private:
352 public:
354 bool hasNext();
356 };
357
361
362protected:
364
365public:
366 Stack (bool ownerOfObjects);
367 ~Stack();
368
369 int size ();
370
371 void push (object::Object *object);
372 void pushUnder (object::Object *object);
373 inline object::Object *getTop () const { return top ? top->object : NULL; }
374 void pop ();
375 inline int size() const { return numElements; }
376};
377
378} // namespace untyped
379
387namespace typed {
388
389template <class T> class Collection;
390
394template <class T> class Iterator
395{
396 friend class Collection<T>;
397
398private:
400
401public:
402 inline Iterator() { }
403 inline Iterator(const Iterator<T> &it2) { this->base = it2.base; }
404 inline Iterator(Iterator<T> &it2) { this->base = it2.base; }
406 inline Iterator &operator=(const Iterator<T> &it2)
407 { this->base = it2.base; return *this; }
409 { this->base = it2.base; return *this; }
410
411 inline bool hasNext() { return this->base.hasNext(); }
412 inline T *getNext() { return (T*)this->base.getNext(); }
413};
414
421template <class T> class Collection: public object::Object
422{
423protected:
425
426public:
427 Collection () { this->base = NULL; }
428 ~Collection () { if (this->base) delete this->base; }
429
430 bool equals(Object *other)
431 { return this->base->equals (((Collection<T>*)other)->base); }
432
433 int hashValue() { return this->base->hashValue (); }
434
436 { this->base->intoStringBuffer(sb); }
438 Iterator<T> it; it.base = this->base->iterator(); return it; }
439 inline int size() { return this->base->size (); }
440};
441
442
446template <class T> class Vector: public Collection <T>
447{
448public:
449 inline Vector(int initSize, bool ownerOfObjects) {
450 this->base = new untyped::Vector(initSize, ownerOfObjects); }
451
452 inline void put(T *newElement, int newPos = -1)
453 { ((untyped::Vector*)this->base)->put(newElement, newPos); }
454 inline void insert(T *newElement, int pos)
455 { ((untyped::Vector*)this->base)->insert(newElement, pos); }
456 inline int insertSorted(T *newElement,
457 object::Comparator *comparator =
459 { return ((untyped::Vector*)this->base)->insertSorted(newElement,
460 comparator); }
461 inline void remove(int pos) { ((untyped::Vector*)this->base)->remove(pos); }
462 inline T *get(int pos) const
463 { return (T*)((untyped::Vector*)this->base)->get(pos); }
464 inline void clear() { ((untyped::Vector*)this->base)->clear(); }
465 inline void sort(object::Comparator *comparator =
467 { ((untyped::Vector*)this->base)->sort(comparator); }
468 inline int bsearch(T *key, bool mustExist, int start, int end,
469 object::Comparator *comparator =
471 { return ((untyped::Vector*)this->base)->bsearch(key, mustExist, start, end,
472 comparator); }
473 inline int bsearch(T *key, bool mustExist,
474 object::Comparator *comparator =
476 { return ((untyped::Vector*)this->base)->bsearch(key, mustExist,
477 comparator); }
478};
479
480
484template <class T> class List: public Collection <T>
485{
486public:
487 inline List(bool ownerOfObjects)
488 { this->base = new untyped::List(ownerOfObjects); }
489
490 inline void clear() { ((untyped::List*)this->base)->clear(); }
491 inline void append(T *element)
492 { ((untyped::List*)this->base)->append(element); }
493 inline bool insertBefore(object::Object *beforeThis, object::Object *neew)
494 { return ((untyped::List*)this->base)->insertBefore(beforeThis, neew); }
495 inline bool removeRef(T *element) {
496 return ((untyped::List*)this->base)->removeRef(element); }
497 inline bool remove(T *element) {
498 return ((untyped::List*)this->base)->remove(element); }
499 inline bool detachRef(T *element) {
500 return ((untyped::List*)this->base)->detachRef(element); }
501
502 inline bool isEmpty() const
503 { return ((untyped::List*)this->base)->isEmpty(); }
504 inline T *getFirst() const
505 { return (T*)((untyped::List*)this->base)->getFirst(); }
506 inline T *getLast() const
507 { return (T*)((untyped::List*)this->base)->getLast(); }
508};
509
513template <class T> class HashSet: public Collection <T>
514{
515protected:
516 inline HashSet() { }
517
518public:
519 inline HashSet(bool owner, int tableSize = 251)
520 { this->base = new untyped::HashSet(owner, tableSize); }
521
522 inline void put(T *object)
523 { return ((untyped::HashSet*)this->base)->put(object); }
524 inline bool contains(T *object) const
525 { return ((untyped::HashSet*)this->base)->contains(object); }
526 inline bool remove(T *object)
527 { return ((untyped::HashSet*)this->base)->remove(object); }
528 //inline T *getReference(T *object)
529 //{ return (T*)((untyped::HashSet*)this->base)->getReference(object); }
530};
531
535template <class K, class V> class HashTable: public HashSet <K>
536{
537public:
538 inline HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize = 251)
539 { this->base = new untyped::HashTable(ownerOfKeys, ownerOfValues,
540 tableSize); }
541
542 inline void put(K *key, V *value)
543 { return ((untyped::HashTable*)this->base)->put(key, value); }
544 inline V *get(K *key) const
545 { return (V*)((untyped::HashTable*)this->base)->get(key); }
546};
547
551template <class T> class Stack: public Collection <T>
552{
553public:
554 inline Stack (bool ownerOfObjects)
555 { this->base = new untyped::Stack (ownerOfObjects); }
556
557 inline void push (T *object) {
558 ((untyped::Stack*)this->base)->push (object); }
559 inline void pushUnder (T *object)
560 { ((untyped::Stack*)this->base)->pushUnder (object); }
561 inline T *getTop () const
562 { return (T*)((untyped::Stack*)this->base)->getTop (); }
563 inline void pop () { ((untyped::Stack*)this->base)->pop (); }
564};
565
566} // namespace untyped
567
568} // namespace container
569
570} // namespace lout
571
572#endif // __LOUT_CONTAINER_HH_
Abstract base class template for all container objects in container::typed.
Definition container.hh:422
bool equals(Object *other)
Returns, whether two objects are equal.
Definition container.hh:430
void intoStringBuffer(misc::StringBuffer *sb)
Store a textual representation of the object in a misc::StringBuffer.
Definition container.hh:435
int hashValue()
Return a hash value for the object.
Definition container.hh:433
Typed version of container::untyped::HashSet.
Definition container.hh:514
bool contains(T *object) const
Definition container.hh:524
HashSet(bool owner, int tableSize=251)
Definition container.hh:519
Typed version of container::untyped::HashTable.
Definition container.hh:536
void put(K *key, V *value)
Definition container.hh:542
HashTable(bool ownerOfKeys, bool ownerOfValues, int tableSize=251)
Definition container.hh:538
Typed version of container::untyped::Iterator.
Definition container.hh:395
Iterator(Iterator< T > &it2)
Definition container.hh:404
Iterator & operator=(const Iterator< T > &it2)
Definition container.hh:406
Iterator & operator=(Iterator< T > &it2)
Definition container.hh:408
Iterator(const Iterator< T > &it2)
Definition container.hh:403
Typed version of container::untyped::List.
Definition container.hh:485
bool removeRef(T *element)
Definition container.hh:495
bool insertBefore(object::Object *beforeThis, object::Object *neew)
Definition container.hh:493
List(bool ownerOfObjects)
Definition container.hh:487
bool detachRef(T *element)
Definition container.hh:499
Typed version of container::untyped::Stack.
Definition container.hh:552
Stack(bool ownerOfObjects)
Definition container.hh:554
Typed version of container::untyped::Vector.
Definition container.hh:447
void put(T *newElement, int newPos=-1)
Definition container.hh:452
int bsearch(T *key, bool mustExist, object::Comparator *comparator=&object::standardComparator)
Definition container.hh:473
Vector(int initSize, bool ownerOfObjects)
Definition container.hh:449
void insert(T *newElement, int pos)
Definition container.hh:454
int bsearch(T *key, bool mustExist, int start, int end, object::Comparator *comparator=&object::standardComparator)
Definition container.hh:468
void sort(object::Comparator *comparator=&object::standardComparator)
Definition container.hh:465
int insertSorted(T *newElement, object::Comparator *comparator=&object::standardComparator)
Definition container.hh:456
The base class for all iterators, as created by container::untyped::Collection::createIterator.
Definition container.hh:64
virtual AbstractIterator * createIterator()=0
Abstract base class for all container objects in container::untyped.
Definition container.hh:112
void intoStringBuffer(misc::StringBuffer *sb)
Store a textual representation of the object in a misc::StringBuffer.
Definition container.cc:88
Node * insertNode(object::Object *object)
Definition container.cc:512
void put(object::Object *object)
Definition container.cc:532
bool remove(object::Object *key)
Definition container.cc:548
bool contains(object::Object *key) const
Definition container.cc:537
virtual void clearNode(Node *node)
Definition container.cc:493
AbstractIterator * createIterator()
Definition container.cc:628
Node * findNode(object::Object *object) const
Definition container.cc:501
int calcHashValue(object::Object *object) const
Definition container.hh:261
object::Object * get(object::Object *key) const
Definition container.cc:708
void intoStringBuffer(misc::StringBuffer *sb)
Store a textual representation of the object in a misc::StringBuffer.
Definition container.cc:676
void put(object::Object *key, object::Object *value)
Definition container.cc:702
This is a small wrapper for AbstractIterator, which may be used directly, not as a pointer,...
Definition container.hh:87
Iterator(Collection0::AbstractIterator *impl)
Definition container.hh:94
Collection0::AbstractIterator * impl
Definition container.hh:91
Iterator & operator=(const Iterator &it2)
Definition container.cc:58
A single-linked list.
Definition container.hh:187
bool remove0(object::Object *element, bool compare, bool doNotDeleteAtAll)
Definition container.cc:388
bool equals(Object *other)
Returns, whether two objects are equal.
Definition container.cc:315
void append(object::Object *element)
Definition container.cc:350
object::Object * getLast() const
Definition container.hh:238
bool removeRef(object::Object *element)
Definition container.hh:229
AbstractIterator * createIterator()
Definition container.cc:436
bool insertBefore(object::Object *beforeThis, object::Object *neew)
Definition container.cc:365
bool remove(object::Object *element)
Definition container.hh:231
object::Object * getFirst() const
Definition container.hh:237
int hashValue()
Return a hash value for the object.
Definition container.cc:328
bool detachRef(object::Object *element)
Definition container.hh:233
void push(object::Object *object)
Definition container.cc:739
void pushUnder(object::Object *object)
Definition container.cc:752
AbstractIterator * createIterator()
Definition container.cc:800
object::Object * getTop() const
Definition container.hh:373
Container, which is implemented by an array, which is dynamically resized.
Definition container.hh:125
void sort(object::Comparator *comparator=&object::standardComparator)
Sort the elements in the vector.
Definition container.cc:207
int insertSorted(object::Object *newElement, object::Comparator *comparator=&object::standardComparator)
Insert into an already sorted vector.
Definition container.hh:163
void put(object::Object *newElement, int newPos=-1)
Definition container.cc:128
int bsearch(Object *key, bool mustExist, int start, int end, object::Comparator *comparator=&object::standardComparator)
Use binary search to find an element in a sorted vector.
Definition container.cc:222
int bsearch(Object *key, bool mustExist, object::Comparator *comparator=&object::standardComparator)
Definition container.hh:176
object::Object * get(int pos) const
Definition container.hh:170
AbstractIterator * createIterator()
Definition container.cc:289
void insert(object::Object *newElement, int pos)
Definition container.cc:170
A class for fast concatenation of a large number of strings.
Definition misc.hh:566
Used for other orders as the one defined by Comparable.
Definition object.hh:67
This is the base class for many other classes, which defines very common virtual methods.
Definition object.hh:25
virtual int hashValue()
Return a hash value for the object.
Definition object.cc:59
virtual bool equals(Object *other)
Returns, whether two objects are equal.
Definition object.cc:50
StandardComparator standardComparator
Definition object.cc:148