source: trunk/libdjvu/Arrays.h @ 15

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

needed libs update

File size: 31.6 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.10 2004/05/13 15:16:34 leonb Exp $
55// $Name: release_3_5_16 $
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.10 2004/05/13 15:16:34 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#ifndef __MWERKS__ //MCW can't compile
484   operator const TYPE* ();
485#endif 
486   /** Insert new elements into an array. This function inserts
487       #howmany# elements at position #n# into the array. The initial value #val#
488       is copied into the new elements. All array elements previously located at subscripts
489       #n# and higher are moved to subscripts #n+howmany# and higher. The upper bound of the
490       valid subscript range is increased in order to account for this shift.
491       @param n subscript of the first inserted element.
492       @param val initial value of the new elements.
493       @param howmany number of elements to insert. */
494   void ins(int n, const TYPE &val, unsigned int howmany=1);
495
496   /** Sort array elements.  Sort all array elements in ascending order.  Array
497       elements are compared using the less-or-equal comparison operator for
498       type #TYPE#. */
499   void sort();
500   /** Sort array elements in subscript range #lo# to #hi#.  Sort all array
501       elements whose subscripts are in range #lo#..#hi# in ascending order.
502       The other elements of the array are left untouched.  An exception is
503       thrown if arguments #lo# and #hi# are not in the valid subscript range.
504       Array elements are compared using the less-or-equal comparison operator
505       for type #TYPE#. 
506       @param lo low bound for the subscripts of the elements to sort. 
507       @param hi high bound for the subscripts of the elements to sort. */
508   void sort(int lo, int hi);
509protected:
510   ArrayBaseT(void) {};
511private:
512      // Callbacks called from ArrayRep
513   static void          destroy(void * data, int lo, int hi);
514   static void          init1(void * data, int lo, int hi);
515   static void          init2(void * data, int lo, int hi,
516                             const void * src, int src_lo, int src_hi);
517   static void          copy(void * dst, int dst_lo, int dst_hi,
518                             const void * src, int src_lo, int src_hi);
519   static void          insert(void * data, int els, int where,
520                               const void * what, int howmany);
521};
522
523template <class TYPE> inline
524ArrayBaseT<TYPE>::operator TYPE* ()
525{
526   check();
527   
528   ArrayRep * rep=(ArrayRep *) get();
529   return &((TYPE *) rep->data)[-rep->minlo];
530}
531
532#ifndef __MWERKS__ //MCW can't compile
533template <class TYPE> inline
534ArrayBaseT<TYPE>::operator const TYPE* ()
535{
536   const ArrayRep * rep=(const ArrayRep *) get();
537   return &((const TYPE *) rep->data)[-rep->minlo];
538}
539#endif
540
541template <class TYPE> inline
542ArrayBaseT<TYPE>::operator const TYPE* () const
543{
544   const ArrayRep * rep=(const ArrayRep *) get();
545   return &((const TYPE *) rep->data)[-rep->minlo];
546}
547
548template <class TYPE> inline TYPE& 
549ArrayBaseT<TYPE>::operator[](int n)
550{
551   check();
552
553   ArrayRep * rep=(ArrayRep *) get();
554   if (n<rep->lobound || n>rep->hibound)
555      G_THROW( ERR_MSG("arrays.ill_sub") );
556   return ((TYPE *) rep->data)[n - rep->minlo];
557}
558
559template <class TYPE> inline const TYPE& 
560ArrayBaseT<TYPE>::operator[](int n) const
561{
562   const ArrayRep * rep=(const ArrayRep *) get();
563   if (n<rep->lobound || n>rep->hibound)
564      G_THROW( ERR_MSG("arrays.ill_sub") );
565   return ((const TYPE *) rep->data)[n - rep->minlo];
566}
567
568template <class TYPE> inline void
569ArrayBaseT<TYPE>::ins(int n, const TYPE &val, unsigned int howmany)
570{
571   check();
572   
573   ((ArrayRep *) get())->ins(n, &val, howmany);
574}
575
576template <class TYPE> void
577ArrayBaseT<TYPE>::sort()
578{
579   sort(lbound(), hbound());
580}
581
582template <class TYPE> void
583ArrayBaseT<TYPE>::sort(int lo, int hi)
584{
585   if (hi <= lo)
586      return;
587      // Test for insertion sort (optimize!)
588   if (hi <= lo + 20)
589   {
590      for (int i=lo+1; i<=hi; i++)
591      {
592         int j = i;
593         TYPE tmp = (*this)[i];
594         while ((--j>=lo) && !((*this)[j]<=tmp))
595            (*this)[j+1] = (*this)[j];
596         (*this)[j+1] = tmp;
597      }
598      return;
599   }
600      // -- determine suitable quick-sort pivot
601   TYPE tmp = (*this)[lo];
602   TYPE pivot = (*this)[(lo+hi)/2];
603   if (pivot <= tmp)
604   { tmp = pivot; pivot=(*this)[lo]; }
605   if ((*this)[hi] <= tmp)
606   { pivot = tmp; }
607   else if ((*this)[hi] <= pivot)
608   { pivot = (*this)[hi]; }
609      // -- partition set
610   int h = hi;
611   int l = lo;
612   while (l < h)
613   {
614      while (! (pivot <= (*this)[l])) l++;
615      while (! ((*this)[h] <= pivot)) h--;
616      if (l < h)
617      {
618         tmp = (*this)[l];
619         (*this)[l] = (*this)[h];
620         (*this)[h] = tmp;
621         l = l+1;
622         h = h-1;
623      }
624   }
625      // -- recursively restart
626   sort(lo, h);
627   sort(l, hi);
628}
629
630/** Dynamic array for simple types. 
631    Template class #TArray<TYPE># implements an array of
632    elements of {\em simple} type #TYPE#. {\em Simple} means that the type
633    may be #char#, #int#, #float# etc. The limitation is imposed by the
634    way in which the #TArray# is working with its elements: it's not trying
635    to execute elements' constructors, destructors or copy operators. It's
636    just doing bitwise copy. Except for this it's pretty much the same as
637    \Ref{DArray}.
638   
639    Please note that most of the methods are implemented in the base classes
640    \Ref{ArrayBase} and \Ref{ArrayBaseT}.
641*/
642
643template <class TYPE>
644class TArray : public ArrayBaseT<TYPE> {
645public:
646   /** Constructs an empty array. The valid subscript range is initially
647       empty. Member function #touch# and #resize# provide convenient ways
648       to enlarge the subscript range. */
649   TArray();
650   /** Constructs an array with subscripts in range 0 to #hibound#.
651       The subscript range can be subsequently modified with member functions
652       #touch# and #resize#.
653       @param hibound upper bound of the initial subscript range. */
654   TArray(int hibound);
655   /** Constructs an array with subscripts in range #lobound# to #hibound#. 
656       The subscript range can be subsequently modified with member functions
657       #touch# and #resize#.
658       @param lobound lower bound of the initial subscript range.
659       @param hibound upper bound of the initial subscript range. */
660   TArray(int lobound, int hibound);
661   
662   virtual ~TArray() {};
663private:
664      // Callbacks called from ArrayRep
665   static void          destroy(void * data, int lo, int hi);
666   static void          init1(void * data, int lo, int hi);
667   static void          init2(void * data, int lo, int hi,
668                             const void * src, int src_lo, int src_hi);
669   static void          insert(void * data, int els, int where,
670                               const void * what, int howmany);
671};
672
673template <class TYPE> void
674TArray<TYPE>::destroy(void * data, int lo, int hi)
675{
676}
677
678template <class TYPE> void
679TArray<TYPE>::init1(void * data, int lo, int hi)
680{
681}
682
683template <class TYPE> void
684TArray<TYPE>::init2(void * data, int lo, int hi,
685                    const void * src, int src_lo, int src_hi)
686{
687   if (data && src)
688   {
689      int els=hi-lo+1;
690      if (els>src_hi-src_lo+1) els=src_hi-src_lo+1;
691      if (els>0)
692         memmove((void *) &((TYPE *) data)[lo],
693                 (void *) &((TYPE *) src)[src_lo], els*sizeof(TYPE));
694   };
695}
696
697// inline removed
698template <class TYPE> void
699TArray<TYPE>::insert(void * data, int els, int where,
700                     const void * what, int howmany)
701{
702   memmove(((TYPE *) data)+where+howmany,
703           ((TYPE *) data)+where, sizeof(TYPE)*(els-where));
704   for(int i=0;i<howmany;i++)
705      ((TYPE *) data)[where+i]=*(TYPE *) what;
706}
707
708template <class TYPE> 
709TArray<TYPE>::TArray ()
710{
711   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
712                       init2, init2, insert));
713}
714
715template <class TYPE> 
716TArray<TYPE>::TArray(int hi)
717{
718   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
719                       init2, init2, insert, hi));
720}
721
722template <class TYPE> 
723TArray<TYPE>::TArray(int lo, int hi)
724{
725   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
726                       init2, init2, insert, lo, hi));
727}
728
729//inline removal ends
730
731/** Dynamic array for general types.
732    Template class #DArray<TYPE># implements an array of
733    elements of type #TYPE#.  Each element is identified by an integer
734    subscript.  The valid subscripts range is defined by dynamically
735    adjustable lower- and upper-bounds.  Besides accessing and setting
736    elements, member functions are provided to insert or delete elements at
737    specified positions.
738
739    This template class must be able to access
740    \begin{itemize}
741    \item a null constructor #TYPE::TYPE()#,
742    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
743    \item and a copy operator #TYPE & operator=(const TYPE &)#.
744    \end{itemize}
745   
746    The class offers "copy-on-demand" policy, which means that when you
747    copy the array object, array elements will stay intact as long as you
748    don't try to modify them. As soon as you make an attempt to change
749    array contents, the copying is done automatically and transparently
750    for you - the procedure that we call "copy-on-demand". This is the main
751    difference between this class and \Ref{GArray} (now obsolete)
752       
753    Please note that most of the methods are implemented in the base classes
754    \Ref{ArrayBase} and \Ref{ArrayBaseT}.
755*/
756
757template <class TYPE>
758class DArray : public ArrayBaseT<TYPE> {
759public:
760   /** Constructs an empty array. The valid subscript range is initially
761       empty. Member function #touch# and #resize# provide convenient ways
762       to enlarge the subscript range. */
763   DArray(void);
764   /** Constructs an array with subscripts in range 0 to #hibound#.
765       The subscript range can be subsequently modified with member functions
766       #touch# and #resize#.
767       @param hibound upper bound of the initial subscript range. */
768   DArray(const int hibound);
769   /** Constructs an array with subscripts in range #lobound# to #hibound#. 
770       The subscript range can be subsequently modified with member functions
771       #touch# and #resize#.
772       @param lobound lower bound of the initial subscript range.
773       @param hibound upper bound of the initial subscript range. */
774   DArray(const int lobound, const int hibound);
775   
776   virtual ~DArray() {};
777private:
778      // Callbacks called from ArrayRep
779   static void          destroy(void * data, int lo, int hi);
780   static void          init1(void * data, int lo, int hi);
781   static void          init2(void * data, int lo, int hi,
782                             const void * src, int src_lo, int src_hi);
783   static void          copy(void * dst, int dst_lo, int dst_hi,
784                             const void * src, int src_lo, int src_hi);
785   static void          insert(void * data, int els, int where,
786                               const void * what, int howmany);
787};
788
789template <class TYPE> void
790DArray<TYPE>::destroy(void * data, int lo, int hi)
791{
792   if (data)
793      for(int i=lo;i<=hi;i++)
794         ((TYPE *) data)[i].TYPE::~TYPE();
795}
796
797template <class TYPE> void
798DArray<TYPE>::init1(void * data, int lo, int hi)
799{
800   if (data)
801      for(int i=lo;i<=hi;i++)
802         new ((void *) &((TYPE *) data)[i]) TYPE;
803}
804
805template <class TYPE> void
806DArray<TYPE>::init2(void * data, int lo, int hi,
807                    const void * src, int src_lo, int src_hi)
808{
809   if (data && src)
810   {
811      int i, j;
812      for(i=lo, j=src_lo;i<=hi && j<=src_hi;i++, j++)
813         new ((void *) &((TYPE *) data)[i]) TYPE(((TYPE *) src)[j]);
814   };
815}
816
817template <class TYPE> void
818DArray<TYPE>::copy(void * dst, int dst_lo, int dst_hi,
819                   const void * src, int src_lo, int src_hi)
820{
821   if (dst && src)
822   {
823      int i, j;
824      for(i=dst_lo, j=src_lo;i<=dst_hi && j<=src_hi;i++, j++)
825         ((TYPE *) dst)[i]=((TYPE *) src)[j];
826   };
827}
828
829template <class TYPE> inline void
830DArray<TYPE>::insert(void * data, int els, int where,
831                     const void * what, int howmany)
832{
833      // Now do the insertion
834   TYPE * d=(TYPE *) data;
835   
836   int i;
837   for (i=els+howmany-1; i>=els; i--)
838   {
839      if (i-where >= (int)howmany)
840         new ((void*) &d[i]) TYPE (d[i-howmany]);
841      else
842         new ((void*) &d[i]) TYPE (*(TYPE *) what);
843   }
844   
845   for (i=els-1; i>=where; i--)
846   {
847      if (i-where >= (int)howmany)
848         d[i] = d[i-howmany];
849      else
850         d[i] = *(TYPE *) what;
851   }
852}
853
854template <class TYPE> inline 
855DArray<TYPE>::DArray ()
856{
857   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
858                       init2, copy, insert));
859}
860
861template <class TYPE> inline 
862DArray<TYPE>::DArray(const int hi)
863{
864   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
865                       init2, copy, insert, hi));
866}
867
868template <class TYPE> inline 
869DArray<TYPE>::DArray(const int lo, const int hi)
870{
871   this->assign(new ArrayRep(sizeof(TYPE), destroy, init1,
872                       init2, copy, insert, lo, hi));
873}
874
875/** Dynamic array for \Ref{GPBase}d classes.
876
877    There are many situations when it's necessary to create arrays of
878    \Ref{GP} pointers. For example, #DArray<GP<Dialog> ># or #DArray<GP<Button> >#.
879    This would result in compilation of two instances of \Ref{DArray} because
880    from the viewpoint of the compiler there are two different classes used
881    as array elements: #GP<Dialog># and #GP<Button>#. In reality though,
882    all \Ref{GP} pointers have absolutely the same binary structure because
883    they are derived from \Ref{GPBase} class and do not add any variables
884    or virtual functions. That's why it's possible to instantiate \Ref{DArray}
885    only once for \Ref{GPBase} elements and then just cast types.
886
887    To implement this idea we have created this #DPArray<TYPE># class,
888    which can be used instead of #DArray<GP<TYPE> >#. It behaves absolutely
889    the same way as \Ref{DArray} but has one big advantage: overhead of
890    using #DPArray# with one more type is negligible.
891  */
892template <class TYPE>
893class DPArray : public DArray<GPBase> {
894public:
895  // -- CONSTRUCTORS
896  DPArray();
897  DPArray(int hibound);
898  DPArray(int lobound, int hibound);
899  DPArray(const DPArray<TYPE> &gc);
900  // -- DESTRUCTOR
901  virtual ~DPArray();
902  // -- ACCESS
903  GP<TYPE>& operator[](int n);
904  const GP<TYPE>& operator[](int n) const;
905  // -- CONVERSION
906  operator GP<TYPE>* ();
907 
908#ifndef __MWERKS__ //MCW can't compile
909  operator const GP<TYPE>* ();
910#endif
911 
912  operator const GP<TYPE>* () const;
913  // -- ALTERATION
914  void ins(int n, const GP<TYPE> &val, unsigned int howmany=1);
915  DPArray<TYPE>& operator= (const DPArray &ga);
916};
917
918template<class TYPE>
919DPArray<TYPE>::DPArray() {}
920
921template<class TYPE>
922DPArray<TYPE>::DPArray(int hibound) :
923      DArray<GPBase>(hibound) {}
924
925template<class TYPE>
926DPArray<TYPE>::DPArray(int lobound, int hibound) :
927      DArray<GPBase>(lobound, hibound) {}
928
929template<class TYPE>
930DPArray<TYPE>::DPArray(const DPArray<TYPE> &gc) :
931      DArray<GPBase>(gc) {}
932
933template<class TYPE>
934DPArray<TYPE>::~DPArray() {}
935
936template<class TYPE>
937inline GP<TYPE> &
938DPArray<TYPE>::operator[](int n)
939{
940   return (GP<TYPE> &) DArray<GPBase>::operator[](n);
941}
942
943template<class TYPE>
944inline const GP<TYPE> &
945DPArray<TYPE>::operator[](int n) const
946{
947   return (const GP<TYPE> &) DArray<GPBase>::operator[](n);
948}
949
950template<class TYPE>
951inline DPArray<TYPE>::operator GP<TYPE>* ()
952{
953   return (GP<TYPE> *) DArray<GPBase>::operator GPBase*();
954}
955
956#ifndef __MWERKS__ //MCW can't compile
957template<class TYPE>
958inline DPArray<TYPE>::operator const GP<TYPE>* ()
959{
960   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
961}
962#endif
963
964template<class TYPE>
965inline DPArray<TYPE>::operator const GP<TYPE>* () const
966{
967   return (const GP<TYPE> *) DArray<GPBase>::operator const GPBase*();
968}
969
970template<class TYPE>
971inline void
972DPArray<TYPE>::ins(int n, const GP<TYPE> & val, unsigned int howmany)
973{
974   DArray<GPBase>::ins(n, val, howmany);
975}
976
977template<class TYPE>
978inline DPArray<TYPE> &
979DPArray<TYPE>::operator= (const DPArray &ga)
980{
981   DArray<GPBase>::operator=(ga);
982   return *this;
983}
984
985// ------------ THE END
986
987//@}
988
989
990#ifdef HAVE_NAMESPACES
991}
992# ifndef NOT_USING_DJVU_NAMESPACE
993using namespace DJVU;
994# endif
995#endif
996#endif
997
Note: See TracBrowser for help on using the repository browser.