//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, either Version 2 of the license,

//C- or (at your option) any later version. 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 from

//C- Lizardtech Software.  Lizardtech Software has authorized us to

//C- replace the original DjVu(r) Reference Library notice by the following

//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.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, either Version 2 of the license,

//C- | or (at your option) any later version. 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- +------------------------------------------------------------------

#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

/** @name Arrays.h

    Files #"Arrays.h"# and #"Arrays.cpp"# implement three array template classes.

    Class \Ref{TArray} implements an array of objects of trivial types

    such as #char#, #int#, #float#, etc. It is faster than general implementation

    for any type done in \Ref{DArray} because it does not cope with

    element's constructors, destructors and copy operators. Although

    implemented as a template, which makes it possible to incorrectly use

    \Ref{TArray} with non-trivial classes, it should not be done.

    A lot of things is shared by these three arrays. That is why there are

    more base classes:

    \begin{itemize}

       \item \Ref{ArrayBase} defines functions independent of the elements type

       \item \Ref{ArrayBaseT} template class defining functions shared by

             \Ref{DArray} and \Ref{TArray}

    \end{itemize}

    The main difference between \Ref{GArray} (now obsolete) and these ones

    is the copy-on-demand strategy, which allows you to copy array objects

    without copying the real data. It's the same thing, which has been

    implemented in \Ref{GString} long ago: as long as you don't try to modify

    the underlying data, it may be shared between several copies of array

    objects. As soon as you attempt to make any changes, a private copy

    is created automatically and transparently for you - the procedure, that

    we call "copy-on-demand".

    Also, please note that now there is no separate class, which does fast

    sorting. Both \Ref{TArray} (dynamic array for trivial types) and

    \Ref{DArray} (dynamic array for arbitrary types) can sort their elements.

    {\bf Historical comments} --- Leon chose to implement his own arrays because

    the STL classes were not universally available and the compilers were

    rarely able to deal with such a template galore. Later it became clear

    that there is no really good reason why arrays should be derived from

    containers. It was also suggested to create separate arrays implementation

    for simple classes and do the copy-on-demand strategy, which would allow

    to assign array objects without immediate copying of their elements. 

    At this point \Ref{DArray} and \Ref{TArray} should only be used when

    it is critical to have the copy-on-demand feature.  The \Ref{GArray}

    implementation is a lot more efficient.

    @memo Template array classes.

    @author 

    Andrei Erofeev <eaf@geocities.com> -- Copy-on-demand implementation.

*/

//@{

// 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 DJVUAPI 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);

   }

}

/** Dynamic array base class.

    This is an auxiliary base class for \Ref{DArray} and \Ref{TArray}

    implementing some shared functions independent of the type of array

    elements. It's not supposed to be constructed by hands. Use \Ref{DArray}

    and \Ref{TArray} instead.

    */

class DJVUAPI ArrayBase : protected _ArrayBase

{

protected:

   void		check(void);

   void		detach(void);

   ArrayBase(void) {};

public:

   /// Returns the number of elements in the array

   int		size() const;

   /** Returns the lower bound of the valid subscript range. */

   int		lbound() const;

   /** Returns the upper bound of the valid subscript range. */

   int		hbound() const;

   /** Erases the array contents. All elements in the array are destroyed.  

       The valid subscript range is set to the empty range. */

   void empty();

   /** Extends the subscript range so that is contains #n#.

       This function does nothing if #n# is already int the valid subscript range.

       If the valid range was empty, both the lower bound and the upper bound

       are set to #n#.  Otherwise the valid subscript range is extended

       to encompass #n#. This function is very handy when called before setting

       an array element:

       \begin{verbatim}

       int lineno=1;

       DArray<GString> a;

       while (! end_of_file()) { 

       a.touch[lineno]; 

       a[lineno++] = read_a_line(); 

       }

       \end{verbatim} 

   */

   void touch(int n);

   /** Resets the valid subscript range to #0#---#hibound#.

       This function may destroy some array elements and may construct

       new array elements with the null constructor. Setting #hibound# to

       #-1# resets the valid subscript range to the empty range.

       @param hibound upper bound of the new subscript range. */      

   void resize(int hibound);

   /** Resets the valid subscript range to #lobound#---#hibound#. 

       This function may destroy some array elements and may construct

       new array elements with the null constructor. Setting #lobound# to #0# and

       #hibound# to #-1# resets the valid subscript range to the empty range.

       @param lobound lower bound of the new subscript range.

       @param hibound upper bound of the new subscript range. */

   void resize(int lobound, int hibound);

   /** Shifts the valid subscript range. Argument #disp# is added to both 

       bounds of the valid subscript range. Array elements previously

       located at subscript #x# will now be located at subscript #x+disp#. */

   void shift(int disp);

   /** Deletes array elements. The array elements corresponding to

       subscripts #n#...#n+howmany-1# are destroyed. All array elements

       previously located at subscripts greater or equal to #n+howmany#

       are moved to subscripts starting with #n#. The new subscript upper

       bound is reduced in order to account for this shift. 

       @param n subscript of the first element to delete.

       @param howmany number of elements to delete. */

   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);

}

/** Dynamic array template base class.

    This is an auxiliary template base class for \Ref{DArray} and \Ref{TArray}

    implementing some shared functions which {\em depend} on the type of

    the array elements (this is contrary to \Ref{ArrayBase}).

    It's not supposed to be constructed by hands. Use \Ref{DArray} and

    \Ref{TArray} instead.

    */

template <class TYPE>

class ArrayBaseT : public ArrayBase

{

public:

   virtual ~ArrayBaseT(void) {};

   /** Returns a reference to the array element for subscript #n#.  This

       reference can be used for both reading (as "#a[n]#") and writing (as

       "#a[n]=v#") an array element.  This operation will not extend the valid

       subscript range: an exception \Ref{GException} is thrown if argument #n#

       is not in the valid subscript range. */

   TYPE& operator[](int n);

   /** Returns a constant reference to the array element for subscript #n#.

       This reference can only be used for reading (as "#a[n]#") an array

       element.  This operation will not extend the valid subscript range: an

       exception \Ref{GException} is thrown if argument #n# is not in the valid

       subscript range.  This variant of #operator[]# is necessary when dealing

       with a #const DArray<TYPE>#. */

   const TYPE& operator[](int n) const;

   /** Returns a pointer for reading or writing the array elements.  This

       pointer can be used to access the array elements with the same

       subscripts and the usual bracket syntax.  This pointer remains valid as

       long as the valid subscript range is unchanged. If you change the

       subscript range, you must stop using the pointers returned by prior

       invocation of this conversion operator. */

   operator TYPE* ();

   /** Returns a pointer for reading (but not modifying) the array elements.

       This pointer can be used to access the array elements with the same

       subscripts and the usual bracket syntax.  This pointer remains valid as

       long as the valid subscript range is unchanged. If you change the

       subscript range, you must stop using the pointers returned by prior

       invocation of this conversion operator. */

   operator const TYPE* () const;

   /** Insert new elements into an array. This function inserts

       #howmany# elements at position #n# into the array. The initial value #val#

       is copied into the new elements. All array elements previously located at subscripts

       #n# and higher are moved to subscripts #n+howmany# and higher. The upper bound of the 

       valid subscript range is increased in order to account for this shift.

       @param n subscript of the first inserted element.

       @param val initial value of the new elements.

       @param howmany number of elements to insert. */

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

   /** Sort array elements.  Sort all array elements in ascending order.  Array

       elements are compared using the less-or-equal comparison operator for

       type #TYPE#. */

   void sort();

   /** Sort array elements in subscript range #lo# to #hi#.  Sort all array

       elements whose subscripts are in range #lo#..#hi# in ascending order.

       The other elements of the array are left untouched.  An exception is

       thrown if arguments #lo# and #hi# are not in the valid subscript range.

       Array elements are compared using the less-or-equal comparison operator

       for type #TYPE#.  

       @param lo low bound for the subscripts of the elements to sort.  

       @param hi high bound for the subscripts of the elements to 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];

}

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);

}

/** Dynamic array for simple types.  

    Template class #TArray<TYPE># implements an array of

    elements of {\em simple} type #TYPE#. {\em Simple} means that the type

    may be #char#, #int#, #float# etc. The limitation is imposed by the

    way in which the #TArray# is working with its elements: it's not trying

    to execute elements' constructors, destructors or copy operators. It's

    just doing bitwise copy. Except for this it's pretty much the same as

    \Ref{DArray}.

    Please note that most of the methods are implemented in the base classes

    \Ref{ArrayBase} and \Ref{ArrayBaseT}.

*/

template <class TYPE>

class TArray : public ArrayBaseT<TYPE> {

public:

   /** Constructs an empty array. The valid subscript range is initially

       empty. Member function #touch# and #resize# provide convenient ways

       to enlarge the subscript range. */

   TArray();

   /** Constructs an array with subscripts in range 0 to #hibound#. 

       The subscript range can be subsequently modified with member functions

       #touch# and #resize#.

       @param hibound upper bound of the initial subscript range. */

   TArray(int hibound);

   /** Constructs an array with subscripts in range #lobound# to #hibound#.  

       The subscript range can be subsequently modified with member functions

       #touch# and #resize#.

       @param lobound lower bound of the initial subscript range.

       @param hibound upper bound of the initial subscript range. */

   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

      ((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

/** Dynamic array for general types.

    Template class #DArray<TYPE># implements an array of

    elements of type #TYPE#.  Each element is identified by an integer

    subscript.  The valid subscripts range is defined by dynamically

    adjustable lower- and upper-bounds.  Besides accessing and setting

    elements, member functions are provided to insert or delete elements at

    specified positions.

    This template class must be able to access

    \begin{itemize}

    \item a null constructor #TYPE::TYPE()#, 

    \item a copy constructor #TYPE::TYPE(const TYPE &)#,

    \item and a copy operator #TYPE & operator=(const TYPE &)#.

    \end{itemize}

    The class offers "copy-on-demand" policy, which means that when you

    copy the array object, array elements will stay intact as long as you

    don't try to modify them. As soon as you make an attempt to change

    array contents, the copying is done automatically and transparently

    for you - the procedure that we call "copy-on-demand". This is the main

    difference between this class and \Ref{GArray} (now obsolete)

    Please note that most of the methods are implemented in the base classes

    \Ref{ArrayBase} and \Ref{ArrayBaseT}.

*/

template <class TYPE>

class DArray : public ArrayBaseT<TYPE> {

public:

   /** Constructs an empty array. The valid subscript range is initially

       empty. Member function #touch# and #resize# provide convenient ways

       to enlarge the subscript range. */

   DArray(void);

   /** Constructs an array with subscripts in range 0 to #hibound#. 

       The subscript range can be subsequently modified with member functions

       #touch# and #resize#.

       @param hibound upper bound of the initial subscript range. */

   DArray(const int hibound);

   /** Constructs an array with subscripts in range #lobound# to #hibound#.  

       The subscript range can be subsequently modified with member functions

       #touch# and #resize#.

       @param lobound lower bound of the initial subscript range.

       @param hibound upper bound of the initial subscript range. */

   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));

}

/** Dynamic array for \Ref{GPBase}d classes.

    There are many situations when it's necessary to create arrays of

    \Ref{GP} pointers. For example, #DArray<GP<Dialog> ># or #DArray<GP<Button> >#.

    This would result in compilation of two instances of \Ref{DArray} because

    from the viewpoint of the compiler there are two different classes used

    as array elements: #GP<Dialog># and #GP<Button>#. In reality though,

    all \Ref{GP} pointers have absolutely the same binary structure because

    they are derived from \Ref{GPBase} class and do not add any variables

    or virtual functions. That's why it's possible to instantiate \Ref{DArray}

    only once for \Ref{GPBase} elements and then just cast types.

    To implement this idea we have created this #DPArray<TYPE># class,

    which can be used instead of #DArray<GP<TYPE> >#. It behaves absolutely

    the same way as \Ref{DArray} but has one big advantage: overhead of

    using #DPArray# with one more type is negligible.

  */

template <class TYPE>

class DPArray : public DArray<GPBase> {

public: