source: trunk/libdjvu/GContainer.h @ 17

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

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

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