Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.

BUG:215923


git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdegraphics@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da

1 files changed, 1366 insertions, 0 deletions

diff --git a/kviewshell/plugins/djvu/libdjvu/GContainer.h b/kviewshell/plugins/djvu/libdjvu/GContainer.h
new file mode 100644
index 00000000..d21838dc
--- /dev/null
+++ b/kviewshell/plugins/djvu/libdjvu/GContainer.h
@@ -0,0 +1,1366 @@
+//C-  -*- C++ -*-
+//C- -------------------------------------------------------------------
+//C- DjVuLibre-3.5
+//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
+//C- Copyright (c) 2001  AT&T
+//C-
+//C- This software is subject to, and may be distributed under, the
+//C- GNU General Public License, Version 2. The license should have
+//C- accompanied the software or you may obtain a copy of the license
+//C- from the Free Software Foundation at http://www.fsf.org .
+//C-
+//C- This program is distributed in the hope that it will be useful,
+//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
+//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+//C- GNU General Public License for more details.
+//C- 
+//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library
+//C- distributed by Lizardtech Software.  On July 19th 2002, Lizardtech 
+//C- Software authorized us to replace the original DjVu(r) Reference 
+//C- Library notice by the following text (see doc/lizard2002.djvu):
+//C-
+//C-  ------------------------------------------------------------------
+//C- | DjVu (r) Reference Library (v. 3.5)
+//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
+//C- | The DjVu Reference Library is protected by U.S. Pat. No.
+//C- | 6,058,214 and patents pending.
+//C- |
+//C- | This software is subject to, and may be distributed under, the
+//C- | GNU General Public License, Version 2. The license should have
+//C- | accompanied the software or you may obtain a copy of the license
+//C- | from the Free Software Foundation at http://www.fsf.org .
+//C- |
+//C- | The computer code originally released by LizardTech under this
+//C- | license and unmodified by other parties is deemed "the LIZARDTECH
+//C- | ORIGINAL CODE."  Subject to any third party intellectual property
+//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 
+//C- | non-exclusive license to make, use, sell, or otherwise dispose of 
+//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 
+//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 
+//C- | General Public License.   This grant only confers the right to 
+//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 
+//C- | the extent such infringement is reasonably necessary to enable 
+//C- | recipient to make, have made, practice, sell, or otherwise dispose 
+//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 
+//C- | any greater extent that may be necessary to utilize further 
+//C- | modifications or combinations.
+//C- |
+//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
+//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
+//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+//C- +------------------------------------------------------------------
+// 
+// $Id: GContainer.h,v 1.15 2004/05/13 15:16:34 leonb Exp $
+// $Name: release_3_5_15 $
+
+#ifndef _GCONTAINER_H_
+#define _GCONTAINER_H_
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+#if NEED_GNUG_PRAGMAS
+# pragma interface
+#endif
+
+
+#include "GException.h"
+#include "GSmartPointer.h"
+#include <string.h>
+
+#ifdef HAVE_NAMESPACES
+namespace DJVU {
+# ifdef NOT_DEFINED // Just to fool emacs c++ mode
+}
+#endif
+#endif
+
+
+// Supports old iterators (first/last/next/prev) on lists and maps?
+#ifndef GCONTAINER_OLD_ITERATORS
+#define GCONTAINER_OLD_ITERATORS 1
+#endif
+
+// Check array bounds at runtime ?
+#ifndef GCONTAINER_BOUNDS_CHECK
+#define GCONTAINER_BOUNDS_CHECK 1
+#endif
+
+// Clears allocated memory prior to running constructors ?
+#ifndef GCONTAINER_ZERO_FILL
+#define GCONTAINER_ZERO_FILL 1
+#endif
+
+// Avoid member templates (needed by old compilers)
+#ifndef GCONTAINER_NO_MEMBER_TEMPLATES
+#if defined(__GNUC__) && (__GNUC__==2) && (__GNUC_MINOR__<91)
+#define GCONTAINER_NO_MEMBER_TEMPLATES 1
+#elif defined(_MSC_VER) && !defined(__ICL)
+#define GCONTAINER_NO_MEMBER_TEMPLATES 1
+#elif defined(__MWERKS__)
+#define GCONTAINER_NO_MEMBER_TEMPLATES 1
+#else
+#define GCONTAINER_NO_MEMBER_TEMPLATES 0
+#endif
+#endif
+
+// Define typename when needed
+#ifndef GCONTAINER_NO_TYPENAME
+#define GCONTAINER_NO_TYPENAME 0
+#endif
+#if GCONTAINER_NO_TYPENAME
+#define typename /**/
+#endif
+
+
+/** @name GContainer.h
+
+    Files #"GContainer.h"# and #"GContainer.cpp"# implement three main
+    template class for generic containers.  
+    Class #GArray# (see \Ref{Dynamic Arrays}) implements an array of objects
+    with variable bounds. Class #GList# (see \Ref{Doubly Linked Lists})
+    implements a doubly linked list of objects.  Class #GMap# (see
+    \Ref{Associative Maps}) implements a hashed associative map.  The
+    container templates are not thread-safe. Thread safety can be implemented
+    using the facilities provided in \Ref{GThreads.h}.
+    
+    @memo 
+    Template class for generic containers.
+    @author 
+    L\'eon Bottou <leonb@research.att.com> -- initial implementation.\\
+    Andrei Erofeev <eaf@geocities.com> -- bug fixes.
+    @version 
+    #$Id: GContainer.h,v 1.15 2004/05/13 15:16:34 leonb Exp $# */
+//@{
+
+
+
+// ------------------------------------------------------------
+// HELPER CLASSES
+// ------------------------------------------------------------
+
+
+
+/* Namespace for containers support classes.  This class is used as a
+   namespace for global identifiers related to the implementation of
+   containers.  It is inherited by all container objects.  This is disabled by
+   defining compilation symbol #GCONTAINER_NO_MEMBER_TEMPATES# to 1. */
+
+
+#ifdef _MSC_VER
+// Language lawyer say MS is wrong on that one. 
+// Cf section 5.4.7 in november 1997 draft.
+#pragma warning( disable : 4243 )
+#endif
+
+
+// GPEnabled inhertenced removed again so the code works on more machines.
+class GCont
+#if GCONTAINER_NO_MEMBER_TEMPLATES
+{
+};
+#else
+{
+public:
+#endif
+  // --- Pointers to type management functions
+  struct Traits
+  {
+    int       size;
+    void     *(*lea)     (void *base, int n);
+    void      (*init)    (void *dst, int n); 
+    void      (*copy)    (void *dst, const void* src, int n, int zap);
+    void      (*fini)    (void *dst, int n);
+  };
+#if !GCONTAINER_NO_MEMBER_TEMPLATES
+protected:
+#endif
+  // --- Management of simple types
+  template <int SZ> class TrivTraits
+  {
+  public:
+    // The unique object
+    static const Traits & traits();
+    // Offset in an array of T
+    static void * lea(void* base, int n)
+      { return (void*)( ((char*)base) + SZ*n ); }
+    // Trivial default constructor
+    static void   init(void* dst, int n) {}
+    // Trivial copy constructor
+    static void   copy(void* dst, const void* src, int n, int ) 
+      { memcpy(dst, src, SZ*n); }
+    // Trivial destructor
+    static void   fini(void* dst, int n) {}
+  };
+  // --- Management of regular types
+  template <class T> class NormTraits
+  {
+  public:
+    // The unique object
+    static const Traits & traits();
+    // Offset in an array of T
+    static void * lea(void* base, int n)
+      { return (void*)( ((T*)base) + n ); }
+    // Template based default constructor
+    static void init(void* dst, int n) 
+      { T* d = (T*)dst;   while (--n>=0) { new ((void*)d) T; d++; } }
+    // Template based copy constructor
+    static void copy(void* dst, const void* src, int n, int zap)
+      { T* d = (T*)dst; const T *s = (const T*)src; 
+        while (--n>=0) { new ((void*)d) T(*s); if (zap) { s->T::~T(); }; d++; s++; } }
+    // Template based destructor
+    static void fini(void* dst, int n) 
+      { T* d = (T*)dst; while (--n>=0) { d->T::~T(); d++; } }
+  };
+  // --- Base class for list nodes
+  struct Node
+  {
+    Node *next;
+    Node *prev;
+  };
+  // -- Class for list nodes
+  template <class T> struct ListNode : public Node
+  { 
+    T val;
+  };
+  // -- Class for map nodes showing the hash
+  struct HNode : public Node
+  {
+    HNode *hprev;
+    unsigned int hashcode;
+  };
+  // -- Class for map nodes showing the hash and the key
+  template <class K> struct SetNode : public HNode
+  { 
+    K key;
+  };
+  // -- Class for map nodes with everything
+  template <class K, class T> struct MapNode : public SetNode<K>
+  {
+    T val;
+  };
+#if !GCONTAINER_NO_MEMBER_TEMPLATES
+};
+#endif
+
+
+#if !GCONTAINER_NO_MEMBER_TEMPLATES
+#define GCONT GCont::
+#else
+#define GCONT
+#endif
+
+template <int SZ> const GCONT Traits & 
+GCONT TrivTraits<SZ>::traits()
+{
+  static const Traits theTraits = {
+    SZ,
+    TrivTraits<SZ>::lea,
+    TrivTraits<SZ>::init,
+    TrivTraits<SZ>::copy,
+    TrivTraits<SZ>::fini
+  };
+  return theTraits;
+}
+
+template <class T> const GCONT Traits & 
+GCONT NormTraits<T>::traits()
+{
+  static const Traits theTraits = {
+    sizeof(T),
+    NormTraits<T>::lea,
+    NormTraits<T>::init,
+    NormTraits<T>::copy,
+    NormTraits<T>::fini
+  };
+  return theTraits;
+}
+
+
+// ------------------------------------------------------------
+// DYNAMIC ARRAYS
+// ------------------------------------------------------------
+
+
+/** @name Dynamic Arrays
+
+    These class implement arrays of objects of any type.  Each element is
+    identified by an integer subscript.  The valid subscripts range is defined
+    by dynamically adjustable lower- and upper-bounds.  Besides accessing and
+    setting elements, member functions are provided to insert or delete
+    elements at specified positions.
+
+    Class \Ref{GArrayTemplate} implements all methods for manipulating arrays
+    of type #TYPE#.  You should not however create instances of this class.
+    You should instead use one of the following classes:
+    \begin{itemize}
+    \item Class \Ref{GArray<TYPE>} is the most general class,
+    \item Class \Ref{GTArray<TYPE>} is more efficient, but only works for
+          types that do not require sophisticated constructors or destructors,
+          such as the plain old C types (e.g. #int# or #char# ...).
+    \item Class \Ref{GPArray<TYPE>} implements an array of smart-pointers
+          \Ref{GP<TYPE>} to objects of type #TYPE#.  Using this class 
+          reduces the size of the code generated by the template instanciation.
+    \end{itemize}
+
+    Another variant of dynamic arrays is implemented in file \Ref{Arrays.h}.
+    The main difference is that class \Ref{TArray}, \Ref{DArray} and
+    \Ref{DPArray} implement a copy-on-demand scheme.
+
+    @memo Dynamic arrays.  */
+//@{
+
+class GArrayBase : public GCont
+{
+public:
+  // -- CONSTRUCTORS
+  GArrayBase(const GArrayBase &ref);
+  GArrayBase(const Traits &traits);
+  GArrayBase(const Traits &traits, int lobound, int hibound);
+  // -- DESTRUCTOR
+  ~GArrayBase();
+  // -- ASSIGNMENT
+  GArrayBase& operator= (const GArrayBase &ga);
+  // -- ALTERATION
+  void empty();
+  void touch(int n);
+  void resize(int lobound, int hibound);
+  void shift(int disp);
+  void del(int n, int howmany=1);
+  void ins(int n, const void *src, int howmany=1);
+  void steal(GArrayBase &ga);
+protected:
+  const Traits &traits;
+  void  *data;
+  GPBufferBase gdata;
+  int   minlo;
+  int   maxhi;
+  int   lobound;
+  int   hibound;
+};
+
+
+/** Common base class for all dynamic arrays.  
+    Class \Ref{GArrayTemplate} implements all methods for manipulating arrays
+    of type #TYPE#.  You should not however create instances of this class.
+    You should instead use class \Ref{GArray}, \Ref{GTArray} or
+    \Ref{GPArray}. */
+
+template<class TYPE>
+class GArrayTemplate : protected GArrayBase
+{
+public:
+  // -- CONSTRUCTORS
+  GArrayTemplate(const Traits &traits) : GArrayBase(traits) {}
+  GArrayTemplate(const Traits &traits, int lobound, int hibound)
+    : GArrayBase(traits, lobound, hibound) {}
+  // -- ACCESS
+  /** Returns the number of elements in the array. */
+  int size() const
+    { return hibound-lobound+1; }
+  /** Returns the lower bound of the valid subscript range. */
+  int lbound() const
+    { return lobound; }
+  /** Returns the upper bound of the valid subscript range. */
+  int hbound() const
+    { return hibound; }
+  /** Returns a reference to the array element for subscript #n#.  This
+      reference can be used for both reading (as "#a[n]#") and writing (as
+      "#a[n]=v#") an array element.  This operation will not extend the valid
+      subscript range: an exception \Ref{GException} is thrown if argument #n#
+      is not in the valid subscript range. */
+  inline TYPE& operator[](int const n);
+  /** Returns a constant reference to the array element for subscript #n#.
+      This reference can only be used for reading (as "#a[n]#") an array
+      element.  This operation will not extend the valid subscript range: an
+      exception \Ref{GException} is thrown if argument #n# is not in the valid
+      subscript range.  This variant of #operator[]# is necessary when dealing
+      with a #const GArray<TYPE>#. */
+  inline const TYPE& operator[](int n) const;
+  // -- CONVERSION
+  /** Returns a pointer for reading or writing the array elements.  This
+      pointer can be used to access the array elements with the same
+      subscripts and the usual bracket syntax.  This pointer remains valid as
+      long as the valid subscript range is unchanged. If you change the
+      subscript range, you must stop using the pointers returned by prior
+      invocation of this conversion operator. */
+  operator TYPE* ()
+    { return ((TYPE*)data)-minlo; }
+  /** Returns a pointer for reading (but not modifying) the array elements.
+      This pointer can be used to access the array elements with the same
+      subscripts and the usual bracket syntax.  This pointer remains valid as
+      long as the valid subscript range is unchanged. If you change the
+      subscript range, you must stop using the pointers returned by prior
+      invocation of this conversion operator. */
+  operator const TYPE* () const
+    { return ((const TYPE*)data)-minlo; }
+  operator const TYPE* ()  // suppress warning with gcc-2.95
+    { return ((const TYPE*)data)-minlo; }
+  // -- ALTERATION
+  /** Erases the array contents. All elements in the array are destroyed.  
+      The valid subscript range is set to the empty range. */
+  void empty()
+    { GArrayBase::empty(); }
+  /** Extends the subscript range so that it contains #n#.
+      This function does nothing if #n# is already int the valid subscript range.
+      If the valid range was empty, both the lower bound and the upper bound
+      are set to #n#.  Otherwise the valid subscript range is extended
+      to encompass #n#. This function is very handy when called before setting
+      an array element:
+      \begin{verbatim}
+       int lineno=1;
+       GArray<GString> a;
+       while (! end_of_file()) { 
+         a.touch(lineno); 
+         a[lineno++] = read_a_line(); 
+       }
+      \end{verbatim} */
+  void touch(int n)
+    { if (n<lobound || n>hibound) GArrayBase::touch(n); }
+  /** Resets the valid subscript range to #0#---#hibound#.
+      This function may destroy some array elements and may construct
+      new array elements with the null constructor. Setting #hibound# to
+      #-1# resets the valid subscript range to the empty range. */
+  void resize(int hibound)
+    { GArrayBase::resize(0, hibound); }
+  /** Resets the valid subscript range to #lobound#---#hibound#. 
+      This function may destroy some array elements and may construct
+      new array elements with the null constructor. Setting #lobound# to #0# and
+      #hibound# to #-1# resets the valid subscript range to the empty range. */
+  void resize(int lobound, int hibound)
+    { GArrayBase::resize(lobound, hibound); }
+  /** Shifts the valid subscript range. Argument #disp# is added to both 
+      bounds of the valid subscript range. Array elements previously
+      located at subscript #x# will now be located at subscript #x+disp#. */
+  void shift(int disp)
+    { GArrayBase::shift(disp); }
+  /** Deletes array elements. The array elements corresponding to
+      subscripts #n#...#n+howmany-1# are destroyed. All array elements
+      previously located at subscripts greater or equal to #n+howmany#
+      are moved to subscripts starting with #n#. The new subscript upper
+      bound is reduced in order to account for this shift. */
+  void del(int n, int howmany=1)
+    { GArrayBase::del(n, howmany); }
+  /** Insert new elements into an array. This function inserts
+      #howmany# elements at position #n# into the array. These
+      elements are constructed using the default constructor for type
+      #TYPE#.  All array elements previously located at subscripts #n#
+      and higher are moved to subscripts #n+howmany# and higher. The
+      upper bound of the valid subscript range is increased in order
+      to account for this shift. */
+  void ins(int n, int howmany=1)
+    { GArrayBase::ins(n, 0, howmany); }
+  /** Insert new elements into an array. The new elements are
+      constructed by copying element #val# using the copy constructor
+      for type #TYPE#. See \Ref{ins(int n, unsigned int howmany=1)}. */
+  void ins(int n, const TYPE &val, int howmany=1)
+    { GArrayBase::ins(n, (const void*)&val, howmany); }
+  /** Steals contents from array #ga#.  After this call, array #ga# is empty,
+      and this array contains everything previously contained in #ga#. */
+  void steal(GArrayTemplate &ga)
+    { GArrayBase::steal(ga); }
+  // -- SORTING
+  /** Sort array elements.  Sort all array elements in ascending
+      order according to the less-or-equal comparison
+      operator for type #TYPE#. */
+  void sort()
+    { sort(lbound(), hbound()); }
+  /** Sort array elements in subscript range #lo# to #hi#.  Sort all array
+      elements whose subscripts are in range #lo# to #hi# in ascending order
+      according to the less-or-equal comparison operator for type #TYPE#.  The
+      other elements of the array are left untouched.  An exception is thrown
+      if arguments #lo# and #hi# are not in the valid subscript range.  */
+  void sort(int lo, int hi);
+};
+
+
+
+/* That one must be implemented as a regular template function. */
+template <class TYPE> void
+GArrayTemplate<TYPE>::sort(int lo, int hi)
+{
+  if (hi <= lo)
+    return;
+  if (hi > hibound || lo<lobound)
+    G_THROW( ERR_MSG("GContainer.illegal_subscript") );
+  TYPE *data = (TYPE*)(*this);
+  // Test for insertion sort
+  if (hi <= lo + 50)
+    {
+      for (int i=lo+1; i<=hi; i++)
+        {
+          int j = i;
+          TYPE tmp = data[i];
+          while ((--j>=lo) && !(data[j]<=tmp))
+            data[j+1] = data[j];
+          data[j+1] = tmp;
+        }
+      return;
+    }
+  // -- determine suitable quick-sort pivot
+  TYPE tmp = data[lo];
+  TYPE pivot = data[(lo+hi)/2];
+  if (pivot <= tmp)
+    { tmp = pivot; pivot=data[lo]; }
+  if (data[hi] <= tmp)
+    { pivot = tmp; }
+  else if (data[hi] <= pivot)
+    { pivot = data[hi]; }
+  // -- partition set
+  int h = hi;
+  int l = lo;
+  while (l < h)
+    {
+      while (! (pivot <= data[l])) l++;
+      while (! (data[h] <= pivot)) h--;
+      if (l < h)
+        {
+          tmp = data[l];
+          data[l] = data[h];
+          data[h] = tmp;
+          l = l+1;
+          h = h-1;
+      }
+    }
+  // -- recursively restart
+  sort(lo, h);
+  sort(l, hi);
+}
+
+template<class TYPE> inline TYPE&
+GArrayTemplate<TYPE>::operator[](int const n)
+{
+#if GCONTAINER_BOUNDS_CHECK
+  if (n<lobound || n>hibound)
+  {
+    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
+  }
+#endif
+  return ((TYPE*)data)[n-minlo];
+}
+
+
+template<class TYPE> inline const TYPE &
+GArrayTemplate<TYPE>::operator[](int const n) const
+{
+#if GCONTAINER_BOUNDS_CHECK
+  if (n<lobound || n>hibound)
+  {
+    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
+  }
+#endif
+  return ((const TYPE*)data)[n-minlo];
+}
+
+
+
+/** Dynamic array for general types.  
+    Template class #GArray<TYPE># implements an array of elements of type
+    #TYPE#. This template class must be able to access the following
+    functions.
+    \begin{itemize}
+    \item a default constructor #TYPE::TYPE()#, 
+    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
+    \item and optionally a destructor #TYPE::~TYPE()#.
+    \end{itemize}
+    This class only implement constructors.  See class \Ref{GArrayTemplate}
+    for a description of all access methods. */
+
+template<class TYPE>
+class GArray : public GArrayTemplate<TYPE>
+{
+public:
+  /** Constructs an empty array. The valid subscript range is initially
+      empty. Member function #touch# and #resize# provide convenient ways
+      to enlarge the subscript range. */
+  GArray() 
+    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits() ) {}
+  /** Constructs an array with subscripts in range 0 to #hibound#. 
+      The subscript range can be subsequently modified with member functions
+      #touch# and #resize#. */
+  GArray(int hi) 
+    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), 0, hi ) {}
+  /** Constructs an array with subscripts in range #lobound# to #hibound#.  
+      The subscript range can be subsequently modified with member functions
+      #touch# and #resize#. */
+  GArray(int lo, int hi) 
+    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), lo, hi ) {}
+  // Copy operator
+  GArray& operator=(const GArray &r)
+    { GArrayBase::operator=(r); return *this; }
+};
+
+
+/** Dynamic array for smart pointers.  
+    Template class #GPArray<TYPE># implements an array of elements of type
+    #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller code sizes
+    can be achieved by using this class instead of the more general
+    #GArray<GP<TYPE>>#.  
+    This class only implement constructors.  See class \Ref{GArrayTemplate}
+    for a description of all access methods.  */
+
+template<class TYPE>
+class GPArray : public GArrayTemplate<GP<TYPE> >
+{
+public:
+  GPArray() 
+    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits() ) {}
+  GPArray(int hi) 
+    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), 0, hi ) {}
+  GPArray(int lo, int hi) 
+    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), lo, hi ) {}
+  // Copy operator
+  GPArray& operator=(const GPArray &r)
+    { GArrayBase::operator=(r); return *this; }
+};
+
+/** Dynamic array for simple types.  
+    Template class #GTArray<TYPE># implements an array of elements of {\em
+    simple} type #TYPE#.  {\em Simple} means that objects of type #TYPE# can
+    be created, copied, moved or destroyed without using specific constructors
+    or destructor functions.  Class #GTArray<TYPE># will move or copy objects
+    using simple bitwise copies.  Otherwise you must use class #GArray<TYPE>#. 
+    This class only implement constructors.  See class \Ref{GArrayTemplate}
+    for a description of all access methods.  */
+template<class TYPE>
+class GTArray : public GArrayTemplate<TYPE>
+{
+public:
+  GTArray() 
+    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits() ) {}
+  GTArray(int hi) 
+    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), 0, hi ) {}
+  GTArray(int lo, int hi) 
+    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), lo, hi ) {}
+  // Copy operator
+  GTArray& operator=(const GTArray &r)
+    { GArrayBase::operator=(r); return *this; }
+};
+
+
+//@}
+
+
+
+// ------------------------------------------------------------
+// DOUBLY LINKED LISTS
+// ------------------------------------------------------------
+
+
+/** @name Doubly Linked Lists
+
+    The template classes \Ref{GList} and \Ref{GPList} implement a doubly
+    linked list of objects of arbitrary types. Member functions are provided
+    to search the list for an element, to insert or delete elements at
+    specified positions.  Theses template class must be able to access
+    \begin{itemize}
+    \item a default constructor #TYPE::TYPE()#,
+    \item a copy constructor #TYPE::TYPE(const TYPE &)#,
+    \item optionally a destructor #TYPE::~TYPE()#,
+    \item and optionally a comparison operator #TYPE::operator==(const TYPE &)#.
+    \end{itemize} 
+    @memo Doubly linked lists.  
+*/
+//@{
+
+/** Generic iterator class.
+    This class represents a position in a list (see \Ref{GList}) or a map
+    (see \Ref{GMap}).   As demonstrated by the following examples,
+    this class should be used to iterate over the objects contained
+    in a list or a map:
+    \begin{verbatim}
+    void print_list(GList<GString> a)
+    {
+      for (GPosition i = a ; i; ++i) 
+        DjVuPrintMessage("%s\n", (const char*) a[i] );
+    }
+
+    void print_list_backwards(GList<GString> a)
+    {
+      for (GPosition i = a.lastpos() ; i; --i) 
+        DjVuPrintMessage("%s\n", (const char*) a[i] );
+    }
+    \end{verbatim}
+    GPosition objects should only be used with the list or map for which they
+    have been created (using the member functions #firstpos# or #lastpos# of
+    the container).  Furthermore, you should never use a GPosition object
+    which designates a list element which has been removed from the list
+    (using member function #del# or by other means.)
+*/
+
+class GPosition : protected GCont
+{
+public:
+  /** Creates a null GPosition object. */
+  GPosition() : ptr(0), cont(0) {}
+  /** Creates a copy of a GPosition object. */
+  GPosition(const GPosition &ref) : ptr(ref.ptr), cont(ref.cont) {}
+  /** Tests whether this GPosition object is non null. */
+  operator int() const 
+    { return !!ptr; }
+  /** Tests whether this GPosition object is null. */
+  int operator !() const 
+    { return !ptr; }
+  /** Moves this GPosition object to the next object in the container. */
+  GPosition& operator ++() 
+    { if (ptr) ptr = ptr->next; return *this; }
+  /** Moves this GPosition object to the previous object in the container. */
+  GPosition& operator --() 
+    { if (ptr) ptr = ptr->prev; return *this; }
+  // Internal. Do not use.
+  GPosition(Node *p, void *c) : ptr(p), cont(c) {}
+#if GCONTAINER_BOUNDS_CHECK
+  Node *check(void *c) 
+    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
+  const Node *check(void *c) const
+    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
+#else
+  Node *check(void *c) 
+    { return ptr; }
+  const Node *check(void *c) const
+    { return ptr; }
+#endif
+protected:
+  Node *ptr;
+  void *cont;
+  friend class GListBase;
+  friend class GSetBase;
+  void throw_invalid(void *c) const no_return;
+};
+
+
+class GListBase : public GCont
+{
+protected:
+  GListBase(const Traits& traits);
+  GListBase(const GListBase &ref);
+  void append(Node *n);
+  void prepend(Node *n);
+  void insert_after(GPosition pos, Node *n);
+  void insert_before(GPosition pos, Node *n);
+  void insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos);
+  void del(GPosition &pos);
+protected:
+  const Traits &traits;
+  int nelem;
+  Node head;
+public:
+  ~GListBase();
+  GListBase & operator= (const GListBase & gl);
+  GPosition firstpos() const { return GPosition(head.next, (void*)this); }
+  GPosition lastpos() const { return GPosition(head.prev, (void*)this); }
+  int isempty() const { return nelem==0; };
+  GPosition nth(unsigned int n) const;
+  void empty();
+};
+
+
+template<class TI>
+class GListImpl : public GListBase
+{
+protected:
+  GListImpl();
+  typedef GCONT ListNode<TI> LNode;
+  static Node * newnode(const TI &elt);
+  int operator==(const GListImpl<TI> &l2) const;
+  int search(const TI &elt, GPosition &pos) const;
+};
+
+template<class TI> 
+GListImpl<TI>::GListImpl() 
+  : GListBase( GCONT NormTraits<LNode>::traits() ) 
+{ 
+}
+
+template<class TI> GCONT Node *
+GListImpl<TI>::newnode(const TI &elt)
+{
+  LNode  *n = (LNode *) operator new (sizeof(LNode ));
+#if GCONTAINER_ZERO_FILL
+  memset(n, 0, sizeof(LNode ));
+#endif
+  new ((void*)&(n->val)) TI(elt);
+  return (Node*) n;
+}
+
+template<class TI> int
+GListImpl<TI>::operator==(const GListImpl<TI> &l2) const
+{
+  Node *p, *q;
+  for (p=head.next, q=l2.head.next; p && q; p=p->next, q=q->next )
+    if (((LNode*)p)->val != ((LNode*)q)->val)
+      return 0;
+  return p==0 && q==0;
+}
+
+template<class TI> int
+GListImpl<TI>::search(const TI &elt, GPosition &pos) const
+{
+  Node *n = (pos ? pos.check((void*)this) : head.next);
+  for (; n; n=n->next) 
+    if ( ((LNode *)n)->val == elt ) 
+      break;
+  if (n) pos = GPosition(n, (void*)this);
+  return (n != 0);
+}
+
+
+/** Common base class for all doubly linked lists.  
+    Class \Ref{GListTemplate} implements all methods for manipulating lists 
+    of of objects of type #TYPE#.  You should not however create instances of 
+    this class. You should instead use class \Ref{GList} or \Ref{GPList}. */
+
+template <class TYPE, class TI>
+class GListTemplate : protected GListImpl<TI>
+{
+public:
+  // -- ACCESS
+  /** Returns the number of elements in the list. */
+  int size() const
+    { return this->nelem; }
+  /** Returns the first position in the list. See \Ref{GPosition}. */
+  GPosition firstpos() const
+    { return GListImpl<TI>::firstpos(); }
+  /** Returns the last position in the list. See \Ref{GPosition}. */
+  GPosition lastpos() const
+    { return GListImpl<TI>::lastpos(); }
+  /** Implicit notation for GList::firstpos(). */
+  operator GPosition() const
+    { return firstpos(); }    
+  /** Returns a reference to the list element at position #pos#.  This
+      reference can be used for both reading (as "#a[n]#") and modifying (as
+      "#a[n]=v#") a list element.  Using an invalid position will cause a
+      segmentation violation. See \Ref{GPosition} for efficient operations on
+      positions. */
+  TYPE& operator[](GPosition pos)
+    { return (TYPE&) (((typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
+  /** Returns a constant reference to the list element at position #pos#.
+      This reference only be used for reading a list element.  An exception
+      \Ref{GException} is thrown if #pos# is not a valid position. This
+      variant of #operator[]# is necessary when dealing with a #const
+      GList<TYPE>#.  See \Ref{GPosition} for efficient operations on
+      positions. */
+  const TYPE& operator[](GPosition pos) const
+    { return (const TYPE&) (((const typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
+  // -- TEST
+  /** Tests whether a list is empty.  
+      Returns a non zero value if the list contains no elements. */
+  int isempty() const 
+    { return this->nelem==0; }
+  /** Compares two lists. Returns a non zero value if and only if both lists
+      contain the same elements (as tested by #TYPE::operator==(const TYPE&)#
+      in the same order. */
+  int operator==(const GListTemplate<TYPE,TI> &l2) const
+    { return GListImpl<TI>::operator==(l2); }
+  // -- SEARCHING
+  /** Returns the position #pos# of the #n#-th list element.  An invalid
+      position is returned if the list contains less than #n# elements. The
+      operation works by sequentially scanning the list until reaching the
+      #n#-th element. */
+  GPosition nth(unsigned int n) const
+    { return GListImpl<TI>::nth(n); }
+  /*  Compatibility */
+  int nth(unsigned int n, GPosition &pos) const
+    { GPosition npos=nth(n); if (npos) pos=npos; return !!pos; }
+  /** Tests whether the list contains a given element.  If the list contains
+      #elt#, the position of the the first list element equal to #elt# as
+      checked by #TYPE::operator==(const TYPE&)# is returned.  Otherwise an
+      invalid position is returned. */
+  GPosition contains(const TYPE &elt) const
+    { GPosition pos; GListImpl<TI>::search((const TI&)elt, pos); return pos; }
+  /** Searches the list for a given element. If position #pos# is a valid
+      position for this list, the search starts at the specified position. If
+      position #pos# is not a valid position, the search starts at the
+      beginning of the list.  The list elements are sequentially compared with
+      #elt# using #TYPE::operator==(const TYPE&)#.  As soon as a list element
+      is equal to #elt#, function #search# sets argument #pos# with the
+      position of this list element and returns 1.  If however the search
+      reaches the end of the list, function #search# returns 0 and leaves
+      #pos# unchanged. */
+  int search(const TYPE &elt, GPosition &pos) const
+    { return GListImpl<TI>::search((const TI&)elt, pos); }
+  // -- ALTERATION
+  /** Erases the list contents.  All list elements are destroyed and
+      unlinked. The list is left with zero elements. */
+  void empty()
+    { GListImpl<TI>::empty(); }
+  /** Inserts an element after the last element of the list. 
+      The new element is initialized with a copy of argument #elt#. */
+  void append(const TYPE &elt)
+    { GListImpl<TI>::append(newnode((const TI&)elt)); }
+  /** Inserts an element before the first element of the list. 
+      The new element is initialized with a copy of argument #elt#. */
+  void prepend(const TYPE &elt)
+    { GListImpl<TI>::prepend(newnode((const TI&)elt)); }
+  /** Inserts a new element after the list element at position #pos#.  When
+      position #pos# is null the element is inserted at the beginning of the
+      list.  The new element is initialized with a copy of #elt#. */
+  void insert_after(GPosition pos, const TYPE &elt)
+    { GListImpl<TI>::insert_after(pos, newnode((const TI&)elt)); }
+  /** Inserts a new element before the list element at position #pos#. When
+      position #pos# is null the element is inserted at the end of the
+      list. The new element is initialized with a copy of #elt#. */
+  void insert_before(GPosition pos, const TYPE &elt)
+    { GListImpl<TI>::insert_before(pos, newnode((const TI&)elt)); }
+  /** Inserts an element of another list into this list.  This function
+      removes the element at position #frompos# in list #frompos#, inserts it
+      in the current list before the element at position #pos#, and advances
+      #frompos# to the next element in list #fromlist#. When position #pos# is
+      null the element is inserted at the end of the list. */
+  void insert_before(GPosition pos, GListTemplate<TYPE,TI> &fromlist, GPosition &frompos)
+    { GListImpl<TI>::insert_before(pos, fromlist, frompos); }
+  /** Destroys the list element at position #pos#.  This function does 
+      nothing unless position #pos# is a valid position. */
+  void del(GPosition &pos)
+    { GListImpl<TI>::del(pos); }
+  /* Old iterators. Do not use. */
+#if GCONTAINER_OLD_ITERATORS
+  void first(GPosition &pos) const { pos = firstpos(); }
+  void last(GPosition &pos) const { pos = lastpos(); }
+  const TYPE *next(GPosition &pos) const 
+    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); ++pos; return x; }
+  const TYPE *prev(GPosition &pos) const 
+    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); --pos; return x; }
+  TYPE *next(GPosition &pos)
+    { if (!pos) return 0; TYPE *x=&((*this)[pos]); ++pos; return x; }
+  TYPE *prev(GPosition &pos)
+    { if (!pos) return 0; TYPE *x=&((*this)[pos]); --pos; return x; }
+#endif
+};
+
+
+/** Doubly linked lists.  Template class #GList<TYPE># implements a doubly
+    linked list of elements of type #TYPE#.  This class only implement
+    constructors.  See class \Ref{GListTemplate} and \Ref{GPosition} for a
+    description of all access methods. */
+
+template <class TYPE>
+class GList : public GListTemplate<TYPE,TYPE>
+{
+public:
+  /** Null Constructor. Constructs a list with zero elements. */
+  GList() : GListTemplate<TYPE,TYPE>() {}
+  GList& operator=(const GList &r) 
+    { GListBase::operator=(r); return *this; }
+};
+
+
+/** Doubly linked lists for smart pointers. 
+    Template class #GList<TYPE># implements a doubly linked list of elements
+    of type #GP<TYPE># (see \Ref{GSmartPointer.h}).  Significantly smaller
+    code sizes can be achieved by using this class instead of the more general
+    #GArray<GP<TYPE>>#.  
+    This class only implement constructors.  See class \Ref{GListTemplate} and
+    \Ref{GPosition} for a description of all access methods. */
+
+template <class TYPE>
+class GPList : public GListTemplate<GP<TYPE>,GPBase>
+{
+public:
+  /** Null Constructor. Constructs a list with zero elements. */
+  GPList() : GListTemplate<GP<TYPE>,GPBase>() {}
+  GPList& operator=(const GPList &r) 
+    { GListBase::operator=(r); return *this; }
+};
+
+
+//@}
+
+
+
+// ------------------------------------------------------------
+// ASSOCIATIVE MAPS
+// ------------------------------------------------------------
+
+/** @name Associative Maps
+
+    These template classes implements a associative maps.  The associative map
+    contains an arbitrary number of entries. Each entry is a pair containing
+    one element of type #KTYPE# (named the "key") and one element of type
+    #VTYPE# (named the "value").  All entries have distinct keys. 
+    These template class must be able to access the following functions:
+    \begin{itemize}
+    \item a #VTYPE# default constructor #VTYPE::VTYPE()#, 
+    \item a #VTYPE# copy constructor #VTYPE::VTYPE(const VTYPE &)#, 
+    \item optionally a #VTYPE# destructor #VTYPE::~VTYPE()#,
+    \item a #KTYPE# default constructor #KTYPE::KTYPE()#, 
+    \item a #KTYPE# copy constructor #KTYPE::KTYPE(const KTYPE &)#, 
+    \item optionally a #KTYPE# destructor #KTYPE::~KTYPE()#,
+    \item a #KTYPE# comparison operator #KTYPE::operator==(const KTYPE &)#,
+    \item and a #KTYPE# hashing function #hash(const KTYPE&)#.
+    \end{itemize} 
+    The hashing function must return an #unsigned int# number. Multiple
+    invocations of the hashing function with equal arguments (in the sense of
+    #KTYPE::operator==#) must always return the same number.  
+    Position objects (see \Ref{GPosition}) may be used to iterate over the
+    entries contained by an associative map. 
+    @memo Associative maps.
+*/
+//@{
+
+class GSetBase : public GCont
+{
+protected:
+  GSetBase(const Traits &traits);
+  GSetBase(const GSetBase &ref);
+  static GCONT HNode *newnode(const void *key);
+  HNode *hashnode(unsigned int hashcode) const;
+  HNode *installnode(HNode *n);
+  void   deletenode(HNode *n);
+protected:
+  const Traits &traits;
+  int nelems;
+  int nbuckets;
+  HNode **table;
+  GPBuffer<HNode *> gtable;
+  HNode *first;
+private:
+  void insertnode(HNode *n);
+  void rehash(int newbuckets);
+public:
+  ~GSetBase();
+  GSetBase& operator=(const GSetBase &ref);
+  GPosition firstpos() const;
+  void del(GPosition &pos); 
+  void empty();
+};
+
+template <class K>
+class GSetImpl : public GSetBase
+{
+protected:
+  GSetImpl();
+  GSetImpl(const Traits &traits);
+  typedef GCONT SetNode<K> SNode;
+  HNode *get(const K &key) const;
+  HNode *get_or_throw(const K &key) const;
+  HNode *get_or_create(const K &key);
+public:
+  GPosition contains(const K &key) const 
+    { return GPosition( get(key), (void*)this); }
+  void del(const K &key) 
+    { deletenode(get(key)); }
+};
+
+template<class K>
+GSetImpl<K>::GSetImpl()
+  : GSetBase( GCONT NormTraits<GCONT SetNode<K> >::traits() )
+{ 
+}
+
+template<class K>
+GSetImpl<K>::GSetImpl(const Traits &traits)
+  : GSetBase(traits) 
+{ 
+}
+
+template<class K> GCONT HNode *
+GSetImpl<K>::get(const K &key) const
+{ 
+  unsigned int hashcode = hash(key);
+  for (SNode *s=(SNode*)hashnode(hashcode); s; s=(SNode*)(s->hprev))
+    if (s->hashcode == hashcode && s->key == key) return s;
+  return 0;
+}
+
+#if GCONTAINER_BOUNDS_CHECK
+template<class K> GCONT HNode *
+GSetImpl<K>::get_or_throw(const K &key) const
+{ 
+  HNode *m = get(key);
+  if (!m)
+  {
+    G_THROW( ERR_MSG("GContainer.cannot_add") );
+  }
+  return m;
+}
+#else
+template<class K> inline GCONT HNode *
+GSetImpl<K>::get_or_throw(const K &key) const
+{ 
+  return get(key);
+}
+#endif
+
+template<class K> GCONT HNode *
+GSetImpl<K>::get_or_create(const K &key)
+{
+  HNode *m = get(key);
+  if (m) return m;
+  SNode *n = (SNode*) operator new (sizeof(SNode));
+#if GCONTAINER_ZERO_FILL
+  memset(n, 0, sizeof(SNode));
+#endif
+  new ((void*)&(n->key)) K ( key );
+  n->hashcode = hash((const K&)(n->key));
+  installnode(n);
+  return n;
+}
+
+template <class K, class TI>
+class GMapImpl : public GSetImpl<K>
+{
+protected:
+  GMapImpl();
+  GMapImpl(const GCONT Traits &traits);
+  typedef GCONT MapNode<K,TI> MNode;
+  GCONT HNode* get_or_create(const K &key);
+};
+
+template<class K, class TI>
+GMapImpl<K,TI>::GMapImpl()
+  : GSetImpl<K> ( GCONT NormTraits<GCONT MapNode<K,TI> >::traits() ) 
+{ 
+}
+
+template<class K, class TI>
+GMapImpl<K,TI>::GMapImpl(const GCONT Traits &traits)
+  : GSetImpl<K>(traits) 
+{ 
+}
+
+template<class K, class TI> GCONT HNode *
+GMapImpl<K,TI>::get_or_create(const K &key)
+{
+  GCONT HNode *m = get(key);
+  if (m) return m;
+  MNode *n = (MNode*) operator new (sizeof(MNode));
+#if GCONTAINER_ZERO_FILL
+  memset(n, 0, sizeof(MNode));
+#endif
+  new ((void*)&(n->key)) K  (key);
+  new ((void*)&(n->val)) TI ();
+  n->hashcode = hash((const K&)(n->key));
+  installnode(n);
+  return n;
+}
+
+
+
+/** Common base class for all associative maps.
+    Class \Ref{GArrayTemplate} implements all methods for manipulating 
+    associative maps with key type #KTYPE# and value type #VTYPE#. 
+    You should not however create instances of this class.
+    You should instead use class \Ref{GMap} or \Ref{GPMap}. */
+
+template <class KTYPE, class VTYPE, class TI>
+class GMapTemplate : protected GMapImpl<KTYPE,TI>
+{
+public:
+  /** Returns the number of elements in the map. */
+  int size() const
+    { return this->nelems; }
+  /** Returns the first position in the map. */
+  GPosition firstpos() const
+    { return GMapImpl<KTYPE,TI>::firstpos(); }
+  /** Implicit notation for GMap::firstpos(). */
+  operator GPosition() const
+    { return firstpos(); }    
+  /** Tests whether the associative map is empty.  
+      Returns a non zero value if and only if the map contains zero entries. */
+  int isempty() const
+    { return this->nelems==0; }
+  /** Searches an entry for key #key#.  If the map contains an entry whose key
+      is equal to #key# according to #KTYPE::operator==(const KTYPE&)#, this
+      function returns its position.  Otherwise it returns an invalid
+      position. */
+  GPosition contains(const KTYPE &key) const
+    { return GMapImpl<KTYPE,TI>::contains(key); }
+  /*  Compatibility */
+  GPosition contains(const KTYPE &key, GPosition &pos) const
+    { return pos = GMapImpl<KTYPE,TI>::contains(key); }
+  // -- ALTERATION
+  /** Erases the associative map contents.  All entries are destroyed and
+      removed. The map is left with zero entries. */
+  void empty()
+    { GMapImpl<KTYPE,TI>::empty(); }
+  /** Returns a constant reference to the key of the map entry at position
+      #pos#.  An exception \Ref{GException} is thrown if position #pos# is not
+      valid.  There is no direct way to change the key of a map entry. */
+  const KTYPE &key(const GPosition &pos) const
+    { return (const KTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->key); }
+  /** Returns a reference to the value of the map entry at position #pos#.
+      This reference can be used for both reading (as "#a[n]#") and modifying
+      (as "#a[n]=v#").  An exception \Ref{GException} is thrown if position
+      #pos# is not valid. */
+  VTYPE& operator[](const GPosition &pos)
+    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
+  /** Returns a constant reference to the value of the map entry at position
+      #pos#.  This reference can only be used for reading (as "#a[n]#") the
+      entry value.  An exception \Ref{GException} is thrown if position #pos#
+      is not valid. */
+  const VTYPE& operator[](const GPosition &pos) const
+    { return (const VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
+  /** Returns a constant reference to the value of the map entry for key
+      #key#.  This reference can only be used for reading (as "#a[n]#") the
+      entry value.  An exception \Ref{GException} is thrown if no entry
+      contains key #key#. This variant of #operator[]# is necessary when
+      dealing with a #const GMAP<KTYPE,VTYPE>#. */
+  const VTYPE& operator[](const KTYPE &key) const
+    { return (const VTYPE&)(((const typename GMapImpl<KTYPE,TI>::MNode*)(get_or_throw(key)))->val); }
+  /** Returns a reference to the value of the map entry for key #key#.  This
+      reference can be used for both reading (as "#a[n]#") and modifying (as
+      "#a[n]=v#"). If there is no entry for key #key#, a new entry is created
+      for that key with the null constructor #VTYPE::VTYPE()#. */
+  VTYPE& operator[](const KTYPE &key)
+    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(get_or_create(key)))->val); }
+  /** Destroys the map entry for position #pos#.  
+      Nothing is done if position #pos# is not a valid position. */
+  void del(GPosition &pos)
+    { GSetBase::del(pos); }
+  /** Destroys the map entry for key #key#.  
+      Nothing is done if there is no entry for key #key#. */
+  void del(const KTYPE &key)
+    { GMapImpl<KTYPE,TI>::del(key); }
+  /* Old iterators. Do not use. */
+#if GCONTAINER_OLD_ITERATORS
+  void first(GPosition &pos) const { pos = firstpos(); }
+  const VTYPE *next(GPosition &pos) const 
+    { if (!pos) return 0; const VTYPE *x=&((*this)[pos]); ++pos; return x; }
+  VTYPE *next(GPosition &pos)
+    { if (!pos) return 0; VTYPE *x=&((*this)[pos]); ++pos; return x; }
+#endif
+};
+
+
+
+/** Associative maps.  
+    Template class #GMap<KTYPE,VTYPE># implements an associative map.
+    The map contains an arbitrary number of entries. Each entry is a
+    pair containing one element of type #KTYPE# (named the "key") and one
+    element of type #VTYPE# (named the "value").  
+    The entry associated to a particular value of the key can retrieved
+    very efficiently.
+    This class only implement constructors.  See class \Ref{GMapTemplate} and
+    \Ref{GPosition} for a description of all access methods.*/
+
+template <class KTYPE, class VTYPE>
+class GMap : public GMapTemplate<KTYPE,VTYPE,VTYPE>
+{
+public:
+  // -- ACCESS
+  GMap() : GMapTemplate<KTYPE,VTYPE,VTYPE>() {}
+  GMap& operator=(const GMap &r) 
+    { GSetBase::operator=(r); return *this; }
+};
+
+/** Associative maps for smart-pointers.  
+    Template class #GMap<KTYPE,VTYPE># implements an associative map for key
+    type #KTYPE# and value type #GP<VTYPE># (see \Ref{GSmartPointer.h}).  The
+    map contains an arbitrary number of entries. Each entry is a pair
+    containing one element of type #KTYPE# (named the "key") and one aelement
+    of type #VTYPE# (named the "value").  The entry associated to a particular
+    value of the key can retrieved very efficiently.
+    Significantly smaller code sizes can be achieved by using this class
+    instead of the more general #GMap<KTYPE,GP<VTYPE>># (see \Ref{GMap}).
+    This class only implement constructors.  See class \Ref{GMapTemplate} and
+    \Ref{GPosition} for a description of all access methods.*/
+
+template <class KTYPE, class VTYPE>
+class GPMap : public GMapTemplate<KTYPE,GP<VTYPE>,GPBase>
+{
+public:
+  GPMap() : GMapTemplate<KTYPE,GP<VTYPE>,GPBase>() {}
+  GPMap& operator=(const GPMap &r) 
+    { GSetBase::operator=(r); return *this; }
+};
+
+
+// ------------------------------------------------------------
+// HASH FUNCTIONS
+// ------------------------------------------------------------
+
+
+/** @name Hash functions
+    These functions let you use template class \Ref{GMap} with the
+    corresponding elementary types. The returned hash code may be reduced to
+    an arbitrary range by computing its remainder modulo the upper bound of
+    the range.
+    @memo Hash functions for elementary types. */
+//@{
+
+/** Hashing function (unsigned int). */
+static inline unsigned int 
+hash(const unsigned int & x) 
+{ 
+  return x; 
+}
+
+/** Hashing function (int). */
+static inline unsigned int 
+hash(const int & x) 
+{ 
+  return (unsigned int)x;
+}
+
+/** Hashing function (long). */
+static inline unsigned int
+hash(const long & x) 
+{ 
+  return (unsigned int)x;
+}
+
+/** Hashing function (unsigned long). */
+static inline unsigned int
+hash(const unsigned long & x) 
+{ 
+  return (unsigned int)x;
+}
+
+/** Hashing function (void *). */
+static inline unsigned int 
+hash(void * const & x) 
+{ 
+  return (unsigned long) x; 
+}
+
+/** Hashing function (const void *). */
+static inline unsigned int 
+hash(const void * const & x) 
+{ 
+  return (unsigned long) x; 
+}
+
+/** Hashing function (float). */
+static inline unsigned int
+hash(const float & x) 
+{ 
+  // optimizer will get rid of unnecessary code  
+  unsigned int *addr = (unsigned int*)&x;
+  if (sizeof(float)<2*sizeof(unsigned int))
+    return addr[0];
+  else
+    return addr[0]^addr[1];
+}
+
+/** Hashing function (double). */
+static inline unsigned int
+hash(const double & x) 
+{ 
+  // optimizer will get rid of unnecessary code
+  unsigned int *addr = (unsigned int*)&x;
+  if (sizeof(double)<2*sizeof(unsigned int))
+    return addr[0];
+  else if (sizeof(double)<4*sizeof(unsigned int))
+    return addr[0]^addr[1];
+  else
+    return addr[0]^addr[1]^addr[2]^addr[3];    
+}
+
+
+//@}
+//@}
+//@}
+
+// ------------ THE END
+
+
+#ifdef HAVE_NAMESPACES
+}
+# ifndef NOT_USING_DJVU_NAMESPACE
+using namespace DJVU;
+# endif
+#endif
+#endif
+
+