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(); 40 virtual ~List() { delete [] inhalt; } 41 42 // OPERATORS 43 const XX & operator[]( 44 unsigned n) const 45 { return elem(n); } 46 XX & operator[]( 47 unsigned n) 48 { return elem(n); } 49 // OPERATIONS 50 void reserve( 51 unsigned i_nSize ) 52 { alloc(i_nSize,true); } 53 virtual void insert( 54 unsigned pos, 55 const XX & elem ); 56 void push_back( 57 const XX & elem_) 58 { insert(size(),elem_); } 59 60 virtual void remove( 61 unsigned pos ); 62 void pop_back() { remove(size()-1); } 63 void erase_all() { while (size()) remove(size()-1); } 64 65 // INQUIRY 66 const XX & front() const { return elem(0); } 67 const XX & back() const { return elem(len-1); } 68 69 unsigned size() const { return len; } 70 unsigned space() const { return allocated; } 71 bool is_valid_index( 72 unsigned n) const 73 { return n < len; } 74 // ACCESS 75 XX & front() { return elem(0); } 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 85 const XX & elem( 86 unsigned n ) const 87 { return inhalt[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> 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 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 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 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 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> 215 DynamicList<XY>::~DynamicList() 216 { 217 this->erase_all(); 218 } 219 220 template <class XY> 221 void 222 DynamicList<XY>::insert(unsigned pos, XY * const & elem_) 223 { 224 if ( pos > this->len ) 225 return; 226 227 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 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