Commit | Line | Data |
---|---|---|
e87b4ac1 PR |
1 | // This may look like C code, but it is really -*- C++ -*- |
2 | /* | |
3 | Copyright (C) 1988 Free Software Foundation | |
4 | written by Doug Lea (dl@rocky.oswego.edu) | |
5 | ||
6 | This file is part of the GNU C++ Library. This library is free | |
7 | software; you can redistribute it and/or modify it under the terms of | |
8 | the GNU Library General Public License as published by the Free | |
9 | Software Foundation; either version 2 of the License, or (at your | |
10 | option) any later version. This library is distributed in the hope | |
11 | that it will be useful, but WITHOUT ANY WARRANTY; without even the | |
12 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
13 | PURPOSE. See the GNU Library General Public License for more details. | |
14 | You should have received a copy of the GNU Library General Public | |
15 | License along with this library; if not, write to the Free Software | |
16 | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
17 | */ | |
18 | // This may look like C code, but it is really -*- C++ -*- | |
19 | /* | |
20 | Copyright (C) 1988, 1982 Free Software Foundation | |
21 | written by Doug Lea (dl@rocky.oswego.edu) | |
22 | ||
23 | This file is part of the GNU C++ Library. This library is free | |
24 | software; you can redistribute it and/or modify it under the terms of | |
25 | the GNU Library General Public License as published by the Free | |
26 | Software Foundation; either version 2 of the License, or (at your | |
27 | option) any later version. This library is distributed in the hope | |
28 | that it will be useful, but WITHOUT ANY WARRANTY; without even the | |
29 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
30 | PURPOSE. See the GNU Library General Public License for more details. | |
31 | You should have received a copy of the GNU Library General Public | |
32 | License along with this library; if not, write to the Free Software | |
33 | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
34 | */ | |
35 | ||
36 | ||
37 | #ifndef _<T>SplayBag_h | |
38 | #ifdef __GNUG__ | |
39 | #pragma interface | |
40 | #endif | |
41 | #define _<T>SplayBag_h 1 | |
42 | ||
43 | #include "<T>.Bag.h" | |
44 | #include "<T>.SplayNode.h" | |
45 | ||
46 | class <T>SplayBag : public <T>Bag | |
47 | { | |
48 | protected: | |
49 | <T>SplayNode* root; | |
50 | ||
51 | <T>SplayNode* leftmost(); | |
52 | <T>SplayNode* rightmost(); | |
53 | <T>SplayNode* pred(<T>SplayNode* t); | |
54 | <T>SplayNode* succ(<T>SplayNode* t); | |
55 | void _kill(<T>SplayNode* t); | |
56 | <T>SplayNode* _copy(<T>SplayNode* t); | |
57 | void _del(<T>SplayNode* t); | |
58 | ||
59 | public: | |
60 | <T>SplayBag(); | |
61 | <T>SplayBag(<T>SplayBag& a); | |
62 | ~<T>SplayBag(); | |
63 | ||
64 | Pix add(<T&> item); | |
65 | void del(<T&> item); | |
66 | void remove(<T&>item); | |
67 | int nof(<T&> item); | |
68 | int contains(<T&> item); | |
69 | ||
70 | void clear(); | |
71 | ||
72 | Pix first(); | |
73 | void next(Pix& i); | |
74 | <T>& operator () (Pix i); | |
75 | Pix seek(<T&> item, Pix from = 0); | |
76 | ||
77 | Pix last(); | |
78 | void prev(Pix& i); | |
79 | ||
80 | int OK(); | |
81 | }; | |
82 | ||
83 | ||
84 | inline <T>SplayBag::~<T>SplayBag() | |
85 | { | |
86 | _kill(root); | |
87 | } | |
88 | ||
89 | inline <T>SplayBag::<T>SplayBag() | |
90 | { | |
91 | root = 0; | |
92 | count = 0; | |
93 | } | |
94 | ||
95 | inline <T>SplayBag::<T>SplayBag(<T>SplayBag& b) | |
96 | { | |
97 | count = b.count; | |
98 | root = _copy(b.root); | |
99 | } | |
100 | ||
101 | inline Pix <T>SplayBag::first() | |
102 | { | |
103 | return Pix(leftmost()); | |
104 | } | |
105 | ||
106 | inline Pix <T>SplayBag::last() | |
107 | { | |
108 | return Pix(rightmost()); | |
109 | } | |
110 | ||
111 | inline void <T>SplayBag::next(Pix& i) | |
112 | { | |
113 | if (i != 0) i = Pix(succ((<T>SplayNode*)i)); | |
114 | } | |
115 | ||
116 | inline void <T>SplayBag::prev(Pix& i) | |
117 | { | |
118 | if (i != 0) i = Pix(pred((<T>SplayNode*)i)); | |
119 | } | |
120 | ||
121 | inline <T>& <T>SplayBag::operator () (Pix i) | |
122 | { | |
123 | if (i == 0) error("null Pix"); | |
124 | return ((<T>SplayNode*)i)->item; | |
125 | } | |
126 | ||
127 | inline void <T>SplayBag::clear() | |
128 | { | |
129 | _kill(root); | |
130 | count = 0; | |
131 | root = 0; | |
132 | } | |
133 | ||
134 | inline int <T>SplayBag::contains(<T&> key) | |
135 | { | |
136 | return seek(key) != 0; | |
137 | } | |
138 | ||
139 | inline void <T>SplayBag::del(<T&> key) | |
140 | { | |
141 | _del((<T>SplayNode*)(seek(key))); | |
142 | } | |
143 | ||
144 | #endif |