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