_int.c

/******************************************************************************
  This file contains routines that can be bound to a Postgres backend and
  called by the backend in the process of processing queries.  The calling
  format for these routines is dictated by Postgres architecture.
******************************************************************************/

/*
#define BS_DEBUG
#define GIST_DEBUG
#define GIST_QUERY_DEBUG
*/

#include "postgres.h"

#include <float.h>

#include "catalog/pg_type.h"
#include "access/gist.h"
#include "access/itup.h"
#include "access/rtree.h"
#include "catalog/pg_type.h"
#include "utils/elog.h"
#include "utils/palloc.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "storage/bufpage.h"
#include "lib/stringinfo.h"

/* number ranges for compression */
#define MAXNUMRANGE 100

#define max(a,b)		((a) >	(b) ? (a) : (b))
#define min(a,b)		((a) <= (b) ? (a) : (b))
#define abs(a)			((a) <	(0) ? -(a) : (a))

/* dimension of array */
#define NDIM 1

/*
 * flags for gist__int_ops, use ArrayType->flags
 * which is unused (see array.h)
 */
#define LEAFKEY		(1<<31)
#define ISLEAFKEY(x)	( ((ArrayType*)(x))->flags & LEAFKEY )

/* useful macros for accessing int4 arrays */
#define ARRPTR(x)  ( (int4 *) ARR_DATA_PTR(x) )
#define ARRNELEMS(x)  ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))

#define ARRISVOID(x) ( (x) ? ( ( ARR_NDIM(x) == NDIM ) ? ( ( ARRNELEMS( x ) ) ? 0 : 1 ) : ( ( ARR_NDIM(x) ) ? (elog(ERROR,"Array is not one-dimensional: %d dimensions",ARRNELEMS( x )),1) : 0 )  ) : 0 )

#define SORT(x) \
	do { \
		 if ( ARRNELEMS( x ) > 1 ) \
			isort( ARRPTR( x ), ARRNELEMS( x ) ); \
	} while(0)

#define PREPAREARR(x) \
	do { \
		 if ( ARRNELEMS( x ) > 1 ) \
			if ( isort( ARRPTR( x ), ARRNELEMS( x ) ) ) \
				x = _int_unique( x ); \
	} while(0)

/* "wish" function */
#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )


/* bigint defines */
#define BITBYTE 8
#define SIGLENINT  64			/* >122 => key will toast, so very slow!!! */
#define SIGLEN	( sizeof(int)*SIGLENINT )
#define SIGLENBIT (SIGLEN*BITBYTE)

typedef char BITVEC[SIGLEN];
typedef char *BITVECP;

#define SIGPTR(x)  ( (BITVECP) ARR_DATA_PTR(x) )


#define LOOPBYTE(a) \
		for(i=0;i<SIGLEN;i++) {\
				a;\
		}

#define LOOPBIT(a) \
		for(i=0;i<SIGLENBIT;i++) {\
				a;\
		}

/* beware of multiple evaluation of arguments to these macros! */
#define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
#define GETBITBYTE(x,i) ( (*((char*)(x)) >> (i)) & 0x01 )
#define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )
#define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITBYTE ) )
#define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )
#define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT)
#define HASH(sign, val) SETBIT((sign), HASHVAL(val))


#ifdef GIST_DEBUG
static void
printarr(ArrayType *a, int num)
{
	StringInfoData bbb;
	char	   *cur;
	int			l;
	int		   *d;

	d = ARRPTR(a);
	initStringInfo(&bbb);
	for (l = 0; l < min(num, ARRNELEMS(a)); l++)
		appendStringInfo(&bbb, "%d ", d[l]);
	elog(DEBUG3, "\t\t%s", bbb.data);
	pfree(bbb.data);
}
static void
printbitvec(BITVEC bv)
{
	int			i;
	char		str[SIGLENBIT + 1];

	str[SIGLENBIT] = '\0';
	LOOPBIT(str[i] = (GETBIT(bv, i)) ? '1' : '0');

	elog(DEBUG3, "BV: %s", str);
}
#endif

/*
** types for functions
*/
typedef ArrayType *(*formarray) (ArrayType *, ArrayType *);
typedef void (*formfloat) (ArrayType *, float *);

/*
** usefull function
*/
static bool isort(int4 *a, const int len);
static ArrayType *new_intArrayType(int num);
static ArrayType *copy_intArrayType(ArrayType *a);
static ArrayType *resize_intArrayType(ArrayType *a, int num);
static int	internal_size(int *a, int len);
static ArrayType *_int_unique(ArrayType *a);

/* common GiST function*/
static GIST_SPLITVEC *_int_common_picksplit(bytea *entryvec,
					  GIST_SPLITVEC *v,
					  formarray unionf,
					  formarray interf,
					  formfloat sizef,
					  float coef);
static float *_int_common_penalty(GISTENTRY *origentry,
					GISTENTRY *newentry,
					float *result,
					formarray unionf,
					formfloat sizef);
static ArrayType *_int_common_union(bytea *entryvec,
				  int *sizep,
				  formarray unionf);

/*
** GiST support methods
*/
PG_FUNCTION_INFO_V1(g_int_consistent);
PG_FUNCTION_INFO_V1(g_int_compress);
PG_FUNCTION_INFO_V1(g_int_decompress);
PG_FUNCTION_INFO_V1(g_int_penalty);
PG_FUNCTION_INFO_V1(g_int_picksplit);
PG_FUNCTION_INFO_V1(g_int_union);
PG_FUNCTION_INFO_V1(g_int_same);

Datum		g_int_consistent(PG_FUNCTION_ARGS);
Datum		g_int_compress(PG_FUNCTION_ARGS);
Datum		g_int_decompress(PG_FUNCTION_ARGS);
Datum		g_int_penalty(PG_FUNCTION_ARGS);
Datum		g_int_picksplit(PG_FUNCTION_ARGS);
Datum		g_int_union(PG_FUNCTION_ARGS);
Datum		g_int_same(PG_FUNCTION_ARGS);


/*
** R-tree support functions
*/
static bool inner_int_contains(ArrayType *a, ArrayType *b);
static bool inner_int_overlap(ArrayType *a, ArrayType *b);
static ArrayType *inner_int_union(ArrayType *a, ArrayType *b);
static ArrayType *inner_int_inter(ArrayType *a, ArrayType *b);
static void rt__int_size(ArrayType *a, float *sz);

PG_FUNCTION_INFO_V1(_int_different);
PG_FUNCTION_INFO_V1(_int_same);
PG_FUNCTION_INFO_V1(_int_contains);
PG_FUNCTION_INFO_V1(_int_contained);
PG_FUNCTION_INFO_V1(_int_overlap);
PG_FUNCTION_INFO_V1(_int_union);
PG_FUNCTION_INFO_V1(_int_inter);

Datum		_int_different(PG_FUNCTION_ARGS);
Datum		_int_same(PG_FUNCTION_ARGS);
Datum		_int_contains(PG_FUNCTION_ARGS);
Datum		_int_contained(PG_FUNCTION_ARGS);
Datum		_int_overlap(PG_FUNCTION_ARGS);
Datum		_int_union(PG_FUNCTION_ARGS);
Datum		_int_inter(PG_FUNCTION_ARGS);

/*
** _intbig methods
*/
PG_FUNCTION_INFO_V1(g_intbig_consistent);
PG_FUNCTION_INFO_V1(g_intbig_compress);
PG_FUNCTION_INFO_V1(g_intbig_decompress);
PG_FUNCTION_INFO_V1(g_intbig_penalty);
PG_FUNCTION_INFO_V1(g_intbig_picksplit);
PG_FUNCTION_INFO_V1(g_intbig_union);
PG_FUNCTION_INFO_V1(g_intbig_same);

Datum		g_intbig_consistent(PG_FUNCTION_ARGS);
Datum		g_intbig_compress(PG_FUNCTION_ARGS);
Datum		g_intbig_decompress(PG_FUNCTION_ARGS);
Datum		g_intbig_penalty(PG_FUNCTION_ARGS);
Datum		g_intbig_picksplit(PG_FUNCTION_ARGS);
Datum		g_intbig_union(PG_FUNCTION_ARGS);
Datum		g_intbig_same(PG_FUNCTION_ARGS);

static bool _intbig_contains(ArrayType *a, ArrayType *b);
static bool _intbig_overlap(ArrayType *a, ArrayType *b);
static ArrayType *_intbig_union(ArrayType *a, ArrayType *b);

static ArrayType *_intbig_inter(ArrayType *a, ArrayType *b);
static void rt__intbig_size(ArrayType *a, float *sz);



/*****************************************************************************
 *			Boolean Search
 *****************************************************************************/

#define BooleanSearchStrategy	20

/*
 * item in polish notation with back link
 * to left operand
 */
typedef struct ITEM
{
	int2		type;
	int2		left;
	int4		val;
}	ITEM;

typedef struct
{
	int4		len;
	int4		size;
	char		data[1];
}	QUERYTYPE;

#define HDRSIZEQT	( 2*sizeof(int4) )
#define COMPUTESIZE(size)	( HDRSIZEQT + size * sizeof(ITEM) )
#define GETQUERY(x)  (ITEM*)( (char*)(x)+HDRSIZEQT )

PG_FUNCTION_INFO_V1(bqarr_in);
PG_FUNCTION_INFO_V1(bqarr_out);
Datum		bqarr_in(PG_FUNCTION_ARGS);
Datum		bqarr_out(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(boolop);
Datum		boolop(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(rboolop);
Datum		rboolop(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(querytree);
Datum		querytree(PG_FUNCTION_ARGS);

static bool signconsistent(QUERYTYPE * query, BITVEC sign, bool leaf);
static bool execconsistent(QUERYTYPE * query, ArrayType *array, bool leaf);

/*****************************************************************************
 *						   GiST functions
 *****************************************************************************/

/*
** The GiST Consistent method for _intments
** Should return false if for all data items x below entry,
** the predicate x op query == FALSE, where op is the oper
** corresponding to strategy in the pg_amop table.
*/
Datum
g_int_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	ArrayType  *query = (ArrayType *) PG_GETARG_POINTER(1);
	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	bool		retval;

	if (strategy == BooleanSearchStrategy)
		PG_RETURN_BOOL(execconsistent((QUERYTYPE *) query,
							   (ArrayType *) DatumGetPointer(entry->key),
				  ISLEAFKEY((ArrayType *) DatumGetPointer(entry->key))));

	/* XXX are we sure it's safe to scribble on the query object here? */
	/* XXX what about toasted input? */
	/* sort query for fast search, key is already sorted */
	if (ARRISVOID(query))
		PG_RETURN_BOOL(false);
	PREPAREARR(query);

	switch (strategy)
	{
		case RTOverlapStrategyNumber:
			retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
									   query);
			break;
		case RTSameStrategyNumber:
			if (GIST_LEAF(entry))
				DirectFunctionCall3(
									g_int_same,
									entry->key,
									PointerGetDatum(query),
									PointerGetDatum(&retval)
					);
			else
				retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
											query);
			break;
		case RTContainsStrategyNumber:
			retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
										query);
			break;
		case RTContainedByStrategyNumber:
			if (GIST_LEAF(entry))
				retval = inner_int_contains(query,
							  (ArrayType *) DatumGetPointer(entry->key));
			else
				retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
										   query);
			break;
		default:
			retval = FALSE;
	}
	PG_RETURN_BOOL(retval);
}

Datum
g_int_union(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_union(
										(bytea *) PG_GETARG_POINTER(0),
										(int *) PG_GETARG_POINTER(1),
										inner_int_union
										));
}

/*
** GiST Compress and Decompress methods
*/
Datum
g_int_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *retval;
	ArrayType  *r;
	int			len;
	int		   *dr;
	int			i,
				min,
				cand;

	if (entry->leafkey)
	{
		r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key);
		PREPAREARR(r);
		r->flags |= LEAFKEY;
		retval = palloc(sizeof(GISTENTRY));
		gistentryinit(*retval, PointerGetDatum(r),
			  entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);

		PG_RETURN_POINTER(retval);
	}

	r = (ArrayType *) PG_DETOAST_DATUM(entry->key);
	if (ISLEAFKEY(r) || ARRISVOID(r))
	{
		if (r != (ArrayType *) DatumGetPointer(entry->key))
			pfree(r);
		PG_RETURN_POINTER(entry);
	}

	if ((len = ARRNELEMS(r)) >= 2 * MAXNUMRANGE)
	{							/* compress */
		if (r == (ArrayType *) DatumGetPointer(entry->key))
			r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key);
		r = resize_intArrayType(r, 2 * (len));

		dr = ARRPTR(r);

		for (i = len - 1; i >= 0; i--)
			dr[2 * i] = dr[2 * i + 1] = dr[i];

		len *= 2;
		cand = 1;
		while (len > MAXNUMRANGE * 2)
		{
			min = 0x7fffffff;
			for (i = 2; i < len; i += 2)
				if (min > (dr[i] - dr[i - 1]))
				{
					min = (dr[i] - dr[i - 1]);
					cand = i;
				}
			memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int));
			len -= 2;
		}
		r = resize_intArrayType(r, len);
		retval = palloc(sizeof(GISTENTRY));
		gistentryinit(*retval, PointerGetDatum(r),
			  entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
		PG_RETURN_POINTER(retval);
	}
	else
		PG_RETURN_POINTER(entry);

	PG_RETURN_POINTER(entry);
}

Datum
g_int_decompress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *retval;
	ArrayType  *r;
	int		   *dr,
				lenr;
	ArrayType  *in;
	int			lenin;
	int		   *din;
	int			i,
				j;

	in = (ArrayType *) PG_DETOAST_DATUM(entry->key);

	if (ARRISVOID(in))
		PG_RETURN_POINTER(entry);

	lenin = ARRNELEMS(in);

	if (lenin < 2 * MAXNUMRANGE || ISLEAFKEY(in))
	{							/* not comressed value */
		if (in != (ArrayType *) DatumGetPointer(entry->key))
		{
			retval = palloc(sizeof(GISTENTRY));
			gistentryinit(*retval, PointerGetDatum(in),
			 entry->rel, entry->page, entry->offset, VARSIZE(in), FALSE);

			PG_RETURN_POINTER(retval);
		}
		PG_RETURN_POINTER(entry);
	}

	din = ARRPTR(in);
	lenr = internal_size(din, lenin);

	r = new_intArrayType(lenr);
	dr = ARRPTR(r);

	for (i = 0; i < lenin; i += 2)
		for (j = din[i]; j <= din[i + 1]; j++)
			if ((!i) || *(dr - 1) != j)
				*dr++ = j;

	if (in != (ArrayType *) DatumGetPointer(entry->key))
		pfree(in);
	retval = palloc(sizeof(GISTENTRY));
	gistentryinit(*retval, PointerGetDatum(r),
			  entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);

	PG_RETURN_POINTER(retval);
}

/*
** The GiST Penalty method for _intments
*/
Datum
g_int_penalty(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_penalty(
									  (GISTENTRY *) PG_GETARG_POINTER(0),
									  (GISTENTRY *) PG_GETARG_POINTER(1),
										  (float *) PG_GETARG_POINTER(2),
										  inner_int_union, rt__int_size
										  ));
}


Datum
g_int_picksplit(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_picksplit(
										  (bytea *) PG_GETARG_POINTER(0),
								  (GIST_SPLITVEC *) PG_GETARG_POINTER(1),
											inner_int_union,
											inner_int_inter,
											rt__int_size,
											0.01
											));
}

/*
** Equality methods
*/


Datum
g_int_same(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) PointerGetDatum(PG_GETARG_POINTER(0));
	ArrayType  *b = (ArrayType *) PointerGetDatum(PG_GETARG_POINTER(1));
	bool	   *result = (bool *) PG_GETARG_POINTER(2);
	int4		n = ARRNELEMS(a);
	int4	   *da,
			   *db;

	if (n != ARRNELEMS(b))
	{
		*result = false;
		PG_RETURN_POINTER(result);
	}
	*result = TRUE;
	da = ARRPTR(a);
	db = ARRPTR(b);
	while (n--)
		if (*da++ != *db++)
		{
			*result = FALSE;
			break;
		}

	PG_RETURN_POINTER(result);
}

Datum
_int_contained(PG_FUNCTION_ARGS)
{
	PG_RETURN_BOOL(DatumGetBool(
								DirectFunctionCall2(
													_int_contains,
								   PointerGetDatum(PG_GETARG_POINTER(1)),
									PointerGetDatum(PG_GETARG_POINTER(0))
													)
								));
}

Datum
_int_contains(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	bool		res;

	if (ARRISVOID(a) || ARRISVOID(b))
		return FALSE;

	PREPAREARR(a);
	PREPAREARR(b);
	res = inner_int_contains(a, b);
	pfree(a);
	pfree(b);
	PG_RETURN_BOOL(res);
}

static bool
inner_int_contains(ArrayType *a, ArrayType *b)
{
	int			na,
				nb;
	int			i,
				j,
				n;
	int		   *da,
			   *db;

	if (ARRISVOID(a) || ARRISVOID(b))
		return FALSE;

	na = ARRNELEMS(a);
	nb = ARRNELEMS(b);
	da = ARRPTR(a);
	db = ARRPTR(b);

#ifdef GIST_DEBUG
	elog(DEBUG3, "contains %d %d", na, nb);
#endif

	i = j = n = 0;
	while (i < na && j < nb)
		if (da[i] < db[j])
			i++;
		else if (da[i] == db[j])
		{
			n++;
			i++;
			j++;
		}
		else
			j++;

	return (n == nb) ? TRUE : FALSE;
}

/*****************************************************************************
 * Operator class for R-tree indexing
 *****************************************************************************/

Datum
_int_different(PG_FUNCTION_ARGS)
{
	PG_RETURN_BOOL(!DatumGetBool(
								 DirectFunctionCall2(
													 _int_same,
								   PointerGetDatum(PG_GETARG_POINTER(0)),
									PointerGetDatum(PG_GETARG_POINTER(1))
													 )
								 ));
}

Datum
_int_same(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	int			na,
				nb;
	int			n;
	int		   *da,
			   *db;
	bool		result;
	bool		avoid = ARRISVOID(a);
	bool		bvoid = ARRISVOID(b);

	if (avoid || bvoid)
		return (avoid && bvoid) ? TRUE : FALSE;

	SORT(a);
	SORT(b);
	na = ARRNELEMS(a);
	nb = ARRNELEMS(b);
	da = ARRPTR(a);
	db = ARRPTR(b);

	result = FALSE;

	if (na == nb)
	{
		result = TRUE;
		for (n = 0; n < na; n++)
			if (da[n] != db[n])
			{
				result = FALSE;
				break;
			}
	}

	pfree(a);
	pfree(b);

	PG_RETURN_BOOL(result);
}

/*	_int_overlap -- does a overlap b?
 */
Datum
_int_overlap(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	bool		result;

	if (ARRISVOID(a) || ARRISVOID(b))
		return FALSE;

	SORT(a);
	SORT(b);

	result = inner_int_overlap(a, b);

	pfree(a);
	pfree(b);

	PG_RETURN_BOOL(result);
}

static bool
inner_int_overlap(ArrayType *a, ArrayType *b)
{
	int			na,
				nb;
	int			i,
				j;
	int		   *da,
			   *db;

	if (ARRISVOID(a) || ARRISVOID(b))
		return FALSE;

	na = ARRNELEMS(a);
	nb = ARRNELEMS(b);
	da = ARRPTR(a);
	db = ARRPTR(b);

#ifdef GIST_DEBUG
	elog(DEBUG3, "g_int_overlap");
#endif

	i = j = 0;
	while (i < na && j < nb)
		if (da[i] < db[j])
			i++;
		else if (da[i] == db[j])
			return TRUE;
		else
			j++;

	return FALSE;
}

Datum
_int_union(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	ArrayType  *result;

	if (!ARRISVOID(a))
		SORT(a);
	if (!ARRISVOID(b))
		SORT(b);

	result = inner_int_union(a, b);

	if (a)
		pfree(a);
	if (b)
		pfree(b);

	PG_RETURN_POINTER(result);
}

static ArrayType *
inner_int_union(ArrayType *a, ArrayType *b)
{
	ArrayType  *r = NULL;
	int			na,
				nb;
	int		   *da,
			   *db,
			   *dr;
	int			i,
				j;

	if (ARRISVOID(a) && ARRISVOID(b))
		return new_intArrayType(0);
	if (ARRISVOID(a))
		r = copy_intArrayType(b);
	if (ARRISVOID(b))
		r = copy_intArrayType(a);

	if (r)
		dr = ARRPTR(r);
	else
	{
		na = ARRNELEMS(a);
		nb = ARRNELEMS(b);
		da = ARRPTR(a);
		db = ARRPTR(b);

		r = new_intArrayType(na + nb);
		dr = ARRPTR(r);

		/* union */
		i = j = 0;
		while (i < na && j < nb)
			if (da[i] < db[j])
				*dr++ = da[i++];
			else
				*dr++ = db[j++];

		while (i < na)
			*dr++ = da[i++];
		while (j < nb)
			*dr++ = db[j++];

	}

	if (ARRNELEMS(r) > 1)
		r = _int_unique(r);

	return r;
}


Datum
_int_inter(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	ArrayType  *result;

	if (ARRISVOID(a) || ARRISVOID(b))
		PG_RETURN_POINTER(new_intArrayType(0));

	SORT(a);
	SORT(b);

	result = inner_int_inter(a, b);

	pfree(a);
	pfree(b);

	PG_RETURN_POINTER(result);
}

static ArrayType *
inner_int_inter(ArrayType *a, ArrayType *b)
{
	ArrayType  *r;
	int			na,
				nb;
	int		   *da,
			   *db,
			   *dr;
	int			i,
				j;

	if (ARRISVOID(a) || ARRISVOID(b))
		return new_intArrayType(0);

	na = ARRNELEMS(a);
	nb = ARRNELEMS(b);
	da = ARRPTR(a);
	db = ARRPTR(b);
	r = new_intArrayType(min(na, nb));
	dr = ARRPTR(r);

	i = j = 0;
	while (i < na && j < nb)
		if (da[i] < db[j])
			i++;
		else if (da[i] == db[j])
		{
			if (i + j == 0 || (i + j > 0 && *(dr - 1) != db[j]))
				*dr++ = db[j];
			i++;
			j++;
		}
		else
			j++;

	if ((dr - ARRPTR(r)) == 0)
	{
		pfree(r);
		return new_intArrayType(0);
	}
	else
		return resize_intArrayType(r, dr - ARRPTR(r));
}

static void
rt__int_size(ArrayType *a, float *size)
{
	*size = (float) ARRNELEMS(a);

	return;
}


/*****************************************************************************
 *				   Miscellaneous operators and functions
 *****************************************************************************/

/* len >= 2 */
static bool
isort(int4 *a, int len)
{
	int4		tmp,
				index;
	int4	   *cur,
			   *end;
	bool		r = FALSE;

	end = a + len;
	do
	{
		index = 0;
		cur = a + 1;
		while (cur < end)
		{
			if (*(cur - 1) > *cur)
			{
				tmp = *(cur - 1);
				*(cur - 1) = *cur;
				*cur = tmp;
				index = 1;
			}
			else if (!r && *(cur - 1) == *cur)
				r = TRUE;
			cur++;
		}
	} while (index);
	return r;
}

static ArrayType *
new_intArrayType(int num)
{
	ArrayType  *r;
	int			nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num;

	r = (ArrayType *) palloc(nbytes);

	MemSet(r, 0, nbytes);
	
	ARR_SIZE(r) = nbytes;
	ARR_NDIM(r) = NDIM;
	ARR_ELEMTYPE(r) = INT4OID;
	r->flags &= ~LEAFKEY;
	*((int *) ARR_DIMS(r)) = num;
	*((int *) ARR_LBOUND(r)) = 1;
	ARR_ELEMTYPE(r) = INT4OID;

	return r;
}

static ArrayType *
resize_intArrayType(ArrayType *a, int num)
{
	int			nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num;

	if (num == ARRNELEMS(a))
		return a;

	a = (ArrayType *) repalloc(a, nbytes);

	a->size = nbytes;
	*((int *) ARR_DIMS(a)) = num;
	return a;
}

static ArrayType *
copy_intArrayType(ArrayType *a)
{
	ArrayType  *r;

	r = new_intArrayType(ARRNELEMS(a));
	memmove(r, a, VARSIZE(a));
	return r;
}

/* num for compressed key */
static int
internal_size(int *a, int len)
{
	int			i,
				size = 0;

	for (i = 0; i < len; i += 2)
		if (!i || a[i] != a[i - 1])		/* do not count repeated range */
			size += a[i + 1] - a[i] + 1;

	return size;
}

/* r is sorted and size of r > 1 */
static ArrayType *
_int_unique(ArrayType *r)
{
	int		   *tmp,
			   *dr,
			   *data;
	int			num = ARRNELEMS(r);

	data = tmp = dr = ARRPTR(r);
	while (tmp - data < num)
		if (*tmp != *dr)
			*(++dr) = *tmp++;
		else
			tmp++;
	return resize_intArrayType(r, dr + 1 - ARRPTR(r));
}

/*********************************************************************
** intbig functions
*********************************************************************/
static void
gensign(BITVEC sign, int *a, int len)
{
	int			i;

	/* we assume that the sign vector is previously zeroed */
	for (i = 0; i < len; i++)
	{
		HASH(sign, *a);
		a++;
	}
}

static bool
_intbig_overlap(ArrayType *a, ArrayType *b)
{
	int			i;
	BITVECP		da,
				db;

	da = SIGPTR(a);
	db = SIGPTR(b);

	LOOPBYTE(if (da[i] & db[i]) return TRUE);
	return FALSE;
}

static bool
_intbig_contains(ArrayType *a, ArrayType *b)
{
	int			i;
	BITVECP		da,
				db;

	da = SIGPTR(a);
	db = SIGPTR(b);

	LOOPBYTE(if (db[i] & ~da[i]) return FALSE);

	return TRUE;
}

static void
rt__intbig_size(ArrayType *a, float *sz)
{
	int			i,
				len = 0;
	BITVECP		bv = SIGPTR(a);

	LOOPBYTE(
			 len +=
			 GETBITBYTE(bv, 0) +
			 GETBITBYTE(bv, 1) +
			 GETBITBYTE(bv, 2) +
			 GETBITBYTE(bv, 3) +
			 GETBITBYTE(bv, 4) +
			 GETBITBYTE(bv, 5) +
			 GETBITBYTE(bv, 6) +
			 GETBITBYTE(bv, 7);
	bv = (BITVECP) (((char *) bv) + 1);
	);

	*sz = (float) len;
	return;
}

static ArrayType *
_intbig_union(ArrayType *a, ArrayType *b)
{
	ArrayType  *r;
	BITVECP		da,
				db,
				dr;
	int			i;

	r = new_intArrayType(SIGLENINT);

	da = SIGPTR(a);
	db = SIGPTR(b);
	dr = SIGPTR(r);

	LOOPBYTE(dr[i] = da[i] | db[i]);

	return r;
}

static ArrayType *
_intbig_inter(ArrayType *a, ArrayType *b)
{
	ArrayType  *r;
	BITVECP		da,
				db,
				dr;
	int			i;

	r = new_intArrayType(SIGLENINT);

	da = SIGPTR(a);
	db = SIGPTR(b);
	dr = SIGPTR(r);

	LOOPBYTE(dr[i] = da[i] & db[i]);

	return r;
}

Datum
g_intbig_same(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) PG_GETARG_POINTER(0);
	ArrayType  *b = (ArrayType *) PG_GETARG_POINTER(1);
	bool	   *result = (bool *) PG_GETARG_POINTER(2);
	BITVECP		da,
				db;
	int			i;

	da = SIGPTR(a);
	db = SIGPTR(b);

	LOOPBYTE(
			 if (da[i] != db[i])
			 {
		*result = FALSE;
		PG_RETURN_POINTER(result);
	}
	);

	*result = TRUE;
	PG_RETURN_POINTER(result);
}

Datum
g_intbig_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *retval;
	ArrayType  *r,
			   *in;
	bool		maycompress = true;
	int			i;

	if (DatumGetPointer(entry->key) != NULL)
		in = (ArrayType *) PG_DETOAST_DATUM(entry->key);
	else
		in = NULL;

	if (!entry->leafkey)
	{
		LOOPBYTE(
				 if ((((char *) ARRPTR(in))[i] & 0xff) != 0xff)
				 {
			maycompress = false;
			break;
		}
		);
		if (maycompress)
		{
			retval = palloc(sizeof(GISTENTRY));
			r = new_intArrayType(1);
			gistentryinit(*retval, PointerGetDatum(r),
			  entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
			PG_RETURN_POINTER(retval);
		}
		PG_RETURN_POINTER(entry);
	}

	retval = palloc(sizeof(GISTENTRY));
	r = new_intArrayType(SIGLENINT);

	if (ARRISVOID(in))
	{
		gistentryinit(*retval, PointerGetDatum(r),
			  entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
		if (in != (ArrayType *) DatumGetPointer(entry->key))
			pfree(in);
		PG_RETURN_POINTER(retval);
	}

	gensign(SIGPTR(r),
			ARRPTR(in),
			ARRNELEMS(in));

	LOOPBYTE(
			 if ((((char *) ARRPTR(in))[i] & 0xff) != 0xff)
			 {
		maycompress = false;
		break;
	}
	);

	if (maycompress)
	{
		pfree(r);
		r = new_intArrayType(1);
	}

	gistentryinit(*retval, PointerGetDatum(r), entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);

	if (in != (ArrayType *) DatumGetPointer(entry->key))
		pfree(in);

	PG_RETURN_POINTER(retval);
}

Datum
g_intbig_decompress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	ArrayType  *key;

	key = (ArrayType *) PG_DETOAST_DATUM(entry->key);

	if (key != (ArrayType *) DatumGetPointer(entry->key))
	{
		GISTENTRY  *retval;

		retval = palloc(sizeof(GISTENTRY));

		gistentryinit(*retval, PointerGetDatum(key),
					  entry->rel, entry->page, entry->offset, (key) ? VARSIZE(key) : 0, FALSE);
		PG_RETURN_POINTER(retval);
	}
	if (ARRNELEMS(key) == 1)
	{
		GISTENTRY  *retval;
		ArrayType  *newkey;

		retval = palloc(sizeof(GISTENTRY));
		newkey = new_intArrayType(SIGLENINT);
		MemSet((void *) ARRPTR(newkey), 0xff, SIGLEN);

		gistentryinit(*retval, PointerGetDatum(newkey),
		 entry->rel, entry->page, entry->offset, VARSIZE(newkey), FALSE);
		PG_RETURN_POINTER(retval);
	}
	PG_RETURN_POINTER(entry);
}

Datum
g_intbig_picksplit(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_picksplit(
										  (bytea *) PG_GETARG_POINTER(0),
								  (GIST_SPLITVEC *) PG_GETARG_POINTER(1),
											_intbig_union,
											_intbig_inter,
											rt__intbig_size,
											0.1
											));
}

Datum
g_intbig_union(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_union(
										(bytea *) PG_GETARG_POINTER(0),
										(int *) PG_GETARG_POINTER(1),
										_intbig_union
										));
}

Datum
g_intbig_penalty(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(_int_common_penalty(
									  (GISTENTRY *) PG_GETARG_POINTER(0),
									  (GISTENTRY *) PG_GETARG_POINTER(1),
										  (float *) PG_GETARG_POINTER(2),
										  _intbig_union, rt__intbig_size
										  ));
}

Datum
g_intbig_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	ArrayType  *query = (ArrayType *) PG_GETARG_POINTER(1);
	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
	bool		retval;
	ArrayType  *q;

	if (strategy == BooleanSearchStrategy)
		PG_RETURN_BOOL(signconsistent((QUERYTYPE *) query,
					   SIGPTR((ArrayType *) DatumGetPointer(entry->key)),
									  false));

	/* XXX what about toasted input? */
	if (ARRISVOID(query))
		return FALSE;

	q = new_intArrayType(SIGLENINT);
	gensign(SIGPTR(q),
			ARRPTR(query),
			ARRNELEMS(query));

	switch (strategy)
	{
		case RTOverlapStrategyNumber:
			retval = _intbig_overlap((ArrayType *) DatumGetPointer(entry->key), q);
			break;
		case RTSameStrategyNumber:
			if (GIST_LEAF(entry))
				DirectFunctionCall3(
									g_intbig_same,
									entry->key,
									PointerGetDatum(q),
									PointerGetDatum(&retval)
					);
			else
				retval = _intbig_contains((ArrayType *) DatumGetPointer(entry->key), q);
			break;
		case RTContainsStrategyNumber:
			retval = _intbig_contains((ArrayType *) DatumGetPointer(entry->key), q);
			break;
		case RTContainedByStrategyNumber:
			retval = _intbig_overlap((ArrayType *) DatumGetPointer(entry->key), q);
			break;
		default:
			retval = FALSE;
	}
	pfree(q);
	PG_RETURN_BOOL(retval);
}

/*****************************************************************
** Common GiST Method
*****************************************************************/

/*
** The GiST Union method for _intments
** returns the minimal set that encloses all the entries in entryvec
*/
static ArrayType *
_int_common_union(bytea *entryvec, int *sizep, formarray unionf)
{
	int			numranges,
				i;
	ArrayType  *out = (ArrayType *) NULL;
	ArrayType  *tmp;

#ifdef GIST_DEBUG
	elog(DEBUG3, "_int_common_union in");
#endif

	numranges = (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY);
	tmp = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[0].key);

	for (i = 1; i < numranges; i++)
	{
		out = (*unionf) (tmp, (ArrayType *)
			  DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key));
		if (i > 1 && tmp)
			pfree(tmp);
		tmp = out;
	}

	out->flags &= ~LEAFKEY;
	*sizep = VARSIZE(out);
	if (*sizep == 0)
	{
		pfree(out);
#ifdef GIST_DEBUG
		elog(DEBUG3, "_int_common_union out1");
#endif
		return NULL;
	}
#ifdef GIST_DEBUG
	elog(DEBUG3, "_int_common_union out");
#endif
	return (out);

}

/*****************************************
 * The GiST Penalty method for _intments *
 *****************************************/

static float *
_int_common_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result,
					formarray unionf,
					formfloat sizef)
{
	ArrayType  *ud;
	float		tmp1,
				tmp2;

#ifdef GIST_DEBUG
	elog(DEBUG3, "penalty");
#endif
	ud = (*unionf) ((ArrayType *) DatumGetPointer(origentry->key),
					(ArrayType *) DatumGetPointer(newentry->key));
	(*sizef) (ud, &tmp1);
	(*sizef) ((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
	*result = tmp1 - tmp2;
	pfree(ud);

#ifdef GIST_DEBUG
	elog(DEBUG3, "--penalty\t%g", *result);
#endif

	return (result);
}

typedef struct
{
	OffsetNumber pos;
	float		cost;
} SPLITCOST;

static int
comparecost(const void *a, const void *b)
{
	if (((SPLITCOST *) a)->cost == ((SPLITCOST *) b)->cost)
		return 0;
	else
		return (((SPLITCOST *) a)->cost > ((SPLITCOST *) b)->cost) ? 1 : -1;
}

/*
** The GiST PickSplit method for _intments
** We use Guttman's poly time split algorithm
*/
static GIST_SPLITVEC *
_int_common_picksplit(bytea *entryvec,
					  GIST_SPLITVEC *v,
					  formarray unionf,
					  formarray interf,
					  formfloat sizef,
					  float coef)
{
	OffsetNumber i,
				j;
	ArrayType  *datum_alpha,
			   *datum_beta;
	ArrayType  *datum_l,
			   *datum_r;
	ArrayType  *union_d,
			   *union_dl,
			   *union_dr;
	ArrayType  *inter_d;
	bool		firsttime;
	float		size_alpha,
				size_beta,
				size_union,
				size_inter;
	float		size_waste,
				waste;
	float		size_l,
				size_r;
	int			nbytes;
	OffsetNumber seed_1 = 0,
				seed_2 = 0;
	OffsetNumber *left,
			   *right;
	OffsetNumber maxoff;
	SPLITCOST  *costvector;

#ifdef GIST_DEBUG
	elog(DEBUG3, "--------picksplit %d", (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY));
#endif

	maxoff = ((VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY)) - 2;
	nbytes = (maxoff + 2) * sizeof(OffsetNumber);
	v->spl_left = (OffsetNumber *) palloc(nbytes);
	v->spl_right = (OffsetNumber *) palloc(nbytes);

	firsttime = true;
	waste = 0.0;
	for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
	{
		datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
		for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
		{
			datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[j].key);

			/* compute the wasted space by unioning these guys */
			/* size_waste = size_union - size_inter; */
			union_d = (*unionf) (datum_alpha, datum_beta);
			(*sizef) (union_d, &size_union);
			inter_d = (*interf) (datum_alpha, datum_beta);
			(*sizef) (inter_d, &size_inter);
			size_waste = size_union - size_inter;

			pfree(union_d);

			if (inter_d != (ArrayType *) NULL)
				pfree(inter_d);

			/*
			 * are these a more promising split that what we've already
			 * seen?
			 */

			if (size_waste > waste || firsttime)
			{
				waste = size_waste;
				seed_1 = i;
				seed_2 = j;
				firsttime = false;
			}
		}
	}

	left = v->spl_left;
	v->spl_nleft = 0;
	right = v->spl_right;
	v->spl_nright = 0;
	if (seed_1 == 0 || seed_2 == 0)
	{
		seed_1 = 1;
		seed_2 = 2;
	}

	datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_1].key);
	datum_l = copy_intArrayType(datum_alpha);
	(*sizef) (datum_l, &size_l);
	datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_2].key);
	datum_r = copy_intArrayType(datum_beta);
	(*sizef) (datum_r, &size_r);

	maxoff = OffsetNumberNext(maxoff);

	/*
	 * sort entries
	 */
	costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
	{
		costvector[i - 1].pos = i;
		datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
		union_d = (*unionf) (datum_l, datum_alpha);
		(*sizef) (union_d, &size_alpha);
		pfree(union_d);
		union_d = (*unionf) (datum_r, datum_alpha);
		(*sizef) (union_d, &size_beta);
		pfree(union_d);
		costvector[i - 1].cost = abs((size_alpha - size_l) - (size_beta - size_r));
	}
	qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);

	/*
	 * Now split up the regions between the two seeds.	An important
	 * property of this split algorithm is that the split vector v has the
	 * indices of items to be split in order in its left and right
	 * vectors.  We exploit this property by doing a merge in the code
	 * that actually splits the page.
	 *
	 * For efficiency, we also place the new index tuple in this loop. This
	 * is handled at the very end, when we have placed all the existing
	 * tuples and i == maxoff + 1.
	 */


	for (j = 0; j < maxoff; j++)
	{
		i = costvector[j].pos;

		/*
		 * If we've already decided where to place this item, just put it
		 * on the right list.  Otherwise, we need to figure out which page
		 * needs the least enlargement in order to store the item.
		 */

		if (i == seed_1)
		{
			*left++ = i;
			v->spl_nleft++;
			continue;
		}
		else if (i == seed_2)
		{
			*right++ = i;
			v->spl_nright++;
			continue;
		}

		/* okay, which page needs least enlargement? */
		datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
		union_dl = (*unionf) (datum_l, datum_alpha);
		union_dr = (*unionf) (datum_r, datum_alpha);
		(*sizef) (union_dl, &size_alpha);
		(*sizef) (union_dr, &size_beta);

		/* pick which page to add it to */
		if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, coef))
		{
			if (datum_l)
				pfree(datum_l);
			if (union_dr)
				pfree(union_dr);
			datum_l = union_dl;
			size_l = size_alpha;
			*left++ = i;
			v->spl_nleft++;
		}
		else
		{
			if (datum_r)
				pfree(datum_r);
			if (union_dl)
				pfree(union_dl);
			datum_r = union_dr;
			size_r = size_beta;
			*right++ = i;
			v->spl_nright++;
		}
	}
	pfree(costvector);
	*right = *left = FirstOffsetNumber;

	datum_l->flags &= ~LEAFKEY;
	datum_r->flags &= ~LEAFKEY;
	v->spl_ldatum = PointerGetDatum(datum_l);
	v->spl_rdatum = PointerGetDatum(datum_r);

#ifdef GIST_DEBUG
	elog(DEBUG3, "--------ENDpicksplit %d %d", v->spl_nleft, v->spl_nright);
#endif
	return v;
}

/*****************************************************************************
 *		BoolSearch
 *****************************************************************************/


#define END		0
#define ERR		1
#define VAL		2
#define OPR		3
#define OPEN	4
#define CLOSE	5

/* parser's states */
#define WAITOPERAND 1
#define WAITENDOPERAND	2
#define WAITOPERATOR	3

/*
 * node of query tree, also used
 * for storing polish notation in parser
 */
typedef struct NODE
{
	int4		type;
	int4		val;
	struct NODE *next;
}	NODE;

typedef struct
{
	char	   *buf;
	int4		state;
	int4		count;
	/* reverse polish notation in list (for temprorary usage) */
	NODE	   *str;
	/* number in str */
	int4		num;
}	WORKSTATE;

/*
 * get token from query string
 */
static int4
gettoken(WORKSTATE * state, int4 *val)
{
	char		nnn[16],
			   *curnnn;

	curnnn = nnn;
	while (1)
	{
		switch (state->state)
		{
			case WAITOPERAND:
				curnnn = nnn;
				if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
					*(state->buf) == '-')
				{
					state->state = WAITENDOPERAND;
					*curnnn = *(state->buf);
					curnnn++;
				}
				else if (*(state->buf) == '!')
				{
					(state->buf)++;
					*val = (int4) '!';
					return OPR;
				}
				else if (*(state->buf) == '(')
				{
					state->count++;
					(state->buf)++;
					return OPEN;
				}
				else if (*(state->buf) != ' ')
					return ERR;
				break;
			case WAITENDOPERAND:
				if (*(state->buf) >= '0' && *(state->buf) <= '9')
				{
					*curnnn = *(state->buf);
					curnnn++;
				}
				else
				{
					*curnnn = '\0';
					*val = (int4) atoi(nnn);
					state->state = WAITOPERATOR;
					return (state->count && *(state->buf) == '\0')
						? ERR : VAL;
				}
				break;
			case WAITOPERATOR:
				if (*(state->buf) == '&' || *(state->buf) == '|')
				{
					state->state = WAITOPERAND;
					*val = (int4) *(state->buf);
					(state->buf)++;
					return OPR;
				}
				else if (*(state->buf) == ')')
				{
					(state->buf)++;
					state->count--;
					return (state->count < 0) ? ERR : CLOSE;
				}
				else if (*(state->buf) == '\0')
					return (state->count) ? ERR : END;
				else if (*(state->buf) != ' ')
					return ERR;
				break;
			default:
				return ERR;
				break;
		}
		(state->buf)++;
	}
	return END;
}

/*
 * push new one in polish notation reverse view
 */
static void
pushquery(WORKSTATE * state, int4 type, int4 val)
{
	NODE	   *tmp = (NODE *) palloc(sizeof(NODE));

	tmp->type = type;
	tmp->val = val;
	tmp->next = state->str;
	state->str = tmp;
	state->num++;
}

#define STACKDEPTH	16

/*
 * make polish notaion of query
 */
static int4
makepol(WORKSTATE * state)
{
	int4		val,
				type;
	int4		stack[STACKDEPTH];
	int4		lenstack = 0;

	while ((type = gettoken(state, &val)) != END)
	{
		switch (type)
		{
			case VAL:
				pushquery(state, type, val);
				while (lenstack && (stack[lenstack - 1] == (int4) '&' ||
									stack[lenstack - 1] == (int4) '!'))
				{
					lenstack--;
					pushquery(state, OPR, stack[lenstack]);
				}
				break;
			case OPR:
				if (lenstack && val == (int4) '|')
					pushquery(state, OPR, val);
				else
				{
					if (lenstack == STACKDEPTH)
						elog(ERROR, "Stack too short");
					stack[lenstack] = val;
					lenstack++;
				}
				break;
			case OPEN:
				if (makepol(state) == ERR)
					return ERR;
				if (lenstack && (stack[lenstack - 1] == (int4) '&' ||
								 stack[lenstack - 1] == (int4) '!'))
				{
					lenstack--;
					pushquery(state, OPR, stack[lenstack]);
				}
				break;
			case CLOSE:
				while (lenstack)
				{
					lenstack--;
					pushquery(state, OPR, stack[lenstack]);
				};
				return END;
				break;
			case ERR:
			default:
				elog(ERROR, "Syntax error");
				return ERR;

		}
	}

	while (lenstack)
	{
		lenstack--;
		pushquery(state, OPR, stack[lenstack]);
	};
	return END;
}

typedef struct
{
	int4	   *arrb;
	int4	   *arre;
}	CHKVAL;

/*
 * is there value 'val' in array or not ?
 */
static bool
checkcondition_arr(void *checkval, int4 val)
{
	int4	   *StopLow = ((CHKVAL *) checkval)->arrb;
	int4	   *StopHigh = ((CHKVAL *) checkval)->arre;
	int4	   *StopMiddle;

	/* Loop invariant: StopLow <= val < StopHigh */

	while (StopLow < StopHigh)
	{
		StopMiddle = StopLow + (StopHigh - StopLow) / 2;
		if (*StopMiddle == val)
			return (true);
		else if (*StopMiddle < val)
			StopLow = StopMiddle + 1;
		else
			StopHigh = StopMiddle;
	}
	return false;
}

static bool
checkcondition_bit(void *checkval, int4 val)
{
	return GETBIT(checkval, HASHVAL(val));
}

/*
 * check for boolean condition
 */
static bool
execute(ITEM * curitem, void *checkval, bool calcnot, bool (*chkcond) (void *checkval, int4 val))
{

	if (curitem->type == VAL)
		return (*chkcond) (checkval, curitem->val);
	else if (curitem->val == (int4) '!')
	{
		return (calcnot) ?
			((execute(curitem - 1, checkval, calcnot, chkcond)) ? false : true)
			: true;
	}
	else if (curitem->val == (int4) '&')
	{
		if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
			return execute(curitem - 1, checkval, calcnot, chkcond);
		else
			return false;
	}
	else
	{							/* |-operator */
		if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
			return true;
		else
			return execute(curitem - 1, checkval, calcnot, chkcond);
	}
	return false;
}

/*
 * signconsistent & execconsistent called by *_consistent
 */
static bool
signconsistent(QUERYTYPE * query, BITVEC sign, bool calcnot)
{
	return execute(
				   GETQUERY(query) + query->size - 1,
				   (void *) sign, calcnot,
				   checkcondition_bit
	);
}

static bool
execconsistent(QUERYTYPE * query, ArrayType *array, bool calcnot)
{
	CHKVAL		chkval;

	chkval.arrb = ARRPTR(array);
	chkval.arre = chkval.arrb + ARRNELEMS(array);
	return execute(
				   GETQUERY(query) + query->size - 1,
				   (void *) &chkval, calcnot,
				   checkcondition_arr
		);
}

/*
 * boolean operations
 */
Datum
rboolop(PG_FUNCTION_ARGS)
{
	return DirectFunctionCall2(
							   boolop,
							   PG_GETARG_DATUM(1),
							   PG_GETARG_DATUM(0)
	);
}

Datum
boolop(PG_FUNCTION_ARGS)
{
	ArrayType  *val = (ArrayType *) PG_DETOAST_DATUM_COPY(PG_GETARG_POINTER(0));
	QUERYTYPE  *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(1));
	CHKVAL		chkval;
	bool		result;

	if (ARRISVOID(val))
	{
		pfree(val);
		PG_FREE_IF_COPY(query, 1);
		PG_RETURN_BOOL(false);
	}

	PREPAREARR(val);
	chkval.arrb = ARRPTR(val);
	chkval.arre = chkval.arrb + ARRNELEMS(val);
	result = execute(
					 GETQUERY(query) + query->size - 1,
					 &chkval, true,
					 checkcondition_arr
		);
	pfree(val);

	PG_FREE_IF_COPY(query, 1);
	PG_RETURN_BOOL(result);
}

static void
findoprnd(ITEM * ptr, int4 *pos)
{
#ifdef BS_DEBUG
	elog(DEBUG3, (ptr[*pos].type == OPR) ?
		 "%d  %c" : "%d  %d ", *pos, ptr[*pos].val);
#endif
	if (ptr[*pos].type == VAL)
	{
		ptr[*pos].left = 0;
		(*pos)--;
	}
	else if (ptr[*pos].val == (int4) '!')
	{
		ptr[*pos].left = -1;
		(*pos)--;
		findoprnd(ptr, pos);
	}
	else
	{
		ITEM	   *curitem = &ptr[*pos];
		int4		tmp = *pos;

		(*pos)--;
		findoprnd(ptr, pos);
		curitem->left = *pos - tmp;
		findoprnd(ptr, pos);
	}
}


/*
 * input
 */
Datum
bqarr_in(PG_FUNCTION_ARGS)
{
	char	   *buf = (char *) PG_GETARG_POINTER(0);
	WORKSTATE	state;
	int4		i;
	QUERYTYPE  *query;
	int4		commonlen;
	ITEM	   *ptr;
	NODE	   *tmp;
	int4		pos = 0;

#ifdef BS_DEBUG
	StringInfoData pbuf;
#endif

	state.buf = buf;
	state.state = WAITOPERAND;
	state.count = 0;
	state.num = 0;
	state.str = NULL;

	/* make polish notation (postfix, but in reverse order) */
	makepol(&state);
	if (!state.num)
		elog(ERROR, "Empty query");

	commonlen = COMPUTESIZE(state.num);
	query = (QUERYTYPE *) palloc(commonlen);
	query->len = commonlen;
	query->size = state.num;
	ptr = GETQUERY(query);

	for (i = state.num - 1; i >= 0; i--)
	{
		ptr[i].type = state.str->type;
		ptr[i].val = state.str->val;
		tmp = state.str->next;
		pfree(state.str);
		state.str = tmp;
	}

	pos = query->size - 1;
	findoprnd(ptr, &pos);
#ifdef BS_DEBUG
	initStringInfo(&pbuf);
	for (i = 0; i < query->size; i++)
	{
		if (ptr[i].type == OPR)
			appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
		else
			appendStringInfo(&pbuf, "%d ", ptr[i].val);
	}
	elog(DEBUG3, "POR: %s", pbuf.data);
	pfree(pbuf.data);
#endif

	PG_RETURN_POINTER(query);
}


/*
 * out function
 */
typedef struct
{
	ITEM	   *curpol;
	char	   *buf;
	char	   *cur;
	int4		buflen;
}	INFIX;

#define RESIZEBUF(inf,addsize) while( ( inf->cur - inf->buf ) + addsize + 1 >= inf->buflen ) { \
	int4 len = inf->cur - inf->buf; \
	inf->buflen *= 2; \
	inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
	inf->cur = inf->buf + len; \
}

static void
infix(INFIX * in, bool first)
{
	if (in->curpol->type == VAL)
	{
		RESIZEBUF(in, 11);
		sprintf(in->cur, "%d", in->curpol->val);
		in->cur = strchr(in->cur, '\0');
		in->curpol--;
	}
	else if (in->curpol->val == (int4) '!')
	{
		bool		isopr = false;

		RESIZEBUF(in, 1);
		*(in->cur) = '!';
		in->cur++;
		*(in->cur) = '\0';
		in->curpol--;
		if (in->curpol->type == OPR)
		{
			isopr = true;
			RESIZEBUF(in, 2);
			sprintf(in->cur, "( ");
			in->cur = strchr(in->cur, '\0');
		}
		infix(in, isopr);
		if (isopr)
		{
			RESIZEBUF(in, 2);
			sprintf(in->cur, " )");
			in->cur = strchr(in->cur, '\0');
		}
	}
	else
	{
		int4		op = in->curpol->val;
		INFIX		nrm;

		in->curpol--;
		if (op == (int4) '|' && !first)
		{
			RESIZEBUF(in, 2);
			sprintf(in->cur, "( ");
			in->cur = strchr(in->cur, '\0');
		}

		nrm.curpol = in->curpol;
		nrm.buflen = 16;
		nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);

		/* get right operand */
		infix(&nrm, false);

		/* get & print left operand */
		in->curpol = nrm.curpol;
		infix(in, false);

		/* print operator & right operand */
		RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
		sprintf(in->cur, " %c %s", op, nrm.buf);
		in->cur = strchr(in->cur, '\0');
		pfree(nrm.buf);

		if (op == (int4) '|' && !first)
		{
			RESIZEBUF(in, 2);
			sprintf(in->cur, " )");
			in->cur = strchr(in->cur, '\0');
		}
	}
}


Datum
bqarr_out(PG_FUNCTION_ARGS)
{
	QUERYTYPE  *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
	INFIX		nrm;

	if (query->size == 0)
		elog(ERROR, "Empty");
	nrm.curpol = GETQUERY(query) + query->size - 1;
	nrm.buflen = 32;
	nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
	*(nrm.cur) = '\0';
	infix(&nrm, true);

	PG_FREE_IF_COPY(query, 0);
	PG_RETURN_POINTER(nrm.buf);
}

static int4
countdroptree(ITEM * q, int4 pos)
{
	if (q[pos].type == VAL)
		return 1;
	else if (q[pos].val == (int4) '!')
		return 1 + countdroptree(q, pos - 1);
	else
		return 1 + countdroptree(q, pos - 1) + countdroptree(q, pos + q[pos].left);
}

/*
 * common algorithm:
 * result of all '!' will be = 'true', so
 * we can modify query tree for clearing
 */
static int4
shorterquery(ITEM * q, int4 len)
{
	int4		index,
				posnot,
				poscor;
	bool		notisleft = false;
	int4		drop,
				i;

	/* out all '!' */
	do
	{
		index = 0;
		drop = 0;
		/* find ! */
		for (posnot = 0; posnot < len; posnot++)
			if (q[posnot].type == OPR && q[posnot].val == (int4) '!')
			{
				index = 1;
				break;
			}

		if (posnot == len)
			return len;

		/* last operator is ! */
		if (posnot == len - 1)
			return 0;

		/* find operator for this operand */
		for (poscor = posnot + 1; poscor < len; poscor++)
		{
			if (q[poscor].type == OPR)
			{
				if (poscor == posnot + 1)
				{
					notisleft = false;
					break;
				}
				else if (q[poscor].left + poscor == posnot)
				{
					notisleft = true;
					break;
				}
			}
		}
		if (q[poscor].val == (int4) '!')
		{
			drop = countdroptree(q, poscor);
			q[poscor - 1].type = VAL;
			for (i = poscor + 1; i < len; i++)
				if (q[i].type == OPR && q[i].left + i <= poscor)
					q[i].left += drop - 2;
			memcpy((void *) &q[poscor - drop + 1],
				   (void *) &q[poscor - 1],
				   sizeof(ITEM) * (len - (poscor - 1)));
			len -= drop - 2;
		}
		else if (q[poscor].val == (int4) '|')
		{
			drop = countdroptree(q, poscor);
			q[poscor - 1].type = VAL;
			q[poscor].val = (int4) '!';
			q[poscor].left = -1;
			for (i = poscor + 1; i < len; i++)
				if (q[i].type == OPR && q[i].left + i < poscor)
					q[i].left += drop - 2;
			memcpy((void *) &q[poscor - drop + 1],
				   (void *) &q[poscor - 1],
				   sizeof(ITEM) * (len - (poscor - 1)));
			len -= drop - 2;
		}
		else
		{						/* &-operator */
			if (
				(notisleft && q[poscor - 1].type == OPR &&
				 q[poscor - 1].val == (int4) '!') ||
				(!notisleft && q[poscor + q[poscor].left].type == OPR &&
				 q[poscor + q[poscor].left].val == (int4) '!')
				)
			{					/* drop subtree */
				drop = countdroptree(q, poscor);
				q[poscor - 1].type = VAL;
				q[poscor].val = (int4) '!';
				q[poscor].left = -1;
				for (i = poscor + 1; i < len; i++)
					if (q[i].type == OPR && q[i].left + i < poscor)
						q[i].left += drop - 2;
				memcpy((void *) &q[poscor - drop + 1],
					   (void *) &q[poscor - 1],
					   sizeof(ITEM) * (len - (poscor - 1)));
				len -= drop - 2;
			}
			else
			{					/* drop only operator */
				int4		subtreepos = (notisleft) ?
				poscor - 1 : poscor + q[poscor].left;
				int4		subtreelen = countdroptree(q, subtreepos);

				drop = countdroptree(q, poscor);
				for (i = poscor + 1; i < len; i++)
					if (q[i].type == OPR && q[i].left + i < poscor)
						q[i].left += drop - subtreelen;
				memcpy((void *) &q[subtreepos + 1],
					   (void *) &q[poscor + 1],
					   sizeof(ITEM) * (len - (poscor - 1)));
				memcpy((void *) &q[poscor - drop + 1],
					   (void *) &q[subtreepos - subtreelen + 1],
					   sizeof(ITEM) * (len - (drop - subtreelen)));
				len -= drop - subtreelen;
			}
		}
	} while (index);
	return len;
}


Datum
querytree(PG_FUNCTION_ARGS)
{
	QUERYTYPE  *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
	INFIX		nrm;
	text	   *res;
	ITEM	   *q;
	int4		len;

	if (query->size == 0)
		elog(ERROR, "Empty");

	q = (ITEM *) palloc(sizeof(ITEM) * query->size);
	memcpy((void *) q, GETQUERY(query), sizeof(ITEM) * query->size);
	len = shorterquery(q, query->size);
	PG_FREE_IF_COPY(query, 0);

	if (len == 0)
	{
		res = (text *) palloc(1 + VARHDRSZ);
		VARATT_SIZEP(res) = 1 + VARHDRSZ;
		*((char *) VARDATA(res)) = 'T';
	}
	else
	{
		nrm.curpol = q + len - 1;
		nrm.buflen = 32;
		nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
		*(nrm.cur) = '\0';
		infix(&nrm, true);

		res = (text *) palloc(nrm.cur - nrm.buf + VARHDRSZ);
		VARATT_SIZEP(res) = nrm.cur - nrm.buf + VARHDRSZ;
		strncpy(VARDATA(res), nrm.buf, nrm.cur - nrm.buf);
	}
	pfree(q);

	PG_RETURN_POINTER(res);
}

/*
** Additional array functions
*/
static int32 intarray_match_first(ArrayType *a, int32 elem);
static ArrayType *intarray_add_elem(ArrayType *a, int32 elem);
static ArrayType *intarray_concat_arrays(ArrayType *a, ArrayType *b);
static ArrayType *int_to_intset(int32 elem);

PG_FUNCTION_INFO_V1(intset);
PG_FUNCTION_INFO_V1(icount);
PG_FUNCTION_INFO_V1(sort);
PG_FUNCTION_INFO_V1(sort_asc);
PG_FUNCTION_INFO_V1(sort_desc);
PG_FUNCTION_INFO_V1(uniq);
PG_FUNCTION_INFO_V1(idx);
PG_FUNCTION_INFO_V1(subarray);
PG_FUNCTION_INFO_V1(intarray_push_elem);
PG_FUNCTION_INFO_V1(intarray_push_array);
PG_FUNCTION_INFO_V1(intarray_del_elem);
PG_FUNCTION_INFO_V1(intset_union_elem);
PG_FUNCTION_INFO_V1(intset_subtract);
Datum		intset(PG_FUNCTION_ARGS);
Datum		icount(PG_FUNCTION_ARGS);
Datum		sort(PG_FUNCTION_ARGS);
Datum		sort_asc(PG_FUNCTION_ARGS);
Datum		sort_desc(PG_FUNCTION_ARGS);
Datum		uniq(PG_FUNCTION_ARGS);
Datum		idx(PG_FUNCTION_ARGS);
Datum		subarray(PG_FUNCTION_ARGS);
Datum		intarray_push_elem(PG_FUNCTION_ARGS);
Datum		intarray_push_array(PG_FUNCTION_ARGS);
Datum		intarray_del_elem(PG_FUNCTION_ARGS);
Datum		intset_union_elem(PG_FUNCTION_ARGS);
Datum		intset_subtract(PG_FUNCTION_ARGS);

static int32
intarray_match_first(ArrayType *a, int32 elem)
{
	int32	   *aa,
				c,
				i;

	c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
	aa = ARRPTR(a);
	for (i = 0; i < c; i++)
		if (aa[i] == elem)
			return (i + 1);
	return 0;
}

static ArrayType *
intarray_add_elem(ArrayType *a, int32 elem)
{
	ArrayType  *result;
	int32	   *r;
	int32		c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);

	result = new_intArrayType(c + 1);
	r = ARRPTR(result);
	if (c > 0)
		memcpy(r, ARRPTR(a), c * sizeof(int32));
	r[c] = elem;
	return result;
}

static ArrayType *
intarray_concat_arrays(ArrayType *a, ArrayType *b)
{
	ArrayType  *result;
	int32		ac = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
	int32		bc = (ARRISVOID(b)) ? 0 : ARRNELEMS(b);

	result = new_intArrayType(ac + bc);
	if (ac)
		memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
	if (bc)
		memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
	return result;
}

static ArrayType *
int_to_intset(int32 n)
{
	ArrayType  *result;
	int32	   *aa;

	result = new_intArrayType(1);
	aa = ARRPTR(result);
	aa[0] = n;
	return result;
}

static int
compASC(const void *a, const void *b)
{
	if (*(int4 *) a == *(int4 *) b)
		return 0;
	return (*(int4 *) a > *(int4 *) b) ? 1 : -1;
}

static int
compDESC(const void *a, const void *b)
{
	if (*(int4 *) a == *(int4 *) b)
		return 0;
	return (*(int4 *) a < *(int4 *) b) ? 1 : -1;
}

#define QSORT(a, direction)						\
if (ARRNELEMS(a) > 1)						\
	qsort((void*)ARRPTR(a), ARRNELEMS(a),sizeof(int4),	\
		(direction) ? compASC : compDESC )

#define UNIX_UNIQ(a) a = resize_intArrayType(a, unix_uniq(ARRPTR(a), ARRNELEMS(a)))

static int32
unix_uniq(int32 *array, int32 count)
{
	register int32 i,
				k = 0;

	for (i = 1; i < count; i++)
		if (array[k] != array[i])
		{
			k++;
			if (i > k)
				array[k] = array[i];
		}
	return (k + 1);
}

Datum
intset(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(int_to_intset(PG_GETARG_INT32(0)));
}

Datum
icount(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	int32		count = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);

	PG_FREE_IF_COPY(a, 0);
	PG_RETURN_INT32(count);
}

Datum
sort(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	text	   *dirstr = (fcinfo->nargs == 2) ? PG_GETARG_TEXT_P(1) : NULL;
	int32		dc = (dirstr) ? VARSIZE(dirstr) - VARHDRSZ : 0;
	char	   *d = (dirstr) ? VARDATA(dirstr) : NULL;
	int			dir = -1;

	if (ARRISVOID(a) || ARRNELEMS(a) < 2)
		PG_RETURN_POINTER(a);

	if (dirstr == NULL || (dc == 3
						   && (d[0] == 'A' || d[0] == 'a')
						   && (d[1] == 'S' || d[1] == 's')
						   && (d[2] == 'C' || d[2] == 'c')))
		dir = 1;
	else if (dc == 4
			 && (d[0] == 'D' || d[0] == 'd')
			 && (d[1] == 'E' || d[1] == 'e')
			 && (d[2] == 'S' || d[2] == 's')
			 && (d[3] == 'C' || d[3] == 'c'))
		dir = 0;
	if (dir == -1)
		elog(ERROR, "Invalid second parameter in function sort. It must be 'ASC' or 'DESC'.");
	QSORT(a, dir);
	PG_RETURN_POINTER(a);
}

Datum
sort_asc(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));

	if (ARRISVOID(a))
		PG_RETURN_POINTER(a);
	QSORT(a, 1);
	PG_RETURN_POINTER(a);
}

Datum
sort_desc(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));

	if (ARRISVOID(a))
		PG_RETURN_POINTER(a);
	QSORT(a, 0);
	PG_RETURN_POINTER(a);
}

Datum
uniq(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));

	if (ARRISVOID(a) || ARRNELEMS(a) < 2)
		PG_RETURN_POINTER(a);
	UNIX_UNIQ(a);
	PG_RETURN_POINTER(a);
}

Datum
idx(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	int32		result = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);

	if (result)
		result = intarray_match_first(a, PG_GETARG_INT32(1));
	PG_FREE_IF_COPY(a, 0);
	PG_RETURN_INT32(result);
}

Datum
subarray(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	ArrayType  *result;
	int32		start = (PG_GETARG_INT32(1) > 0) ? PG_GETARG_INT32(1) - 1 : PG_GETARG_INT32(1);
	int32		len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
	int32		end = 0;
	int32		c;

	if (ARRISVOID(a))
	{
		PG_FREE_IF_COPY(a, 0);
		PG_RETURN_POINTER(new_intArrayType(0));
	}

	c = ARRNELEMS(a);

	if (start < 0)
		start = c + start;

	if (len < 0)
		end = c + len;
	else if (len == 0)
		end = c;
	else
		end = start + len;

	if (end > c)
		end = c;

	if (start < 0)
		start = 0;

	if (start >= end || end <= 0)
	{
		PG_FREE_IF_COPY(a, 0);
		PG_RETURN_POINTER(new_intArrayType(0));
	}


	result = new_intArrayType(end - start);
	if (end - start > 0)
		memcpy(ARRPTR(result), ARRPTR(a) + start, (end - start) * sizeof(int32));
	PG_FREE_IF_COPY(a, 0);
	PG_RETURN_POINTER(result);
}

Datum
intarray_push_elem(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	ArrayType  *result;

	result = intarray_add_elem(a, PG_GETARG_INT32(1));
	PG_FREE_IF_COPY(a, 0);
	PG_RETURN_POINTER(result);
}

Datum
intarray_push_array(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
	ArrayType  *result;

	result = intarray_concat_arrays(a, b);
	PG_FREE_IF_COPY(a, 0);
	PG_FREE_IF_COPY(b, 1);
	PG_RETURN_POINTER(result);
}

Datum
intarray_del_elem(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	int32		c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
	int32	   *aa = ARRPTR(a);
	int32		n = 0,
				i;
	int32		elem = PG_GETARG_INT32(1);

	for (i = 0; i < c; i++)
		if (aa[i] != elem)
		{
			if (i > n)
				aa[n++] = aa[i];
			else
				n++;
		}
	if (c > 0)
		a = resize_intArrayType(a, n);
	PG_RETURN_POINTER(a);
}

Datum
intset_union_elem(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
	ArrayType  *result;

	result = intarray_add_elem(a, PG_GETARG_INT32(1));
	PG_FREE_IF_COPY(a, 0);
	QSORT(result, 1);
	UNIX_UNIQ(result);
	PG_RETURN_POINTER(result);
}

Datum
intset_subtract(PG_FUNCTION_ARGS)
{
	ArrayType  *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
	ArrayType  *result;
	int32		ca = ARRISVOID(a);
	int32		cb = ARRISVOID(b);
	int32	   *aa,
			   *bb,
			   *r;
	int32		n = 0,
				i = 0,
				k = 0;

	QSORT(a, 1);
	UNIX_UNIQ(a);
	ca = ARRNELEMS(a);
	QSORT(b, 1);
	UNIX_UNIQ(b);
	cb = ARRNELEMS(b);
	result = new_intArrayType(ca);
	aa = ARRPTR(a);
	bb = ARRPTR(b);
	r = ARRPTR(result);
	while (i < ca)
	{
		if (k == cb || aa[i] < bb[k])
			r[n++] = aa[i++];
		else if (aa[i] == bb[k])
		{
			i++;
			k++;
		}
		else
			k++;
	}
	result = resize_intArrayType(result, n);
	pfree(a);
	pfree(b);
	PG_RETURN_POINTER(result);
}