summaryrefslogtreecommitdiff
path: root/utils/DList.h
blob: cba72f17a14f0fcee085b5a257bc90077c309902 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1992-1995
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	plain and generic double-linked lists (original ideas by Yves Berteaud)
 *
 *	$Id$
 *	$CurLog$
 */

#ifndef DList_H_
#define DList_H_

#include "cplus_bugs.h"
#include <sys/types.h>

class CcuAllocator;

typedef void CcuDListItem;

#ifdef CPLUS_BUG20
class CcuDListLink;
#endif

class CcuDList {
friend	class	CcuDListIter;

#ifndef CPLUS_BUG20
	class CcuDListLink {
	static	CcuAllocator*	DListLinkMem;
	public:
		CcuDListItem*	Entry;
		CcuDListLink*	Previous;
		CcuDListLink*	Next;
	inline		CcuDListLink (CcuDListItem* e, CcuDListLink* p) : Entry (e), Previous (p), Next (p->Next)	{ Previous->Next = Next->Previous = this; }
	inline		CcuDListLink (CcuDListItem* e) : Entry (e), Previous (this), Next (this)	{}
		void*	operator new (size_t);
		void	operator delete (void*);
	};
#endif

public:
	enum	dlist_status	{ NoError, WasEmpty, TooEarly, TooFar, BadIterator };
	enum	dlist_remove	{ All = -1 };

private:

	CcuDListLink*	LastLink;
	dlist_status	StatusFlag;

	void	InsertAfterLink (CcuDListLink*, CcuDListItem*);
	CcuDListItem*	RemoveLink (CcuDListLink*);

public:
inline		CcuDList () : LastLink (0), StatusFlag (NoError)				{ }
		CcuDList (CcuDListItem*);
		CcuDList (const CcuDList&);
		~CcuDList ();
		CcuDList&	operator = (const CcuDList&);
inline	dlist_status	GetStatus () const		{ return StatusFlag; }

inline	int	IsEmpty () const			{ return !LastLink; }
	CcuDListItem*	First ();
	CcuDListItem*	Last ();
	CcuDListItem*	Nth (int n);
	int	Length () const;
	int	Find (CcuDListItem*) const;

	void	Append (CcuDListItem*);
	void	Prepend (CcuDListItem*);
inline	CcuDList&	operator << (CcuDListItem* it)	{ Append (it); return *this; }

	CcuDListItem*	RemoveFirst ();
	CcuDListItem*	RemoveLast ();
	int	Remove (CcuDListItem*, int = 1);
	int	Remove (int (*) (CcuDListItem*), int = 1);
	void	Clear ();

	void	InsertAfter (const CcuDListIter&, CcuDListItem*);
	void	InsertBefore (const CcuDListIter&, CcuDListItem*);
	CcuDListItem*	RemoveAfter (const CcuDListIter&);
	CcuDListItem*	RemoveAt (CcuDListIter&);
};

class CcuDListIter {
friend	class	CcuDList;

public:
	enum	dlistiter_status	{ Normal, StartOfList, EndOfList };

private:
	const CcuDList*	TheList;
#ifdef CPLUS_BUG20
	CcuDListLink*	CurLink;
#else
	CcuDList::CcuDListLink*	CurLink;
#endif
	dlistiter_status	StatusFlag;

public:
inline		CcuDListIter (const CcuDList& l) : TheList (&l), CurLink (0), StatusFlag (StartOfList)	{}
inline	void	Reset ()		{ CurLink = 0; StatusFlag = StartOfList; }
inline	void	GotoEnd ()		{ CurLink = TheList->LastLink; StatusFlag = CurLink ? EndOfList : StartOfList; }
inline	CcuDListIter&	operator = (const CcuDList& l)	{ TheList = &l; CurLink = 0; StatusFlag = StartOfList; return *this; }
inline	CcuDListIter&	operator = (const CcuDListIter& li)	{ TheList = li.TheList; CurLink = li.CurLink; StatusFlag = li.StatusFlag; return *this; }
	CcuDListIter&	operator ++ ();
	CcuDListIter&	operator -- ();
	int	Find (CcuDListItem*);
	int	FindBack (CcuDListItem*);
	CcuDListItem*	operator * () const;
inline	dlistiter_status	GetStatus () const		{ return StatusFlag; }
inline	operator int () const	{ return StatusFlag == Normal; }
};


#ifndef CPLUS_BUG19
template <class ITEM> class CcuDListIterOf;

template <class ITEM> class CcuDListOf : public CcuDList {
public:
inline		CcuDListOf () : CcuDList ()	{}
inline		CcuDListOf (ITEM* it) : CcuDList (it)	{}
inline	ITEM*	First ()	{ return (ITEM*) (CcuDList::First ()); }
inline	ITEM*	Last ()	{ return (ITEM*) (CcuDList::Last ()); }
inline	ITEM*	Nth (int n)	{ return (ITEM*) (CcuDList::Nth (n)); }
inline	int	Find (ITEM* it) const	{ return CcuDList::Find (it); }

inline	void	Append (ITEM* it)	{ CcuDList::Append (it); }
inline	void	Prepend (ITEM* it)	{ CcuDList::Prepend (it); }
inline	CcuDListOf <ITEM>&	operator << (ITEM* it)	{ CcuDList::Append (it); return *this; }

inline	ITEM*	RemoveFirst ()	{ return (ITEM*) (CcuDList::RemoveFirst ()); }
inline	ITEM*	RemoveLast ()	{ return (ITEM*) (CcuDList::RemoveLast ()); }
inline	int	Remove (ITEM* it, int nb = 1)	{ return CcuDList::Remove (it, nb); }
inline	int	Remove (int (*p) (ITEM*), int nb = 1)	{ return CcuDList::Remove ((int (*) (ITEM*)) p, nb); }

inline	void	InsertAfter (const CcuDListIterOf <ITEM>& li, ITEM*it)	{ CcuDList::InsertAfter (li, it); }
inline	void	InsertBefore (const CcuDListIterOf <ITEM>& li, ITEM* it)	{ CcuDList::InsertBefore (li, it); }
inline	ITEM*	RemoveAfter (const CcuDListIterOf <ITEM>& li)		{ return (ITEM*) CcuDList::RemoveAfter (li); }
inline	ITEM*	RemoveAt (CcuDListIterOf <ITEM>& li)		{ return (ITEM*) CcuDList::RemoveAfter (li); }
};

template <class ITEM> class CcuDListIterOf : public CcuDListIter {
public:
inline		CcuDListIterOf (const CcuDListOf <ITEM>& l) : CcuDListIter (l)	{ }
inline	CcuDListIterOf <ITEM>&	operator =  (const CcuDListOf <ITEM>& l)	{ return (CcuDListIterOf <ITEM>&) CcuDListIter::operator = (l); }
inline	CcuDListIterOf <ITEM>&	operator =  (const CcuDListIterOf <ITEM>& li)	{ return (CcuDListIterOf <ITEM>&) CcuDListIter::operator = (li); }
inline	ITEM*	operator * () const	{ return (ITEM*) CcuDListIter::operator * (); }
inline	int	Find (ITEM* it)	{ return CcuDListIter::Find (it); }
inline	int	FindBack (ITEM* it)	{ return CcuDListIter::FindBack (it); }
};
#endif	/* CPLUS_BUG19 */


#endif	/* DList_H_ */