/ray/src/lib/tl/tlarray.h

Go to the documentation of this file.

/*
 * lib/tl/tlarray.h 
 * 
 * Implementation of a dynamic array template which can also be used 
 * as stack. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_Array_H_
#define _TemplateLibrary_Array_H_ 1

#include <lib/sconfig.h>    /* MUST be first */

#include <lib/salloc.h>
#include <lib/tl/binsearch.h>


template<typename T,typename _OP=TLDefaultOperators_CDT<T> >class TLArray
{
    protected:
        // The actual array data fields: 
        size_t asize;   
        size_t nelem;   
        char *_array;   
        
    public:
        _OP OP;
        
    protected:
        inline T &array(size_t idx)
            {  return(*(T*)(_array+idx*OP.size()));  }
        inline T *arrayP(size_t idx)
            {  return((T*)(_array+idx*OP.size()));  }
        
        virtual void _realloc(size_t new_asize)
        {
            char *new_array=(char*)OP.realloc(_array,new_asize*OP.size());
            _array=new_array;  asize=new_asize;
        }
        void _free()
        {
            if(_array)
            {  OP.free(_array);  _array=NULL;  }
        }
        size_t _get_downsize()
        {
            if(asize>512) return((asize-nelem)>512 ? asize-256 : asize);
            if(nelem<=16)  return(16);
            return(asize-nelem>3*asize/4 ? asize-asize/2 : asize);
        }
        void _downsize()
        {
            size_t newsize=_get_downsize();
            if(newsize!=asize)  _realloc(newsize);
        }
        inline void _upsize1()
        {
            if(nelem>=asize)  _realloc(/*new_asize=*/asize>512 ? 
                (asize+512) : (asize ? asize*2 : 16));
        }
        void _clearall()
        {
            if(!OP.pdt)  for(size_t i=nelem; i--;)  OP.clr(arrayP(i));
            nelem=0;
        }
        
    private:
        TLArray(const TLArray &);
        void operator=(const TLArray &);
    public:
        TLArray(const _OP &op=_OP()) : asize(0),nelem(0),_array(NULL),OP(op) {}
        virtual ~TLArray()
            {  _clearall();  _free();  }
        
        inline bool IsEmpty() const
            {  return(!nelem);  }
        
        inline size_t NElem() const
            {  return(nelem);  }
        
        inline T &operator[](size_t idx)
            {  return(array(idx));  }
        inline const T &operator[](size_t idx) const
            {  return(array(idx));  }
        
        void clear(bool keep_memory=0)
            {  _clearall();  if(!keep_memory && asize>32)  _free();  }
        
        int insert(const T &e,size_t idx)
        {
            if(idx>nelem)  return(-2);  /* CORRECT! */
            _upsize1();
            if(idx==nelem)  {  OP.ini(arrayP(nelem++),e);  return(0);  }
            size_t i=nelem-1;  OP.ini(arrayP(nelem++),array(i));
            for(; i>idx; i--)  OP.ass(array(i),array(i-1));
            OP.ass(array(idx),e);  return(0);
        }
        
        int remove(size_t idx)
        {
            if(idx>=nelem)  return(-2);  --nelem;
            for(size_t i=idx; i<nelem; i++)  OP.ass(array(i),array(i+1));
            OP.clr(arrayP(nelem));  _downsize();  return(0);
        }
        
        inline int assign(const T &e,size_t idx)
            {  if(idx>=nelem)  return(-2);  OP.ass(array(idx),e);  return(0);  }
        
        template<typename K>inline ssize_t LinSearch(const K &key,size_t sidx=0)
        {
            for(size_t i=sidx; i<nelem; i++)
                if(OP.eq(array(i),key))  return(i);
            return(-1);
        }
        
        template<typename K>inline ssize_t BinSearch(const K &key)
            {  return(TLBinarySearch(_array,nelem,key,OP));  }
};

#endif  /* _TemplateLibrary_Array_H_ */

---