source: trunk/libdjvu/Arrays.h @ 199

Last change on this file since 199 was 17, checked in by Eugene Romanenko, 16 years ago

update makefiles, remove absolute paths, update djvulibre to version 3.5.17

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