| /************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *************************************************************/ |
| |
| |
| |
| #ifndef __LISTEN_123456__ |
| #define __LISTEN_123456__ |
| |
| #include <string.h> |
| #include <iostream> |
| #include <stdlib.h> |
| |
| template <class XX> |
| class List |
| { |
| public : |
| typedef XX * iterator; |
| typedef const XX * const_iterator; |
| |
| // LIFECYCLE |
| List(); |
| virtual ~List() { delete [] inhalt; } |
| |
| // OPERATORS |
| const XX & operator[]( |
| unsigned n) const |
| { return elem(n); } |
| XX & operator[]( |
| unsigned n) |
| { return elem(n); } |
| // OPERATIONS |
| void reserve( |
| unsigned i_nSize ) |
| { alloc(i_nSize,true); } |
| virtual void insert( |
| unsigned pos, |
| const XX & elem ); |
| void push_back( |
| const XX & elem_) |
| { insert(size(),elem_); } |
| |
| virtual void remove( |
| unsigned pos ); |
| void pop_back() { remove(size()-1); } |
| void erase_all() { while (size()) remove(size()-1); } |
| |
| // INQUIRY |
| const XX & front() const { return elem(0); } |
| const XX & back() const { return elem(len-1); } |
| |
| unsigned size() const { return len; } |
| unsigned space() const { return allocated; } |
| bool is_valid_index( |
| unsigned n) const |
| { return n < len; } |
| // ACCESS |
| XX & front() { return elem(0); } |
| XX & back() { return elem(len-1); } |
| |
| protected: |
| void checkSize( |
| unsigned newLength); |
| void alloc( |
| unsigned newSpace, |
| bool re = false ); |
| |
| const XX & elem( |
| unsigned n ) const |
| { return inhalt[n]; } |
| XX & elem( |
| unsigned n ) |
| { return inhalt[n]; } |
| // DATA |
| XX * inhalt; |
| unsigned len; |
| unsigned allocated; |
| |
| private: |
| // forbidden functions |
| List(const List<XX> & L); |
| List<XX> & operator=( |
| const List<XX> & L); |
| |
| }; |
| |
| template <class XY> |
| class DynamicList : public List<XY*> |
| { |
| public: |
| virtual ~DynamicList(); |
| |
| virtual void insert( |
| unsigned pos, |
| XY * const & elem ); |
| virtual void remove( |
| unsigned pos ); |
| }; |
| |
| |
| |
| template <class XX> |
| List<XX>::List() |
| : inhalt(0), |
| len(0), |
| allocated(0) |
| |
| { |
| alloc(1); |
| } |
| |
| |
| template <class XX> |
| void |
| List<XX>::insert(unsigned pos, const XX & elem_) |
| { |
| if ( pos > len ) |
| return; |
| |
| checkSize(len+2); |
| for ( unsigned p = len; p > pos; --p) |
| { |
| inhalt[p] = inhalt[p-1]; |
| } |
| inhalt[pos] = elem_; |
| len++; |
| } |
| |
| |
| template <class XX> |
| void |
| List<XX>::remove(unsigned pos) |
| { |
| if ( pos >= len ) |
| return; |
| len--; |
| for ( unsigned p = pos; p < len; ++p) |
| { |
| inhalt[p] = inhalt[p+1]; |
| } |
| } |
| |
| |
| // Protected: |
| template <class XX> |
| void |
| List<XX>::checkSize(unsigned newLength) |
| { |
| // neuen Platzbedarf pruefen: |
| unsigned newSpace = space(); |
| if (newLength > newSpace) |
| { |
| if (!newSpace) |
| newSpace = 1; |
| const unsigned nBorder = 65536 / 2; |
| while(newLength > newSpace) |
| { |
| if (newSpace < nBorder) |
| newSpace <<= 1; |
| else |
| { |
| std::cerr << "List becomes too big" << std::endl; |
| exit(1); |
| } |
| } |
| } |
| |
| // Veraenderung ?: |
| if (newSpace != space()) |
| alloc(newSpace,true); |
| } |
| |
| template <class XX> |
| void |
| List<XX>::alloc( unsigned newSpace, |
| bool re ) |
| { |
| XX * pNew = new XX[newSpace]; |
| |
| if (inhalt != 0) |
| { |
| if (re) |
| { |
| for (unsigned i = 0; i < len; ++i) |
| { |
| pNew[i] = inhalt[i]; |
| } // end for |
| } |
| delete [] inhalt; |
| } |
| |
| inhalt = pNew; |
| allocated = newSpace; |
| } |
| |
| |
| template <class XY> |
| DynamicList<XY>::~DynamicList() |
| { |
| this->erase_all(); |
| } |
| |
| template <class XY> |
| void |
| DynamicList<XY>::insert(unsigned pos, XY * const & elem_) |
| { |
| if ( pos > this->len ) |
| return; |
| |
| this->checkSize(this->len+2); |
| memmove(this->inhalt[pos+1], this->inhalt[pos], (this->len-pos) * sizeof(XY*) ); |
| this->inhalt[pos] = elem_; |
| this->len++; |
| } |
| |
| template <class XY> |
| void |
| DynamicList<XY>::remove( unsigned pos ) |
| { |
| if (!this->is_valid_index(pos) ) |
| return; |
| this->len--; |
| delete this->inhalt[pos]; |
| memmove(this->inhalt[pos], this->inhalt[pos+1], (this->len-pos) * sizeof(XY*) ); |
| } |
| |
| |
| |
| #endif |
| |