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