source: trunk/libdjvu/GContainer.h @ 280

Last change on this file since 280 was 280, checked in by rbri, 11 years ago

DJVU plugin: djvulibre updated to version 3.5.22

File size: 47.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, 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: GContainer.h,v 1.21 2008/01/07 11:48:52 leonb Exp $
57// $Name: release_3_5_22 $
58
59#ifndef _GCONTAINER_H_
60#define _GCONTAINER_H_
61#ifdef HAVE_CONFIG_H
62#include "config.h"
63#endif
64#if NEED_GNUG_PRAGMAS
65# pragma interface
66#endif
67
68
69#include "GException.h"
70#include "GSmartPointer.h"
71#include <string.h>
72
73#ifdef HAVE_NAMESPACES
74namespace DJVU {
75# ifdef NOT_DEFINED // Just to fool emacs c++ mode
76}
77#endif
78#endif
79
80
81// Supports old iterators (first/last/next/prev) on lists and maps?
82#ifndef GCONTAINER_OLD_ITERATORS
83#define GCONTAINER_OLD_ITERATORS 1
84#endif
85
86// Check array bounds at runtime ?
87#ifndef GCONTAINER_BOUNDS_CHECK
88#define GCONTAINER_BOUNDS_CHECK 1
89#endif
90
91// Clears allocated memory prior to running constructors ?
92#ifndef GCONTAINER_ZERO_FILL
93#define GCONTAINER_ZERO_FILL 1
94#endif
95
96// Avoid member templates (needed by old compilers)
97#ifndef GCONTAINER_NO_MEMBER_TEMPLATES
98#if defined(__GNUC__) && (__GNUC__==2) && (__GNUC_MINOR__<91)
99#define GCONTAINER_NO_MEMBER_TEMPLATES 1
100#elif defined(_MSC_VER) && !defined(__ICL)
101#define GCONTAINER_NO_MEMBER_TEMPLATES 1
102#elif defined(__MWERKS__)
103#define GCONTAINER_NO_MEMBER_TEMPLATES 1
104#else
105#define GCONTAINER_NO_MEMBER_TEMPLATES 0
106#endif
107#endif
108
109// Define typename when needed
110#ifndef GCONTAINER_NO_TYPENAME
111#define GCONTAINER_NO_TYPENAME 0
112#endif
113#if GCONTAINER_NO_TYPENAME
114#define typename /**/
115#endif
116
117
118/** @name GContainer.h
119
120    Files #"GContainer.h"# and #"GContainer.cpp"# implement three main
121    template class for generic containers. 
122    Class #GArray# (see \Ref{Dynamic Arrays}) implements an array of objects
123    with variable bounds. Class #GList# (see \Ref{Doubly Linked Lists})
124    implements a doubly linked list of objects.  Class #GMap# (see
125    \Ref{Associative Maps}) implements a hashed associative map.  The
126    container templates are not thread-safe. Thread safety can be implemented
127    using the facilities provided in \Ref{GThreads.h}.
128   
129    @memo
130    Template class for generic containers.
131    @author
132    L\'eon Bottou <leonb@research.att.com> -- initial implementation.\\
133    Andrei Erofeev <eaf@geocities.com> -- bug fixes.
134    @version
135    #$Id: GContainer.h,v 1.21 2008/01/07 11:48:52 leonb Exp $# */
136//@{
137
138
139
140// ------------------------------------------------------------
141// HASH FUNCTIONS
142// ------------------------------------------------------------
143
144
145/** @name Hash functions
146    These functions let you use template class \Ref{GMap} with the
147    corresponding elementary types. The returned hash code may be reduced to
148    an arbitrary range by computing its remainder modulo the upper bound of
149    the range.
150    @memo Hash functions for elementary types. */
151//@{
152
153/** Hashing function (unsigned int). */
154static inline unsigned int 
155hash(const unsigned int & x) 
156{ 
157  return x; 
158}
159
160/** Hashing function (int). */
161static inline unsigned int 
162hash(const int & x) 
163{ 
164  return (unsigned int)x;
165}
166
167/** Hashing function (long). */
168static inline unsigned int
169hash(const long & x) 
170{ 
171  return (unsigned int)x;
172}
173
174/** Hashing function (unsigned long). */
175static inline unsigned int
176hash(const unsigned long & x) 
177{ 
178  return (unsigned int)x;
179}
180
181/** Hashing function (const void *). */
182static inline unsigned int 
183hash(const void * const & x) 
184{ 
185  return (unsigned long) x; 
186}
187
188/** Hashing function (float). */
189static inline unsigned int
190hash(const float & x) 
191{ 
192  // optimizer will get rid of unnecessary code 
193  unsigned int *addr = (unsigned int*)&x;
194  if (sizeof(float)<2*sizeof(unsigned int))
195    return addr[0];
196  else
197    return addr[0]^addr[1];
198}
199
200/** Hashing function (double). */
201static inline unsigned int
202hash(const double & x) 
203{ 
204  // optimizer will get rid of unnecessary code
205  unsigned int *addr = (unsigned int*)&x;
206  if (sizeof(double)<2*sizeof(unsigned int))
207    return addr[0];
208  else if (sizeof(double)<4*sizeof(unsigned int))
209    return addr[0]^addr[1];
210  else
211    return addr[0]^addr[1]^addr[2]^addr[3];   
212}
213
214
215
216// ------------------------------------------------------------
217// HELPER CLASSES
218// ------------------------------------------------------------
219
220
221
222/* Namespace for containers support classes.  This class is used as a
223   namespace for global identifiers related to the implementation of
224   containers.  It is inherited by all container objects.  This is disabled by
225   defining compilation symbol #GCONTAINER_NO_MEMBER_TEMPATES# to 1. */
226
227
228#ifdef _MSC_VER
229// Language lawyer say MS is wrong on that one.
230// Cf section 5.4.7 in november 1997 draft.
231#pragma warning( disable : 4243 )
232#endif
233
234
235// GPEnabled inhertenced removed again so the code works on more machines.
236class GCont
237#if GCONTAINER_NO_MEMBER_TEMPLATES
238{
239};
240#else
241{
242public:
243#endif
244  // --- Pointers to type management functions
245  struct Traits
246  {
247    int       size;
248    void     *(*lea)     (void *base, int n);
249    void      (*init)    (void *dst, int n); 
250    void      (*copy)    (void *dst, const void* src, int n, int zap);
251    void      (*fini)    (void *dst, int n);
252  };
253#if !GCONTAINER_NO_MEMBER_TEMPLATES
254protected:
255#endif
256  // --- Management of simple types
257  template <int SZ> class TrivTraits
258  {
259  public:
260    // The unique object
261    static const Traits & traits();
262    // Offset in an array of T
263    static void * lea(void* base, int n)
264      { return (void*)( ((char*)base) + SZ*n ); }
265    // Trivial default constructor
266    static void   init(void* dst, int n) {}
267    // Trivial copy constructor
268    static void   copy(void* dst, const void* src, int n, int ) 
269      { memcpy(dst, src, SZ*n); }
270    // Trivial destructor
271    static void   fini(void* dst, int n) {}
272  };
273  // --- Management of regular types
274  template <class T> class NormTraits
275  {
276  public:
277    // The unique object
278    static const Traits & traits();
279    // Offset in an array of T
280    static void * lea(void* base, int n)
281      { return (void*)( ((T*)base) + n ); }
282    // Template based default constructor
283    static void init(void* dst, int n) 
284      { T* d = (T*)dst; while (--n>=0) { new ((void*)d) T; d++; } }
285    // Template based copy constructor
286    static void copy(void* dst, const void* src, int n, int zap)
287      { T* d = (T*)dst; T* s = (T*)src; while (--n>=0) { 
288          new ((void*)d) T(*s); if (zap) { s->~T(); }; d++; s++; } }
289    // Template based destructor
290    static void fini(void* dst, int n) 
291      { T* d = (T*)dst; while (--n>=0) { d->~T(); d++; } }
292  };
293  // --- Base class for list nodes
294  struct Node
295  {
296    Node *next;
297    Node *prev;
298  };
299  // -- Class for list nodes
300  template <class T> struct ListNode : public Node
301  { 
302    T val;
303  };
304  // -- Class for map nodes showing the hash
305  struct HNode : public Node
306  {
307    HNode *hprev;
308    unsigned int hashcode;
309  };
310  // -- Class for map nodes showing the hash and the key
311  template <class K> struct SetNode : public HNode
312  { 
313    K key;
314  };
315  // -- Class for map nodes with everything
316  template <class K, class T> struct MapNode : public SetNode<K>
317  {
318    T val;
319  };
320#if !GCONTAINER_NO_MEMBER_TEMPLATES
321};
322#endif
323
324
325#if !GCONTAINER_NO_MEMBER_TEMPLATES
326#define GCONT GCont::
327#else
328#define GCONT
329#endif
330
331template <int SZ> const GCONT Traits & 
332GCONT TrivTraits<SZ>::traits()
333{
334  static const Traits theTraits = {
335    SZ,
336    TrivTraits<SZ>::lea,
337    TrivTraits<SZ>::init,
338    TrivTraits<SZ>::copy,
339    TrivTraits<SZ>::fini
340  };
341  return theTraits;
342}
343
344template <class T> const GCONT Traits & 
345GCONT NormTraits<T>::traits()
346{
347  static const Traits theTraits = {
348    sizeof(T),
349    NormTraits<T>::lea,
350    NormTraits<T>::init,
351    NormTraits<T>::copy,
352    NormTraits<T>::fini
353  };
354  return theTraits;
355}
356
357
358// ------------------------------------------------------------
359// DYNAMIC ARRAYS
360// ------------------------------------------------------------
361
362
363/** @name Dynamic Arrays
364
365    These class implement arrays of objects of any type.  Each element is
366    identified by an integer subscript.  The valid subscripts range is defined
367    by dynamically adjustable lower- and upper-bounds.  Besides accessing and
368    setting elements, member functions are provided to insert or delete
369    elements at specified positions.
370
371    Class \Ref{GArrayTemplate} implements all methods for manipulating arrays
372    of type #TYPE#.  You should not however create instances of this class.
373    You should instead use one of the following classes:
374    \begin{itemize}
375    \item Class \Ref{GArray<TYPE>} is the most general class,
376    \item Class \Ref{GTArray<TYPE>} is more efficient, but only works for
377          types that do not require sophisticated constructors or destructors,
378          such as the plain old C types (e.g. #int# or #char# ...).
379    \item Class \Ref{GPArray<TYPE>} implements an array of smart-pointers
380          \Ref{GP<TYPE>} to objects of type #TYPE#.  Using this class
381          reduces the size of the code generated by the template instanciation.
382    \end{itemize}
383
384    Another variant of dynamic arrays is implemented in file \Ref{Arrays.h}.
385    The main difference is that class \Ref{TArray}, \Ref{DArray} and
386    \Ref{DPArray} implement a copy-on-demand scheme.
387
388    @memo Dynamic arrays.  */
389//@{
390
391class DJVUAPI GArrayBase : public GCont
392{
393public:
394  // -- CONSTRUCTORS
395  GArrayBase(const GArrayBase &ref);
396  GArrayBase(const Traits &traits);
397  GArrayBase(const Traits &traits, int lobound, int hibound);
398  // -- DESTRUCTOR
399  ~GArrayBase();
400  // -- ASSIGNMENT
401  GArrayBase& operator= (const GArrayBase &ga);
402  // -- ALTERATION
403  void empty();
404  void touch(int n);
405  void resize(int lobound, int hibound);
406  void shift(int disp);
407  void del(int n, int howmany=1);
408  void ins(int n, const void *src, int howmany=1);
409  void steal(GArrayBase &ga);
410protected:
411  const Traits &traits;
412  void  *data;
413  int   minlo;
414  int   maxhi;
415  int   lobound;
416  int   hibound;
417};
418
419
420/** Common base class for all dynamic arrays. 
421    Class \Ref{GArrayTemplate} implements all methods for manipulating arrays
422    of type #TYPE#.  You should not however create instances of this class.
423    You should instead use class \Ref{GArray}, \Ref{GTArray} or
424    \Ref{GPArray}. */
425
426template<class TYPE>
427class GArrayTemplate : protected GArrayBase
428{
429public:
430  // -- CONSTRUCTORS
431  GArrayTemplate(const Traits &traits) : GArrayBase(traits) {}
432  GArrayTemplate(const Traits &traits, int lobound, int hibound)
433    : GArrayBase(traits, lobound, hibound) {}
434  // -- ACCESS
435  /** Returns the number of elements in the array. */
436  int size() const
437    { return hibound-lobound+1; }
438  /** Returns the lower bound of the valid subscript range. */
439  int lbound() const
440    { return lobound; }
441  /** Returns the upper bound of the valid subscript range. */
442  int hbound() const
443    { return hibound; }
444  /** Returns a reference to the array element for subscript #n#.  This
445      reference can be used for both reading (as "#a[n]#") and writing (as
446      "#a[n]=v#") an array element.  This operation will not extend the valid
447      subscript range: an exception \Ref{GException} is thrown if argument #n#
448      is not in the valid subscript range. */
449  inline TYPE& operator[](int const n);
450  /** Returns a constant reference to the array element for subscript #n#.
451      This reference can only be used for reading (as "#a[n]#") an array
452      element.  This operation will not extend the valid subscript range: an
453      exception \Ref{GException} is thrown if argument #n# is not in the valid
454      subscript range.  This variant of #operator[]# is necessary when dealing
455      with a #const GArray<TYPE>#. */
456  inline const TYPE& operator[](int n) const;
457  // -- CONVERSION
458  /** Returns a pointer for reading or writing the array elements.  This
459      pointer can be used to access the array elements with the same
460      subscripts and the usual bracket syntax.  This pointer remains valid as
461      long as the valid subscript range is unchanged. If you change the
462      subscript range, you must stop using the pointers returned by prior
463      invocation of this conversion operator. */
464  operator TYPE* ()
465    { return ((TYPE*)data)-minlo; }
466  /** Returns a pointer for reading (but not modifying) the array elements.
467      This pointer can be used to access the array elements with the same
468      subscripts and the usual bracket syntax.  This pointer remains valid as
469      long as the valid subscript range is unchanged. If you change the
470      subscript range, you must stop using the pointers returned by prior
471      invocation of this conversion operator. */
472  operator const TYPE* () const
473    { return ((const TYPE*)data)-minlo; }
474  // -- ALTERATION
475  /** Erases the array contents. All elements in the array are destroyed. 
476      The valid subscript range is set to the empty range. */
477  void empty()
478    { GArrayBase::empty(); }
479  /** Extends the subscript range so that it contains #n#.
480      This function does nothing if #n# is already int the valid subscript range.
481      If the valid range was empty, both the lower bound and the upper bound
482      are set to #n#.  Otherwise the valid subscript range is extended
483      to encompass #n#. This function is very handy when called before setting
484      an array element:
485      \begin{verbatim}
486       int lineno=1;
487       GArray<GString> a;
488       while (! end_of_file()) {
489         a.touch(lineno);
490         a[lineno++] = read_a_line();
491       }
492      \end{verbatim} */
493  void touch(int n)
494    { if (n<lobound || n>hibound) GArrayBase::touch(n); }
495  /** Resets the valid subscript range to #0#---#hibound#.
496      This function may destroy some array elements and may construct
497      new array elements with the null constructor. Setting #hibound# to
498      #-1# resets the valid subscript range to the empty range. */
499  void resize(int hibound)
500    { GArrayBase::resize(0, hibound); }
501  /** Resets the valid subscript range to #lobound#---#hibound#.
502      This function may destroy some array elements and may construct
503      new array elements with the null constructor. Setting #lobound# to #0# and
504      #hibound# to #-1# resets the valid subscript range to the empty range. */
505  void resize(int lobound, int hibound)
506    { GArrayBase::resize(lobound, hibound); }
507  /** Shifts the valid subscript range. Argument #disp# is added to both
508      bounds of the valid subscript range. Array elements previously
509      located at subscript #x# will now be located at subscript #x+disp#. */
510  void shift(int disp)
511    { GArrayBase::shift(disp); }
512  /** Deletes array elements. The array elements corresponding to
513      subscripts #n#...#n+howmany-1# are destroyed. All array elements
514      previously located at subscripts greater or equal to #n+howmany#
515      are moved to subscripts starting with #n#. The new subscript upper
516      bound is reduced in order to account for this shift. */
517  void del(int n, int howmany=1)
518    { GArrayBase::del(n, howmany); }
519  /** Insert new elements into an array. This function inserts
520      #howmany# elements at position #n# into the array. These
521      elements are constructed using the default constructor for type
522      #TYPE#.  All array elements previously located at subscripts #n#
523      and higher are moved to subscripts #n+howmany# and higher. The
524      upper bound of the valid subscript range is increased in order
525      to account for this shift. */
526  void ins(int n, int howmany=1)
527    { GArrayBase::ins(n, 0, howmany); }
528  /** Insert new elements into an array. The new elements are
529      constructed by copying element #val# using the copy constructor
530      for type #TYPE#. See \Ref{ins(int n, unsigned int howmany=1)}. */
531  void ins(int n, const TYPE &val, int howmany=1)
532    { GArrayBase::ins(n, (const void*)&val, howmany); }
533  /** Steals contents from array #ga#.  After this call, array #ga# is empty,
534      and this array contains everything previously contained in #ga#. */
535  void steal(GArrayTemplate &ga)
536    { GArrayBase::steal(ga); }
537  // -- SORTING
538  /** Sort array elements.  Sort all array elements in ascending
539      order according to the less-or-equal comparison
540      operator for type #TYPE#. */
541  void sort()
542    { sort(lbound(), hbound()); }
543  /** Sort array elements in subscript range #lo# to #hi#.  Sort all array
544      elements whose subscripts are in range #lo# to #hi# in ascending order
545      according to the less-or-equal comparison operator for type #TYPE#.  The
546      other elements of the array are left untouched.  An exception is thrown
547      if arguments #lo# and #hi# are not in the valid subscript range.  */
548  void sort(int lo, int hi);
549};
550
551
552
553/* That one must be implemented as a regular template function. */
554template <class TYPE> void
555GArrayTemplate<TYPE>::sort(int lo, int hi)
556{
557  if (hi <= lo)
558    return;
559  if (hi > hibound || lo<lobound)
560    G_THROW( ERR_MSG("GContainer.illegal_subscript") );
561  TYPE *data = (TYPE*)(*this);
562  // Test for insertion sort
563  if (hi <= lo + 50)
564    {
565      for (int i=lo+1; i<=hi; i++)
566        {
567          int j = i;
568          TYPE tmp = data[i];
569          while ((--j>=lo) && !(data[j]<=tmp))
570            data[j+1] = data[j];
571          data[j+1] = tmp;
572        }
573      return;
574    }
575  // -- determine suitable quick-sort pivot
576  TYPE tmp = data[lo];
577  TYPE pivot = data[(lo+hi)/2];
578  if (pivot <= tmp)
579    { tmp = pivot; pivot=data[lo]; }
580  if (data[hi] <= tmp)
581    { pivot = tmp; }
582  else if (data[hi] <= pivot)
583    { pivot = data[hi]; }
584  // -- partition set
585  int h = hi;
586  int l = lo;
587  while (l < h)
588    {
589      while (! (pivot <= data[l])) l++;
590      while (! (data[h] <= pivot)) h--;
591      if (l < h)
592        {
593          tmp = data[l];
594          data[l] = data[h];
595          data[h] = tmp;
596          l = l+1;
597          h = h-1;
598      }
599    }
600  // -- recursively restart
601  sort(lo, h);
602  sort(l, hi);
603}
604
605template<class TYPE> inline TYPE&
606GArrayTemplate<TYPE>::operator[](int const n)
607{
608#if GCONTAINER_BOUNDS_CHECK
609  if (n<lobound || n>hibound)
610  {
611    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
612  }
613#endif
614  return ((TYPE*)data)[n-minlo];
615}
616
617
618template<class TYPE> inline const TYPE &
619GArrayTemplate<TYPE>::operator[](int const n) const
620{
621#if GCONTAINER_BOUNDS_CHECK
622  if (n<lobound || n>hibound)
623  {
624    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
625  }
626#endif
627  return ((const TYPE*)data)[n-minlo];
628}
629
630
631
632/** Dynamic array for general types. 
633    Template class #GArray<TYPE># implements an array of elements of type
634    #TYPE#. This template class must be able to access the following
635    functions.
636    \begin{itemize}
637    \item a default constructor #TYPE::TYPE()#,
638    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
639    \item and optionally a destructor #TYPE::~TYPE()#.
640    \end{itemize}
641    This class only implement constructors.  See class \Ref{GArrayTemplate}
642    for a description of all access methods. */
643
644template<class TYPE>
645class GArray : public GArrayTemplate<TYPE>
646{
647public:
648  /** Constructs an empty array. The valid subscript range is initially
649      empty. Member function #touch# and #resize# provide convenient ways
650      to enlarge the subscript range. */
651  GArray() 
652    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits() ) {}
653  /** Constructs an array with subscripts in range 0 to #hibound#.
654      The subscript range can be subsequently modified with member functions
655      #touch# and #resize#. */
656  GArray(int hi) 
657    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), 0, hi ) {}
658  /** Constructs an array with subscripts in range #lobound# to #hibound#. 
659      The subscript range can be subsequently modified with member functions
660      #touch# and #resize#. */
661  GArray(int lo, int hi) 
662    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), lo, hi ) {}
663  // Copy operator
664  GArray& operator=(const GArray &r)
665    { GArrayBase::operator=(r); return *this; }
666};
667
668
669/** Dynamic array for smart pointers. 
670    Template class #GPArray<TYPE># implements an array of elements of type
671    #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller code sizes
672    can be achieved by using this class instead of the more general
673    #GArray<GP<TYPE>>#. 
674    This class only implement constructors.  See class \Ref{GArrayTemplate}
675    for a description of all access methods.  */
676
677template<class TYPE>
678class GPArray : public GArrayTemplate<GP<TYPE> >
679{
680public:
681  GPArray() 
682    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits() ) {}
683  GPArray(int hi) 
684    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), 0, hi ) {}
685  GPArray(int lo, int hi) 
686    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), lo, hi ) {}
687  // Copy operator
688  GPArray& operator=(const GPArray &r)
689    { GArrayBase::operator=(r); return *this; }
690};
691
692/** Dynamic array for simple types. 
693    Template class #GTArray<TYPE># implements an array of elements of {\em
694    simple} type #TYPE#.  {\em Simple} means that objects of type #TYPE# can
695    be created, copied, moved or destroyed without using specific constructors
696    or destructor functions.  Class #GTArray<TYPE># will move or copy objects
697    using simple bitwise copies.  Otherwise you must use class #GArray<TYPE>#.
698    This class only implement constructors.  See class \Ref{GArrayTemplate}
699    for a description of all access methods.  */
700template<class TYPE>
701class GTArray : public GArrayTemplate<TYPE>
702{
703public:
704  GTArray() 
705    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits() ) {}
706  GTArray(int hi) 
707    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), 0, hi ) {}
708  GTArray(int lo, int hi) 
709    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), lo, hi ) {}
710  // Copy operator
711  GTArray& operator=(const GTArray &r)
712    { GArrayBase::operator=(r); return *this; }
713};
714
715
716//@}
717
718
719
720// ------------------------------------------------------------
721// DOUBLY LINKED LISTS
722// ------------------------------------------------------------
723
724
725/** @name Doubly Linked Lists
726
727    The template classes \Ref{GList} and \Ref{GPList} implement a doubly
728    linked list of objects of arbitrary types. Member functions are provided
729    to search the list for an element, to insert or delete elements at
730    specified positions.  Theses template class must be able to access
731    \begin{itemize}
732    \item a default constructor #TYPE::TYPE()#,
733    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
734    \item optionally a destructor #TYPE::~TYPE()#,
735    \item and optionally a comparison operator #TYPE::operator==(const TYPE &)#.
736    \end{itemize}
737    @memo Doubly linked lists. 
738*/
739//@{
740
741/** Generic iterator class.
742    This class represents a position in a list (see \Ref{GList}) or a map
743    (see \Ref{GMap}).   As demonstrated by the following examples,
744    this class should be used to iterate over the objects contained
745    in a list or a map:
746    \begin{verbatim}
747    void print_list(GList<GString> a)
748    {
749      for (GPosition i = a ; i; ++i)
750        DjVuPrintMessage("%s\n", (const char*) a[i] );
751    }
752
753    void print_list_backwards(GList<GString> a)
754    {
755      for (GPosition i = a.lastpos() ; i; --i)
756        DjVuPrintMessage("%s\n", (const char*) a[i] );
757    }
758    \end{verbatim}
759    GPosition objects should only be used with the list or map for which they
760    have been created (using the member functions #firstpos# or #lastpos# of
761    the container).  Furthermore, you should never use a GPosition object
762    which designates a list element which has been removed from the list
763    (using member function #del# or by other means.)
764*/
765
766class DJVUAPI GPosition : protected GCont
767{
768public:
769  /** Creates a null GPosition object. */
770  GPosition() : ptr(0), cont(0) {}
771  /** Creates a copy of a GPosition object. */
772  GPosition(const GPosition &ref) : ptr(ref.ptr), cont(ref.cont) {}
773  /** Tests whether this GPosition object is non null. */
774  operator int() const 
775    { return !!ptr; }
776  /** Tests whether this GPosition object is null. */
777  int operator !() const 
778    { return !ptr; }
779  /** Moves this GPosition object to the next object in the container. */
780  GPosition& operator ++() 
781    { if (ptr) ptr = ptr->next; return *this; }
782  /** Moves this GPosition object to the previous object in the container. */
783  GPosition& operator --() 
784    { if (ptr) ptr = ptr->prev; return *this; }
785  // Internal. Do not use.
786  GPosition(Node *p, void *c) : ptr(p), cont(c) {}
787#if GCONTAINER_BOUNDS_CHECK
788  Node *check(void *c) 
789    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
790  const Node *check(void *c) const
791    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
792#else
793  Node *check(void *c) 
794    { return ptr; }
795  const Node *check(void *c) const
796    { return ptr; }
797#endif
798protected:
799  Node *ptr;
800  void *cont;
801  friend class GListBase;
802  friend class GSetBase;
803  void throw_invalid(void *c) const no_return;
804};
805
806
807class DJVUAPI GListBase : public GCont
808{
809protected:
810  GListBase(const Traits& traits);
811  GListBase(const GListBase &ref);
812  void append(Node *n);
813  void prepend(Node *n);
814  void insert_after(GPosition pos, Node *n);
815  void insert_before(GPosition pos, Node *n);
816  void insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos);
817  void del(GPosition &pos);
818protected:
819  const Traits &traits;
820  int nelem;
821  Node head;
822public:
823  ~GListBase();
824  GListBase & operator= (const GListBase & gl);
825  GPosition firstpos() const { return GPosition(head.next, (void*)this); }
826  GPosition lastpos() const { return GPosition(head.prev, (void*)this); }
827  bool isempty() const { return nelem==0; };
828  GPosition nth(unsigned int n) const;
829  void empty();
830};
831
832
833template<class TI>
834class GListImpl : public GListBase
835{
836protected:
837  GListImpl();
838  typedef GCONT ListNode<TI> LNode;
839  static Node * newnode(const TI &elt);
840  int operator==(const GListImpl<TI> &l2) const;
841  int search(const TI &elt, GPosition &pos) const;
842};
843
844template<class TI> 
845GListImpl<TI>::GListImpl() 
846  : GListBase( GCONT NormTraits<LNode>::traits() ) 
847{ 
848}
849
850template<class TI> GCONT Node *
851GListImpl<TI>::newnode(const TI &elt)
852{
853  LNode  *n = (LNode *) operator new (sizeof(LNode ));
854#if GCONTAINER_ZERO_FILL
855  memset(n, 0, sizeof(LNode ));
856#endif
857  new ((void*)&(n->val)) TI(elt);
858  return (Node*) n;
859}
860
861template<class TI> int
862GListImpl<TI>::operator==(const GListImpl<TI> &l2) const
863{
864  Node *p, *q;
865  for (p=head.next, q=l2.head.next; p && q; p=p->next, q=q->next )
866    if (((LNode*)p)->val != ((LNode*)q)->val)
867      return 0;
868  return p==0 && q==0;
869}
870
871template<class TI> int
872GListImpl<TI>::search(const TI &elt, GPosition &pos) const
873{
874  Node *n = (pos ? pos.check((void*)this) : head.next);
875  for (; n; n=n->next) 
876    if ( ((LNode *)n)->val == elt ) 
877      break;
878  if (n) pos = GPosition(n, (void*)this);
879  return (n != 0);
880}
881
882
883/** Common base class for all doubly linked lists. 
884    Class \Ref{GListTemplate} implements all methods for manipulating lists
885    of of objects of type #TYPE#.  You should not however create instances of
886    this class. You should instead use class \Ref{GList} or \Ref{GPList}. */
887
888template <class TYPE, class TI>
889class GListTemplate : protected GListImpl<TI>
890{
891public:
892  // -- ACCESS
893  /** Returns the number of elements in the list. */
894  int size() const
895    { return this->nelem; }
896  /** Returns the first position in the list. See \Ref{GPosition}. */
897  GPosition firstpos() const
898    { return GListImpl<TI>::firstpos(); }
899  /** Returns the last position in the list. See \Ref{GPosition}. */
900  GPosition lastpos() const
901    { return GListImpl<TI>::lastpos(); }
902  /** Implicit notation for GList::firstpos(). */
903  operator GPosition() const
904    { return firstpos(); }   
905  /** Returns a reference to the list element at position #pos#.  This
906      reference can be used for both reading (as "#a[n]#") and modifying (as
907      "#a[n]=v#") a list element.  Using an invalid position will cause a
908      segmentation violation. See \Ref{GPosition} for efficient operations on
909      positions. */
910  TYPE& operator[](GPosition pos)
911    { return (TYPE&) (((typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
912  /** Returns a constant reference to the list element at position #pos#.
913      This reference only be used for reading a list element.  An exception
914      \Ref{GException} is thrown if #pos# is not a valid position. This
915      variant of #operator[]# is necessary when dealing with a #const
916      GList<TYPE>#.  See \Ref{GPosition} for efficient operations on
917      positions. */
918  const TYPE& operator[](GPosition pos) const
919    { return (const TYPE&) (((const typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
920  // -- TEST
921  /** Tests whether a list is empty. 
922      Returns a non zero value if the list contains no elements. */
923  bool isempty() const 
924    { return this->nelem==0; }
925  /** Compares two lists. Returns a non zero value if and only if both lists
926      contain the same elements (as tested by #TYPE::operator==(const TYPE&)#
927      in the same order. */
928  int operator==(const GListTemplate<TYPE,TI> &l2) const
929    { return GListImpl<TI>::operator==(l2); }
930  // -- SEARCHING
931  /** Returns the position #pos# of the #n#-th list element.  An invalid
932      position is returned if the list contains less than #n# elements. The
933      operation works by sequentially scanning the list until reaching the
934      #n#-th element. */
935  GPosition nth(unsigned int n) const
936    { return GListImpl<TI>::nth(n); }
937  /*  Compatibility */
938  int nth(unsigned int n, GPosition &pos) const
939    { GPosition npos=nth(n); if (npos) pos=npos; return !!pos; }
940  /** Tests whether the list contains a given element.  If the list contains
941      #elt#, the position of the the first list element equal to #elt# as
942      checked by #TYPE::operator==(const TYPE&)# is returned.  Otherwise an
943      invalid position is returned. */
944  GPosition contains(const TYPE &elt) const
945    { GPosition pos; GListImpl<TI>::search((const TI&)elt, pos); return pos; }
946  /** Searches the list for a given element. If position #pos# is a valid
947      position for this list, the search starts at the specified position. If
948      position #pos# is not a valid position, the search starts at the
949      beginning of the list.  The list elements are sequentially compared with
950      #elt# using #TYPE::operator==(const TYPE&)#.  As soon as a list element
951      is equal to #elt#, function #search# sets argument #pos# with the
952      position of this list element and returns 1.  If however the search
953      reaches the end of the list, function #search# returns 0 and leaves
954      #pos# unchanged. */
955  int search(const TYPE &elt, GPosition &pos) const
956    { return GListImpl<TI>::search((const TI&)elt, pos); }
957  // -- ALTERATION
958  /** Erases the list contents.  All list elements are destroyed and
959      unlinked. The list is left with zero elements. */
960  void empty()
961    { GListImpl<TI>::empty(); }
962  /** Inserts an element after the last element of the list.
963      The new element is initialized with a copy of argument #elt#. */
964  void append(const TYPE &elt)
965    { GListImpl<TI>::append(newnode((const TI&)elt)); }
966  /** Inserts an element before the first element of the list.
967      The new element is initialized with a copy of argument #elt#. */
968  void prepend(const TYPE &elt)
969    { GListImpl<TI>::prepend(newnode((const TI&)elt)); }
970  /** Inserts a new element after the list element at position #pos#.  When
971      position #pos# is null the element is inserted at the beginning of the
972      list.  The new element is initialized with a copy of #elt#. */
973  void insert_after(GPosition pos, const TYPE &elt)
974    { GListImpl<TI>::insert_after(pos, newnode((const TI&)elt)); }
975  /** Inserts a new element before the list element at position #pos#. When
976      position #pos# is null the element is inserted at the end of the
977      list. The new element is initialized with a copy of #elt#. */
978  void insert_before(GPosition pos, const TYPE &elt)
979    { GListImpl<TI>::insert_before(pos, newnode((const TI&)elt)); }
980  /** Inserts an element of another list into this list.  This function
981      removes the element at position #frompos# in list #frompos#, inserts it
982      in the current list before the element at position #pos#, and advances
983      #frompos# to the next element in list #fromlist#. When position #pos# is
984      null the element is inserted at the end of the list. */
985  void insert_before(GPosition pos, GListTemplate<TYPE,TI> &fromlist, GPosition &frompos)
986    { GListImpl<TI>::insert_before(pos, fromlist, frompos); }
987  /** Destroys the list element at position #pos#.  This function does
988      nothing unless position #pos# is a valid position. */
989  void del(GPosition &pos)
990    { GListImpl<TI>::del(pos); }
991  /* Old iterators. Do not use. */
992#if GCONTAINER_OLD_ITERATORS
993  void first(GPosition &pos) const { pos = firstpos(); }
994  void last(GPosition &pos) const { pos = lastpos(); }
995  const TYPE *next(GPosition &pos) const 
996    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); ++pos; return x; }
997  const TYPE *prev(GPosition &pos) const 
998    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); --pos; return x; }
999  TYPE *next(GPosition &pos)
1000    { if (!pos) return 0; TYPE *x=&((*this)[pos]); ++pos; return x; }
1001  TYPE *prev(GPosition &pos)
1002    { if (!pos) return 0; TYPE *x=&((*this)[pos]); --pos; return x; }
1003#endif
1004};
1005
1006
1007/** Doubly linked lists.  Template class #GList<TYPE># implements a doubly
1008    linked list of elements of type #TYPE#.  This class only implement
1009    constructors.  See class \Ref{GListTemplate} and \Ref{GPosition} for a
1010    description of all access methods. */
1011
1012template <class TYPE>
1013class GList : public GListTemplate<TYPE,TYPE>
1014{
1015public:
1016  /** Null Constructor. Constructs a list with zero elements. */
1017  GList() : GListTemplate<TYPE,TYPE>() {}
1018  GList& operator=(const GList &r) 
1019    { GListBase::operator=(r); return *this; }
1020};
1021
1022
1023/** Doubly linked lists for smart pointers.
1024    Template class #GList<TYPE># implements a doubly linked list of elements
1025    of type #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller
1026    code sizes can be achieved by using this class instead of the more general
1027    #GArray<GP<TYPE>>#. 
1028    This class only implement constructors.  See class \Ref{GListTemplate} and
1029    \Ref{GPosition} for a description of all access methods. */
1030
1031template <class TYPE>
1032class GPList : public GListTemplate<GP<TYPE>,GPBase>
1033{
1034public:
1035  /** Null Constructor. Constructs a list with zero elements. */
1036  GPList() : GListTemplate<GP<TYPE>,GPBase>() {}
1037  GPList& operator=(const GPList &r) 
1038    { GListBase::operator=(r); return *this; }
1039};
1040
1041
1042//@}
1043
1044
1045
1046// ------------------------------------------------------------
1047// ASSOCIATIVE MAPS
1048// ------------------------------------------------------------
1049
1050/** @name Associative Maps
1051
1052    These template classes implements a associative maps.  The associative map
1053    contains an arbitrary number of entries. Each entry is a pair containing
1054    one element of type #KTYPE# (named the "key") and one element of type
1055    #VTYPE# (named the "value").  All entries have distinct keys.
1056    These template class must be able to access the following functions:
1057    \begin{itemize}
1058    \item a #VTYPE# default constructor #VTYPE::VTYPE()#,
1059    \item a #VTYPE# copy constructor #VTYPE::VTYPE(const VTYPE &)#,
1060    \item optionally a #VTYPE# destructor #VTYPE::~VTYPE()#,
1061    \item a #KTYPE# default constructor #KTYPE::KTYPE()#,
1062    \item a #KTYPE# copy constructor #KTYPE::KTYPE(const KTYPE &)#,
1063    \item optionally a #KTYPE# destructor #KTYPE::~KTYPE()#,
1064    \item a #KTYPE# comparison operator #KTYPE::operator==(const KTYPE &)#,
1065    \item and a #KTYPE# hashing function #hash(const KTYPE&)#.
1066    \end{itemize}
1067    The hashing function must return an #unsigned int# number. Multiple
1068    invocations of the hashing function with equal arguments (in the sense of
1069    #KTYPE::operator==#) must always return the same number. 
1070    Position objects (see \Ref{GPosition}) may be used to iterate over the
1071    entries contained by an associative map.
1072    @memo Associative maps.
1073*/
1074//@{
1075
1076class DJVUAPI GSetBase : public GCont
1077{
1078protected:
1079  GSetBase(const Traits &traits);
1080  GSetBase(const GSetBase &ref);
1081  static GCONT HNode *newnode(const void *key);
1082  HNode *hashnode(unsigned int hashcode) const;
1083  HNode *installnode(HNode *n);
1084  void   deletenode(HNode *n);
1085protected:
1086  const Traits &traits;
1087  int nelems;
1088  int nbuckets;
1089  HNode **table;
1090  GPBuffer<HNode *> gtable;
1091  HNode *first;
1092private:
1093  void insertnode(HNode *n);
1094  void rehash(int newbuckets);
1095public:
1096  ~GSetBase();
1097  GSetBase& operator=(const GSetBase &ref);
1098  GPosition firstpos() const;
1099  void del(GPosition &pos); 
1100  void empty();
1101};
1102
1103template <class K>
1104class GSetImpl : public GSetBase
1105{
1106protected:
1107  GSetImpl();
1108  GSetImpl(const Traits &traits);
1109  typedef GCONT SetNode<K> SNode;
1110  HNode *get(const K &key) const;
1111  HNode *get_or_throw(const K &key) const;
1112  HNode *get_or_create(const K &key);
1113public:
1114  GPosition contains(const K &key) const 
1115    { return GPosition( get(key), (void*)this); }
1116  void del(const K &key) 
1117    { deletenode(get(key)); }
1118};
1119
1120template<class K>
1121GSetImpl<K>::GSetImpl()
1122  : GSetBase( GCONT NormTraits<GCONT SetNode<K> >::traits() )
1123{ 
1124}
1125
1126template<class K>
1127GSetImpl<K>::GSetImpl(const Traits &traits)
1128  : GSetBase(traits) 
1129{ 
1130}
1131
1132template<class K> GCONT HNode *
1133GSetImpl<K>::get(const K &key) const
1134{ 
1135  unsigned int hashcode = hash(key);
1136  for (SNode *s=(SNode*)hashnode(hashcode); s; s=(SNode*)(s->hprev))
1137    if (s->hashcode == hashcode && s->key == key) return s;
1138  return 0;
1139}
1140
1141#if GCONTAINER_BOUNDS_CHECK
1142template<class K> GCONT HNode *
1143GSetImpl<K>::get_or_throw(const K &key) const
1144{ 
1145  HNode *m = get(key);
1146  if (!m)
1147  {
1148    G_THROW( ERR_MSG("GContainer.cannot_add") );
1149  }
1150  return m;
1151}
1152#else
1153template<class K> inline GCONT HNode *
1154GSetImpl<K>::get_or_throw(const K &key) const
1155{ 
1156  return get(key);
1157}
1158#endif
1159
1160template<class K> GCONT HNode *
1161GSetImpl<K>::get_or_create(const K &key)
1162{
1163  HNode *m = get(key);
1164  if (m) return m;
1165  SNode *n = (SNode*) operator new (sizeof(SNode));
1166#if GCONTAINER_ZERO_FILL
1167  memset(n, 0, sizeof(SNode));
1168#endif
1169  new ((void*)&(n->key)) K ( key );
1170  n->hashcode = hash((const K&)(n->key));
1171  installnode(n);
1172  return n;
1173}
1174
1175template <class K, class TI>
1176class GMapImpl : public GSetImpl<K>
1177{
1178protected:
1179  GMapImpl();
1180  GMapImpl(const GCONT Traits &traits);
1181  typedef GCONT MapNode<K,TI> MNode;
1182  GCONT HNode* get_or_create(const K &key);
1183};
1184
1185template<class K, class TI>
1186GMapImpl<K,TI>::GMapImpl()
1187  : GSetImpl<K> ( GCONT NormTraits<GCONT MapNode<K,TI> >::traits() ) 
1188{ 
1189}
1190
1191template<class K, class TI>
1192GMapImpl<K,TI>::GMapImpl(const GCONT Traits &traits)
1193  : GSetImpl<K>(traits) 
1194{ 
1195}
1196
1197template<class K, class TI> GCONT HNode *
1198GMapImpl<K,TI>::get_or_create(const K &key)
1199{
1200  GCONT HNode *m = get(key);
1201  if (m) return m;
1202  MNode *n = (MNode*) operator new (sizeof(MNode));
1203#if GCONTAINER_ZERO_FILL
1204  memset(n, 0, sizeof(MNode));
1205#endif
1206  new ((void*)&(n->key)) K  (key);
1207  new ((void*)&(n->val)) TI ();
1208  n->hashcode = hash((const K&)(n->key));
1209  installnode(n);
1210  return n;
1211}
1212
1213
1214
1215/** Common base class for all associative maps.
1216    Class \Ref{GArrayTemplate} implements all methods for manipulating
1217    associative maps with key type #KTYPE# and value type #VTYPE#.
1218    You should not however create instances of this class.
1219    You should instead use class \Ref{GMap} or \Ref{GPMap}. */
1220
1221template <class KTYPE, class VTYPE, class TI>
1222class GMapTemplate : protected GMapImpl<KTYPE,TI>
1223{
1224public:
1225  /** Returns the number of elements in the map. */
1226  int size() const
1227    { return this->nelems; }
1228  /** Returns the first position in the map. */
1229  GPosition firstpos() const
1230    { return GMapImpl<KTYPE,TI>::firstpos(); }
1231  /** Implicit notation for GMap::firstpos(). */
1232  operator GPosition() const
1233    { return firstpos(); }   
1234  /** Tests whether the associative map is empty. 
1235      Returns a non zero value if and only if the map contains zero entries. */
1236  bool isempty() const
1237    { return this->nelems==0; }
1238  /** Searches an entry for key #key#.  If the map contains an entry whose key
1239      is equal to #key# according to #KTYPE::operator==(const KTYPE&)#, this
1240      function returns its position.  Otherwise it returns an invalid
1241      position. */
1242  GPosition contains(const KTYPE &key) const
1243    { return GMapImpl<KTYPE,TI>::contains(key); }
1244  /*  Compatibility */
1245  GPosition contains(const KTYPE &key, GPosition &pos) const
1246    { return pos = GMapImpl<KTYPE,TI>::contains(key); }
1247  // -- ALTERATION
1248  /** Erases the associative map contents.  All entries are destroyed and
1249      removed. The map is left with zero entries. */
1250  void empty()
1251    { GMapImpl<KTYPE,TI>::empty(); }
1252  /** Returns a constant reference to the key of the map entry at position
1253      #pos#.  An exception \Ref{GException} is thrown if position #pos# is not
1254      valid.  There is no direct way to change the key of a map entry. */
1255  const KTYPE &key(const GPosition &pos) const
1256    { return (const KTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->key); }
1257  /** Returns a reference to the value of the map entry at position #pos#.
1258      This reference can be used for both reading (as "#a[n]#") and modifying
1259      (as "#a[n]=v#").  An exception \Ref{GException} is thrown if position
1260      #pos# is not valid. */
1261  VTYPE& operator[](const GPosition &pos)
1262    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
1263  /** Returns a constant reference to the value of the map entry at position
1264      #pos#.  This reference can only be used for reading (as "#a[n]#") the
1265      entry value.  An exception \Ref{GException} is thrown if position #pos#
1266      is not valid. */
1267  const VTYPE& operator[](const GPosition &pos) const
1268    { return (const VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
1269  /** Returns a constant reference to the value of the map entry for key
1270      #key#.  This reference can only be used for reading (as "#a[n]#") the
1271      entry value.  An exception \Ref{GException} is thrown if no entry
1272      contains key #key#. This variant of #operator[]# is necessary when
1273      dealing with a #const GMAP<KTYPE,VTYPE>#. */
1274  const VTYPE& operator[](const KTYPE &key) const
1275    { return (const VTYPE&)(((const typename GMapImpl<KTYPE,TI>::MNode*)(get_or_throw(key)))->val); }
1276  /** Returns a reference to the value of the map entry for key #key#.  This
1277      reference can be used for both reading (as "#a[n]#") and modifying (as
1278      "#a[n]=v#"). If there is no entry for key #key#, a new entry is created
1279      for that key with the null constructor #VTYPE::VTYPE()#. */
1280  VTYPE& operator[](const KTYPE &key)
1281    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(get_or_create(key)))->val); }
1282  /** Destroys the map entry for position #pos#. 
1283      Nothing is done if position #pos# is not a valid position. */
1284  void del(GPosition &pos)
1285    { GSetBase::del(pos); }
1286  /** Destroys the map entry for key #key#. 
1287      Nothing is done if there is no entry for key #key#. */
1288  void del(const KTYPE &key)
1289    { GMapImpl<KTYPE,TI>::del(key); }
1290  /* Old iterators. Do not use. */
1291#if GCONTAINER_OLD_ITERATORS
1292  void first(GPosition &pos) const { pos = firstpos(); }
1293  const VTYPE *next(GPosition &pos) const 
1294    { if (!pos) return 0; const VTYPE *x=&((*this)[pos]); ++pos; return x; }
1295  VTYPE *next(GPosition &pos)
1296    { if (!pos) return 0; VTYPE *x=&((*this)[pos]); ++pos; return x; }
1297#endif
1298};
1299
1300
1301
1302/** Associative maps. 
1303    Template class #GMap<KTYPE,VTYPE># implements an associative map.
1304    The map contains an arbitrary number of entries. Each entry is a
1305    pair containing one element of type #KTYPE# (named the "key") and one
1306    element of type #VTYPE# (named the "value"). 
1307    The entry associated to a particular value of the key can retrieved
1308    very efficiently.
1309    This class only implement constructors.  See class \Ref{GMapTemplate} and
1310    \Ref{GPosition} for a description of all access methods.*/
1311
1312template <class KTYPE, class VTYPE>
1313class GMap : public GMapTemplate<KTYPE,VTYPE,VTYPE>
1314{
1315public:
1316  // -- ACCESS
1317  GMap() : GMapTemplate<KTYPE,VTYPE,VTYPE>() {}
1318  GMap& operator=(const GMap &r) 
1319    { GSetBase::operator=(r); return *this; }
1320};
1321
1322/** Associative maps for smart-pointers. 
1323    Template class #GMap<KTYPE,VTYPE># implements an associative map for key
1324    type #KTYPE# and value type #GP<VTYPE># (see \Ref{GSmartPointer.h}).  The
1325    map contains an arbitrary number of entries. Each entry is a pair
1326    containing one element of type #KTYPE# (named the "key") and one aelement
1327    of type #VTYPE# (named the "value").  The entry associated to a particular
1328    value of the key can retrieved very efficiently.
1329    Significantly smaller code sizes can be achieved by using this class
1330    instead of the more general #GMap<KTYPE,GP<VTYPE>># (see \Ref{GMap}).
1331    This class only implement constructors.  See class \Ref{GMapTemplate} and
1332    \Ref{GPosition} for a description of all access methods.*/
1333
1334template <class KTYPE, class VTYPE>
1335class GPMap : public GMapTemplate<KTYPE,GP<VTYPE>,GPBase>
1336{
1337public:
1338  GPMap() : GMapTemplate<KTYPE,GP<VTYPE>,GPBase>() {}
1339  GPMap& operator=(const GPMap &r) 
1340    { GSetBase::operator=(r); return *this; }
1341};
1342
1343
1344
1345//@}
1346//@}
1347//@}
1348
1349// ------------ THE END
1350
1351
1352#ifdef HAVE_NAMESPACES
1353}
1354# ifndef NOT_USING_DJVU_NAMESPACE
1355using namespace DJVU;
1356# endif
1357#endif
1358#endif
1359
1360
Note: See TracBrowser for help on using the repository browser.