summaryrefslogtreecommitdiffstats
path: root/kviewshell/plugins/djvu/libdjvu/GContainer.h
diff options
context:
space:
mode:
Diffstat (limited to 'kviewshell/plugins/djvu/libdjvu/GContainer.h')
-rw-r--r--kviewshell/plugins/djvu/libdjvu/GContainer.h1366
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
+
+