#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

#include <Judy.h>


MODULE = Bit::Vector::Judy		PACKAGE = Bit::Vector::Judy		

=pod

basic functions - just the macros from Judy1(3)

=cut

void
judy1_init(set)
	unsigned long set
    CODE:
    	set = (unsigned long)(Pvoid_t)0;
    OUTPUT:
	set

void
judy1_set(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1S(rc, set1, i);
	set = (unsigned long)set1;
    OUTPUT:
	set

void
judy1_unset(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1U(rc, set1, i);
	set = (unsigned long)set1;
    OUTPUT:
	set

int
judy1_test(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1T(rc, set1, i);
	RETVAL = rc;
    OUTPUT:
    	RETVAL

void
judy1_free(set)
	unsigned long set
    CODE:
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1FA(rc, set1);
	set = (unsigned long)set1;
    OUTPUT:
	set

unsigned long
judy1_count(set, index1, index2)
	unsigned long set
	unsigned long index1
	unsigned long index2
    CODE:
	int rc;
	Word_t i1 = index1;
	Word_t i2 = index2;
	Word_t count;
	Pvoid_t set1 = (Pvoid_t)set;
	J1C(count, set1, i1, i2);
	RETVAL = count;
    OUTPUT:
	RETVAL

unsigned long
judy1_bycount(set, nth)
	unsigned long set
	unsigned long nth
    CODE:
	int rc;
	Word_t n = nth;
	Word_t i;
	Pvoid_t set1 = (Pvoid_t)set;
	J1BC(rc, set1, n, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
	RETVAL

unsigned long
judy1_memused(set)
	unsigned long set
    CODE:
	Word_t rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1MU(rc, set1);
	RETVAL = rc;
    OUTPUT:
	RETVAL

unsigned long
judy1_first(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1F(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

unsigned long
judy1_next(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1N(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL


unsigned long
judy1_last(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1L(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

unsigned long
judy1_prev(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1P(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

unsigned long
judy1_first_empty(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1FE(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

unsigned long
judy1_next_empty(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1NE(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL


unsigned long
judy1_last_empty(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1LE(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

unsigned long
judy1_prev_empty(set, index)
	unsigned long set
	unsigned long index
    CODE:
	Word_t i = index;
	int rc;
	Pvoid_t set1 = (Pvoid_t)set;
	J1PE(rc, set1, i);
	if (!rc) XSRETURN_UNDEF;
	RETVAL = i;
    OUTPUT:
    	RETVAL

=pod

Some operations on vectors

=cut

unsigned long 
judy1_clone(set)
	unsigned long set
    CODE:
	Pvoid_t set1 = (Pvoid_t)set;
	Pvoid_t setr = NULL;
	Word_t i1 = 0;
	int rc1;
	J1F(rc1, set1, i1);
	while (rc1) {
	    int rcr;
	    J1S(rcr, setr, i1);
	    J1N(rc1, set1, i1);
	}
	RETVAL = (unsigned long)setr;
    OUTPUT:
    	RETVAL


unsigned long 
judy1_and(set1, set2)
	unsigned long set1
	unsigned long set2
    CODE:
	Pvoid_t s1 = (Pvoid_t)set1;
	Pvoid_t s2 = (Pvoid_t)set2;
	Pvoid_t r = NULL;
	Word_t i1 = 0, i2 = 0;
	int rc1, rc2;

	J1F(rc1, s1, i1);
	J1F(rc2, s2, i2);
	while (rc1 && rc2) {
	    if (i1 == i2) {
		int rc; 
		J1S(rc, r, i1);
		J1N(rc1, s1, i1);
		J1N(rc2, s2, i2);
	    } else if (i1 > i2) {
		i2 = i1;
		J1F(rc2, s2, i2);
	    } else {
		i1 = i2;
		J1F(rc1, s1, i1);
	    }
	}
	RETVAL = (unsigned long)r;
    OUTPUT:
    	RETVAL

unsigned long 
judy1_or(set1, set2)
	unsigned long set1
	unsigned long set2
    CODE:
	Pvoid_t s1 = (Pvoid_t)set1;
	Pvoid_t s2 = (Pvoid_t)set2;
	Pvoid_t r = NULL;
	Word_t i1 = 0, i2 = 0;
	int rc1, rc2;

	J1F(rc1, s1, i1);
	while (rc1) {
	    int rcr;
	    J1S(rcr, r,  i1);
	    J1N(rc1, s1, i1);
	}
	J1F(rc2, s2, i2);
	while (rc2) {
	    int rcr;
	    J1S(rcr, r,  i2);
	    J1N(rc2, s2, i2);
	}
	RETVAL = (unsigned long)r;
    OUTPUT:
    	RETVAL

=pod

=head2 judy1_assign_or

set1 |= set2

=cut

unsigned long 
judy1_assign_or(set1, set2)
	unsigned long set1
	unsigned long set2
    CODE:
	Pvoid_t s1 = (Pvoid_t)set1;
	Pvoid_t s2 = (Pvoid_t)set2;
	Pvoid_t r = NULL;
	Word_t i1 = 0, i2 = 0;
	int rc1, rc2;

	J1F(rc2, s2, i2);
	while (rc2) {
	    int rcr;
	    J1S(rcr, s1, i2);
	    J1N(rc2, s2, i2);
	}
	set1 = (unsigned long)s1;
    OUTPUT:
    	set1

=pod

=head2 judy1_andnot

set1 &= ~set2

=cut

unsigned long 
judy1_assign_andnot(set1, set2)
	unsigned long set1
	unsigned long set2
    CODE:
	Pvoid_t s1 = (Pvoid_t)set1;
	Pvoid_t s2 = (Pvoid_t)set2;
	Pvoid_t r = NULL;
	Word_t i1 = 0, i2 = 0;
	int rc1, rc2;

	J1F(rc2, s2, i2);
	while (rc2) {
	    int rcr;
	    J1U(rcr, s1, i2);
	    J1N(rc2, s2, i2);
	}
	set1 = (unsigned long)s1;
    OUTPUT:
    	set1

=pod

=head2 judy1_assign_and

set1 &= set2

=cut

unsigned long 
judy1_assign_and(set1, set2)
	unsigned long set1
	unsigned long set2
    CODE:
	Pvoid_t s1 = (Pvoid_t)set1;
	Pvoid_t s2 = (Pvoid_t)set2;
	Pvoid_t r = NULL;
	Word_t i1 = 0, i2 = 0;
	int rc1, rc2;

	J1F(rc1, s1, i1);
	J1F(rc2, s2, i2);
	while (rc1 && rc2) {
	    if (i1 == i2) {
		int rc; 
		J1S(rc, r, i1);
		J1N(rc1, s1, i1);
		J1N(rc2, s2, i2);
	    } else if (i1 > i2) {
		i2 = i1;
		J1F(rc2, s2, i2);
	    } else {
		i1 = i2;
		J1F(rc1, s1, i1);
	    }
	}
	set1 = (unsigned long)r;
    OUTPUT:
    	set1

=pod 

I/O

=cut

SV *
judy1_freeze(set)
	unsigned long set
    CODE:
	Pvoid_t s1 = (Pvoid_t)set;
	Word_t i0 = 0;
	Word_t i1 = 0;
	int rc1;

	size_t s = 16;
	size_t o = 0;
	RETVAL = newSVpvn("", 0);

	J1F(rc1, s1, i1);
	while(rc1) {
	    Word_t d = i1 - i0;
	    unsigned char buf[10];	/* 7 * 10 >= 64 bits */
	    unsigned char *p =buf + 10-1;
	    *p = d & 0x7F;
	    for (;;) {
		d >>= 7;
		if (!d) break;
		*--p = d & 0x7F | 0x80;
	    }
	    sv_catpvn(RETVAL, p, buf + 10 - p);
	    /*
		  void    sv_catpvn(SV* sv, const char* ptr, STRLEN len)
		  char*   sv_grow(SV* sv, STRLEN newlen)
	          void    sv_insert(SV* bigsv, STRLEN offset, STRLEN len, char* little, STRLEN littlelen)
	     */
	    i0 = i1;
	    J1N(rc1, s1, i1);
	}

    OUTPUT:
    	RETVAL

void
judy1_thaw(unsigned long set, char *str, unsigned long length(str))
    CODE:
	Pvoid_t s1 = (Pvoid_t)set;
	Word_t i = 0;
	int rc;

	unsigned char *p = str;
	unsigned char *pe = str + XSauto_length_of_str;
	Word_t d = 0;
	while (p < pe) {
	    d = (d << 7) | (*p & 0x7F);
	    if (!(*p & 0x80)) {
		i += d;
		J1S(rc, s1, i);
		d = 0;
	    }
	    p++;
	}
	set = (unsigned long)s1;
    OUTPUT:
    	set