PTLib
Version 2.10.4
Main Page
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
lists.h
Go to the documentation of this file.
1
/*
2
* lists.h
3
*
4
* List Container Classes
5
*
6
* Portable Windows Library
7
*
8
* Copyright (c) 1993-1998 Equivalence Pty. Ltd.
9
*
10
* The contents of this file are subject to the Mozilla Public License
11
* Version 1.0 (the "License"); you may not use this file except in
12
* compliance with the License. You may obtain a copy of the License at
13
* http://www.mozilla.org/MPL/
14
*
15
* Software distributed under the License is distributed on an "AS IS"
16
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
17
* the License for the specific language governing rights and limitations
18
* under the License.
19
*
20
* The Original Code is Portable Windows Library.
21
*
22
* The Initial Developer of the Original Code is Equivalence Pty. Ltd.
23
*
24
* Portions are Copyright (C) 1993 Free Software Foundation, Inc.
25
* All Rights Reserved.
26
*
27
* Contributor(s): ______________________________________.
28
*
29
* $Revision: 24177 $
30
* $Author: rjongbloed $
31
* $Date: 2010-04-05 06:52:04 -0500 (Mon, 05 Apr 2010) $
32
*/
33
34
#ifndef PTLIB_LISTS_H
35
#define PTLIB_LISTS_H
36
37
#ifdef P_USE_PRAGMA
38
#pragma interface
39
#endif
40
41
43
// PList container class
44
45
struct
PListElement
46
{
47
PListElement
(
PObject
* theData);
48
PListElement
*
prev
;
49
PListElement
*
next
;
50
PObject
*
data
;
51
52
PDECLARE_POOL_ALLOCATOR
();
53
};
54
55
struct
PListInfo
56
{
57
PListInfo
() {
head
=
tail
= NULL; }
58
PListElement
*
head
;
59
PListElement
*
tail
;
60
61
PDECLARE_POOL_ALLOCATOR
();
62
};
63
84
class
PAbstractList
:
public
PCollection
85
{
86
PCONTAINERINFO(
PAbstractList
,
PCollection
);
87
88
public
:
96
PINLINE
PAbstractList
();
98
99
// Overrides from class PObject
126
virtual
Comparison
Compare
(
127
const
PObject
& obj
128
)
const
;
129
139
virtual
PBoolean
SetSize
(
140
PINDEX newSize
141
);
143
152
virtual
PINDEX
Append
(
153
PObject
* obj
154
);
155
168
virtual
PINDEX
Insert
(
169
const
PObject
& before,
170
PObject
* obj
171
);
172
180
virtual
PINDEX
InsertAt
(
181
PINDEX index,
182
PObject
* obj
183
);
184
191
virtual
PBoolean
Remove
(
192
const
PObject
* obj
193
);
194
204
virtual
PObject
*
RemoveAt
(
205
PINDEX index
206
);
207
219
virtual
PBoolean
SetAt
(
220
PINDEX index,
221
PObject
* val
222
);
223
234
virtual
PBoolean
ReplaceAt
(
235
PINDEX index,
236
PObject
* val
237
);
238
249
virtual
PObject
*
GetAt
(
250
PINDEX index
251
)
const
;
252
260
virtual
PINDEX
GetObjectsIndex
(
261
const
PObject
* obj
262
)
const
;
263
272
virtual
PINDEX
GetValuesIndex
(
273
const
PObject
& obj
274
)
const
;
276
277
278
protected
:
289
PINLINE
PObject
&
GetReferenceAt
(
290
PINDEX index
291
)
const
;
292
302
PBoolean
SetCurrent
(
303
PINDEX index,
304
PListElement
* & lastElement
305
)
const
;
306
307
PObject
*
RemoveElement
(
PListElement
* element);
308
309
// The types below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
310
typedef
PListElement
Element
;
311
PListInfo
*
info
;
312
};
313
314
321
template
<
class
T>
class
PList
:
public
PAbstractList
322
{
323
PCLASSINFO(
PList
,
PAbstractList
);
324
325
public
:
333
PList
()
334
:
PAbstractList
() { }
336
342
virtual
PObject
*
Clone
()
const
343
{
return
PNEW
PList
(0,
this
); }
345
348
class
iterator_base
:
public
std::iterator<std::bidirectional_iterator_tag, T> {
349
protected
:
350
iterator_base
(
PListElement
* e) :
element
(e) { }
351
PListElement
*
element
;
352
353
void
Next
() {
element
=
PAssertNULL
(
element
)->next; }
354
void
Prev
() {
element
=
PAssertNULL
(
element
)->prev; }
355
T *
Ptr
()
const
{
return
(T *)
PAssertNULL
(
element
)->data; }
356
357
public
:
358
bool
operator==
(
const
iterator_base
& it)
const
{
return
element
== it.
element
; }
359
bool
operator!=
(
const
iterator_base
& it)
const
{
return
element
!= it.
element
; }
360
};
361
362
class
iterator
:
public
iterator_base
{
363
public
:
364
iterator
(
PListElement
* e = NULL) :
iterator_base
(e) { }
365
366
iterator
operator++
() {
iterator_base::Next
();
return
*
this
; }
367
iterator
operator--
() {
iterator_base::Prev
();
return
*
this
; }
368
iterator
operator++
(
int
) {
iterator
it = *
this
;
iterator_base::Next
();
return
it; }
369
iterator
operator--
(
int
) {
iterator
it = *
this
;
iterator_base::Prev
();
return
it; }
370
371
T *
operator->
()
const
{
return
iterator_base::Ptr
(); }
372
T &
operator*
()
const
{
return
*
iterator_base::Ptr
(); }
373
};
374
375
iterator
begin
() {
return
info
->
head
; }
376
iterator
end
() {
return
iterator(); }
377
iterator
rbegin
() {
return
info
->
tail
; }
378
iterator
rend
() {
return
iterator(); }
379
380
381
class
const_iterator
:
public
iterator_base
{
382
public
:
383
const_iterator
(
PListElement
* e = NULL) :
iterator_base
(e) { }
384
385
const_iterator
operator++
() {
iterator_base::Next
();
return
*
this
; }
386
const_iterator
operator--
() {
iterator_base::Prev
();
return
*
this
; }
387
const_iterator
operator++
(
int
) {
const_iterator
it = *
this
;
iterator_base::Next
();
return
it; }
388
const_iterator
operator--
(
int
) {
const_iterator
it = *
this
;
iterator_base::Prev
();
return
it; }
389
390
const
T *
operator->
()
const
{
return
iterator_base::Ptr
(); }
391
const
T &
operator*
()
const
{
return
*
iterator_base::Ptr
(); }
392
};
393
394
const_iterator
begin
()
const
{
return
info
->
head
; }
395
const_iterator
end
()
const
{
return
const_iterator(); }
396
const_iterator
rbegin
()
const
{
return
info
->
tail
; }
397
const_iterator
rend
()
const
{
return
iterator(); }
398
399
T &
front
()
const
{
return
*(T *)
PAssertNULL
(
info
->
head
)->data; }
400
T &
back
()
const
{
return
*(T *)
PAssertNULL
(
info
->
tail
)->data; }
401
void
erase
(
const
iterator & it) {
Remove
(&*it); }
402
void
erase
(
const
const_iterator & it) {
Remove
(&*it); }
403
404
typedef
T
value_type
;
406
420
T &
operator[]
(
421
PINDEX index
422
)
const
{
return
(T &)
GetReferenceAt
(index); }
424
425
protected
:
426
PList
(
int
dummy,
const
PList
* c)
427
:
PAbstractList
(dummy, c) { }
428
};
429
430
442
#define PLIST(cls, T) typedef PList<T> cls
443
455
#define PDECLARE_LIST(cls, T) \
456
PLIST(cls##_PTemplate, T); \
457
PDECLARE_CLASS(cls, PList<T>) \
458
protected: \
459
cls(int dummy, const cls * c) \
460
: PList<T>(dummy, c) { } \
461
public: \
462
cls() \
463
: PList<T>() { } \
464
virtual PObject * Clone() const \
465
{ return PNEW cls(0, this); } \
466
467
480
template
<
class
T>
class
PQueue
:
public
PAbstractList
481
{
482
PCLASSINFO(
PQueue
,
PAbstractList
);
483
484
public
:
493
PQueue
()
494
:
PAbstractList
() {
DisallowDeleteObjects
(); }
496
502
virtual
PObject
*
Clone
()
const
503
{
return
PNEW
PQueue
(0,
this
); }
505
511
virtual
void
Enqueue
(
512
T * obj
513
) {
PAbstractList::Append
(obj); }
519
virtual
T *
Dequeue
()
520
{
if
(
GetSize
() == 0)
return
NULL;
else
return
(T *)
PAbstractList::RemoveAt
(0);}
522
523
protected
:
524
PQueue
(
int
dummy,
const
PQueue
* c)
525
:
PAbstractList
(dummy, c)
526
{
reference
->
deleteObjects
= c->
reference
->
deleteObjects
; }
527
};
528
529
542
#define PQUEUE(cls, T) typedef PQueue<T> cls
543
544
557
#define PDECLARE_QUEUE(cls, T) \
558
PQUEUE(cls##_PTemplate, T); \
559
PDECLARE_CLASS(cls, cls##_PTemplate) \
560
protected: \
561
cls(int dummy, const cls * c) \
562
: cls##_PTemplate(dummy, c) { } \
563
public: \
564
cls() \
565
: cls##_PTemplate() { } \
566
virtual PObject * Clone() const \
567
{ return PNEW cls(0, this); } \
568
569
582
template
<
class
T>
class
PStack
:
public
PAbstractList
583
{
584
PCLASSINFO(
PStack
,
PAbstractList
);
585
586
public
:
595
PStack
()
596
:
PAbstractList
() {
DisallowDeleteObjects
(); }
598
604
virtual
PObject
*
Clone
()
const
605
{
return
PNEW
PStack
(0,
this
); }
607
614
virtual
void
Push
(
615
T * obj
616
) {
PAbstractList::InsertAt
(0, obj); }
617
623
virtual
T *
Pop
()
624
{
return
(T *)
PAbstractList::RemoveAt
(0); }
625
632
virtual
T &
Top
()
633
{
PAssert
(
GetSize
() > 0,
PStackEmpty
);
return
*(T *)
GetAt
(0); }
635
636
protected
:
637
PStack
(
int
dummy,
const
PStack
* c)
638
:
PAbstractList
(dummy, c)
639
{
reference
->
deleteObjects
= c->
reference
->
deleteObjects
; }
640
};
641
642
655
#define PSTACK(cls, T) typedef PStack<T> cls
656
657
670
#define PDECLARE_STACK(cls, T) \
671
PSTACK(cls##_PTemplate, T); \
672
PDECLARE_CLASS(cls, cls##_PTemplate) \
673
protected: \
674
cls(int dummy, const cls * c) \
675
: cls##_PTemplate(dummy, c) { } \
676
public: \
677
cls() \
678
: cls##_PTemplate() { } \
679
virtual PObject * Clone() const \
680
{ return PNEW cls(0, this); } \
681
682
684
// Sorted List of PObjects
685
686
struct
PSortedListElement
687
{
688
PSortedListElement
*
parent
;
689
PSortedListElement
*
left
;
690
PSortedListElement
*
right
;
691
PObject
*
data
;
692
PINDEX
subTreeSize
;
693
enum
{
Red
,
Black
}
colour
;
694
695
PDECLARE_POOL_ALLOCATOR
();
696
};
697
698
struct
PSortedListInfo
699
{
700
PSortedListInfo
();
701
702
PSortedListElement
*
root
;
703
//PSortedListElement * lastElement;
704
//PINDEX lastIndex;
705
PSortedListElement
nil
;
706
707
PSortedListElement
*
Successor
(
const
PSortedListElement
* node)
const
;
708
PSortedListElement
*
Predecessor
(
const
PSortedListElement
* node)
const
;
709
PSortedListElement
*
OrderSelect
(
PSortedListElement
* node, PINDEX index)
const
;
710
711
typedef
PSortedListElement
Element
;
712
713
PDECLARE_POOL_ALLOCATOR
();
714
};
715
742
class
PAbstractSortedList
:
public
PCollection
743
{
744
PCONTAINERINFO(
PAbstractSortedList
,
PCollection
);
745
746
public
:
754
PAbstractSortedList
();
756
785
virtual
Comparison
Compare
(
const
PObject
& obj)
const
;
787
797
virtual
PBoolean
SetSize
(
798
PINDEX newSize
// New size for the sorted list, this is ignored.
799
);
801
810
virtual
PINDEX
Append
(
811
PObject
* obj
// New object to place into the collection.
812
);
813
823
virtual
PINDEX
Insert
(
824
const
PObject
& before,
// Object value to insert before.
825
PObject
* obj
// New object to place into the collection.
826
);
827
837
virtual
PINDEX
InsertAt
(
838
PINDEX index,
// Index position in collection to place the object.
839
PObject
* obj
// New object to place into the collection.
840
);
841
852
virtual
PBoolean
Remove
(
853
const
PObject
* obj
// Existing object to remove from the collection.
854
);
855
865
virtual
PObject
*
RemoveAt
(
866
PINDEX index
// Index position in collection to place the object.
867
);
868
875
virtual
void
RemoveAll
();
876
883
virtual
PBoolean
SetAt
(
884
PINDEX index,
// Index position in collection to set.
885
PObject
* val
// New value to place into the collection.
886
);
887
894
virtual
PObject
*
GetAt
(
895
PINDEX index
// Index position in the collection of the object.
896
)
const
;
897
909
virtual
PINDEX
GetObjectsIndex
(
910
const
PObject
* obj
911
)
const
;
912
virtual
PINDEX
GetObjectsIndex
(
913
const
PObject
* obj,
914
PSortedListElement
* & lastElement
915
)
const
;
916
925
virtual
PINDEX
GetValuesIndex
(
926
const
PObject
& obj
927
)
const
;
929
930
// The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
931
typedef
PSortedListElement
Element
;
932
933
protected
:
934
935
// New functions for class
936
void
RemoveElement
(
Element
* node);
937
void
LeftRotate
(
Element
* node);
938
void
RightRotate
(
Element
* node);
939
void
DeleteSubTrees
(
Element
* node,
PBoolean
deleteObject);
940
PINDEX
ValueSelect
(
const
Element
* node,
const
PObject
& obj,
const
Element
** lastElement)
const
;
941
942
// The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
943
PSortedListInfo
*
info
;
944
};
945
946
954
template
<
class
T>
class
PSortedList
:
public
PAbstractSortedList
955
{
956
PCLASSINFO(
PSortedList
,
PAbstractSortedList
);
957
958
public
:
966
PSortedList
()
967
:
PAbstractSortedList
() { }
969
975
virtual
PObject
*
Clone
()
const
976
{
return
PNEW
PSortedList
(0,
this
); }
978
991
T &
operator[]
(
992
PINDEX index
993
)
const
{
return
*(T *)
GetAt
(index); }
995
996
protected
:
997
PSortedList
(
int
dummy,
const
PSortedList
* c)
998
:
PAbstractSortedList
(dummy, c) { }
999
};
1000
1001
1013
#define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
1014
1015
1028
#define PDECLARE_SORTED_LIST(cls, T) \
1029
PSORTED_LIST(cls##_PTemplate, T); \
1030
PDECLARE_CLASS(cls, PSortedList<T>) \
1031
protected: \
1032
cls(int dummy, const cls * c) \
1033
: PSortedList<T>(dummy, c) { } \
1034
public: \
1035
cls() \
1036
: PSortedList<T>() { } \
1037
virtual PObject * Clone() const \
1038
{ return PNEW cls(0, this); } \
1039
1040
1041
#endif // PTLIB_LISTS_H
1042
1043
1044
// End Of File ///////////////////////////////////////////////////////////////
include
ptlib
lists.h
Generated on Tue Mar 11 2014 15:09:29 for PTLib by
1.8.1.2