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 SOLTOOLS_ST_LIST_HXX 25 #define SOLTOOLS_ST_LIST_HXX 26 27 #include <string.h> 28 #include <iostream> 29 #include <stdlib.h> 30 31 template <class XX> 32 class ST_List /// Soltools-List. 33 { 34 public : 35 typedef XX * iterator; 36 typedef const XX * const_iterator; 37 38 // LIFECYCLE 39 ST_List(); 40 ST_List( 41 const ST_List<XX> & i_rList ); 42 virtual ~ST_List() { } 43 44 // OPERATORS 45 ST_List<XX> & operator=( 46 const ST_List<XX> & i_rList ); 47 48 const XX & operator[]( 49 unsigned n) const 50 { return elem(n); } 51 XX & operator[]( 52 unsigned n) 53 { return elem(n); } 54 // OPERATIONS 55 void reserve( 56 unsigned i_nSize ) 57 { alloc(i_nSize,true); } 58 void insert( 59 iterator i_aPos, 60 const XX & elem_ ) 61 { Insert(i_aPos-begin(), elem_); } 62 virtual void Insert( 63 unsigned pos, 64 const XX & elem ); 65 void push_back( 66 const XX & elem_) 67 { Insert(size(),elem_); } 68 void remove( 69 iterator i_aPos ) 70 { Remove(i_aPos-begin()); } 71 virtual void Remove( 72 unsigned pos ); 73 void pop_back() { Remove(size()-1); } 74 void erase_all() { while (size()) Remove(size()-1); } 75 76 // INQUIRY 77 const_iterator begin() const { return &inhalt[0]; } 78 const_iterator end() const { return &inhalt[len]; } 79 80 const XX & front() const { return elem(0); } 81 const XX & back() const { return elem(len-1); } 82 83 unsigned size() const { return len; } 84 unsigned space() const { return allocated; } 85 bool is_valid_index( 86 unsigned n) const 87 { return n < len; } 88 // ACCESS 89 iterator begin() { return &inhalt[0]; } 90 iterator end() { return &inhalt[len]; } 91 92 XX & front() { return elem(0); } 93 XX & back() { return elem(len-1); } 94 95 protected: 96 void checkSize( 97 unsigned newLength); 98 void alloc( 99 unsigned newSpace, 100 bool re = false ); 101 102 const XX & elem( 103 unsigned n ) const 104 { return inhalt[n]; } 105 XX & elem( 106 unsigned n ) 107 { return inhalt[n]; } 108 // DATA 109 XX * inhalt; 110 unsigned len; 111 unsigned allocated; 112 }; 113 114 115 116 template <class XY> 117 class DynamicList : public ST_List< XY* > 118 { 119 public: 120 DynamicList(); 121 DynamicList( 122 const DynamicList<XY> & 123 i_rList ); 124 virtual ~DynamicList(); /// Deletes all member pointers 125 126 DynamicList<XY> & operator=( 127 const DynamicList<XY> & 128 i_rList ); 129 130 virtual void Insert( 131 unsigned pos, 132 XY * const & elem ); 133 virtual void Remove( 134 unsigned pos ); 135 }; 136 137 138 139 template <class XX> 140 ST_List<XX>::ST_List() 141 : inhalt(0), 142 len(0), 143 allocated(0) 144 { 145 alloc(1); 146 } 147 148 template <class XX> 149 ST_List<XX>::ST_List( const ST_List<XX> & i_rList ) 150 : inhalt(0), 151 len(0), 152 allocated(0) 153 { 154 alloc(i_rList.size()); 155 156 for ( const_iterator it = i_rList.begin(); 157 it != i_rList.end(); 158 ++it ) 159 { 160 push_back(*it); 161 } 162 } 163 164 template <class XX> 165 ST_List<XX> & 166 ST_List<XX>::operator=( const ST_List<XX> & i_rList ) 167 { 168 for ( const_iterator it = i_rList.begin(); 169 it != i_rList.end(); 170 ++it ) 171 { 172 push_back(*it); 173 } 174 return *this; 175 } 176 177 template <class XX> 178 void 179 ST_List<XX>::Insert(unsigned pos, const XX & elem_) 180 { 181 if ( pos > len ) 182 return; 183 184 checkSize(len+2); 185 for ( unsigned p = len; p > pos; --p) 186 { 187 inhalt[p] = inhalt[p-1]; 188 } 189 inhalt[pos] = elem_; 190 len++; 191 } 192 193 194 template <class XX> 195 void 196 ST_List<XX>::Remove(unsigned pos) 197 { 198 if ( pos >= len ) 199 return; 200 len--; 201 for ( unsigned p = pos; p < len; ++p) 202 { 203 inhalt[p] = inhalt[p+1]; 204 } 205 } 206 207 208 // Protected: 209 template <class XX> 210 void 211 ST_List<XX>::checkSize(unsigned newLength) 212 { 213 // neuen Platzbedarf pruefen: 214 unsigned newSpace = space(); 215 if (newLength >= newSpace) 216 { 217 if (!newSpace) 218 newSpace = 1; 219 const unsigned nBorder = 2000000000; 220 while(newLength >= newSpace) 221 { 222 if (newSpace < nBorder) 223 newSpace <<= 1; 224 else 225 { 226 std::cerr << "List becomes too big" << std::endl; 227 exit(1); 228 } 229 } 230 } 231 232 // Veraenderung ?: 233 if (newSpace != space()) 234 alloc(newSpace,true); 235 } 236 237 template <class XX> 238 void 239 ST_List<XX>::alloc( unsigned newSpace, 240 bool re ) 241 { 242 XX * pNew = new XX[newSpace]; 243 244 if (inhalt != 0) 245 { 246 if (re) 247 { 248 for (unsigned i = 0; i < len; ++i) 249 { 250 pNew[i] = inhalt[i]; 251 } // end for 252 } 253 delete [] inhalt; 254 } 255 256 inhalt = pNew; 257 allocated = newSpace; 258 } 259 260 261 template <class XY> 262 DynamicList<XY>::DynamicList() 263 { 264 } 265 266 template <class XY> 267 DynamicList<XY>::DynamicList( const DynamicList<XY> & i_rList ) 268 : ST_List< XY* >(i_rList) 269 { 270 for ( typename DynamicList<XY>::iterator it = this->begin(); 271 it != DynamicList<XY>::end(); 272 ++it ) 273 { 274 // Copying the contents the pointers point at: 275 (*it) = new XY( *(*it) ); 276 } 277 } 278 279 template <class XY> 280 DynamicList<XY>::~DynamicList() 281 { 282 this->erase_all(); 283 } 284 285 template <class XY> 286 DynamicList<XY> & 287 DynamicList<XY>::operator=( const DynamicList<XY> & i_rList ) 288 { 289 for ( typename DynamicList<XY>::const_iterator it = i_rList.begin(); 290 it != i_rList.end(); 291 ++it ) 292 { 293 push_back( new XY(*(*it)) ); 294 } 295 return *this; 296 } 297 298 299 template <class XY> 300 void 301 DynamicList<XY>::Insert(unsigned pos, XY * const & elem_) 302 { 303 if ( pos > this->len ) 304 return; 305 306 checkSize(DynamicList<XY>::len+2); 307 memmove( DynamicList<XY>::inhalt+pos+1, DynamicList<XY>::inhalt+pos, (DynamicList<XY>::len-pos) * sizeof(XY*) ); 308 this->inhalt[pos] = elem_; 309 this->len++; 310 } 311 312 template <class XY> 313 void 314 DynamicList<XY>::Remove( unsigned pos ) 315 { 316 if (!this->is_valid_index(pos) ) 317 return; 318 this->len--; 319 delete DynamicList<XY>::inhalt[pos]; 320 memmove(DynamicList<XY>::inhalt+pos, DynamicList<XY>::inhalt+pos+1, (DynamicList<XY>::len-pos) * sizeof(XY*) ); 321 } 322 323 324 325 #endif 326 327