1*dd7bc091SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*dd7bc091SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*dd7bc091SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*dd7bc091SAndrew Rist * distributed with this work for additional information 6*dd7bc091SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*dd7bc091SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*dd7bc091SAndrew Rist * "License"); you may not use this file except in compliance 9*dd7bc091SAndrew Rist * with the License. You may obtain a copy of the License at 10*dd7bc091SAndrew Rist * 11*dd7bc091SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12*dd7bc091SAndrew Rist * 13*dd7bc091SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*dd7bc091SAndrew Rist * software distributed under the License is distributed on an 15*dd7bc091SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*dd7bc091SAndrew Rist * KIND, either express or implied. See the License for the 17*dd7bc091SAndrew Rist * specific language governing permissions and limitations 18*dd7bc091SAndrew Rist * under the License. 19*dd7bc091SAndrew Rist * 20*dd7bc091SAndrew Rist *************************************************************/ 21*dd7bc091SAndrew Rist 22*dd7bc091SAndrew 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(); 40cdf0e10cSrcweir virtual ~List() { delete [] inhalt; } 41cdf0e10cSrcweir 42cdf0e10cSrcweir // OPERATORS 43cdf0e10cSrcweir const XX & operator[]( 44cdf0e10cSrcweir unsigned n) const 45cdf0e10cSrcweir { return elem(n); } 46cdf0e10cSrcweir XX & operator[]( 47cdf0e10cSrcweir unsigned n) 48cdf0e10cSrcweir { return elem(n); } 49cdf0e10cSrcweir // OPERATIONS 50cdf0e10cSrcweir void reserve( 51cdf0e10cSrcweir unsigned i_nSize ) 52cdf0e10cSrcweir { alloc(i_nSize,true); } 53cdf0e10cSrcweir virtual void insert( 54cdf0e10cSrcweir unsigned pos, 55cdf0e10cSrcweir const XX & elem ); 56cdf0e10cSrcweir void push_back( 57cdf0e10cSrcweir const XX & elem_) 58cdf0e10cSrcweir { insert(size(),elem_); } 59cdf0e10cSrcweir 60cdf0e10cSrcweir virtual void remove( 61cdf0e10cSrcweir unsigned pos ); 62cdf0e10cSrcweir void pop_back() { remove(size()-1); } 63cdf0e10cSrcweir void erase_all() { while (size()) remove(size()-1); } 64cdf0e10cSrcweir 65cdf0e10cSrcweir // INQUIRY 66cdf0e10cSrcweir const XX & front() const { return elem(0); } 67cdf0e10cSrcweir const XX & back() const { return elem(len-1); } 68cdf0e10cSrcweir 69cdf0e10cSrcweir unsigned size() const { return len; } 70cdf0e10cSrcweir unsigned space() const { return allocated; } 71cdf0e10cSrcweir bool is_valid_index( 72cdf0e10cSrcweir unsigned n) const 73cdf0e10cSrcweir { return n < len; } 74cdf0e10cSrcweir // ACCESS 75cdf0e10cSrcweir XX & front() { return elem(0); } 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 85cdf0e10cSrcweir const XX & elem( 86cdf0e10cSrcweir unsigned n ) const 87cdf0e10cSrcweir { return inhalt[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> 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 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 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 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 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> 215cdf0e10cSrcweir DynamicList<XY>::~DynamicList() 216cdf0e10cSrcweir { 217cdf0e10cSrcweir this->erase_all(); 218cdf0e10cSrcweir } 219cdf0e10cSrcweir 220cdf0e10cSrcweir template <class XY> 221cdf0e10cSrcweir void 222cdf0e10cSrcweir DynamicList<XY>::insert(unsigned pos, XY * const & elem_) 223cdf0e10cSrcweir { 224cdf0e10cSrcweir if ( pos > this->len ) 225cdf0e10cSrcweir return; 226cdf0e10cSrcweir 227cdf0e10cSrcweir 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 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