// generic useful stuff for any C++ program

#ifndef _TOOLS_H
#define _TOOLS_H

#ifdef __GNUC__
# define gamma __gamma
#endif

#include <math.h>

#ifdef __GNUC__
# undef gamma
#endif

#include <assert.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef __GNUC__
# include <new>
#else
# include <new.h>
#endif

#ifdef NULL
# undef NULL
#endif
#define NULL 0

typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned int uint;

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define rnd(max) (rand() % (max))
#define rndreset() (srand(1))
#define rndtime()                                                              \
	{                                                                      \
		loopi(lastmillis & 0xF) rnd(i + 1);                            \
	}
#define loop(v, m) for (int v = 0; v < (m); v++)
#define loopi(m) loop(i, m)
#define loopj(m) loop(j, m)
#define loopk(m) loop(k, m)
#define loopl(m) loop(l, m)

#ifdef WIN32
# pragma warning(3 : 4189)
// #pragma comment(linker,"/OPT:NOWIN98")
# define PATHDIV '\\'
#else
# define __cdecl
# define _vsnprintf vsnprintf
# define PATHDIV '/'
#endif

// easy safe strings

#define _MAXDEFSTR 260
typedef char string[_MAXDEFSTR];

inline void
strn0cpy(char *d, const char *s, size_t m)
{
	strncpy(d, s, m);
	d[(m)-1] = 0;
};
inline void
strcpy_s(char *d, const char *s)
{
	strn0cpy(d, s, _MAXDEFSTR);
};
inline void
strcat_s(char *d, const char *s)
{
	size_t n = strlen(d);
	strn0cpy(d + n, s, _MAXDEFSTR - n);
};

inline void
formatstring(char *d, const char *fmt, va_list v)
{
	_vsnprintf(d, _MAXDEFSTR, fmt, v);
	d[_MAXDEFSTR - 1] = 0;
};

struct sprintf_s_f {
	char *d;
	sprintf_s_f(char *str) : d(str) {};
	void
	operator()(const char *fmt, ...)
	{
		va_list v;
		va_start(v, fmt);
		_vsnprintf(d, _MAXDEFSTR, fmt, v);
		va_end(v);
		d[_MAXDEFSTR - 1] = 0;
	};
};

#define sprintf_s(d) sprintf_s_f((char *)d)
#define sprintf_sd(d)                                                          \
	string d;                                                              \
	sprintf_s(d)
#define sprintf_sdlv(d, last, fmt)                                             \
	string d;                                                              \
	{                                                                      \
		va_list ap;                                                    \
		va_start(ap, last);                                            \
		formatstring(d, fmt, ap);                                      \
		va_end(ap);                                                    \
	}
#define sprintf_sdv(d, fmt) sprintf_sdlv(d, fmt, fmt)

// fast pentium f2i

#ifdef _MSC_VER
inline int
fast_f2nat(float a)
{ // only for positive floats
	static const float fhalf = 0.5f;
	int retval;

	__asm fld a __asm fsub fhalf __asm fistp retval // perf regalloc?

	    return retval;
};
#else
# define fast_f2nat(val) ((int)(val))
#endif

extern char *path(char *s);
extern char *loadfile(char *fn, int *size);
extern void endianswap(void *, int, int);

// memory pool that uses buckets and linear allocation for small objects
// VERY fast, and reasonably good memory reuse

struct pool {
	enum { POOLSIZE = 4096 }; // can be absolutely anything
	enum { PTRSIZE = sizeof(char *) };
	enum {
		MAXBUCKETS = 65
	}; // meaning up to size 256 on 32bit pointer systems
	enum { MAXREUSESIZE = MAXBUCKETS * PTRSIZE - PTRSIZE };
	inline size_t
	bucket(size_t s)
	{
		return (s + PTRSIZE - 1) >> PTRBITS;
	};
	enum { PTRBITS = PTRSIZE == 2 ? 1 : PTRSIZE == 4 ? 2 : 3 };

	char *p;
	size_t left;
	char *blocks;
	void *reuse[MAXBUCKETS];

	pool();
	~pool() { dealloc_block(blocks); };

	void *alloc(size_t size);
	void dealloc(void *p, size_t size);
	void *realloc(void *p, size_t oldsize, size_t newsize);

	char *string(const char *s, size_t l);

	char *
	string(const char *s)
	{
		return string(s, strlen(s));
	}

	void
	deallocstr(char *s)
	{
		dealloc(s, strlen(s) + 1);
	}

	char *
	stringbuf(const char *s)
	{
		return string(s, _MAXDEFSTR - 1);
	}

	void dealloc_block(void *b);
	void allocnext(size_t allocsize);
};

pool *gp();

template <class T> struct vector {
	T *buf;
	int alen;
	int ulen;
	pool *p;

	vector()
	{
		this->p = gp();
		alen = 8;
		buf = (T *)p->alloc(alen * sizeof(T));
		ulen = 0;
	};

	~vector()
	{
		setsize(0);
		p->dealloc(buf, alen * sizeof(T));
	};

	vector(vector<T> &v);
	void operator=(vector<T> &v);

	T &
	add(const T &x)
	{
		if (ulen == alen)
			realloc();
		new (&buf[ulen]) T(x);
		return buf[ulen++];
	};

	T &
	add()
	{
		if (ulen == alen)
			realloc();
		new (&buf[ulen]) T;
		return buf[ulen++];
	};

	T &
	pop()
	{
		return buf[--ulen];
	};
	T &
	last()
	{
		return buf[ulen - 1];
	};
	bool
	empty()
	{
		return ulen == 0;
	};

	int
	length()
	{
		return ulen;
	};
	T &
	operator[](int i)
	{
		assert(i >= 0 && i < ulen);
		return buf[i];
	};
	void
	setsize(int i)
	{
		for (; ulen > i; ulen--)
			buf[ulen - 1].~T();
	};
	T *
	getbuf()
	{
		return buf;
	};

	void
	sort(void *cf)
	{
		qsort(buf, ulen, sizeof(T),
		    (int(__cdecl *)(const void *, const void *))cf);
	};

	void
	realloc()
	{
		int olen = alen;
		buf = (T *)p->realloc(
		    buf, olen * sizeof(T), (alen *= 2) * sizeof(T));
	};

	T
	remove(int i)
	{
		T e = buf[i];
		for (int p = i + 1; p < ulen; p++)
			buf[p - 1] = buf[p];
		ulen--;
		return e;
	};

	T &
	insert(int i, const T &e)
	{
		add(T());
		for (int p = ulen - 1; p > i; p--)
			buf[p] = buf[p - 1];
		buf[i] = e;
		return buf[i];
	};
};

#define loopv(v)                                                               \
	if (false) {                                                           \
	} else                                                                 \
		for (int i = 0; i < (v).length(); i++)
#define loopvrev(v)                                                            \
	if (false) {                                                           \
	} else                                                                 \
		for (int i = (v).length() - 1; i >= 0; i--)

template <class T> struct hashtable {
	struct chain {
		chain *next;
		const char *key;
		T data;
	};

	int size;
	int numelems;
	chain **table;
	pool *parent;
	chain *enumc;

	hashtable()
	{
		this->size = 1 << 10;
		this->parent = gp();
		numelems = 0;
		table = (chain **)parent->alloc(size * sizeof(T));
		for (int i = 0; i < size; i++)
			table[i] = NULL;
	};

	hashtable(hashtable<T> &v);
	void operator=(hashtable<T> &v);

	T *
	access(const char *key, T *data = NULL)
	{
		unsigned int h = 5381;
		for (int i = 0, k; k = key[i]; i++)
			h = ((h << 5) + h) ^ k; // bernstein k=33 xor
		h = h & (size - 1); // primes not much of an advantage
		for (chain *c = table[h]; c; c = c->next) {
			char ch;
			for (const char *p1 = key, *p2 = c->key;
			     (ch = *p1++) == *p2++;)
				if (!ch) // if(strcmp(key,c->key)==0)
				{
					T *d = &c->data;
					if (data)
						c->data = *data;
					return d;
				}
		}
		if (data) {
			chain *c = (chain *)parent->alloc(sizeof(chain));
			c->data = *data;
			c->key = key;
			c->next = table[h];
			table[h] = c;
			numelems++;
		}
		return NULL;
	}
};

#define enumerate(ht, t, e, b)                                                 \
	loopi(ht->size) for (ht->enumc = ht->table[i]; ht->enumc;              \
	                     ht->enumc = ht->enumc->next)                      \
	{                                                                      \
		t e = &ht->enumc->data;                                        \
		b;                                                             \
	}

inline char *
newstring(const char *s)
{
	return gp()->string(s);
}

inline char *
newstring(const char *s, size_t l)
{
	return gp()->string(s, l);
}

inline char *
newstringbuf(const char *s)
{
	return gp()->stringbuf(s);
}

#endif