source: trunk/libdjvu/Arrays.h @ 206

Last change on this file since 206 was 206, checked in by Eugene Romanenko, 14 years ago

DJVU plugin: djvulibre updated to version 3.5.19

File size: 31.4 KB
Line 
1//C-  -*- C++ -*-
2//C- -------------------------------------------------------------------
3//C- DjVuLibre-3.5
4//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
5//C- Copyright (c) 2001  AT&T
6//C-
7//C- This software is subject to, and may be distributed under, the
8//C- GNU General Public License, either Version 2 of the license,
9//C- or (at your option) any later version. The license should have
10//C- accompanied the software or you may obtain a copy of the license
11//C- from the Free Software Foundation at http://www.fsf.org .
12//C-
13//C- This program is distributed in the hope that it will be useful,
14//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16//C- GNU General Public License for more details.
17//C-
18//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19//C- Lizardtech Software.  Lizardtech Software has authorized us to
20//C- replace the original DjVu(r) Reference Library notice by the following
21//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22//C-
23//C-  ------------------------------------------------------------------
24//C- | DjVu (r) Reference Library (v. 3.5)
25//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26//C- | The DjVu Reference Library is protected by U.S. Pat. No.
27//C- | 6,058,214 and patents pending.
28//C- |
29//C- | This software is subject to, and may be distributed under, the
30//C- | GNU General Public License, either Version 2 of the license,
31//C- | or (at your option) any later version. The license should have
32//C- | accompanied the software or you may obtain a copy of the license
33//C- | from the Free Software Foundation at http://www.fsf.org .
34//C- |
35//C- | The computer code originally released by LizardTech under this
36//C- | license and unmodified by other parties is deemed "the LIZARDTECH
37//C- | ORIGINAL CODE."  Subject to any third party intellectual property
38//C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39//C- | non-exclusive license to make, use, sell, or otherwise dispose of
40//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42//C- | General Public License.   This grant only confers the right to
43//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44//C- | the extent such infringement is reasonably necessary to enable
45//C- | recipient to make, have made, practice, sell, or otherwise dispose
46//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47//C- | any greater extent that may be necessary to utilize further
48//C- | modifications or combinations.
49//C- |
50//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54//C- +------------------------------------------------------------------
55//
56// $Id: Arrays.h,v 1.12 2007/03/25 20:48:29 leonb Exp $
57// $Name: release_3_5_19 $
58
59#ifndef _ARRAYS_H_
60#define _ARRAYS_H_
61#ifdef HAVE_CONFIG_H
62#include "config.h"
63#endif
64#if NEED_GNUG_PRAGMAS
65# pragma interface
66#endif
67
68#include "GException.h"
69#include "GSmartPointer.h"
70#include <string.h>
71
72#ifdef HAVE_NAMESPACES
73namespace DJVU {
74# ifdef NOT_DEFINED // Just to fool emacs c++ mode
75}
76#endif
77#endif
78
79
80
81/** @name Arrays.h
82
83    Files #"Arrays.h"# and #"Arrays.cpp"# implement three array template classes.
84    Class \Ref{TArray} implements an array of objects of trivial types
85    such as #char#, #int#, #float#, etc. It is faster than general implementation
86    for any type done in \Ref{DArray} because it does not cope with
87    element's constructors, destructors and copy operators. Although
88    implemented as a template, which makes it possible to incorrectly use
89    \Ref{TArray} with non-trivial classes, it should not be done.
90
91    A lot of things is shared by these three arrays. That is why there are
92    more base classes:
93    \begin{itemize}
94       \item \Ref{ArrayBase} defines functions independent of the elements type
95       \item \Ref{ArrayBaseT} template class defining functions shared by
96             \Ref{DArray} and \Ref{TArray}
97    \end{itemize}
98
99    The main difference between \Ref{GArray} (now obsolete) and these ones
100    is the copy-on-demand strategy, which allows you to copy array objects
101    without copying the real data. It's the same thing, which has been
102    implemented in \Ref{GString} long ago: as long as you don't try to modify
103    the underlying data, it may be shared between several copies of array
104    objects. As soon as you attempt to make any changes, a private copy
105    is created automatically and transparently for you - the procedure, that
106    we call "copy-on-demand".
107
108    Also, please note that now there is no separate class, which does fast
109    sorting. Both \Ref{TArray} (dynamic array for trivial types) and
110    \Ref{DArray} (dynamic array for arbitrary types) can sort their elements.
111   
112    {\bf Historical comments} --- Leon chose to implement his own arrays because
113    the STL classes were not universally available and the compilers were
114    rarely able to deal with such a template galore. Later it became clear
115    that there is no really good reason why arrays should be derived from
116    containers. It was also suggested to create separate arrays implementation
117    for simple classes and do the copy-on-demand strategy, which would allow
118    to assign array objects without immediate copying of their elements.
119
120    At this point \Ref{DArray} and \Ref{TArray} should only be used when
121    it is critical to have the copy-on-demand feature.  The \Ref{GArray}
122    implementation is a lot more efficient.
123   
124    @memo Template array classes.
125    @author
126    Andrei Erofeev <eaf@geocities.com> -- Copy-on-demand implementation.
127    @version
128    #$Id: Arrays.h,v 1.12 2007/03/25 20:48:29 leonb Exp $# */
129//@{
130
131// Auxiliary classes: Will be used in place of GPBase and GPEnabled objects
132class _ArrayRep
133{
134   friend class _ArrayBase;
135public:
136   _ArrayRep(void) : count(0) {}
137   _ArrayRep(const _ArrayRep &) {}
138   virtual ~_ArrayRep(void) {}
139
140   _ArrayRep & operator=(const _ArrayRep &) { return *this; }
141
142   int          get_count(void) const { return count; }
143private:
144   int          count;
145
146   void         ref(void) { count++; }
147   void         unref(void) { if (--count==0) delete this; }
148};
149
150class _ArrayBase
151{
152public:
153   _ArrayBase(void) : rep(0) {}
154   _ArrayBase(const _ArrayBase & ab) : rep(0)
155   {
156      if (ab.rep) ab.rep->ref();
157      rep=ab.rep;
158   }
159   _ArrayBase(_ArrayRep * ar) : rep(0)
160   {
161      if (ar) ar->ref();
162      rep=ar;
163   }
164   virtual ~_ArrayBase(void)
165   {
166      if (rep) { rep->unref(); rep=0; }
167   }
168
169   _ArrayRep *  get(void) const { return rep; }
170   _ArrayBase & assign(_ArrayRep * ar)
171   {
172      if (ar) ar->ref();
173      if (rep) rep->unref();
174      rep=ar;
175      return *this;
176   }
177   _ArrayBase & operator=(const _ArrayBase & ab) { return assign(ab.rep); }
178   bool         operator==(const _ArrayBase & ab) { return rep==ab.rep; }
179private:
180   _ArrayRep    * rep;
181};
182
183// Internal "Array repository" holding the pointer to the actual data,
184// data bounds, etc. It copes with data elements with the help of five
185// static functions which pointers are supposed to be passed to the
186// constructor.
187class ArrayRep : public _ArrayRep
188{
189public:
190   ArrayRep(int elsize,
191            void (* xdestroy)(void *, int, int),
192            void (* xinit1)(void *, int, int),
193            void (* xinit2)(void *, int, int, const void *, int, int),
194            void (* xcopy)(void *, int, int, const void *, int, int),
195            void (* xinsert)(void *, int, int, const void *, int));
196   ArrayRep(int elsize,
197            void (* xdestroy)(void *, int, int),
198            void (* xinit1)(void *, int, int),
199            void (* xinit2)(void *, int, int, const void *, int, int),
200            void (* xcopy)(void *, int, int, const void *, int, int),
201            void (* xinsert)(void *, int, int, const void *, int),
202            int hibound);
203   ArrayRep(int elsize,
204            void (* xdestroy)(void *, int, int),
205            void (* xinit1)(void *, int, int),
206            void (* xinit2)(void *, int, int, const void *, int, int),
207            void (* xcopy)(void *, int, int, const void *, int, int),
208            void (* xinsert)(void *, int, int, const void *, int),
209            int lobound, int hibound);
210   ArrayRep(const ArrayRep & rep);
211   
212   virtual ~ArrayRep();
213   
214      // Following is the standard interface to DArray. DArray will call these
215      // functions to access data.
216   int          size() const;
217   int          lbound() const;
218   int          hbound() const;
219
220   void         empty();
221   void         touch(int n);
222   void         resize(int lobound, int hibound);
223   void         shift(int disp);
224   void         del(int n, unsigned int howmany=1);
225
226      // ins() is an exception. It does it job only partially.
227      // The derived class is supposed to finish insertion.
228   void         ins(int n, const void * what, unsigned int howmany);
229
230   ArrayRep &   operator=(const ArrayRep & rep);
231
232      // All data is public because DArray... classes will need access to it
233   void         *data;
234   int          minlo;
235   int          maxhi;
236   int          lobound;
237   int          hibound;
238   int          elsize;
239private:
240      // These functions can't be virtual as they're called from
241      // constructors and destructors :((
242      // destroy(): should destroy elements in data[] array from 'lo' to 'hi'
243   void         (* destroy)(void * data, int lo, int hi);
244      // init1(): should initialize elements in data[] from 'lo' to 'hi'
245      // using default constructors
246   void         (* init1)(void * data, int lo, int hi);
247      // init2(): should initialize elements in data[] from 'lo' to 'hi'
248      // using corresponding elements from src[] (copy constructor)
249   void         (* init2)(void * data, int lo, int hi,
250                          const void * src, int src_lo, int src_hi);
251      // copy(): should copy elements from src[] to dst[] (copy operator)
252   void         (* copy)(void * dst, int dst_lo, int dst_hi,
253                         const void * src, int src_lo, int src_hi);
254      // insert(): should insert '*what' at position 'where' 'howmany' times
255      // into array data[] having 'els' initialized elements
256   void         (* insert)(void * data, int els, int where, const void * what,
257                           int howmany);
258};
259
260inline int
261ArrayRep::size() const
262{
263   return hibound - lobound + 1;
264}
265
266inline int
267ArrayRep::lbound() const
268{
269  return lobound;
270}
271
272inline int
273ArrayRep::hbound() const
274{
275  return hibound;
276}
277
278inline void
279ArrayRep::empty()
280{
281  resize(0, -1);
282}
283
284inline void
285ArrayRep::touch(int n)
286{
287   if (hibound < lobound)
288   {
289      resize(n,n);
290   } else
291   {
292      int nlo = lobound;
293      int nhi = hibound;
294      if (n < nlo) nlo = n;
295      if (n > nhi) nhi = n;
296      resize(nlo, nhi);
297   }
298}
299
300/** Dynamic array base class.
301    This is an auxiliary base class for \Ref{DArray} and \Ref{TArray}
302    implementing some shared functions independent of the type of array
303    elements. It's not supposed to be constructed by hands. Use \Ref{DArray}
304    and \Ref{TArray} instead.
305    */
306   
307class ArrayBase : protected _ArrayBase
308{
309protected:
310   void         check(void);
311   void         detach(void);
312
313   ArrayBase(void) {};
314public:
315   /// Returns the number of elements in the array
316   int          size() const;
317   /** Returns the lower bound of the valid subscript range. */
318   int          lbound() const;
319   /** Returns the upper bound of the valid subscript range. */
320   int          hbound() const;
321   /** Erases the array contents. All elements in the array are destroyed. 
322       The valid subscript range is set to the empty range. */
323   void empty();
324   /** Extends the subscript range so that is contains #n#.
325       This function does nothing if #n# is already int the valid subscript range.
326       If the valid range was empty, both the lower bound and the upper bound
327       are set to #n#.  Otherwise the valid subscript range is extended
328       to encompass #n#. This function is very handy when called before setting
329       an array element:
330       \begin{verbatim}
331       int lineno=1;
332       DArray<GString> a;
333       while (! end_of_file()) {
334       a.touch[lineno];
335       a[lineno++] = read_a_line();
336       }
337       \end{verbatim}
338   */
339   void touch(int n);
340   /** Resets the valid subscript range to #0#---#hibound#.
341       This function may destroy some array elements and may construct
342       new array elements with the null constructor. Setting #hibound# to
343       #-1# resets the valid subscript range to the empty range.
344       @param hibound upper bound of the new subscript range. */     
345   void resize(int hibound);
346   /** Resets the valid subscript range to #lobound#---#hibound#.
347       This function may destroy some array elements and may construct
348       new array elements with the null constructor. Setting #lobound# to #0# and
349       #hibound# to #-1# resets the valid subscript range to the empty range.
350       @param lobound lower bound of the new subscript range.
351       @param hibound upper bound of the new subscript range. */
352   void resize(int lobound, int hibound);
353   /** Shifts the valid subscript range. Argument #disp# is added to both
354       bounds of the valid subscript range. Array elements previously
355       located at subscript #x# will now be located at subscript #x+disp#. */
356   void shift(int disp);
357   /** Deletes array elements. The array elements corresponding to
358       subscripts #n#...#n+howmany-1# are destroyed. All array elements
359       previously located at subscripts greater or equal to #n+howmany#
360       are moved to subscripts starting with #n#. The new subscript upper
361       bound is reduced in order to account for this shift.
362       @param n subscript of the first element to delete.
363       @param howmany number of elements to delete. */
364   void del(int n, unsigned int howmany=1);
365
366   virtual ~ArrayBase(void) {};
367};
368
369inline void
370ArrayBase::detach(void)
371{
372   ArrayRep * new_rep=new ArrayRep(*(ArrayRep *) get());
373   assign(new_rep);
374}
375
376inline void
377ArrayBase::check(void)
378{
379   if (get()->get_count()>1) detach();
380}
381
382inline int
383ArrayBase::size() const
384{
385   return ((const ArrayRep *) get())->size();
386}
387
388inline int
389ArrayBase::lbound() const
390{
391   return ((const ArrayRep *) get())->lobound;
392}
393
394inline int
395ArrayBase::hbound() const
396{
397   return ((const ArrayRep *) get())->hibound;
398}
399
400inline void
401ArrayBase::empty()
402{
403   check();
404   ((ArrayRep *) get())->empty();
405}
406
407inline void
408ArrayBase::resize(int lo, int hi)
409{
410   check();
411   ((ArrayRep *) get())->resize(lo, hi);
412}
413
414inline void
415ArrayBase::resize(int hi)
416{
417   resize(0, hi);
418}
419
420inline void
421ArrayBase::touch(int n)
422{
423   check();
424   ((ArrayRep *) get())->touch(n);
425}
426
427inline void
428ArrayBase::shift(int disp)
429{
430   check();
431   ((ArrayRep *) get())->shift(disp);
432}
433
434inline void
435ArrayBase::del(int n, unsigned int howmany)
436{
437   check();
438   
439   ((ArrayRep *) get())->del(n, howmany);
440}
441
442/** Dynamic array template base class.
443    This is an auxiliary template base class for \Ref{DArray} and \Ref{TArray}
444    implementing some shared functions which {\em depend} on the type of
445    the array elements (this is contrary to \Ref{ArrayBase}).
446    It's not supposed to be constructed by hands. Use \Ref{DArray} and
447    \Ref{TArray} instead.
448    */
449
450template <class TYPE>
451class ArrayBaseT : public ArrayBase
452{
453public:
454   virtual ~ArrayBaseT(void) {};
455   
456   /** Returns a reference to the array element for subscript #n#.  This
457       reference can be used for both reading (as "#a[n]#") and writing (as
458       "#a[n]=v#") an array element.  This operation will not extend the valid
459       subscript range: an exception \Ref{GException} is thrown if argument #n#
460       is not in the valid subscript range. */
461   TYPE& operator[](int n);
462   /** Returns a constant reference to the array element for subscript #n#.
463       This reference can only be used for reading (as "#a[n]#") an array
464       element.  This operation will not extend the valid subscript range: an
465       exception \Ref{GException} is thrown if argument #n# is not in the valid
466       subscript range.  This variant of #operator[]# is necessary when dealing
467       with a #const DArray<TYPE>#. */
468   const TYPE& operator[](int n) const;
469   
470   /** Returns a pointer for reading or writing the array elements.  This
471       pointer can be used to access the array elements with the same
472       subscripts and the usual bracket syntax.  This pointer remains valid as
473       long as the valid subscript range is unchanged. If you change the
474       subscript range, you must stop using the pointers returned by prior
475       invocation of this conversion operator. */
476   operator TYPE* ();
477   /** Returns a pointer for reading (but not modifying) the array elements.
478       This pointer can be used to access the array elements with the same
479       subscripts and the usual bracket syntax.  This pointer remains valid as
480       long as the valid subscript range is unchanged. If you change the
481       subscript range, you must stop using the pointers returned by prior
482       invocation of this conversion operator. */
483   operator const TYPE* () const;
484   
485   /** Insert new elements into an array. This function inserts
486       #howmany# elements at position #n# into the array. The initial value #val#
487       is copied into the new elements. All array elements previously located at subscripts
488       #n# and higher are moved to subscripts #n+howmany# and higher. The upper bound of the
489       valid subscript range is increased in order to account for this shift.
490       @param n subscript of the first inserted element.
491       @param val initial value of the new elements.
492       @param howmany number of elements to insert. */
493   void ins(int n, const TYPE &val, unsigned int howmany=1);
494
495   /** Sort array elements.  Sort all array elements in ascending order.  Array
496       elements are compared using the less-or-equal comparison operator for
497       type #TYPE#. */
498   void sort();
499   /** Sort array elements in subscript range #lo# to #hi#.  Sort all array
500       elements whose subscripts are in range #lo#..#hi# in ascending order.
501       The other elements of the array are left untouched.  An exception is
502       thrown if arguments #lo# and #hi# are not in the valid subscript range.
503       Array elements are compared using the less-or-equal comparison operator
504       for type #TYPE#. 
505       @param lo low bound for the subscripts of the elements to sort. 
506       @param hi high bound for the subscripts of the elements to sort. */
507   void sort(int lo, int hi);
508protected:
509   ArrayBaseT(void) {};
510private:
511      // Callbacks called from ArrayRep
512   static void          destroy(void * data, int lo, int hi);
513   static void          init1(void * data, int lo, int hi);
514   static void          init2(void * data, int lo, int hi,
515                             const void * src, int src_lo, int src_hi);
516   static void          copy(void * dst, int dst_lo, int dst_hi,
517                             const void * src, int src_lo, int src_hi);
518   static void          insert(void * data, int els, int where,
519                               const void * what, int howmany);
520};
521
522template <class TYPE> inline
523ArrayBaseT<TYPE>::operator TYPE* ()
524{
525   check();
526   
527   ArrayRep * rep=(ArrayRep *) get();
528   return &((TYPE *) rep->data)[-rep->minlo];
529}
530
531template <class TYPE> inline
532ArrayBaseT<TYPE>::operator const TYPE* () const
533{
534   const ArrayRep * rep=(const ArrayRep *) get();
535   return &((const TYPE *) rep->data)[-rep->minlo];
536}
537
538template <class TYPE> inline TYPE& 
539ArrayBaseT<TYPE>::operator[](int n)
540{
541   check();
542
543   ArrayRep * rep=(ArrayRep *) get();
544   if (n<rep->lobound || n>rep->hibound)
545      G_THROW( ERR_MSG("arrays.ill_sub") );
546   return ((TYPE *) rep->data)[n - rep->minlo];
547}
548
549template <class TYPE> inline const TYPE& 
550ArrayBaseT<TYPE>::operator[](int n) const
551{
552   const ArrayRep * rep=(const ArrayRep *) get();
553   if (n<rep->lobound || n>rep->hibound)
554      G_THROW( ERR_MSG("arrays.ill_sub") );
555   return ((const TYPE *) rep->data)[n - rep->minlo];
556}
557
558template <class TYPE> inline void
559ArrayBaseT<TYPE>::ins(int n, const TYPE &val, unsigned int howmany)
560{
561   check();
562   
563   ((ArrayRep *) get())->ins(n, &val, howmany);
564}
565
566template <class TYPE> void
567ArrayBaseT<TYPE>::sort()
568{
569   sort(lbound(), hbound());
570}
571
572template <class TYPE> void
573ArrayBaseT<TYPE>::sort(int lo, int hi)
574{
575   if (hi <= lo)
576      return;
577      // Test for insertion sort (optimize!)
578   if (hi <= lo + 20)
579   {
580      for (int i=lo+1; i<=hi; i++)
581      {
582         int j = i;
583         TYPE tmp = (*this)[i];
584         while ((--j>=lo) && !((*this)[j]<=tmp))
585            (*this)[j+1] = (*this)[j];
586         (*this)[j+1] = tmp;
587      }
588      return;
589   }
590      // -- determine suitable quick-sort pivot
591   TYPE tmp = (*this)[lo];
592   TYPE pivot = (*this)[(lo+hi)/2];
593   if (pivot <= tmp)
594   { tmp = pivot; pivot=(*this)[lo]; }
595   if ((*this)[hi] <= tmp)
596   { pivot = tmp; }
597   else if ((*this)[hi] <= pivot)
598   { pivot = (*this)[hi]; }
599      // -- partition set
600   int h = hi;
601   int l = lo;
602   while (l < h)
603   {
604      while (! (pivot <= (*this)[l])) l++;
605      while (! ((*this)[h] <= pivot)) h--;
606      if (l < h)
607      {
608         tmp = (*this)[l];
609         (*this)[l] = (*this)[h];
610         (*this)[h] = tmp;
611         l = l+1;
612         h = h-1;
613      }
614   }
615      // -- recursively restart
616   sort(lo, h);
617   sort(l, hi);
618}
619
620/** Dynamic array for simple types. 
621    Template class #TArray<TYPE># implements an array of
622    elements of {\em simple} type #TYPE#. {\em Simple} means that the type
623    may be #char#, #int#, #float# etc. The limitation is imposed by the
624    way in which the #TArray# is working with its elements: it's not trying
625    to execute elements' constructors, destructors or copy operators. It's
626    just doing bitwise copy. Except for this it's pretty much the same as
627    \Ref{DArray}.
628   
629    Please note that most of the methods are implemented in the base classes
630    \Ref{ArrayBase} and \Ref{ArrayBaseT}.
631*/
632
633template <class TYPE>
634class TArray : public ArrayBaseT<TYPE> {
635public:
636   /** Constructs an empty array. The valid subscript range is initially
637       empty. Member function #touch# and #resize# provide convenient ways
638       to enlarge the subscript range. */
639   TArray();
640   /** Constructs an array with subscripts in range 0 to #hibound#.
641       The subscript range can be subsequently modified with member functions
642       #touch# and #resize#.
643       @param hibound upper bound of the initial subscript range. */
644   TArray(int hibound);
645   /** Constructs an array with subscripts in range #lobound# to #hibound#. 
646       The subscript range can be subsequently modified with member functions
647       #touch# and #resize#.
648       @param lobound lower bound of the initial subscript range.
649       @param hibound upper bound of the initial subscript range. */
650   TArray(int lobound, int hibound);
651   
652   virtual ~TArray() {};
653private:
654      // Callbacks called from ArrayRep
655   static void          destroy(void * data, int lo, int hi);
656   static void          init1(void * data, int lo, int hi);
657   static void          init2(void * data, int lo, int hi,
658                             const void * src, int src_lo, int src_hi);
659   static void          insert(void * data, int els, int where,
660                               const void * what, int howmany);
661};
662
663template <class TYPE> void
664TArray<TYPE>::destroy(void * data, int lo, int hi)
665{
666}
667
668template <class TYPE> void
669TArray<TYPE>::init1(void * data, int lo, int hi)
670{
671}
672
673template <class TYPE> void
674TArray<TYPE>::init2(void * data, int lo, int hi,
675                    const void * src, int src_lo, int src_hi)
676{
677   if (data && src)
678   {
679      int els=hi-lo+1;
680      if (els>src_hi-src_lo+1) els=src_hi-src_lo+1;
681      if (els>0)
682         memmove((void *) &((TYPE *) data)[lo],
683                 (void *) &((TYPE *) src)[src_lo], els*sizeof(TYPE));
684   };
685}
686
687// inline removed
688template <class TYPE> void
689TArray<TYPE>::insert(void * data, int els, int where,
690                     const void * what, int howmany)
691{
692   memmove(((TYPE *) data)+where+howmany,
693           ((TYPE *) data)+where, sizeof(TYPE)*(els-where));
694   for(int i=0;i<howmany;i++)
695      ((TYPE *) data)[where+i]=*(TYPE *) what;
696}
697
698template <class TYPE> 
699TArray<TYPE>::TArray ()
700{
701   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
702                       init2, init2, insert));
703}
704
705template <class TYPE> 
706TArray<TYPE>::TArray(int hi)
707{
708   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
709                       init2, init2, insert, hi));
710}
711
712template <class TYPE> 
713TArray<TYPE>::TArray(int lo, int hi)
714{
715   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
716                       init2, init2, insert, lo, hi));
717}
718
719//inline removal ends
720
721/** Dynamic array for general types.
722    Template class #DArray<TYPE># implements an array of
723    elements of type #TYPE#.  Each element is identified by an integer
724    subscript.  The valid subscripts range is defined by dynamically
725    adjustable lower- and upper-bounds.  Besides accessing and setting
726    elements, member functions are provided to insert or delete elements at
727    specified positions.
728
729    This template class must be able to access
730    \begin{itemize}
731    \item a null constructor #TYPE::TYPE()#,
732    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
733    \item and a copy operator #TYPE & operator=(const TYPE &)#.
734    \end{itemize}
735   
736    The class offers "copy-on-demand" policy, which means that when you
737    copy the array object, array elements will stay intact as long as you
738    don't try to modify them. As soon as you make an attempt to change
739    array contents, the copying is done automatically and transparently
740    for you - the procedure that we call "copy-on-demand". This is the main
741    difference between this class and \Ref{GArray} (now obsolete)
742       
743    Please note that most of the methods are implemented in the base classes
744    \Ref{ArrayBase} and \Ref{ArrayBaseT}.
745*/
746
747template <class TYPE>
748class DArray : public ArrayBaseT<TYPE> {
749public:
750   /** Constructs an empty array. The valid subscript range is initially
751       empty. Member function #touch# and #resize# provide convenient ways
752       to enlarge the subscript range. */
753   DArray(void);
754   /** Constructs an array with subscripts in range 0 to #hibound#.
755       The subscript range can be subsequently modified with member functions
756       #touch# and #resize#.
757       @param hibound upper bound of the initial subscript range. */
758   DArray(const int hibound);
759   /** Constructs an array with subscripts in range #lobound# to #hibound#. 
760       The subscript range can be subsequently modified with member functions
761       #touch# and #resize#.
762       @param lobound lower bound of the initial subscript range.
763       @param hibound upper bound of the initial subscript range. */
764   DArray(const int lobound, const int hibound);
765   
766   virtual ~DArray() {};
767private:
768      // Callbacks called from ArrayRep
769   static void          destroy(void * data, int lo, int hi);
770   static void          init1(void * data, int lo, int hi);
771   static void          init2(void * data, int lo, int hi,
772                             const void * src, int src_lo, int src_hi);
773   static void          copy(void * dst, int dst_lo, int dst_hi,
774                             const void * src, int src_lo, int src_hi);
775   static void          insert(void * data, int els, int where,
776                               const void * what, int howmany);
777};
778
779template <class TYPE> void
780DArray<TYPE>::destroy(void * data, int lo, int hi)
781{
782   if (data)
783      for(int i=lo;i<=hi;i++)
784         ((TYPE *) data)[i].TYPE::~TYPE();
785}
786
787template <class TYPE> void
788DArray<TYPE>::init1(void * data, int lo, int hi)
789{
790   if (data)
791      for(int i=lo;i<=hi;i++)
792         new ((void *) &((TYPE *) data)[i]) TYPE;
793}
794
795template <class TYPE> void
796DArray<TYPE>::init2(void * data, int lo, int hi,
797                    const void * src, int src_lo, int src_hi)
798{
799   if (data && src)
800   {
801      int i, j;
802      for(i=lo, j=src_lo;i<=hi && j<=src_hi;i++, j++)
803         new ((void *) &((TYPE *) data)[i]) TYPE(((TYPE *) src)[j]);
804   };
805}
806
807template <class TYPE> void
808DArray<TYPE>::copy(void * dst, int dst_lo, int dst_hi,
809                   const void * src, int src_lo, int src_hi)
810{
811   if (dst && src)
812   {
813      int i, j;
814      for(i=dst_lo, j=src_lo;i<=dst_hi && j<=src_hi;i++, j++)
815         ((TYPE *) dst)[i]=((TYPE *) src)[j];
816   };
817}
818
819template <class TYPE> inline void
820DArray<TYPE>::insert(void * data, int els, int where,
821                     const void * what, int howmany)
822{
823      // Now do the insertion
824   TYPE * d=(TYPE *) data;
825   
826   int i;
827   for (i=els+howmany-1; i>=els; i--)
828   {
829      if (i-where >= (int)howmany)
830         new ((void*) &d[i]) TYPE (d[i-howmany]);
831      else
832         new ((void*) &d[i]) TYPE (*(TYPE *) what);
833   }
834   
835   for (i=els-1; i>=where; i--)
836   {
837      if (i-where >= (int)howmany)
838         d[i] = d[i-howmany];
839      else
840         d[i] = *(TYPE *) what;
841   }
842}
843
844template <class TYPE> inline 
845DArray<TYPE>::DArray ()
846{
847   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
848                       init2, copy, insert));
849}
850
851template <class TYPE> inline 
852DArray<TYPE>::DArray(const int hi)
853{
854   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
855                       init2, copy, insert, hi));
856}
857
858template <class TYPE> inline 
859DArray<TYPE>::DArray(const int lo, const int hi)
860{
861   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
862                       init2, copy, insert, lo, hi));
863}
864
865/** Dynamic array for \Ref{GPBase}d classes.
866
867    There are many situations when it's necessary to create arrays of
868    \Ref{GP} pointers. For example, #DArray<GP<Dialog> ># or #DArray<GP<Button> >#.
869    This would result in compilation of two instances of \Ref{DArray} because
870    from the viewpoint of the compiler there are two different classes used
871    as array elements: #GP<Dialog># and #GP<Button>#. In reality though,
872    all \Ref{GP} pointers have absolutely the same binary structure because
873    they are derived from \Ref{GPBase} class and do not add any variables
874    or virtual functions. That's why it's possible to instantiate \Ref{DArray}
875    only once for \Ref{GPBase} elements and then just cast types.
876
877    To implement this idea we have created this #DPArray<TYPE># class,
878    which can be used instead of #DArray<GP<TYPE> >#. It behaves absolutely
879    the same way as \Ref{DArray} but has one big advantage: overhead of
880    using #DPArray# with one more type is negligible.
881  */
882template <class TYPE>
883class DPArray : public DArray<GPBase> {
884public:
885  // -- CONSTRUCTORS
886  DPArray();
887  DPArray(int hibound);
888  DPArray(int lobound, int hibound);
889  DPArray(const DPArray<TYPE> &gc);
890  // -- DESTRUCTOR
891  virtual ~DPArray();
892  // -- ACCESS
893  GP<TYPE>& operator[](int n);
894  const GP<TYPE>& operator[](int n) const;
895  // -- CONVERSION
896  operator GP<TYPE>* ();
897 
898#ifndef __MWERKS__ //MCW can't compile
899  operator const GP<TYPE>* ();
900#endif
901 
902  operator const GP<TYPE>* () const;
903  // -- ALTERATION
904  void ins(int n, const GP<TYPE> &val, unsigned int howmany=1);
905  DPArray<TYPE>& operator= (const DPArray &ga);
906};
907
908template<class TYPE>
909DPArray<TYPE>::DPArray() {}
910
911template<class TYPE>
912DPArray<TYPE>::DPArray(int hibound) :
913      DArray<GPBase>(hibound) {}
914
915template<class TYPE>
916DPArray<TYPE>::DPArray(int lobound, int hibound) :
917      DArray<GPBase>(lobound, hibound) {}
918
919template<class TYPE>
920DPArray<TYPE>::DPArray(const DPArray<TYPE> &gc) :
921      DArray<GPBase>(gc) {}
922
923template<class TYPE>
924DPArray<TYPE>::~DPArray() {}
925
926template<class TYPE>
927inline GP<TYPE> &
928DPArray<TYPE>::operator[](int n)
929{
930   return (GP<TYPE> &) DArray<GPBase>::operator[](n);
931}
932
933template<class TYPE>
934inline const GP<TYPE> &
935DPArray<TYPE>::operator[](int n) const
936{
937   return (const GP<TYPE> &) DArray<GPBase>::operator[](n);
938}
939
940template<class TYPE>
941inline DPArray<TYPE>::operator GP<TYPE>* ()
942{
943   return (GP<TYPE> *) DArray<GPBase>::operator GPBase*();
944}
945
946#ifndef __MWERKS__ //MCW can't compile
947template<class TYPE>
948inline DPArray<TYPE>::operator const GP<TYPE>* ()
949{
950   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
951}
952#endif
953
954template<class TYPE>
955inline DPArray<TYPE>::operator const GP<TYPE>* () const
956{
957   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
958}
959
960template<class TYPE>
961inline void
962DPArray<TYPE>::ins(int n, const GP<TYPE> & val, unsigned int howmany)
963{
964   DArray<GPBase>::ins(n, val, howmany);
965}
966
967template<class TYPE>
968inline DPArray<TYPE> &
969DPArray<TYPE>::operator= (const DPArray &ga)
970{
971   DArray<GPBase>::operator=(ga);
972   return *this;
973}
974
975// ------------ THE END
976
977//@}
978
979
980#ifdef HAVE_NAMESPACES
981}
982# ifndef NOT_USING_DJVU_NAMESPACE
983using namespace DJVU;
984# endif
985#endif
986#endif
987
Note: See TracBrowser for help on using the repository browser.