/*
 *  serp.c
 *  Sierpinsky
 *
 *  Created by Victor Grishchenko on 11/26/08.
 *  Copyright 2008 Delft Technical University. All rights reserved.
 *
 */

#include "serp.h"
#include <assert.h>
#include <stdio.h>

#define SRP_CAP (1<<5)
#define SERP_BASE_SIZE (1<<5)

/**	The most common m-number usage pattern is probably a|=b;
	to avoid new malloc for every bitwise operation,
	deallocated arrays are cached for reuse.  
serp*   serpool[10][SRP_CAP];
int     serpool_size [10] = {0,0,0,0,0,0,0,0,0,0};  SINFUL */

serp*	serp_new (serp n) {
	serp* ret = //serpool_size[0] ? 
        //serpool[0][--(serpool_size[0])] :
        (serp*) malloc(SERP_BASE_SIZE*sizeof(serp));
	ret[0] = n;
	ret[1] = 0;
    //ret[SERP_BASE_SIZE-1] = 0;
	return ret;
}

void    serp_free (serp* s) {
    /*int cell = 0;
    while (cell<10 && s[(SERP_BASE_SIZE<<cell)-1]) 
        cell++; // reach the size marker
    assert(cell<10);
    if (serpool_size[cell]==SRP_CAP)*/
        free(s);
    //else
      //  serpool[cell][serpool_size[cell]++] = s;
}

serp	serp_mass (serp num) {
	register serp _1 = num;
	_1|=(_1|=(_1|=(_1|=(_1|=_1>>1)>>2)>>4)>>8)>>16;
	_1>>=1;
	while (!ALL1(num))  {
		while (_1>num) { _1>>=1; }
		num -= _1;
		_1>>=1;
	}
	return num;
}


#define swapp(a, b)  { register serp* c=a; a=b; b=c; }

serp* serp_bitwise_op (serp* a, serp* b, int op) {
	serp * ret = serp_new(0);
	int l = 0;
	serp str[sizeof(serp)*32], *a_=str, *b_=str+sizeof(serp)*16, push=0;
	*b_ = *a_ = 0;
	while (*a || *b || *a_ || *b_) {
		if (!*a_ && *a) *++a_ = *a++;
		if (!*b_ && *b) *++b_ = *b++;
		if (*a_==*b_) {
			if (op&1<<3) 
				push = *b_;
			a_--, b_--;
		} else {
			if (*a_>*b_) {
				swapp(a,b);
				swapp(a_,b_);
				op = (op&1) | (op&2)<<1 | (op&4)>>1 | (op&8);
			}
			int bm = serp_mass(*b_);
			if (*b_-bm<*a_) {  // a is a subset of b; split b
				*(b_+1) = *b_ - 1;			// TODO: macros left() right() up()
				*b_ = *b_ - (bm>>1) - 1;	// TODO: split b to proper size
				b_++;
			} else { // a is unrelated to b
				if (op&1<<2)
					push = *b_;
				b_--;
			}
		}
		if (push) {
			if (ALL1(l) && l>=SERP_BASE_SIZE-1) { 
                int newsize = (l+1)<<1;
				ret = realloc(ret,sizeof(serp)*newsize);
                //ret[newsize-1] = 0; // size marker
            }
            ret[l++] = push;
			push = 0;
			serp p,m;
			while ( l>=2 &&	ALL1(ret[l-2]-ret[l-1]) &&	
				   (p=ret[l-2]+1) && (m=serp_mass(p))>1 &&	
				   p-(m>>1)-1==ret[l-1] ) 		
				ret[--l-1]=p;
		}
	}
	ret[l] = 0;
	return ret;
}

int     compare_serp (const void *a, const void *b) {
	const serp *da = (const serp *) a;
	const serp *db = (const serp *) b;
	return (*da < *db) - (*da > *db);
}

serp*	serp_or(serp* a, serp* b)	{ return serp_bitwise_op(a, b, OR); }
serp* 	serp_and(serp* a, serp* b)	{ return serp_bitwise_op(a, b, AND); }
serp* 	serp_xor(serp* a, serp* b)	{ return serp_bitwise_op(a, b, XOR); }
serp* 	serp_sub(serp* a, serp* b)	{ return serp_bitwise_op(a, b, SUB); }

void	serp_init (serp* a) {
	int l=0;
	while (a[l]) l++;
	qsort(a,l,sizeof(serp),compare_serp);
	serp* pw=a, *pr=a;
	while (*pr) {
		*pw = *pr;
		serp skipto = *pw - serp_mass(*pw);
		while (*pr>skipto) pr++;
		pw++;
	}
	*pw = *pr;
}

int		serp_in (serp a, serp* b) {
    serp* found = bsearch( &a, b, serp_length(b), sizeof(serp), compare_serp );
    return found!=NULL;
}

serp	lin2serp (int num) {
	serp mass = 1, ret = 1;
	while (num) {
		mass <<= 1;
		if (num&1)
			ret += mass - 1;
		num>>=1;
	}
	return ret;
}

int		serp_length (serp* bm) {
	int l=0;
	while (bm[l]) l++;
	return l;
}

serp	serp_left (serp a) {
	if (!a) return 0;
	int mass = serp_mass(a);
	if (mass<=1) return 0;
	int childmass = mass>>1;
	return a -1 -childmass;
}

serp	serp_right (serp a) {
	if (!a) return 0;
	int mass = serp_mass(a);
	if (mass<=1) return 0;
	return a-1;
}

int     serp_height (serp num) {
	int mass = serp_mass(num), height=0;
	while (mass>1) mass>>=1, height++;
	return height;
}

int		normal_bits () {
	int r = rand(), ret=0;
	for(int i=0; i<sizeof(int)*8; i++, r>>=1)
		ret += r&1; // CS classics
	if (ret<16)
		return (15-ret)*2;
	else
		return (ret-16)*2 + 1;
}


serp	serp_random (serp* bm) {
	if (!bm || !*bm) return 0;
	int length = serp_length(bm);
	int minheight = 32;
	for(int i=0; i<length; i++)
		if (serp_height(bm[i])<minheight)
			minheight = serp_height(bm[i]);
	int bitfilter = normal_bits()*3/8 + minheight;
	int fits = 0;
	for(int i=0; i<length; i++)
		if (serp_height(bm[i])<=bitfilter)
			fits++;
	int randserp=0;
	int r = rand() % fits;
	for(int i=0; !randserp && i<length; i++)
		if (serp_height(bm[i])<=bitfilter && r--==0)
			randserp = i;

	serp pick = bm[randserp];
	
	int path = rand();
	for(int h=serp_height(pick); h; h--, path>>=1)
		pick = path&1 ? serp_left(pick) : serp_right(pick);
	return pick;
}

int		serp_offset (serp s) {
	return 0; // FIXME
}

int		serp_size (serp s){
	return 0; // FIXME
}

serp	serp_parent (serp a) {
	int mass = serp_mass(a);
	if (serp_mass(a+1)==(mass<<1|1))
		return a+1;
	else
		return a + mass + 1;
}


int		serp_jump_distance (serp _a, serp _b) {
	int a = _a<_b?_a:_b,  b = _a<_b?_b:_a ;
	int jd = 0;
	while ( b-serp_mass(b)+1 > a ) 
		b = serp_parent(b), jd++;
	while ( a < b )
		a = serp_parent(a), jd++;
	return jd;
}


/*
int serp_intersects(serp* a, serp n) {
find:
 (1) the least number in a greater than n (possible superset)
 (2) the greatest number in a lesser than n (possible subset)
 by the means of binary search
}
*/

// IS NOT IT SIMPLER TO USE PLAIN ARRAYS?
// 1 mln packets => 4Mb of arrays for acknowledgements
// serp: up to 1 mln malloc/free, less memory
// 1000 packets is more realistic

// Serp is essentially an array of intervals. (Aligned.)