Revision d6f96b8d84b3dbff3983ff4bbd1f96be31f9d112 authored by stamatak on 29 January 2014, 17:07:46 UTC, committed by stamatak on 29 January 2014, 17:07:46 UTC
1 parent e6f2196
rmqs.h
#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
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...