source: trunk/libdjvu/GContainer.h @ 15

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

needed libs update

File size: 47.3 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.15 2004/05/13 15:16:34 leonb Exp $
55// $Name: release_3_5_16 $
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.15 2004/05/13 15:16:34 leonb 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  operator const TYPE* ()  // suppress warning with gcc-2.95
398    { return ((const TYPE*)data)-minlo; }
399  // -- ALTERATION
400  /** Erases the array contents. All elements in the array are destroyed. 
401      The valid subscript range is set to the empty range. */
402  void empty()
403    { GArrayBase::empty(); }
404  /** Extends the subscript range so that it contains #n#.
405      This function does nothing if #n# is already int the valid subscript range.
406      If the valid range was empty, both the lower bound and the upper bound
407      are set to #n#.  Otherwise the valid subscript range is extended
408      to encompass #n#. This function is very handy when called before setting
409      an array element:
410      \begin{verbatim}
411       int lineno=1;
412       GArray<GString> a;
413       while (! end_of_file()) {
414         a.touch(lineno);
415         a[lineno++] = read_a_line();
416       }
417      \end{verbatim} */
418  void touch(int n)
419    { if (n<lobound || n>hibound) GArrayBase::touch(n); }
420  /** Resets the valid subscript range to #0#---#hibound#.
421      This function may destroy some array elements and may construct
422      new array elements with the null constructor. Setting #hibound# to
423      #-1# resets the valid subscript range to the empty range. */
424  void resize(int hibound)
425    { GArrayBase::resize(0, hibound); }
426  /** Resets the valid subscript range to #lobound#---#hibound#.
427      This function may destroy some array elements and may construct
428      new array elements with the null constructor. Setting #lobound# to #0# and
429      #hibound# to #-1# resets the valid subscript range to the empty range. */
430  void resize(int lobound, int hibound)
431    { GArrayBase::resize(lobound, hibound); }
432  /** Shifts the valid subscript range. Argument #disp# is added to both
433      bounds of the valid subscript range. Array elements previously
434      located at subscript #x# will now be located at subscript #x+disp#. */
435  void shift(int disp)
436    { GArrayBase::shift(disp); }
437  /** Deletes array elements. The array elements corresponding to
438      subscripts #n#...#n+howmany-1# are destroyed. All array elements
439      previously located at subscripts greater or equal to #n+howmany#
440      are moved to subscripts starting with #n#. The new subscript upper
441      bound is reduced in order to account for this shift. */
442  void del(int n, int howmany=1)
443    { GArrayBase::del(n, howmany); }
444  /** Insert new elements into an array. This function inserts
445      #howmany# elements at position #n# into the array. These
446      elements are constructed using the default constructor for type
447      #TYPE#.  All array elements previously located at subscripts #n#
448      and higher are moved to subscripts #n+howmany# and higher. The
449      upper bound of the valid subscript range is increased in order
450      to account for this shift. */
451  void ins(int n, int howmany=1)
452    { GArrayBase::ins(n, 0, howmany); }
453  /** Insert new elements into an array. The new elements are
454      constructed by copying element #val# using the copy constructor
455      for type #TYPE#. See \Ref{ins(int n, unsigned int howmany=1)}. */
456  void ins(int n, const TYPE &val, int howmany=1)
457    { GArrayBase::ins(n, (const void*)&val, howmany); }
458  /** Steals contents from array #ga#.  After this call, array #ga# is empty,
459      and this array contains everything previously contained in #ga#. */
460  void steal(GArrayTemplate &ga)
461    { GArrayBase::steal(ga); }
462  // -- SORTING
463  /** Sort array elements.  Sort all array elements in ascending
464      order according to the less-or-equal comparison
465      operator for type #TYPE#. */
466  void sort()
467    { sort(lbound(), hbound()); }
468  /** Sort array elements in subscript range #lo# to #hi#.  Sort all array
469      elements whose subscripts are in range #lo# to #hi# in ascending order
470      according to the less-or-equal comparison operator for type #TYPE#.  The
471      other elements of the array are left untouched.  An exception is thrown
472      if arguments #lo# and #hi# are not in the valid subscript range.  */
473  void sort(int lo, int hi);
474};
475
476
477
478/* That one must be implemented as a regular template function. */
479template <class TYPE> void
480GArrayTemplate<TYPE>::sort(int lo, int hi)
481{
482  if (hi <= lo)
483    return;
484  if (hi > hibound || lo<lobound)
485    G_THROW( ERR_MSG("GContainer.illegal_subscript") );
486  TYPE *data = (TYPE*)(*this);
487  // Test for insertion sort
488  if (hi <= lo + 50)
489    {
490      for (int i=lo+1; i<=hi; i++)
491        {
492          int j = i;
493          TYPE tmp = data[i];
494          while ((--j>=lo) && !(data[j]<=tmp))
495            data[j+1] = data[j];
496          data[j+1] = tmp;
497        }
498      return;
499    }
500  // -- determine suitable quick-sort pivot
501  TYPE tmp = data[lo];
502  TYPE pivot = data[(lo+hi)/2];
503  if (pivot <= tmp)
504    { tmp = pivot; pivot=data[lo]; }
505  if (data[hi] <= tmp)
506    { pivot = tmp; }
507  else if (data[hi] <= pivot)
508    { pivot = data[hi]; }
509  // -- partition set
510  int h = hi;
511  int l = lo;
512  while (l < h)
513    {
514      while (! (pivot <= data[l])) l++;
515      while (! (data[h] <= pivot)) h--;
516      if (l < h)
517        {
518          tmp = data[l];
519          data[l] = data[h];
520          data[h] = tmp;
521          l = l+1;
522          h = h-1;
523      }
524    }
525  // -- recursively restart
526  sort(lo, h);
527  sort(l, hi);
528}
529
530template<class TYPE> inline TYPE&
531GArrayTemplate<TYPE>::operator[](int const n)
532{
533#if GCONTAINER_BOUNDS_CHECK
534  if (n<lobound || n>hibound)
535  {
536    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
537  }
538#endif
539  return ((TYPE*)data)[n-minlo];
540}
541
542
543template<class TYPE> inline const TYPE &
544GArrayTemplate<TYPE>::operator[](int const n) const
545{
546#if GCONTAINER_BOUNDS_CHECK
547  if (n<lobound || n>hibound)
548  {
549    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
550  }
551#endif
552  return ((const TYPE*)data)[n-minlo];
553}
554
555
556
557/** Dynamic array for general types. 
558    Template class #GArray<TYPE># implements an array of elements of type
559    #TYPE#. This template class must be able to access the following
560    functions.
561    \begin{itemize}
562    \item a default constructor #TYPE::TYPE()#,
563    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
564    \item and optionally a destructor #TYPE::~TYPE()#.
565    \end{itemize}
566    This class only implement constructors.  See class \Ref{GArrayTemplate}
567    for a description of all access methods. */
568
569template<class TYPE>
570class GArray : public GArrayTemplate<TYPE>
571{
572public:
573  /** Constructs an empty array. The valid subscript range is initially
574      empty. Member function #touch# and #resize# provide convenient ways
575      to enlarge the subscript range. */
576  GArray() 
577    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits() ) {}
578  /** Constructs an array with subscripts in range 0 to #hibound#.
579      The subscript range can be subsequently modified with member functions
580      #touch# and #resize#. */
581  GArray(int hi) 
582    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), 0, hi ) {}
583  /** Constructs an array with subscripts in range #lobound# to #hibound#. 
584      The subscript range can be subsequently modified with member functions
585      #touch# and #resize#. */
586  GArray(int lo, int hi) 
587    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), lo, hi ) {}
588  // Copy operator
589  GArray& operator=(const GArray &r)
590    { GArrayBase::operator=(r); return *this; }
591};
592
593
594/** Dynamic array for smart pointers. 
595    Template class #GPArray<TYPE># implements an array of elements of type
596    #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller code sizes
597    can be achieved by using this class instead of the more general
598    #GArray<GP<TYPE>>#. 
599    This class only implement constructors.  See class \Ref{GArrayTemplate}
600    for a description of all access methods.  */
601
602template<class TYPE>
603class GPArray : public GArrayTemplate<GP<TYPE> >
604{
605public:
606  GPArray() 
607    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits() ) {}
608  GPArray(int hi) 
609    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), 0, hi ) {}
610  GPArray(int lo, int hi) 
611    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), lo, hi ) {}
612  // Copy operator
613  GPArray& operator=(const GPArray &r)
614    { GArrayBase::operator=(r); return *this; }
615};
616
617/** Dynamic array for simple types. 
618    Template class #GTArray<TYPE># implements an array of elements of {\em
619    simple} type #TYPE#.  {\em Simple} means that objects of type #TYPE# can
620    be created, copied, moved or destroyed without using specific constructors
621    or destructor functions.  Class #GTArray<TYPE># will move or copy objects
622    using simple bitwise copies.  Otherwise you must use class #GArray<TYPE>#.
623    This class only implement constructors.  See class \Ref{GArrayTemplate}
624    for a description of all access methods.  */
625template<class TYPE>
626class GTArray : public GArrayTemplate<TYPE>
627{
628public:
629  GTArray() 
630    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits() ) {}
631  GTArray(int hi) 
632    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), 0, hi ) {}
633  GTArray(int lo, int hi) 
634    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), lo, hi ) {}
635  // Copy operator
636  GTArray& operator=(const GTArray &r)
637    { GArrayBase::operator=(r); return *this; }
638};
639
640
641//@}
642
643
644
645// ------------------------------------------------------------
646// DOUBLY LINKED LISTS
647// ------------------------------------------------------------
648
649
650/** @name Doubly Linked Lists
651
652    The template classes \Ref{GList} and \Ref{GPList} implement a doubly
653    linked list of objects of arbitrary types. Member functions are provided
654    to search the list for an element, to insert or delete elements at
655    specified positions.  Theses template class must be able to access
656    \begin{itemize}
657    \item a default constructor #TYPE::TYPE()#,
658    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
659    \item optionally a destructor #TYPE::~TYPE()#,
660    \item and optionally a comparison operator #TYPE::operator==(const TYPE &)#.
661    \end{itemize}
662    @memo Doubly linked lists. 
663*/
664//@{
665
666/** Generic iterator class.
667    This class represents a position in a list (see \Ref{GList}) or a map
668    (see \Ref{GMap}).   As demonstrated by the following examples,
669    this class should be used to iterate over the objects contained
670    in a list or a map:
671    \begin{verbatim}
672    void print_list(GList<GString> a)
673    {
674      for (GPosition i = a ; i; ++i)
675        DjVuPrintMessage("%s\n", (const char*) a[i] );
676    }
677
678    void print_list_backwards(GList<GString> a)
679    {
680      for (GPosition i = a.lastpos() ; i; --i)
681        DjVuPrintMessage("%s\n", (const char*) a[i] );
682    }
683    \end{verbatim}
684    GPosition objects should only be used with the list or map for which they
685    have been created (using the member functions #firstpos# or #lastpos# of
686    the container).  Furthermore, you should never use a GPosition object
687    which designates a list element which has been removed from the list
688    (using member function #del# or by other means.)
689*/
690
691class GPosition : protected GCont
692{
693public:
694  /** Creates a null GPosition object. */
695  GPosition() : ptr(0), cont(0) {}
696  /** Creates a copy of a GPosition object. */
697  GPosition(const GPosition &ref) : ptr(ref.ptr), cont(ref.cont) {}
698  /** Tests whether this GPosition object is non null. */
699  operator int() const 
700    { return !!ptr; }
701  /** Tests whether this GPosition object is null. */
702  int operator !() const 
703    { return !ptr; }
704  /** Moves this GPosition object to the next object in the container. */
705  GPosition& operator ++() 
706    { if (ptr) ptr = ptr->next; return *this; }
707  /** Moves this GPosition object to the previous object in the container. */
708  GPosition& operator --() 
709    { if (ptr) ptr = ptr->prev; return *this; }
710  // Internal. Do not use.
711  GPosition(Node *p, void *c) : ptr(p), cont(c) {}
712#if GCONTAINER_BOUNDS_CHECK
713  Node *check(void *c) 
714    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
715  const Node *check(void *c) const
716    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
717#else
718  Node *check(void *c) 
719    { return ptr; }
720  const Node *check(void *c) const
721    { return ptr; }
722#endif
723protected:
724  Node *ptr;
725  void *cont;
726  friend class GListBase;
727  friend class GSetBase;
728  void throw_invalid(void *c) const no_return;
729};
730
731
732class GListBase : public GCont
733{
734protected:
735  GListBase(const Traits& traits);
736  GListBase(const GListBase &ref);
737  void append(Node *n);
738  void prepend(Node *n);
739  void insert_after(GPosition pos, Node *n);
740  void insert_before(GPosition pos, Node *n);
741  void insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos);
742  void del(GPosition &pos);
743protected:
744  const Traits &traits;
745  int nelem;
746  Node head;
747public:
748  ~GListBase();
749  GListBase & operator= (const GListBase & gl);
750  GPosition firstpos() const { return GPosition(head.next, (void*)this); }
751  GPosition lastpos() const { return GPosition(head.prev, (void*)this); }
752  int isempty() const { return nelem==0; };
753  GPosition nth(unsigned int n) const;
754  void empty();
755};
756
757
758template<class TI>
759class GListImpl : public GListBase
760{
761protected:
762  GListImpl();
763  typedef GCONT ListNode<TI> LNode;
764  static Node * newnode(const TI &elt);
765  int operator==(const GListImpl<TI> &l2) const;
766  int search(const TI &elt, GPosition &pos) const;
767};
768
769template<class TI> 
770GListImpl<TI>::GListImpl() 
771  : GListBase( GCONT NormTraits<LNode>::traits() ) 
772{ 
773}
774
775template<class TI> GCONT Node *
776GListImpl<TI>::newnode(const TI &elt)
777{
778  LNode  *n = (LNode *) operator new (sizeof(LNode ));
779#if GCONTAINER_ZERO_FILL
780  memset(n, 0, sizeof(LNode ));
781#endif
782  new ((void*)&(n->val)) TI(elt);
783  return (Node*) n;
784}
785
786template<class TI> int
787GListImpl<TI>::operator==(const GListImpl<TI> &l2) const
788{
789  Node *p, *q;
790  for (p=head.next, q=l2.head.next; p && q; p=p->next, q=q->next )
791    if (((LNode*)p)->val != ((LNode*)q)->val)
792      return 0;
793  return p==0 && q==0;
794}
795
796template<class TI> int
797GListImpl<TI>::search(const TI &elt, GPosition &pos) const
798{
799  Node *n = (pos ? pos.check((void*)this) : head.next);
800  for (; n; n=n->next) 
801    if ( ((LNode *)n)->val == elt ) 
802      break;
803  if (n) pos = GPosition(n, (void*)this);
804  return (n != 0);
805}
806
807
808/** Common base class for all doubly linked lists. 
809    Class \Ref{GListTemplate} implements all methods for manipulating lists
810    of of objects of type #TYPE#.  You should not however create instances of
811    this class. You should instead use class \Ref{GList} or \Ref{GPList}. */
812
813template <class TYPE, class TI>
814class GListTemplate : protected GListImpl<TI>
815{
816public:
817  // -- ACCESS
818  /** Returns the number of elements in the list. */
819  int size() const
820    { return this->nelem; }
821  /** Returns the first position in the list. See \Ref{GPosition}. */
822  GPosition firstpos() const
823    { return GListImpl<TI>::firstpos(); }
824  /** Returns the last position in the list. See \Ref{GPosition}. */
825  GPosition lastpos() const
826    { return GListImpl<TI>::lastpos(); }
827  /** Implicit notation for GList::firstpos(). */
828  operator GPosition() const
829    { return firstpos(); }   
830  /** Returns a reference to the list element at position #pos#.  This
831      reference can be used for both reading (as "#a[n]#") and modifying (as
832      "#a[n]=v#") a list element.  Using an invalid position will cause a
833      segmentation violation. See \Ref{GPosition} for efficient operations on
834      positions. */
835  TYPE& operator[](GPosition pos)
836    { return (TYPE&) (((typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
837  /** Returns a constant reference to the list element at position #pos#.
838      This reference only be used for reading a list element.  An exception
839      \Ref{GException} is thrown if #pos# is not a valid position. This
840      variant of #operator[]# is necessary when dealing with a #const
841      GList<TYPE>#.  See \Ref{GPosition} for efficient operations on
842      positions. */
843  const TYPE& operator[](GPosition pos) const
844    { return (const TYPE&) (((const typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
845  // -- TEST
846  /** Tests whether a list is empty. 
847      Returns a non zero value if the list contains no elements. */
848  int isempty() const 
849    { return this->nelem==0; }
850  /** Compares two lists. Returns a non zero value if and only if both lists
851      contain the same elements (as tested by #TYPE::operator==(const TYPE&)#
852      in the same order. */
853  int operator==(const GListTemplate<TYPE,TI> &l2) const
854    { return GListImpl<TI>::operator==(l2); }
855  // -- SEARCHING
856  /** Returns the position #pos# of the #n#-th list element.  An invalid
857      position is returned if the list contains less than #n# elements. The
858      operation works by sequentially scanning the list until reaching the
859      #n#-th element. */
860  GPosition nth(unsigned int n) const
861    { return GListImpl<TI>::nth(n); }
862  /*  Compatibility */
863  int nth(unsigned int n, GPosition &pos) const
864    { GPosition npos=nth(n); if (npos) pos=npos; return !!pos; }
865  /** Tests whether the list contains a given element.  If the list contains
866      #elt#, the position of the the first list element equal to #elt# as
867      checked by #TYPE::operator==(const TYPE&)# is returned.  Otherwise an
868      invalid position is returned. */
869  GPosition contains(const TYPE &elt) const
870    { GPosition pos; GListImpl<TI>::search((const TI&)elt, pos); return pos; }
871  /** Searches the list for a given element. If position #pos# is a valid
872      position for this list, the search starts at the specified position. If
873      position #pos# is not a valid position, the search starts at the
874      beginning of the list.  The list elements are sequentially compared with
875      #elt# using #TYPE::operator==(const TYPE&)#.  As soon as a list element
876      is equal to #elt#, function #search# sets argument #pos# with the
877      position of this list element and returns 1.  If however the search
878      reaches the end of the list, function #search# returns 0 and leaves
879      #pos# unchanged. */
880  int search(const TYPE &elt, GPosition &pos) const
881    { return GListImpl<TI>::search((const TI&)elt, pos); }
882  // -- ALTERATION
883  /** Erases the list contents.  All list elements are destroyed and
884      unlinked. The list is left with zero elements. */
885  void empty()
886    { GListImpl<TI>::empty(); }
887  /** Inserts an element after the last element of the list.
888      The new element is initialized with a copy of argument #elt#. */
889  void append(const TYPE &elt)
890    { GListImpl<TI>::append(newnode((const TI&)elt)); }
891  /** Inserts an element before the first element of the list.
892      The new element is initialized with a copy of argument #elt#. */
893  void prepend(const TYPE &elt)
894    { GListImpl<TI>::prepend(newnode((const TI&)elt)); }
895  /** Inserts a new element after the list element at position #pos#.  When
896      position #pos# is null the element is inserted at the beginning of the
897      list.  The new element is initialized with a copy of #elt#. */
898  void insert_after(GPosition pos, const TYPE &elt)
899    { GListImpl<TI>::insert_after(pos, newnode((const TI&)elt)); }
900  /** Inserts a new element before the list element at position #pos#. When
901      position #pos# is null the element is inserted at the end of the
902      list. The new element is initialized with a copy of #elt#. */
903  void insert_before(GPosition pos, const TYPE &elt)
904    { GListImpl<TI>::insert_before(pos, newnode((const TI&)elt)); }
905  /** Inserts an element of another list into this list.  This function
906      removes the element at position #frompos# in list #frompos#, inserts it
907      in the current list before the element at position #pos#, and advances
908      #frompos# to the next element in list #fromlist#. When position #pos# is
909      null the element is inserted at the end of the list. */
910  void insert_before(GPosition pos, GListTemplate<TYPE,TI> &fromlist, GPosition &frompos)
911    { GListImpl<TI>::insert_before(pos, fromlist, frompos); }
912  /** Destroys the list element at position #pos#.  This function does
913      nothing unless position #pos# is a valid position. */
914  void del(GPosition &pos)
915    { GListImpl<TI>::del(pos); }
916  /* Old iterators. Do not use. */
917#if GCONTAINER_OLD_ITERATORS
918  void first(GPosition &pos) const { pos = firstpos(); }
919  void last(GPosition &pos) const { pos = lastpos(); }
920  const TYPE *next(GPosition &pos) const 
921    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); ++pos; return x; }
922  const TYPE *prev(GPosition &pos) const 
923    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); --pos; return x; }
924  TYPE *next(GPosition &pos)
925    { if (!pos) return 0; TYPE *x=&((*this)[pos]); ++pos; return x; }
926  TYPE *prev(GPosition &pos)
927    { if (!pos) return 0; TYPE *x=&((*this)[pos]); --pos; return x; }
928#endif
929};
930
931
932/** Doubly linked lists.  Template class #GList<TYPE># implements a doubly
933    linked list of elements of type #TYPE#.  This class only implement
934    constructors.  See class \Ref{GListTemplate} and \Ref{GPosition} for a
935    description of all access methods. */
936
937template <class TYPE>
938class GList : public GListTemplate<TYPE,TYPE>
939{
940public:
941  /** Null Constructor. Constructs a list with zero elements. */
942  GList() : GListTemplate<TYPE,TYPE>() {}
943  GList& operator=(const GList &r) 
944    { GListBase::operator=(r); return *this; }
945};
946
947
948/** Doubly linked lists for smart pointers.
949    Template class #GList<TYPE># implements a doubly linked list of elements
950    of type #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller
951    code sizes can be achieved by using this class instead of the more general
952    #GArray<GP<TYPE>>#. 
953    This class only implement constructors.  See class \Ref{GListTemplate} and
954    \Ref{GPosition} for a description of all access methods. */
955
956template <class TYPE>
957class GPList : public GListTemplate<GP<TYPE>,GPBase>
958{
959public:
960  /** Null Constructor. Constructs a list with zero elements. */
961  GPList() : GListTemplate<GP<TYPE>,GPBase>() {}
962  GPList& operator=(const GPList &r) 
963    { GListBase::operator=(r); return *this; }
964};
965
966
967//@}
968
969
970
971// ------------------------------------------------------------
972// ASSOCIATIVE MAPS
973// ------------------------------------------------------------
974
975/** @name Associative Maps
976
977    These template classes implements a associative maps.  The associative map
978    contains an arbitrary number of entries. Each entry is a pair containing
979    one element of type #KTYPE# (named the "key") and one element of type
980    #VTYPE# (named the "value").  All entries have distinct keys.
981    These template class must be able to access the following functions:
982    \begin{itemize}
983    \item a #VTYPE# default constructor #VTYPE::VTYPE()#,
984    \item a #VTYPE# copy constructor #VTYPE::VTYPE(const VTYPE &)#,
985    \item optionally a #VTYPE# destructor #VTYPE::~VTYPE()#,
986    \item a #KTYPE# default constructor #KTYPE::KTYPE()#,
987    \item a #KTYPE# copy constructor #KTYPE::KTYPE(const KTYPE &)#,
988    \item optionally a #KTYPE# destructor #KTYPE::~KTYPE()#,
989    \item a #KTYPE# comparison operator #KTYPE::operator==(const KTYPE &)#,
990    \item and a #KTYPE# hashing function #hash(const KTYPE&)#.
991    \end{itemize}
992    The hashing function must return an #unsigned int# number. Multiple
993    invocations of the hashing function with equal arguments (in the sense of
994    #KTYPE::operator==#) must always return the same number. 
995    Position objects (see \Ref{GPosition}) may be used to iterate over the
996    entries contained by an associative map.
997    @memo Associative maps.
998*/
999//@{
1000
1001class GSetBase : public GCont
1002{
1003protected:
1004  GSetBase(const Traits &traits);
1005  GSetBase(const GSetBase &ref);
1006  static GCONT HNode *newnode(const void *key);
1007  HNode *hashnode(unsigned int hashcode) const;
1008  HNode *installnode(HNode *n);
1009  void   deletenode(HNode *n);
1010protected:
1011  const Traits &traits;
1012  int nelems;
1013  int nbuckets;
1014  HNode **table;
1015  GPBuffer<HNode *> gtable;
1016  HNode *first;
1017private:
1018  void insertnode(HNode *n);
1019  void rehash(int newbuckets);
1020public:
1021  ~GSetBase();
1022  GSetBase& operator=(const GSetBase &ref);
1023  GPosition firstpos() const;
1024  void del(GPosition &pos); 
1025  void empty();
1026};
1027
1028template <class K>
1029class GSetImpl : public GSetBase
1030{
1031protected:
1032  GSetImpl();
1033  GSetImpl(const Traits &traits);
1034  typedef GCONT SetNode<K> SNode;
1035  HNode *get(const K &key) const;
1036  HNode *get_or_throw(const K &key) const;
1037  HNode *get_or_create(const K &key);
1038public:
1039  GPosition contains(const K &key) const 
1040    { return GPosition( get(key), (void*)this); }
1041  void del(const K &key) 
1042    { deletenode(get(key)); }
1043};
1044
1045template<class K>
1046GSetImpl<K>::GSetImpl()
1047  : GSetBase( GCONT NormTraits<GCONT SetNode<K> >::traits() )
1048{ 
1049}
1050
1051template<class K>
1052GSetImpl<K>::GSetImpl(const Traits &traits)
1053  : GSetBase(traits) 
1054{ 
1055}
1056
1057template<class K> GCONT HNode *
1058GSetImpl<K>::get(const K &key) const
1059{ 
1060  unsigned int hashcode = hash(key);
1061  for (SNode *s=(SNode*)hashnode(hashcode); s; s=(SNode*)(s->hprev))
1062    if (s->hashcode == hashcode && s->key == key) return s;
1063  return 0;
1064}
1065
1066#if GCONTAINER_BOUNDS_CHECK
1067template<class K> GCONT HNode *
1068GSetImpl<K>::get_or_throw(const K &key) const
1069{ 
1070  HNode *m = get(key);
1071  if (!m)
1072  {
1073    G_THROW( ERR_MSG("GContainer.cannot_add") );
1074  }
1075  return m;
1076}
1077#else
1078template<class K> inline GCONT HNode *
1079GSetImpl<K>::get_or_throw(const K &key) const
1080{ 
1081  return get(key);
1082}
1083#endif
1084
1085template<class K> GCONT HNode *
1086GSetImpl<K>::get_or_create(const K &key)
1087{
1088  HNode *m = get(key);
1089  if (m) return m;
1090  SNode *n = (SNode*) operator new (sizeof(SNode));
1091#if GCONTAINER_ZERO_FILL
1092  memset(n, 0, sizeof(SNode));
1093#endif
1094  new ((void*)&(n->key)) K ( key );
1095  n->hashcode = hash((const K&)(n->key));
1096  installnode(n);
1097  return n;
1098}
1099
1100template <class K, class TI>
1101class GMapImpl : public GSetImpl<K>
1102{
1103protected:
1104  GMapImpl();
1105  GMapImpl(const GCONT Traits &traits);
1106  typedef GCONT MapNode<K,TI> MNode;
1107  GCONT HNode* get_or_create(const K &key);
1108};
1109
1110template<class K, class TI>
1111GMapImpl<K,TI>::GMapImpl()
1112  : GSetImpl<K> ( GCONT NormTraits<GCONT MapNode<K,TI> >::traits() ) 
1113{ 
1114}
1115
1116template<class K, class TI>
1117GMapImpl<K,TI>::GMapImpl(const GCONT Traits &traits)
1118  : GSetImpl<K>(traits) 
1119{ 
1120}
1121
1122template<class K, class TI> GCONT HNode *
1123GMapImpl<K,TI>::get_or_create(const K &key)
1124{
1125  GCONT HNode *m = get(key);
1126  if (m) return m;
1127  MNode *n = (MNode*) operator new (sizeof(MNode));
1128#if GCONTAINER_ZERO_FILL
1129  memset(n, 0, sizeof(MNode));
1130#endif
1131  new ((void*)&(n->key)) K  (key);
1132  new ((void*)&(n->val)) TI ();
1133  n->hashcode = hash((const K&)(n->key));
1134  installnode(n);
1135  return n;
1136}
1137
1138
1139
1140/** Common base class for all associative maps.
1141    Class \Ref{GArrayTemplate} implements all methods for manipulating
1142    associative maps with key type #KTYPE# and value type #VTYPE#.
1143    You should not however create instances of this class.
1144    You should instead use class \Ref{GMap} or \Ref{GPMap}. */
1145
1146template <class KTYPE, class VTYPE, class TI>
1147class GMapTemplate : protected GMapImpl<KTYPE,TI>
1148{
1149public:
1150  /** Returns the number of elements in the map. */
1151  int size() const
1152    { return this->nelems; }
1153  /** Returns the first position in the map. */
1154  GPosition firstpos() const
1155    { return GMapImpl<KTYPE,TI>::firstpos(); }
1156  /** Implicit notation for GMap::firstpos(). */
1157  operator GPosition() const
1158    { return firstpos(); }   
1159  /** Tests whether the associative map is empty. 
1160      Returns a non zero value if and only if the map contains zero entries. */
1161  int isempty() const
1162    { return this->nelems==0; }
1163  /** Searches an entry for key #key#.  If the map contains an entry whose key
1164      is equal to #key# according to #KTYPE::operator==(const KTYPE&)#, this
1165      function returns its position.  Otherwise it returns an invalid
1166      position. */
1167  GPosition contains(const KTYPE &key) const
1168    { return GMapImpl<KTYPE,TI>::contains(key); }
1169  /*  Compatibility */
1170  GPosition contains(const KTYPE &key, GPosition &pos) const
1171    { return pos = GMapImpl<KTYPE,TI>::contains(key); }
1172  // -- ALTERATION
1173  /** Erases the associative map contents.  All entries are destroyed and
1174      removed. The map is left with zero entries. */
1175  void empty()
1176    { GMapImpl<KTYPE,TI>::empty(); }
1177  /** Returns a constant reference to the key of the map entry at position
1178      #pos#.  An exception \Ref{GException} is thrown if position #pos# is not
1179      valid.  There is no direct way to change the key of a map entry. */
1180  const KTYPE &key(const GPosition &pos) const
1181    { return (const KTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->key); }
1182  /** Returns a reference to the value of the map entry at position #pos#.
1183      This reference can be used for both reading (as "#a[n]#") and modifying
1184      (as "#a[n]=v#").  An exception \Ref{GException} is thrown if position
1185      #pos# is not valid. */
1186  VTYPE& operator[](const GPosition &pos)
1187    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
1188  /** Returns a constant reference to the value of the map entry at position
1189      #pos#.  This reference can only be used for reading (as "#a[n]#") the
1190      entry value.  An exception \Ref{GException} is thrown if position #pos#
1191      is not valid. */
1192  const VTYPE& operator[](const GPosition &pos) const
1193    { return (const VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
1194  /** Returns a constant reference to the value of the map entry for key
1195      #key#.  This reference can only be used for reading (as "#a[n]#") the
1196      entry value.  An exception \Ref{GException} is thrown if no entry
1197      contains key #key#. This variant of #operator[]# is necessary when
1198      dealing with a #const GMAP<KTYPE,VTYPE>#. */
1199  const VTYPE& operator[](const KTYPE &key) const
1200    { return (const VTYPE&)(((const typename GMapImpl<KTYPE,TI>::MNode*)(get_or_throw(key)))->val); }
1201  /** Returns a reference to the value of the map entry for key #key#.  This
1202      reference can be used for both reading (as "#a[n]#") and modifying (as
1203      "#a[n]=v#"). If there is no entry for key #key#, a new entry is created
1204      for that key with the null constructor #VTYPE::VTYPE()#. */
1205  VTYPE& operator[](const KTYPE &key)
1206    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(get_or_create(key)))->val); }
1207  /** Destroys the map entry for position #pos#. 
1208      Nothing is done if position #pos# is not a valid position. */
1209  void del(GPosition &pos)
1210    { GSetBase::del(pos); }
1211  /** Destroys the map entry for key #key#. 
1212      Nothing is done if there is no entry for key #key#. */
1213  void del(const KTYPE &key)
1214    { GMapImpl<KTYPE,TI>::del(key); }
1215  /* Old iterators. Do not use. */
1216#if GCONTAINER_OLD_ITERATORS
1217  void first(GPosition &pos) const { pos = firstpos(); }
1218  const VTYPE *next(GPosition &pos) const 
1219    { if (!pos) return 0; const VTYPE *x=&((*this)[pos]); ++pos; return x; }
1220  VTYPE *next(GPosition &pos)
1221    { if (!pos) return 0; VTYPE *x=&((*this)[pos]); ++pos; return x; }
1222#endif
1223};
1224
1225
1226
1227/** Associative maps. 
1228    Template class #GMap<KTYPE,VTYPE># implements an associative map.
1229    The map contains an arbitrary number of entries. Each entry is a
1230    pair containing one element of type #KTYPE# (named the "key") and one
1231    element of type #VTYPE# (named the "value"). 
1232    The entry associated to a particular value of the key can retrieved
1233    very efficiently.
1234    This class only implement constructors.  See class \Ref{GMapTemplate} and
1235    \Ref{GPosition} for a description of all access methods.*/
1236
1237template <class KTYPE, class VTYPE>
1238class GMap : public GMapTemplate<KTYPE,VTYPE,VTYPE>
1239{
1240public:
1241  // -- ACCESS
1242  GMap() : GMapTemplate<KTYPE,VTYPE,VTYPE>() {}
1243  GMap& operator=(const GMap &r) 
1244    { GSetBase::operator=(r); return *this; }
1245};
1246
1247/** Associative maps for smart-pointers. 
1248    Template class #GMap<KTYPE,VTYPE># implements an associative map for key
1249    type #KTYPE# and value type #GP<VTYPE># (see \Ref{GSmartPointer.h}).  The
1250    map contains an arbitrary number of entries. Each entry is a pair
1251    containing one element of type #KTYPE# (named the "key") and one aelement
1252    of type #VTYPE# (named the "value").  The entry associated to a particular
1253    value of the key can retrieved very efficiently.
1254    Significantly smaller code sizes can be achieved by using this class
1255    instead of the more general #GMap<KTYPE,GP<VTYPE>># (see \Ref{GMap}).
1256    This class only implement constructors.  See class \Ref{GMapTemplate} and
1257    \Ref{GPosition} for a description of all access methods.*/
1258
1259template <class KTYPE, class VTYPE>
1260class GPMap : public GMapTemplate<KTYPE,GP<VTYPE>,GPBase>
1261{
1262public:
1263  GPMap() : GMapTemplate<KTYPE,GP<VTYPE>,GPBase>() {}
1264  GPMap& operator=(const GPMap &r) 
1265    { GSetBase::operator=(r); return *this; }
1266};
1267
1268
1269// ------------------------------------------------------------
1270// HASH FUNCTIONS
1271// ------------------------------------------------------------
1272
1273
1274/** @name Hash functions
1275    These functions let you use template class \Ref{GMap} with the
1276    corresponding elementary types. The returned hash code may be reduced to
1277    an arbitrary range by computing its remainder modulo the upper bound of
1278    the range.
1279    @memo Hash functions for elementary types. */
1280//@{
1281
1282/** Hashing function (unsigned int). */
1283static inline unsigned int 
1284hash(const unsigned int & x) 
1285{ 
1286  return x; 
1287}
1288
1289/** Hashing function (int). */
1290static inline unsigned int 
1291hash(const int & x) 
1292{ 
1293  return (unsigned int)x;
1294}
1295
1296/** Hashing function (long). */
1297static inline unsigned int
1298hash(const long & x) 
1299{ 
1300  return (unsigned int)x;
1301}
1302
1303/** Hashing function (unsigned long). */
1304static inline unsigned int
1305hash(const unsigned long & x) 
1306{ 
1307  return (unsigned int)x;
1308}
1309
1310/** Hashing function (void *). */
1311static inline unsigned int 
1312hash(void * const & x) 
1313{ 
1314  return (unsigned long) x; 
1315}
1316
1317/** Hashing function (const void *). */
1318static inline unsigned int 
1319hash(const void * const & x) 
1320{ 
1321  return (unsigned long) x; 
1322}
1323
1324/** Hashing function (float). */
1325static inline unsigned int
1326hash(const float & x) 
1327{ 
1328  // optimizer will get rid of unnecessary code 
1329  unsigned int *addr = (unsigned int*)&x;
1330  if (sizeof(float)<2*sizeof(unsigned int))
1331    return addr[0];
1332  else
1333    return addr[0]^addr[1];
1334}
1335
1336/** Hashing function (double). */
1337static inline unsigned int
1338hash(const double & x) 
1339{ 
1340  // optimizer will get rid of unnecessary code
1341  unsigned int *addr = (unsigned int*)&x;
1342  if (sizeof(double)<2*sizeof(unsigned int))
1343    return addr[0];
1344  else if (sizeof(double)<4*sizeof(unsigned int))
1345    return addr[0]^addr[1];
1346  else
1347    return addr[0]^addr[1]^addr[2]^addr[3];   
1348}
1349
1350
1351//@}
1352//@}
1353//@}
1354
1355// ------------ THE END
1356
1357
1358#ifdef HAVE_NAMESPACES
1359}
1360# ifndef NOT_USING_DJVU_NAMESPACE
1361using namespace DJVU;
1362# endif
1363#endif
1364#endif
1365
1366
Note: See TracBrowser for help on using the repository browser.