138268e38SAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
338268e38SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
438268e38SAndrew Rist * or more contributor license agreements. See the NOTICE file
538268e38SAndrew Rist * distributed with this work for additional information
638268e38SAndrew Rist * regarding copyright ownership. The ASF licenses this file
738268e38SAndrew Rist * to you under the Apache License, Version 2.0 (the
838268e38SAndrew Rist * "License"); you may not use this file except in compliance
938268e38SAndrew Rist * with the License. You may obtain a copy of the License at
1038268e38SAndrew Rist *
1138268e38SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
1238268e38SAndrew Rist *
1338268e38SAndrew Rist * Unless required by applicable law or agreed to in writing,
1438268e38SAndrew Rist * software distributed under the License is distributed on an
1538268e38SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
1638268e38SAndrew Rist * KIND, either express or implied. See the License for the
1738268e38SAndrew Rist * specific language governing permissions and limitations
1838268e38SAndrew Rist * under the License.
1938268e38SAndrew Rist *
2038268e38SAndrew Rist *************************************************************/
2138268e38SAndrew Rist
2238268e38SAndrew Rist
23cdf0e10cSrcweir
24cdf0e10cSrcweir #ifndef SOLTOOLS_ST_LIST_HXX
25cdf0e10cSrcweir #define SOLTOOLS_ST_LIST_HXX
26cdf0e10cSrcweir
27cdf0e10cSrcweir #include <string.h>
28cdf0e10cSrcweir #include <iostream>
29cdf0e10cSrcweir #include <stdlib.h>
30cdf0e10cSrcweir
31cdf0e10cSrcweir template <class XX>
32cdf0e10cSrcweir class ST_List /// Soltools-List.
33cdf0e10cSrcweir {
34cdf0e10cSrcweir public :
35cdf0e10cSrcweir typedef XX * iterator;
36cdf0e10cSrcweir typedef const XX * const_iterator;
37cdf0e10cSrcweir
38cdf0e10cSrcweir // LIFECYCLE
39cdf0e10cSrcweir ST_List();
40cdf0e10cSrcweir ST_List(
41cdf0e10cSrcweir const ST_List<XX> & i_rList );
~ST_List()42cdf0e10cSrcweir virtual ~ST_List() { }
43cdf0e10cSrcweir
44cdf0e10cSrcweir // OPERATORS
45cdf0e10cSrcweir ST_List<XX> & operator=(
46cdf0e10cSrcweir const ST_List<XX> & i_rList );
47cdf0e10cSrcweir
operator [](unsigned n) const48cdf0e10cSrcweir const XX & operator[](
49cdf0e10cSrcweir unsigned n) const
50cdf0e10cSrcweir { return elem(n); }
operator [](unsigned n)51cdf0e10cSrcweir XX & operator[](
52cdf0e10cSrcweir unsigned n)
53cdf0e10cSrcweir { return elem(n); }
54cdf0e10cSrcweir // OPERATIONS
reserve(unsigned i_nSize)55cdf0e10cSrcweir void reserve(
56cdf0e10cSrcweir unsigned i_nSize )
57cdf0e10cSrcweir { alloc(i_nSize,true); }
insert(iterator i_aPos,const XX & elem_)58cdf0e10cSrcweir void insert(
59cdf0e10cSrcweir iterator i_aPos,
60cdf0e10cSrcweir const XX & elem_ )
61cdf0e10cSrcweir { Insert(i_aPos-begin(), elem_); }
62cdf0e10cSrcweir virtual void Insert(
63cdf0e10cSrcweir unsigned pos,
64cdf0e10cSrcweir const XX & elem );
push_back(const XX & elem_)65cdf0e10cSrcweir void push_back(
66cdf0e10cSrcweir const XX & elem_)
67cdf0e10cSrcweir { Insert(size(),elem_); }
remove(iterator i_aPos)68cdf0e10cSrcweir void remove(
69cdf0e10cSrcweir iterator i_aPos )
70cdf0e10cSrcweir { Remove(i_aPos-begin()); }
71cdf0e10cSrcweir virtual void Remove(
72cdf0e10cSrcweir unsigned pos );
pop_back()73cdf0e10cSrcweir void pop_back() { Remove(size()-1); }
erase_all()74cdf0e10cSrcweir void erase_all() { while (size()) Remove(size()-1); }
75cdf0e10cSrcweir
76cdf0e10cSrcweir // INQUIRY
begin() const77cdf0e10cSrcweir const_iterator begin() const { return &inhalt[0]; }
end() const78cdf0e10cSrcweir const_iterator end() const { return &inhalt[len]; }
79cdf0e10cSrcweir
front() const80cdf0e10cSrcweir const XX & front() const { return elem(0); }
back() const81cdf0e10cSrcweir const XX & back() const { return elem(len-1); }
82cdf0e10cSrcweir
size() const83cdf0e10cSrcweir unsigned size() const { return len; }
space() const84cdf0e10cSrcweir unsigned space() const { return allocated; }
is_valid_index(unsigned n) const85cdf0e10cSrcweir bool is_valid_index(
86cdf0e10cSrcweir unsigned n) const
87cdf0e10cSrcweir { return n < len; }
88cdf0e10cSrcweir // ACCESS
begin()89cdf0e10cSrcweir iterator begin() { return &inhalt[0]; }
end()90cdf0e10cSrcweir iterator end() { return &inhalt[len]; }
91cdf0e10cSrcweir
front()92cdf0e10cSrcweir XX & front() { return elem(0); }
back()93cdf0e10cSrcweir XX & back() { return elem(len-1); }
94cdf0e10cSrcweir
95cdf0e10cSrcweir protected:
96cdf0e10cSrcweir void checkSize(
97cdf0e10cSrcweir unsigned newLength);
98cdf0e10cSrcweir void alloc(
99cdf0e10cSrcweir unsigned newSpace,
100cdf0e10cSrcweir bool re = false );
101cdf0e10cSrcweir
elem(unsigned n) const102cdf0e10cSrcweir const XX & elem(
103cdf0e10cSrcweir unsigned n ) const
104cdf0e10cSrcweir { return inhalt[n]; }
elem(unsigned n)105cdf0e10cSrcweir XX & elem(
106cdf0e10cSrcweir unsigned n )
107cdf0e10cSrcweir { return inhalt[n]; }
108cdf0e10cSrcweir // DATA
109cdf0e10cSrcweir XX * inhalt;
110cdf0e10cSrcweir unsigned len;
111cdf0e10cSrcweir unsigned allocated;
112cdf0e10cSrcweir };
113cdf0e10cSrcweir
114cdf0e10cSrcweir
115cdf0e10cSrcweir
116cdf0e10cSrcweir template <class XY>
117cdf0e10cSrcweir class DynamicList : public ST_List< XY* >
118cdf0e10cSrcweir {
119cdf0e10cSrcweir public:
120cdf0e10cSrcweir DynamicList();
121cdf0e10cSrcweir DynamicList(
122cdf0e10cSrcweir const DynamicList<XY> &
123cdf0e10cSrcweir i_rList );
124cdf0e10cSrcweir virtual ~DynamicList(); /// Deletes all member pointers
125cdf0e10cSrcweir
126cdf0e10cSrcweir DynamicList<XY> & operator=(
127cdf0e10cSrcweir const DynamicList<XY> &
128cdf0e10cSrcweir i_rList );
129cdf0e10cSrcweir
130cdf0e10cSrcweir virtual void Insert(
131cdf0e10cSrcweir unsigned pos,
132cdf0e10cSrcweir XY * const & elem );
133cdf0e10cSrcweir virtual void Remove(
134cdf0e10cSrcweir unsigned pos );
135cdf0e10cSrcweir };
136cdf0e10cSrcweir
137cdf0e10cSrcweir
138cdf0e10cSrcweir
139cdf0e10cSrcweir template <class XX>
ST_List()140cdf0e10cSrcweir ST_List<XX>::ST_List()
141cdf0e10cSrcweir : inhalt(0),
142cdf0e10cSrcweir len(0),
143cdf0e10cSrcweir allocated(0)
144cdf0e10cSrcweir {
145cdf0e10cSrcweir alloc(1);
146cdf0e10cSrcweir }
147cdf0e10cSrcweir
148cdf0e10cSrcweir template <class XX>
ST_List(const ST_List<XX> & i_rList)149cdf0e10cSrcweir ST_List<XX>::ST_List( const ST_List<XX> & i_rList )
150cdf0e10cSrcweir : inhalt(0),
151cdf0e10cSrcweir len(0),
152cdf0e10cSrcweir allocated(0)
153cdf0e10cSrcweir {
154cdf0e10cSrcweir alloc(i_rList.size());
155cdf0e10cSrcweir
156cdf0e10cSrcweir for ( const_iterator it = i_rList.begin();
157cdf0e10cSrcweir it != i_rList.end();
158cdf0e10cSrcweir ++it )
159cdf0e10cSrcweir {
160cdf0e10cSrcweir push_back(*it);
161cdf0e10cSrcweir }
162cdf0e10cSrcweir }
163cdf0e10cSrcweir
164cdf0e10cSrcweir template <class XX>
165cdf0e10cSrcweir ST_List<XX> &
operator =(const ST_List<XX> & i_rList)166cdf0e10cSrcweir ST_List<XX>::operator=( const ST_List<XX> & i_rList )
167cdf0e10cSrcweir {
168cdf0e10cSrcweir for ( const_iterator it = i_rList.begin();
169cdf0e10cSrcweir it != i_rList.end();
170cdf0e10cSrcweir ++it )
171cdf0e10cSrcweir {
172cdf0e10cSrcweir push_back(*it);
173cdf0e10cSrcweir }
174cdf0e10cSrcweir return *this;
175cdf0e10cSrcweir }
176cdf0e10cSrcweir
177cdf0e10cSrcweir template <class XX>
178cdf0e10cSrcweir void
Insert(unsigned pos,const XX & elem_)179cdf0e10cSrcweir ST_List<XX>::Insert(unsigned pos, const XX & elem_)
180cdf0e10cSrcweir {
181cdf0e10cSrcweir if ( pos > len )
182cdf0e10cSrcweir return;
183cdf0e10cSrcweir
184cdf0e10cSrcweir checkSize(len+2);
185cdf0e10cSrcweir for ( unsigned p = len; p > pos; --p)
186cdf0e10cSrcweir {
187cdf0e10cSrcweir inhalt[p] = inhalt[p-1];
188cdf0e10cSrcweir }
189cdf0e10cSrcweir inhalt[pos] = elem_;
190cdf0e10cSrcweir len++;
191cdf0e10cSrcweir }
192cdf0e10cSrcweir
193cdf0e10cSrcweir
194cdf0e10cSrcweir template <class XX>
195cdf0e10cSrcweir void
Remove(unsigned pos)196cdf0e10cSrcweir ST_List<XX>::Remove(unsigned pos)
197cdf0e10cSrcweir {
198cdf0e10cSrcweir if ( pos >= len )
199cdf0e10cSrcweir return;
200cdf0e10cSrcweir len--;
201cdf0e10cSrcweir for ( unsigned p = pos; p < len; ++p)
202cdf0e10cSrcweir {
203cdf0e10cSrcweir inhalt[p] = inhalt[p+1];
204cdf0e10cSrcweir }
205cdf0e10cSrcweir }
206cdf0e10cSrcweir
207cdf0e10cSrcweir
208cdf0e10cSrcweir // Protected:
209cdf0e10cSrcweir template <class XX>
210cdf0e10cSrcweir void
checkSize(unsigned newLength)211cdf0e10cSrcweir ST_List<XX>::checkSize(unsigned newLength)
212cdf0e10cSrcweir {
213cdf0e10cSrcweir // neuen Platzbedarf pruefen:
214cdf0e10cSrcweir unsigned newSpace = space();
215cdf0e10cSrcweir if (newLength >= newSpace)
216cdf0e10cSrcweir {
217cdf0e10cSrcweir if (!newSpace)
218cdf0e10cSrcweir newSpace = 1;
219cdf0e10cSrcweir const unsigned nBorder = 2000000000;
220cdf0e10cSrcweir while(newLength >= newSpace)
221cdf0e10cSrcweir {
222cdf0e10cSrcweir if (newSpace < nBorder)
223cdf0e10cSrcweir newSpace <<= 1;
224cdf0e10cSrcweir else
225cdf0e10cSrcweir {
226cdf0e10cSrcweir std::cerr << "List becomes too big" << std::endl;
227cdf0e10cSrcweir exit(1);
228cdf0e10cSrcweir }
229cdf0e10cSrcweir }
230cdf0e10cSrcweir }
231cdf0e10cSrcweir
232cdf0e10cSrcweir // Veraenderung ?:
233cdf0e10cSrcweir if (newSpace != space())
234cdf0e10cSrcweir alloc(newSpace,true);
235cdf0e10cSrcweir }
236cdf0e10cSrcweir
237cdf0e10cSrcweir template <class XX>
238cdf0e10cSrcweir void
alloc(unsigned newSpace,bool re)239cdf0e10cSrcweir ST_List<XX>::alloc( unsigned newSpace,
240cdf0e10cSrcweir bool re )
241cdf0e10cSrcweir {
242cdf0e10cSrcweir XX * pNew = new XX[newSpace];
243cdf0e10cSrcweir
244cdf0e10cSrcweir if (inhalt != 0)
245cdf0e10cSrcweir {
246cdf0e10cSrcweir if (re)
247cdf0e10cSrcweir {
248cdf0e10cSrcweir for (unsigned i = 0; i < len; ++i)
249cdf0e10cSrcweir {
250cdf0e10cSrcweir pNew[i] = inhalt[i];
251cdf0e10cSrcweir } // end for
252cdf0e10cSrcweir }
253cdf0e10cSrcweir delete [] inhalt;
254cdf0e10cSrcweir }
255cdf0e10cSrcweir
256cdf0e10cSrcweir inhalt = pNew;
257cdf0e10cSrcweir allocated = newSpace;
258cdf0e10cSrcweir }
259cdf0e10cSrcweir
260cdf0e10cSrcweir
261cdf0e10cSrcweir template <class XY>
DynamicList()262cdf0e10cSrcweir DynamicList<XY>::DynamicList()
263cdf0e10cSrcweir {
264cdf0e10cSrcweir }
265cdf0e10cSrcweir
266cdf0e10cSrcweir template <class XY>
DynamicList(const DynamicList<XY> & i_rList)267cdf0e10cSrcweir DynamicList<XY>::DynamicList( const DynamicList<XY> & i_rList )
268cdf0e10cSrcweir : ST_List< XY* >(i_rList)
269cdf0e10cSrcweir {
270cdf0e10cSrcweir for ( typename DynamicList<XY>::iterator it = this->begin();
271cdf0e10cSrcweir it != DynamicList<XY>::end();
272cdf0e10cSrcweir ++it )
273cdf0e10cSrcweir {
274cdf0e10cSrcweir // Copying the contents the pointers point at:
275cdf0e10cSrcweir (*it) = new XY( *(*it) );
276cdf0e10cSrcweir }
277cdf0e10cSrcweir }
278cdf0e10cSrcweir
279cdf0e10cSrcweir template <class XY>
~DynamicList()280cdf0e10cSrcweir DynamicList<XY>::~DynamicList()
281cdf0e10cSrcweir {
282cdf0e10cSrcweir this->erase_all();
283cdf0e10cSrcweir }
284cdf0e10cSrcweir
285cdf0e10cSrcweir template <class XY>
286cdf0e10cSrcweir DynamicList<XY> &
operator =(const DynamicList<XY> & i_rList)287cdf0e10cSrcweir DynamicList<XY>::operator=( const DynamicList<XY> & i_rList )
288cdf0e10cSrcweir {
289cdf0e10cSrcweir for ( typename DynamicList<XY>::const_iterator it = i_rList.begin();
290cdf0e10cSrcweir it != i_rList.end();
291cdf0e10cSrcweir ++it )
292cdf0e10cSrcweir {
293*7ee1d29cSAriel Constenla-Haile this->push_back( new XY(*(*it)) );
294cdf0e10cSrcweir }
295cdf0e10cSrcweir return *this;
296cdf0e10cSrcweir }
297cdf0e10cSrcweir
298cdf0e10cSrcweir
299cdf0e10cSrcweir template <class XY>
300cdf0e10cSrcweir void
Insert(unsigned pos,XY * const & elem_)301cdf0e10cSrcweir DynamicList<XY>::Insert(unsigned pos, XY * const & elem_)
302cdf0e10cSrcweir {
303cdf0e10cSrcweir if ( pos > this->len )
304cdf0e10cSrcweir return;
305cdf0e10cSrcweir
306*7ee1d29cSAriel Constenla-Haile this->checkSize(DynamicList<XY>::len+2);
307cdf0e10cSrcweir memmove( DynamicList<XY>::inhalt+pos+1, DynamicList<XY>::inhalt+pos, (DynamicList<XY>::len-pos) * sizeof(XY*) );
308cdf0e10cSrcweir this->inhalt[pos] = elem_;
309cdf0e10cSrcweir this->len++;
310cdf0e10cSrcweir }
311cdf0e10cSrcweir
312cdf0e10cSrcweir template <class XY>
313cdf0e10cSrcweir void
Remove(unsigned pos)314cdf0e10cSrcweir DynamicList<XY>::Remove( unsigned pos )
315cdf0e10cSrcweir {
316cdf0e10cSrcweir if (!this->is_valid_index(pos) )
317cdf0e10cSrcweir return;
318cdf0e10cSrcweir this->len--;
319cdf0e10cSrcweir delete DynamicList<XY>::inhalt[pos];
320cdf0e10cSrcweir memmove(DynamicList<XY>::inhalt+pos, DynamicList<XY>::inhalt+pos+1, (DynamicList<XY>::len-pos) * sizeof(XY*) );
321cdf0e10cSrcweir }
322cdf0e10cSrcweir
323cdf0e10cSrcweir
324cdf0e10cSrcweir
325cdf0e10cSrcweir #endif
326cdf0e10cSrcweir
327