MNArrayList.h

Go to the documentation of this file.

/* Copyright (C) 2000 KOM/Darmstadt University of Technology
 *
 * You are allowed to use all other parts of the code under the following terms:
 *
 * For non-commercial use, code may be used in unmodified form provided
 * that this copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This software is provided "as is" and without any express or implied
 * warranties, including, without limitation, the implied warranty of
 * fitness for a particular purpose.
 *
 * The code may be subjected to the GNU General Public License, Version 2,
 * and re-distributed under the terms of this license.
 * As a special exception, permission is granted to link this code
 * with the Qt library and distribute executables, as long as you
 * follow the requirements of the GNU GPL in regard to all of the
 * software in the executable aside from Qt.
 *
 * Commercial use other than under the terms of the GNU General Public
 * License is allowed only after express negotiation of conditions
 * with the authors.
 */
#ifndef MN_ARRAY_LIST_H
#define MN_ARRAY_LIST_H

#include <assert.h>
#include <stdio.h>
#include <sys/types.h>
#include <string.h>
#include <strings.h>

#include "MNValid.h"

template <class T> class MNArrayList
{
    DECLARE_VALID
private:
    size_t _use_size;
    size_t _real_size;
    T*     _array;

    typedef T Item;

    void clone( const MNArrayList<T>& orig ) {
        if( _array ) delete [] _array;

        _use_size  = orig._use_size;
        _real_size = orig._real_size;
        _array     = new Item[ _real_size ];
        memcpy ( _array, orig._array, _real_size*sizeof(Item) );
    }

    void grow( ) {
        if ( _real_size == 0 )
        {
            _real_size = 10;
            _array     = new Item[ _real_size ];
            memset ( _array, 0, _real_size*sizeof(Item) );
        } else {
            Item* _old_array = _array;
            _real_size += 10;
            _array           = new Item[ _real_size ];
            memcpy ( _array, _old_array, (_real_size-10)*sizeof(Item) );
            delete [] _old_array;
        }
    }

    void private_del( size_t it ) {
        size_t rest = _use_size - it;
        if ( rest > 1 )
        {
            memmove( &_array[it],
                     &_array[it+1],
                     (rest-1)*sizeof(Item) );
        }
        // else nothing to do, it pointed to the last item
        _use_size--;
    }

public:
    typedef int Iterator;

    MNArrayList() {
        _use_size       = 0;
        _real_size = 0;
        _array          = NULL;
        // _array = new Item[ x * y ];
        // memset ( _array, '\0', x*y*sizeof(Item) );
        MAKE_VALID
    }

    MNArrayList( const MNArrayList<T>& orig ) {
        _use_size       = 0;
        _real_size = 0;
        _array          = NULL;
        clone(orig);
        MAKE_VALID
    }

    ~MNArrayList( ) {
        delete [] _array;
        MAKE_INVALID
    }

    inline T& operator()(int idx) {
        CHECK_VALID
        assert( 0 <= idx );
        assert( (size_t)idx < _use_size);
        return _array[ idx ];
    }

    inline const T& operator()(int idx) const {
        CHECK_VALID
        assert( 0 <= idx );
        assert( (size_t)idx < _use_size);
        return _array[ idx ];
    }

    MNArrayList<T>& operator=( const MNArrayList<T>& orig ) {
        clone(orig);
        return *this;
    }


    inline size_t size() const {
        CHECK_VALID
        return _use_size;
    }

    inline T* array() const {
        CHECK_VALID
        return _array;
    }

    void append( const Item& t ) {
        CHECK_VALID
        if ( _use_size == _real_size ) grow();
        _array[_use_size] = t;
        _use_size++;
    }

    bool empty() const {
        CHECK_VALID
        return ( _use_size==0 );
    }

    Iterator first() {
        CHECK_VALID
        return 0;
    }

    const T& inf( size_t it ) const {
        CHECK_VALID
        assert( it < _use_size );
        return _array[it];
    }

    const T& inf( Iterator it ) const {
        CHECK_VALID
        assert( it >= 0 );
        assert( (size_t)it < _use_size );
        return _array[it];
    }

    Iterator next( Iterator& it ) {
        CHECK_VALID
        assert( it >= 0 );
        it++;
        return it;
    }

    void del( size_t it ) {
        CHECK_VALID
        assert( (size_t)it < _use_size );
        private_del(it);
    }

    void del( Iterator& it ) {
        CHECK_VALID
        assert( it >= 0 );
        assert( (size_t)it < _use_size );
        private_del( (size_t&)it );

        // invalidate the iterator (inf,next,del will zap)
        it = -1;
    }

    void clear() {
        _use_size = 0;
    }
};

#endif /* MN_ARRAY_LIST_H */

---