/ray/src/lib/tl/tlsortedarray.h

Go to the documentation of this file.

/*
 * lib/tl/tlsortedarray.h 
 * 
 * Implementation of a sorted array template. 
 * 
 * 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_SortedArray_H_
#define _TemplateLibrary_SortedArray_H_ 1

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

#include <lib/tl/tlarray.h>



template<typename T,typename _OP=TLDefaultOperators_CDT<T> >
    class TLSortedArray : 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>::array;
        using TLArray<T,_OP>::arrayP;
        using TLArray<T,_OP>::_upsize1;
        
        TLSortedArray(const TLSortedArray &);
        void operator=(const TLSortedArray &);
    public:
        TLSortedArray(const _OP &op=_OP()) : TLArray<T,_OP>(op)  {}
        ~TLSortedArray()  {}
        
        using TLArray<T,_OP>::IsEmpty;
        using TLArray<T,_OP>::NElem;
        
        using TLArray<T,_OP>::operator[];
        
        using TLArray<T,_OP>::clear();
        
        inline T *last()  {  return(nelem ? arrayP(nelem-1) : NULL);  }
        inline const T *last() const { return(nelem ? arrayP(nelem-1) : NULL); }
        
        template<typename K>ssize_t GetInsertIdx(const K &ent,int allow_dup)
        {
            if(!nelem || OP.gt(array(0),ent))  return(0);
            if(OP.lt(array(nelem-1),ent))  return(nelem);
            size_t a=0,b=nelem-1;
            if(!allow_dup)  {
                while(b>a)
                {  size_t m=(a+b)/2;  OP.lt(array(m),ent) ? a=m : b=m;  }
                return(OP.eq(array(a),ent) ? -1 : a);  }
            if(allow_dup<0) while(b>a)
            {  size_t m=(a+b)/2;  OP.lt(array(m),ent) ? a=m : b=m;  }
            else while(b>a)
            {  size_t m=(a+b)/2;  OP.gt(array(m),ent) ? b=m : a=m;  }
            return(a);
        }
        
        int insert(const T &ent,int allow_dup,ssize_t *ret_idx=NULL)
        {
            ssize_t idx=GetInsertIdx(ent,allow_dup);
            if(idx<0)  return(1);
            TLArray<T,_OP>::insert(ent,idx);
            if(ret_idx) *ret_idx=idx;  return(0);
        }
        
        ssize_t ReOrder(size_t idx,int allow_dup)
        {
            if(idx>=nelem)  return(-2);
            ssize_t newidx=GetInsertIdx(array(idx),allow_dup);
            if(newidx<0)  {  Remove(idx);  return(-3);  }
            if((size_t)newidx==idx)  return(idx);
            T tmp(array(idx));
            if((size_t)newidx>idx)
                 for(ssize_t i=idx; i<newidx; i++) OP.ass(array(i),array(i+1));
            else for(ssize_t i=idx; i>newidx; i--) OP.ass(array(i),array(i-1));
            OP.ass(array(newidx),tmp);  return(newidx);
        }
        
        void ReOrder()
        {
            if(nelem<1)  return;  // 1 element is always sorted :)
            T tmp;
            for(size_t i=1; i<nelem; i++)
            {
                size_t j1=i-1;
                if(OP.le(array(j1),array(i)))  continue;
                OP.ass(tmp,array(i));
                size_t j=i;
                do
                {  OP.ass(array(j),array(j1));  if(!j) break;  j=j1--;  }
                while(OP.lt(tmp,array(j1)));
                OP.ass(array(j),tmp);
            }
        }
        
        template<typename K>ssize_t search(const K &key)
            {  return(TLBinarySearch(_array,nelem,key,OP));  }
        
        using TLArray<T,_OP>::remove;
        
        template<typename K>ssize_t remove(const K &key)
        {
            if(!nelem || OP.gt(array(0),key) || 
                OP.lt(array(nelem-1),key))  return(0);
            size_t a=0,b=nelem-1;
            while(b>a)
            {  size_t m=(a+b)/2;  OP.lt(array(m),key) ? a=m : b=m;  }
            if(a+1<nelem && OP.eq(array(a+1),key))  {
                size_t a1=a;  b=nelem-1;
                while(b>a1)
                { size_t m=(a1+b)/2; OP.gt(array(m),key) ? b=m : a1=m; }
            }
            // Remove entries a..b. 
            size_t delta=b-a+1;
            nelem-=delta;
            for(size_t i=a; i<nelem; i++)  OP.ass(array(i),array(i+delta));
            if(!OP.pdt) for(size_t i=nelem+delta; i-->nelem;) OP.clr(arrayP(i));
            _downsize();  return(delta);
        }
        
        size_t CheckOrder()
        {
            size_t nerr=0;
            for(size_t i=1; i<nelem; i++)
            {  if(OP.gt(array(i),array(i+1)))  ++nerr;  }
            return(nerr);
        }
};

#endif  /* _TemplateLibrary_SortedArray_H_ */

---