1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 #ifndef __LISTEN_123456__
25 #define __LISTEN_123456__
26
27 #include <string.h>
28 #include <iostream>
29 #include <stdlib.h>
30
31 template <class XX>
32 class List
33 {
34 public :
35 typedef XX * iterator;
36 typedef const XX * const_iterator;
37
38 // LIFECYCLE
39 List();
~List()40 virtual ~List() { delete [] inhalt; }
41
42 // OPERATORS
operator [](unsigned n) const43 const XX & operator[](
44 unsigned n) const
45 { return elem(n); }
operator [](unsigned n)46 XX & operator[](
47 unsigned n)
48 { return elem(n); }
49 // OPERATIONS
reserve(unsigned i_nSize)50 void reserve(
51 unsigned i_nSize )
52 { alloc(i_nSize,true); }
53 virtual void insert(
54 unsigned pos,
55 const XX & elem );
push_back(const XX & elem_)56 void push_back(
57 const XX & elem_)
58 { insert(size(),elem_); }
59
60 virtual void remove(
61 unsigned pos );
pop_back()62 void pop_back() { remove(size()-1); }
erase_all()63 void erase_all() { while (size()) remove(size()-1); }
64
65 // INQUIRY
front() const66 const XX & front() const { return elem(0); }
back() const67 const XX & back() const { return elem(len-1); }
68
size() const69 unsigned size() const { return len; }
space() const70 unsigned space() const { return allocated; }
is_valid_index(unsigned n) const71 bool is_valid_index(
72 unsigned n) const
73 { return n < len; }
74 // ACCESS
front()75 XX & front() { return elem(0); }
back()76 XX & back() { return elem(len-1); }
77
78 protected:
79 void checkSize(
80 unsigned newLength);
81 void alloc(
82 unsigned newSpace,
83 bool re = false );
84
elem(unsigned n) const85 const XX & elem(
86 unsigned n ) const
87 { return inhalt[n]; }
elem(unsigned n)88 XX & elem(
89 unsigned n )
90 { return inhalt[n]; }
91 // DATA
92 XX * inhalt;
93 unsigned len;
94 unsigned allocated;
95
96 private:
97 // forbidden functions
98 List(const List<XX> & L);
99 List<XX> & operator=(
100 const List<XX> & L);
101
102 };
103
104 template <class XY>
105 class DynamicList : public List<XY*>
106 {
107 public:
108 virtual ~DynamicList();
109
110 virtual void insert(
111 unsigned pos,
112 XY * const & elem );
113 virtual void remove(
114 unsigned pos );
115 };
116
117
118
119 template <class XX>
List()120 List<XX>::List()
121 : inhalt(0),
122 len(0),
123 allocated(0)
124
125 {
126 alloc(1);
127 }
128
129
130 template <class XX>
131 void
insert(unsigned pos,const XX & elem_)132 List<XX>::insert(unsigned pos, const XX & elem_)
133 {
134 if ( pos > len )
135 return;
136
137 checkSize(len+2);
138 for ( unsigned p = len; p > pos; --p)
139 {
140 inhalt[p] = inhalt[p-1];
141 }
142 inhalt[pos] = elem_;
143 len++;
144 }
145
146
147 template <class XX>
148 void
remove(unsigned pos)149 List<XX>::remove(unsigned pos)
150 {
151 if ( pos >= len )
152 return;
153 len--;
154 for ( unsigned p = pos; p < len; ++p)
155 {
156 inhalt[p] = inhalt[p+1];
157 }
158 }
159
160
161 // Protected:
162 template <class XX>
163 void
checkSize(unsigned newLength)164 List<XX>::checkSize(unsigned newLength)
165 {
166 // neuen Platzbedarf pruefen:
167 unsigned newSpace = space();
168 if (newLength > newSpace)
169 {
170 if (!newSpace)
171 newSpace = 1;
172 const unsigned nBorder = 65536 / 2;
173 while(newLength > newSpace)
174 {
175 if (newSpace < nBorder)
176 newSpace <<= 1;
177 else
178 {
179 std::cerr << "List becomes too big" << std::endl;
180 exit(1);
181 }
182 }
183 }
184
185 // Veraenderung ?:
186 if (newSpace != space())
187 alloc(newSpace,true);
188 }
189
190 template <class XX>
191 void
alloc(unsigned newSpace,bool re)192 List<XX>::alloc( unsigned newSpace,
193 bool re )
194 {
195 XX * pNew = new XX[newSpace];
196
197 if (inhalt != 0)
198 {
199 if (re)
200 {
201 for (unsigned i = 0; i < len; ++i)
202 {
203 pNew[i] = inhalt[i];
204 } // end for
205 }
206 delete [] inhalt;
207 }
208
209 inhalt = pNew;
210 allocated = newSpace;
211 }
212
213
214 template <class XY>
~DynamicList()215 DynamicList<XY>::~DynamicList()
216 {
217 this->erase_all();
218 }
219
220 template <class XY>
221 void
insert(unsigned pos,XY * const & elem_)222 DynamicList<XY>::insert(unsigned pos, XY * const & elem_)
223 {
224 if ( pos > this->len )
225 return;
226
227 this->checkSize(this->len+2);
228 memmove(this->inhalt[pos+1], this->inhalt[pos], (this->len-pos) * sizeof(XY*) );
229 this->inhalt[pos] = elem_;
230 this->len++;
231 }
232
233 template <class XY>
234 void
remove(unsigned pos)235 DynamicList<XY>::remove( unsigned pos )
236 {
237 if (!this->is_valid_index(pos) )
238 return;
239 this->len--;
240 delete this->inhalt[pos];
241 memmove(this->inhalt[pos], this->inhalt[pos+1], (this->len-pos) * sizeof(XY*) );
242 }
243
244
245
246 #endif
247
248