summaryrefslogtreecommitdiffstats
path: root/kviewshell/plugins/djvu/libdjvu/GContainer.h
blob: 61fabfaf7f496da64e3e8f7dc7870c508d6b8bcd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
//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 $# */
//@{

// ------------------------------------------------------------
// 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


// ------------------------------------------------------------
// 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(this->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(this->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, this->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, this->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) 
    { this->deletenode(this->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 = this->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 this->get(key);
}
#endif

template<class K> GCONT HNode *
GSetImpl<K>::get_or_create(const K &key)
{
  HNode *m = this->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));
  this->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 = this->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));
  this->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*)(this->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*)(this->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; }
};


#ifdef HAVE_NAMESPACES
}
# ifndef NOT_USING_DJVU_NAMESPACE
using namespace DJVU;
# endif
#endif
#endif