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
|
#ifndef _rmqs_h_
#define _rmqs_h_
#define MEM_COUNT
#include "rmq.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static DT *a = NULL;
// size of array a
static DTidx n;
// table M for the out-of-block queries (contains indices of block-minima)
static DTsucc** M = NULL;
// because M just stores offsets (rel. to start of block), this method
// re-calculates the true index:
static inline DTidx m(DTidx k, DTidx block);
// depth of table M:
static DTidx M_depth;
// table M' for superblock-queries (contains indices of block-minima)
static DTidx** Mprime = NULL;
// depth of table M':
static DTidx Mprime_depth;
// type of blocks
static DTsucc2 *type = NULL;
// precomputed in-block queries
static DTsucc** Prec = NULL;
// microblock size
static DTidx s;
// block size
static DTidx sprime;
// superblock size
static DTidx sprimeprime;
// number of blocks (always n/sprime)
static DTidx nb;
// number of superblocks (always n/sprimeprime)
static DTidx nsb;
// number of microblocks (always n/s)
static DTidx nmb;
// return microblock-number of entry i:
static inline DTidx microblock(DTidx i);
// return block-number of entry i:
static inline DTidx block(DTidx i);
// return superblock-number of entry i:
static inline DTidx superblock(DTidx i);
// precomputed Catalan triangle (17 is enough for 64bit computing):
static const DTidx Catalan[17][17];
// minus infinity (change for 64bit version)
static const DT minus_infinity;
// stuff for clearing the least significant x bits (change for 64-bit computing)
static const DTsucc HighestBitsSet[8];
static DTsucc clearbits(DTsucc, DTidx);
// Least Significant Bits for 8-bit-numbers:
static const char LSBTable256[256];
// return least signigicant bit in constant time (change for 64bit version)
static DTidx lsb(DTsucc);
// the following stuff is for fast base 2 logarithms:
// (currently only implemented for 32 bit numbers)
static const char LogTable256[256];
static DTidx log2fast(DTidx);
// set if input array a is very small, so that naive scanning is better:
static bool ARRAY_VERY_SMALL;
#endif
|
