• Skip to content
• Skip to link menu

KDE 3.5 API Reference

• KDE API Reference
• API Reference

• Sitemap
• Contact Us

 

kviewshell

Arrays.h

Go to the documentation of this file.

//C-  -*- C++ -*-
//C- -------------------------------------------------------------------
//C- DjVuLibre-3.5
//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
//C- Copyright (c) 2001  AT&T
//C-
//C- This software is subject to, and may be distributed under, the
//C- GNU General Public License, Version 2. The license should have
//C- accompanied the software or you may obtain a copy of the license
//C- from the Free Software Foundation at http://www.fsf.org .
//C-
//C- This program is distributed in the hope that it will be useful,
//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//C- GNU General Public License for more details.
//C- 
//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library
//C- distributed by Lizardtech Software.  On July 19th 2002, Lizardtech 
//C- Software authorized us to replace the original DjVu(r) Reference 
//C- Library notice by the following text (see doc/lizard2002.djvu):
//C-
//C-  ------------------------------------------------------------------
//C- | DjVu (r) Reference Library (v. 3.5)
//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
//C- | The DjVu Reference Library is protected by U.S. Pat. No.
//C- | 6,058,214 and patents pending.
//C- |
//C- | This software is subject to, and may be distributed under, the
//C- | GNU General Public License, Version 2. The license should have
//C- | accompanied the software or you may obtain a copy of the license
//C- | from the Free Software Foundation at http://www.fsf.org .
//C- |
//C- | The computer code originally released by LizardTech under this
//C- | license and unmodified by other parties is deemed "the LIZARDTECH
//C- | ORIGINAL CODE."  Subject to any third party intellectual property
//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 
//C- | non-exclusive license to make, use, sell, or otherwise dispose of 
//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 
//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 
//C- | General Public License.   This grant only confers the right to 
//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 
//C- | the extent such infringement is reasonably necessary to enable 
//C- | recipient to make, have made, practice, sell, or otherwise dispose 
//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 
//C- | any greater extent that may be necessary to utilize further 
//C- | modifications or combinations.
//C- |
//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
//C- +------------------------------------------------------------------
// 
// $Id: Arrays.h,v 1.10 2004/05/13 15:16:34 leonb Exp $
// $Name: release_3_5_15 $

#ifndef _ARRAYS_H_
#define _ARRAYS_H_
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#if NEED_GNUG_PRAGMAS
# pragma interface
#endif

#include "GException.h"
#include "GSmartPointer.h"
#include <string.h>

#ifdef HAVE_NAMESPACES
namespace DJVU {
# ifdef NOT_DEFINED // Just to fool emacs c++ mode
}
#endif
#endif




// Auxiliary classes: Will be used in place of GPBase and GPEnabled objects
class _ArrayRep
{
   friend class _ArrayBase;
public:
   _ArrayRep(void) : count(0) {}
   _ArrayRep(const _ArrayRep &) {}
   virtual ~_ArrayRep(void) {}

   _ArrayRep & operator=(const _ArrayRep &) { return *this; }

   int      get_count(void) const { return count; }
private:
   int      count;

   void     ref(void) { count++; }
   void     unref(void) { if (--count==0) delete this; }
};

class _ArrayBase
{
public:
   _ArrayBase(void) : rep(0) {}
   _ArrayBase(const _ArrayBase & ab) : rep(0)
   {
      if (ab.rep) ab.rep->ref();
      rep=ab.rep;
   }
   _ArrayBase(_ArrayRep * ar) : rep(0)
   {
      if (ar) ar->ref();
      rep=ar;
   }
   virtual ~_ArrayBase(void)
   {
      if (rep) { rep->unref(); rep=0; }
   }

   _ArrayRep *  get(void) const { return rep; }
   _ArrayBase & assign(_ArrayRep * ar)
   {
      if (ar) ar->ref();
      if (rep) rep->unref();
      rep=ar;
      return *this;
   }
   _ArrayBase & operator=(const _ArrayBase & ab) { return assign(ab.rep); }
   bool     operator==(const _ArrayBase & ab) { return rep==ab.rep; }
private:
   _ArrayRep    * rep;
};

// Internal "Array repository" holding the pointer to the actual data,
// data bounds, etc. It copes with data elements with the help of five
// static functions which pointers are supposed to be passed to the
// constructor.
class ArrayRep : public _ArrayRep
{
public:
   ArrayRep(int elsize,
        void (* xdestroy)(void *, int, int),
        void (* xinit1)(void *, int, int),
        void (* xinit2)(void *, int, int, const void *, int, int),
        void (* xcopy)(void *, int, int, const void *, int, int),
        void (* xinsert)(void *, int, int, const void *, int));
   ArrayRep(int elsize,
        void (* xdestroy)(void *, int, int),
        void (* xinit1)(void *, int, int),
        void (* xinit2)(void *, int, int, const void *, int, int),
        void (* xcopy)(void *, int, int, const void *, int, int),
        void (* xinsert)(void *, int, int, const void *, int),
        int hibound);
   ArrayRep(int elsize,
        void (* xdestroy)(void *, int, int),
        void (* xinit1)(void *, int, int),
        void (* xinit2)(void *, int, int, const void *, int, int),
        void (* xcopy)(void *, int, int, const void *, int, int),
        void (* xinsert)(void *, int, int, const void *, int),
        int lobound, int hibound);
   ArrayRep(const ArrayRep & rep);
   
   virtual ~ArrayRep();
   
      // Following is the standard interface to DArray. DArray will call these
      // functions to access data.
   int      size() const;
   int      lbound() const;
   int      hbound() const;

   void     empty();
   void     touch(int n);
   void     resize(int lobound, int hibound);
   void     shift(int disp);
   void     del(int n, unsigned int howmany=1);

      // ins() is an exception. It does it job only partially.
      // The derived class is supposed to finish insertion.
   void     ins(int n, const void * what, unsigned int howmany);

   ArrayRep &   operator=(const ArrayRep & rep);

      // All data is public because DArray... classes will need access to it
   void     *data;
   int      minlo;
   int      maxhi;
   int      lobound;
   int      hibound;
   int      elsize;
private:
      // These functions can't be virtual as they're called from
      // constructors and destructors :((
      // destroy(): should destroy elements in data[] array from 'lo' to 'hi'
   void     (* destroy)(void * data, int lo, int hi);
      // init1(): should initialize elements in data[] from 'lo' to 'hi'
      // using default constructors
   void     (* init1)(void * data, int lo, int hi);
      // init2(): should initialize elements in data[] from 'lo' to 'hi'
      // using corresponding elements from src[] (copy constructor)
   void     (* init2)(void * data, int lo, int hi,
              const void * src, int src_lo, int src_hi);
      // copy(): should copy elements from src[] to dst[] (copy operator)
   void     (* copy)(void * dst, int dst_lo, int dst_hi,
             const void * src, int src_lo, int src_hi);
      // insert(): should insert '*what' at position 'where' 'howmany' times
      // into array data[] having 'els' initialized elements
   void     (* insert)(void * data, int els, int where, const void * what,
               int howmany);
};

inline int
ArrayRep::size() const
{
   return hibound - lobound + 1;
}

inline int
ArrayRep::lbound() const
{
  return lobound;
}

inline int
ArrayRep::hbound() const
{
  return hibound;
}

inline void
ArrayRep::empty()
{
  resize(0, -1);
}

inline void
ArrayRep::touch(int n)
{
   if (hibound < lobound)
   {
      resize(n,n);
   } else
   {
      int nlo = lobound;
      int nhi = hibound;
      if (n < nlo) nlo = n;
      if (n > nhi) nhi = n;
      resize(nlo, nhi);
   }
}

class ArrayBase : protected _ArrayBase
{
protected:
   void     check(void);
   void     detach(void);

   ArrayBase(void) {};
public:
   int      size() const;
   int      lbound() const;
   int      hbound() const;
   void empty();
   void touch(int n);
   void resize(int hibound);
   void resize(int lobound, int hibound);
   void shift(int disp);
   void del(int n, unsigned int howmany=1);

   virtual ~ArrayBase(void) {};
};

inline void
ArrayBase::detach(void)
{
   ArrayRep * new_rep=new ArrayRep(*(ArrayRep *) get());
   assign(new_rep);
}

inline void
ArrayBase::check(void)
{
   if (get()->get_count()>1) detach();
}

inline int
ArrayBase::size() const
{
   return ((const ArrayRep *) get())->size();
}

inline int
ArrayBase::lbound() const
{
   return ((const ArrayRep *) get())->lobound;
}

inline int
ArrayBase::hbound() const
{
   return ((const ArrayRep *) get())->hibound;
}

inline void
ArrayBase::empty()
{
   check();
   ((ArrayRep *) get())->empty();
}

inline void
ArrayBase::resize(int lo, int hi)
{
   check();
   ((ArrayRep *) get())->resize(lo, hi);
}

inline void
ArrayBase::resize(int hi)
{
   resize(0, hi);
}

inline void
ArrayBase::touch(int n)
{
   check();
   ((ArrayRep *) get())->touch(n);
}

inline void
ArrayBase::shift(int disp)
{
   check();
   ((ArrayRep *) get())->shift(disp);
}

inline void
ArrayBase::del(int n, unsigned int howmany)
{
   check();
   
   ((ArrayRep *) get())->del(n, howmany);
}

template <class TYPE>
class ArrayBaseT : public ArrayBase
{
public:
   virtual ~ArrayBaseT(void) {};
   
   TYPE& operator[](int n);
   const TYPE& operator[](int n) const;
   
   operator TYPE* ();
   operator const TYPE* () const;
   
#ifndef __MWERKS__ //MCW can't compile
   operator const TYPE* ();
#endif  

   void ins(int n, const TYPE &val, unsigned int howmany=1);

   void sort();
   void sort(int lo, int hi);
protected:
   ArrayBaseT(void) {};
private:
      // Callbacks called from ArrayRep
   static void      destroy(void * data, int lo, int hi);
   static void      init1(void * data, int lo, int hi);
   static void      init2(void * data, int lo, int hi,
                 const void * src, int src_lo, int src_hi);
   static void      copy(void * dst, int dst_lo, int dst_hi,
                 const void * src, int src_lo, int src_hi);
   static void      insert(void * data, int els, int where,
                   const void * what, int howmany);
};

template <class TYPE> inline
ArrayBaseT<TYPE>::operator TYPE* ()
{
   check();
   
   ArrayRep * rep=(ArrayRep *) get();
   return &((TYPE *) rep->data)[-rep->minlo];
}

#ifndef __MWERKS__ //MCW can't compile
template <class TYPE> inline
ArrayBaseT<TYPE>::operator const TYPE* ()
{
   const ArrayRep * rep=(const ArrayRep *) get();
   return &((const TYPE *) rep->data)[-rep->minlo];
}
#endif

template <class TYPE> inline
ArrayBaseT<TYPE>::operator const TYPE* () const
{
   const ArrayRep * rep=(const ArrayRep *) get();
   return &((const TYPE *) rep->data)[-rep->minlo];
}

template <class TYPE> inline TYPE& 
ArrayBaseT<TYPE>::operator[](int n)
{
   check();

   ArrayRep * rep=(ArrayRep *) get();
   if (n<rep->lobound || n>rep->hibound)
      G_THROW( ERR_MSG("arrays.ill_sub") );
   return ((TYPE *) rep->data)[n - rep->minlo];
}

template <class TYPE> inline const TYPE& 
ArrayBaseT<TYPE>::operator[](int n) const
{
   const ArrayRep * rep=(const ArrayRep *) get();
   if (n<rep->lobound || n>rep->hibound)
      G_THROW( ERR_MSG("arrays.ill_sub") );
   return ((const TYPE *) rep->data)[n - rep->minlo];
}

template <class TYPE> inline void
ArrayBaseT<TYPE>::ins(int n, const TYPE &val, unsigned int howmany)
{
   check();
   
   ((ArrayRep *) get())->ins(n, &val, howmany);
}

template <class TYPE> void
ArrayBaseT<TYPE>::sort()
{
   sort(lbound(), hbound());
}

template <class TYPE> void
ArrayBaseT<TYPE>::sort(int lo, int hi)
{
   if (hi <= lo)
      return;
      // Test for insertion sort (optimize!)
   if (hi <= lo + 20)
   {
      for (int i=lo+1; i<=hi; i++)
      {
     int j = i;
     TYPE tmp = (*this)[i];
     while ((--j>=lo) && !((*this)[j]<=tmp))
            (*this)[j+1] = (*this)[j];
     (*this)[j+1] = tmp;
      }
      return;
   }
      // -- determine suitable quick-sort pivot
   TYPE tmp = (*this)[lo];
   TYPE pivot = (*this)[(lo+hi)/2];
   if (pivot <= tmp)
   { tmp = pivot; pivot=(*this)[lo]; }
   if ((*this)[hi] <= tmp)
   { pivot = tmp; }
   else if ((*this)[hi] <= pivot)
   { pivot = (*this)[hi]; }
      // -- partition set
   int h = hi;
   int l = lo;
   while (l < h)
   {
      while (! (pivot <= (*this)[l])) l++;
      while (! ((*this)[h] <= pivot)) h--;
      if (l < h)
      {
     tmp = (*this)[l];
     (*this)[l] = (*this)[h];
     (*this)[h] = tmp;
     l = l+1;
     h = h-1;
      }
   }
      // -- recursively restart
   sort(lo, h);
   sort(l, hi);
}

template <class TYPE>
class TArray : public ArrayBaseT<TYPE> {
public:
   TArray();
   TArray(int hibound);
   TArray(int lobound, int hibound);
   
   virtual ~TArray() {};
private:
      // Callbacks called from ArrayRep
   static void      destroy(void * data, int lo, int hi);
   static void      init1(void * data, int lo, int hi);
   static void      init2(void * data, int lo, int hi,
                 const void * src, int src_lo, int src_hi);
   static void      insert(void * data, int els, int where,
                   const void * what, int howmany);
};

template <class TYPE> void
TArray<TYPE>::destroy(void * data, int lo, int hi)
{
}

template <class TYPE> void
TArray<TYPE>::init1(void * data, int lo, int hi)
{
}

template <class TYPE> void
TArray<TYPE>::init2(void * data, int lo, int hi,
            const void * src, int src_lo, int src_hi)
{
   if (data && src)
   {
      int els=hi-lo+1;
      if (els>src_hi-src_lo+1) els=src_hi-src_lo+1;
      if (els>0)
     memmove((void *) &((TYPE *) data)[lo],
         (void *) &((TYPE *) src)[src_lo], els*sizeof(TYPE));
   };
}

// inline removed
template <class TYPE> void
TArray<TYPE>::insert(void * data, int els, int where,
             const void * what, int howmany)
{
   memmove(((TYPE *) data)+where+howmany,
       ((TYPE *) data)+where, sizeof(TYPE)*(els-where));
   for(int i=0;i<howmany;i++)
      ((TYPE *) data)[where+i]=*(TYPE *) what;
}

template <class TYPE> 
TArray<TYPE>::TArray ()
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, init2, insert));
}

template <class TYPE> 
TArray<TYPE>::TArray(int hi)
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, init2, insert, hi));
}

template <class TYPE> 
TArray<TYPE>::TArray(int lo, int hi)
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, init2, insert, lo, hi));
}

//inline removal ends

template <class TYPE>
class DArray : public ArrayBaseT<TYPE> {
public:
   DArray(void);
   DArray(const int hibound);
   DArray(const int lobound, const int hibound);
   
   virtual ~DArray() {};
private:
      // Callbacks called from ArrayRep
   static void      destroy(void * data, int lo, int hi);
   static void      init1(void * data, int lo, int hi);
   static void      init2(void * data, int lo, int hi,
                 const void * src, int src_lo, int src_hi);
   static void      copy(void * dst, int dst_lo, int dst_hi,
                 const void * src, int src_lo, int src_hi);
   static void      insert(void * data, int els, int where,
                   const void * what, int howmany);
};

template <class TYPE> void
DArray<TYPE>::destroy(void * data, int lo, int hi)
{
   if (data)
      for(int i=lo;i<=hi;i++)
     ((TYPE *) data)[i].TYPE::~TYPE();
}

template <class TYPE> void
DArray<TYPE>::init1(void * data, int lo, int hi)
{
   if (data)
      for(int i=lo;i<=hi;i++)
     new ((void *) &((TYPE *) data)[i]) TYPE;
}

template <class TYPE> void
DArray<TYPE>::init2(void * data, int lo, int hi,
            const void * src, int src_lo, int src_hi)
{
   if (data && src)
   {
      int i, j;
      for(i=lo, j=src_lo;i<=hi && j<=src_hi;i++, j++)
     new ((void *) &((TYPE *) data)[i]) TYPE(((TYPE *) src)[j]);
   };
}

template <class TYPE> void
DArray<TYPE>::copy(void * dst, int dst_lo, int dst_hi,
           const void * src, int src_lo, int src_hi)
{
   if (dst && src)
   {
      int i, j;
      for(i=dst_lo, j=src_lo;i<=dst_hi && j<=src_hi;i++, j++)
     ((TYPE *) dst)[i]=((TYPE *) src)[j];
   };
}

template <class TYPE> inline void
DArray<TYPE>::insert(void * data, int els, int where,
             const void * what, int howmany)
{
      // Now do the insertion
   TYPE * d=(TYPE *) data;
   
   int i;
   for (i=els+howmany-1; i>=els; i--)
   {
      if (i-where >= (int)howmany)
     new ((void*) &d[i]) TYPE (d[i-howmany]);
      else
     new ((void*) &d[i]) TYPE (*(TYPE *) what);
   }
   
   for (i=els-1; i>=where; i--)
   {
      if (i-where >= (int)howmany)
     d[i] = d[i-howmany];
      else
     d[i] = *(TYPE *) what;
   }
}

template <class TYPE> inline 
DArray<TYPE>::DArray ()
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, copy, insert));
}

template <class TYPE> inline 
DArray<TYPE>::DArray(const int hi)
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, copy, insert, hi));
}

template <class TYPE> inline 
DArray<TYPE>::DArray(const int lo, const int hi)
{
   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
               init2, copy, insert, lo, hi));
}

template <class TYPE>
class DPArray : public DArray<GPBase> {
public:
  // -- CONSTRUCTORS
  DPArray();
  DPArray(int hibound);
  DPArray(int lobound, int hibound);
  DPArray(const DPArray<TYPE> &gc);
  // -- DESTRUCTOR
  virtual ~DPArray();
  // -- ACCESS
  GP<TYPE>& operator[](int n);
  const GP<TYPE>& operator[](int n) const;
  // -- CONVERSION
  operator GP<TYPE>* ();
  
#ifndef __MWERKS__ //MCW can't compile
  operator const GP<TYPE>* ();
#endif 
 
  operator const GP<TYPE>* () const;
  // -- ALTERATION
  void ins(int n, const GP<TYPE> &val, unsigned int howmany=1);
  DPArray<TYPE>& operator= (const DPArray &ga);
};

template<class TYPE>
DPArray<TYPE>::DPArray() {}

template<class TYPE>
DPArray<TYPE>::DPArray(int hibound) :
      DArray<GPBase>(hibound) {}

template<class TYPE>
DPArray<TYPE>::DPArray(int lobound, int hibound) :
      DArray<GPBase>(lobound, hibound) {}

template<class TYPE>
DPArray<TYPE>::DPArray(const DPArray<TYPE> &gc) :
      DArray<GPBase>(gc) {}

template<class TYPE>
DPArray<TYPE>::~DPArray() {}

template<class TYPE>
inline GP<TYPE> &
DPArray<TYPE>::operator[](int n)
{
   return (GP<TYPE> &) DArray<GPBase>::operator[](n);
}

template<class TYPE>
inline const GP<TYPE> &
DPArray<TYPE>::operator[](int n) const
{
   return (const GP<TYPE> &) DArray<GPBase>::operator[](n);
}

template<class TYPE>
inline DPArray<TYPE>::operator GP<TYPE>* ()
{
   return (GP<TYPE> *) DArray<GPBase>::operator GPBase*();
}

#ifndef __MWERKS__ //MCW can't compile
template<class TYPE>
inline DPArray<TYPE>::operator const GP<TYPE>* ()
{
   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
}
#endif

template<class TYPE>
inline DPArray<TYPE>::operator const GP<TYPE>* () const
{
   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
}

template<class TYPE>
inline void
DPArray<TYPE>::ins(int n, const GP<TYPE> & val, unsigned int howmany)
{
   DArray<GPBase>::ins(n, val, howmany);
}

template<class TYPE>
inline DPArray<TYPE> &
DPArray<TYPE>::operator= (const DPArray &ga)
{
   DArray<GPBase>::operator=(ga);
   return *this;
}

// ------------ THE END



#ifdef HAVE_NAMESPACES
}
# ifndef NOT_USING_DJVU_NAMESPACE
using namespace DJVU;
# endif
#endif
#endif

kviewshell

Skip menu "kviewshell"

• Main Page
• Namespace List
• Class Hierarchy
• Alphabetical List
• Class List
• File List
• Namespace Members
• Class Members

API Reference

Skip menu "API Reference"

• kviewshell

Generated for API Reference by doxygen 1.5.9
This website is maintained by Adriaan de Groot and Allen Winter.
KDE^® and the K Desktop Environment^® logo are registered trademarks of KDE e.V. | Legal