/ray/src/lib/tl/tlarrayheap.h

Go to the documentation of this file.

/*
 * lib/tl/tlarrayheap.h 
 * 
 * Complete implementation of heap template (array-based heap). 
 * 
 * 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_ArrayHeap_H_
#define _TemplateLibrary_ArrayHeap_H_ 1

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

#include <lib/tl/tlarray.h>


template<typename T,typename _OP=TLDefaultOperators_CDT<T> >class TLArrayHeap : 
    private TLArray<T,_OP>
{
    public:
        // Access to operator template: 
        using TLArray<T,_OP>::OP;
        
    private:
        using TLArray<T,_OP>::nelem;
        using TLArray<T,_OP>::asize;
        using TLArray<T,_OP>::_free;
        using TLArray<T,_OP>::_upsize1;
        
        inline T &heap(size_t idx)
            {  return(TLArray<T,_OP>::array(idx));  }
        inline T *heapP(size_t idx)
            {  return(TLArray<T,_OP>::arrayP(idx));  }
        
        void _realloc(size_t new_asize)
        {
            // Need 1 special extra element: [0]. 
            char *new_heap=(char*)OP.realloc(TLArray<T,_OP>::_array,
                (new_asize+1)*OP.size());
            TLArray<T,_OP>::_array=new_heap;  asize=new_asize;
        }
        void _clearall()
        {
            // NOTE!! This is different in TLArray!!
            if(!OP.pdt)  for(size_t i=nelem; i; --i)  OP.clr(heapP(i));
            nelem=0;
        }
        
        void _UpHeap(size_t idx)  // internal idx
        {
            // Store temporary in [0]: 
            OP.ini(heapP(0),heap(idx));
            while(idx>1 && OP.le(heap(idx/2),heap(0)))
            {  OP.ass(heap(idx),heap(idx/2));  idx/=2;  }
            OP.ass(heap(idx),heap(0));  OP.clr(heapP(0));
        }
        
        void _DownHeap(size_t idx)  // internal idx
        {
            size_t j,e=nelem/2;
            // Store temporary in [0]: 
            OP.ini(heapP(0),heap(idx));
            while(idx<=e)
            {
                j=idx+idx;
                if(j<nelem && OP.lt(heap(j),heap(j+1)))  ++j;
                if(OP.le(heap(j),heap(0)))  break;
                OP.ass(heap(idx),heap(j));  idx=j;
            }
            OP.ass(heap(idx),heap(0));  OP.clr(heapP(0));
        }
        
        template<typename K>size_t _RecSearch(const K &key,size_t idx)
        {
            // Search element in [idx], then in both subtrees (if needed). 
            if(OP.eq(heap(idx),key))  return(idx);
            idx+=idx;  size_t res=0;  if(idx>nelem)  return(res);
            if(OP.ge(heap(idx),key))  res=_RecSearch(key,idx);
            if(!res && ++idx<=nelem && OP.ge(heap(idx),key))
            {  res=_RecSearch(key,idx);  }
            return(res);
        }
        
        template<typename K>inline size_t _LinSearch(const K &key)
        {
            for(size_t i=1; i<=nelem; i++)
                if(OP.eq(heap(i),key))  return(i);
            return(0);
        }
        
        void _ReHeap(size_t /*internal*/idx,int size_change=0)  // internal idx
        {
            // This implementation could be optimized. 
            if(size_change<=0)  _DownHeap(idx);
            if(size_change>=0)  _UpHeap(idx);
        }
        
        void _RemoveIdx(size_t idx,T *e=NULL)
        {
            if(e)  OP.ass(*e,heap(idx));
            if(nelem==idx)  {  OP.clr(heapP(nelem--));  return;  }
            OP.ass(heap(idx),heap(nelem));  OP.clr(heapP(nelem--));
            _ReHeap(idx);
        }
        
        TLArrayHeap(const TLArrayHeap &);
        void operator=(const TLArrayHeap &);
    public:
        TLArrayHeap(const _OP &op=_OP()) : TLArray<T,_OP>(op)  {}
        ~TLArrayHeap()
            {  _clearall();  _free();   }  // NOTE: OUR version of _clearall()
        
        #if 0   /* See using directives below. */

        inline bool IsEmpty() const
            {  return(TLArray<T,_OP>::IsEmpty());  }
        
        inline size_t NElem() const
            {  return(TLArray<T,_OP>::NElem());  }
        #else

        using TLArray<T,_OP>::IsEmpty;
        using TLArray<T,_OP>::NElem;
        #endif
        
        inline T &operator[](size_t idx)
            {  return(heap(idx+1 /* <-- Correct! */));  }
        inline const T &operator[](size_t idx) const
            {  return(heap(idx+1 /* <-- Correct! */));  }
        
        void clear(bool keep_memory=0)
        {  _clearall();  TLArray<T,_OP>::clear(keep_memory);  } // OUR version!!
        
        inline T *first()  {  return(nelem ? heapP(1) : NULL);  }
        inline const T *first() const  {  return(nelem ? heapP(1) : NULL);  }
        
        inline void DownHeapFirst()
            {  if(nelem>1) _DownHeap(1);   }
        
        inline void ReHeap(size_t idx,int size_change=0)
            {  if(idx<nelem)  _ReHeap(idx+1,size_change);  }
        
        void insert(const T &e)
            {  _upsize1();  OP.ini(heapP(++nelem),e);  _UpHeap(nelem);  }
        
        int ReplaceFirst(const T &e)
        {
            if(!nelem) return(1);
            OP.ass(heap(1),e);  _DownHeap(1);  return(0);
        }
        
        int PopFirst(T *e=NULL)
        {
            if(!nelem)  return(1);
            if(e)  OP.ass(*e,heap(1));
            if(nelem>1)  OP.ass(heap(1),heap(nelem));
            OP.clr(heapP(nelem--));  _DownHeap(1);  return(0);
        }
        
        template<typename K>inline ssize_t LinSearch(const K &key)
            {  return((ssize_t)_LinSearch(key)-1);  }
        
        template<typename K>inline ssize_t RecSearch(const K &key)
            {  return(nelem ? ((ssize_t)_RecSearch(key,1))-1 : -1);  }
        
        template<typename K>int remove(const K &key,T *e=NULL)
        {
            size_t idx=_LinSearch(key);  if(!idx)  return(1);  // CORRECT
            _RemoveIdx(idx,e);  return(0);
        }
        
        int RemoveIdx(size_t idx,T *e=NULL)
            {  if(idx>=nelem)  return(1);  _RemoveIdx(idx+1,e);  return(0);  }
        
        template<typename K>int replace(const K &key,const T &new_ent)
        {
            size_t idx=_LinSearch(key);  if(!idx)  return(1);  // CORRECT
            OP.ass(heap(idx),new_ent);  _ReHeap(idx);  return(0);
        }
        
        int ReplaceIdx(size_t idx,const T &new_ent)
        {
            if(idx>=nelem)  return(1);  ++idx;
            OP.ass(heap(idx),new_ent);  _ReHeap(idx);  return(0);
        }
        
        size_t CheckHeap()
        {
            size_t nerr=0;
            for(size_t i=1; ; i++)
            {
                size_t c=i+i;  if(c>nelem)  break;
                if(OP.lt(heap(i),heap(c)))  ++nerr;
                if(++c>nelem)  break;
                if(OP.lt(heap(i),heap(c)))  ++nerr;
            }
            return(nerr);
        }
};

#endif  /* _TemplateLibrary_ArrayHeap_H_ */

---