/*
This file implements a bit-vector integer set.
Copyright (C) 2004 The University of Texas at Austin

Based upon Daniel Huson's implementation. 

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/

#include<int_set.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>

static short static_inited = 0;
static IS_WORD mask[IS_WORDBITS];
static short k2word[IS_MAXBITS];
static short k2bit[IS_MAXBITS];

static int IS_MIN(int a, int b) {if(a<=b)return a;else return b;}
static int IS_MAX(int a, int b) {if(a>=b)return a;else return b;}
static void init_static();
static void resize_int_set(int_set s, const int n);
static void compute_nelements_int_set(int_set s);
static void init_int_set(int_set s, const int maxsize);
static void find_min_max(const int_set A, const int_set B, int_set* min_set, int_set* max_set);

/***** PUBLIC *****/
int_set new_int_set(const int size){
  int_set s;
  init_static();
  s = (int_set) malloc(sizeof(struct int_set_struct));
  if(size > IS_MAXBITS) printf("size=%d\n", size);
  if(size==0)
    init_int_set(s, IS_WORDBITS);
  else 
    init_int_set(s, size);
  return s;
}

void del_int_set(int_set s){
  assert(s); assert(s->data);
  free(s->data);
  free(s);
}

void get_entries_int_set(int_set s, int* entries){
  int k, i;

  assert(s); i = 0; 
  for(k = s->min; k <= s->max; k++)
    if(member_int_set(s, k)) entries[i++] = k;
}

int words_int_set(int_set s){
  return k2word[s->max] - k2word[s->min] + 1;
}

int size_int_set(int_set s){
  assert(s);
  return s->nelements;
}

/* is A a subset of B? */
short subseteq_int_set(int_set A, int_set B){
  int k;
  int nw;

  assert(A);
  assert(B);
  if(B->nelements==0) return 0;
  if(A->nelements > B->nelements) return 0;
  if(A->nelements==0) return 1;
  nw = A->words;
  /*for(k = 0; k < nw; k++){*/
  for(k = k2word[A->min]; k <= k2word[A->max]; k++){
    if(k >= B->words){
      if(A->data[k]) 
	return 0;
    }
    else if ((A->data[k] | B->data[k]) != B->data[k])
      return 0;
  }
  return 1;
}

short equal_int_set(int_set A, int_set B){
  
  int k;

  if(A->nelements != B->nelements) return 0;
  if(A->min!=B->min || A->max!=B->max) return 0;
  for(k=k2word[A->min]; k <= k2word[A->max]; k++)
    if(A->data[k] != B->data[k]) return 0;

  return 1;
}
    
/* set A = A union B */
int_set unionequal_int_set(int_set A, int_set B){
  int k; 
  
  assert(A);
  assert(B);

  /*return A if B is empty*/
  if(B->nelements==0) return A;

  if(B->bits > A->bits) resize_int_set(A, B->bits);
  
  for(k = k2word[B->min]; k <= k2word[B->max]; k++)
    A->data[k] |= B->data[k];

  /*note that A could be the empty set*/
  if(B->min<A->min || A->nelements==0)A->min=B->min; 
  if(B->max>A->max || A->nelements==0)A->max=B->max;

  compute_nelements_int_set(A);

  return A;
}

/*return A union B*/
int_set union_int_set(int_set A, int_set B){
  int k; int_set result, min_set, max_set;
  
  assert(A);
  assert(B);

  /*handle empty set cases*/
  result=new_int_set(IS_MAX(A->bits, B->bits));
  if(A->nelements==0){assign_int_set(result, B); return result; }
  else if(B->nelements==0){assign_int_set(result, A); return result; }

  find_min_max(A, B, &min_set, &max_set);
  /*nw = IS_MAX(A->words, B->words);*/

  for(k = k2word[min_set->min]; k <= k2word[max_set->max]; k++){
    if(k<A->words) result->data[k] |= A->data[k];
    if(k<B->words) result->data[k] |= B->data[k];
  }
  
  result->min=min_set->min; result->max=max_set->max;
  compute_nelements_int_set(result);
  return result;
}

/*return A intersection B*/
int_set intersect_int_set(int_set A, int_set B){
  int i, k, nw, min, max, first_defined_k, last_defined_k; 
  int_set result, min_set_, min_set, max_set;
  
  assert(A); assert(B);
  
  result=new_int_set(IS_MIN(A->bits, B->bits));

  /*handle empty set cases*/
  if(A->nelements==0 || B->nelements==0){return result;}
  
  find_min_max(A, B, &min_set, &max_set);
  nw = IS_MIN(A->words, B->words);

  if(A->words<B->words)min_set_ = A;
  else if(A->words>B->words)min_set_ = B;
  else { if(A->bits<B->bits)min_set_ = A; else min_set_ = B;}

  min = -1; max = -1; last_defined_k=-1; first_defined_k=-1;

  for(k = k2word[min_set->min]; k <= k2word[min_set_->max]; k++){
    result->data[k]=A->data[k]&B->data[k];
    if(result->data[k] && first_defined_k==-1)first_defined_k=k;
    if(result->data[k])last_defined_k=k;
  }
  if(first_defined_k!=-1){
    /*find min*/
    for(i=0;i<IS_WORDBITS;i++)
      if(result->data[first_defined_k]&mask[i]) {
	min=first_defined_k*IS_WORDBITS + i; break;
      }
    /*find max*/
    for(i = IS_WORDBITS-1; i>-1; i--)
      if(result->data[last_defined_k]&mask[i]) {
	max=last_defined_k*IS_WORDBITS + i; break;
      }
  }
  else { 
    /* this means result is empty*/
    assert(result->nelements==0);
    return result;
  }
  
  result->min=min; result->max=max;

  compute_nelements_int_set(result);
  return result;
}

void insert_int_set(int_set s, const int k){
  int p, r;
  
  assert(s);
  assert(k>=0);
  if(k>=s->bits) resize_int_set(s, 2*k);
  
  p=k2word[k];
  r=k2bit[k];
  
  if(!(s->data[p] & mask[r])){
    s->data[p]|=mask[r];
    s->nelements++;
  }
  /*set max and min of set respectively*/
  if(s->nelements==1){s->max=k;s->min=k;}
  else{ if(k > s->max)s->max=k;if(k < s->min)s->min=k;}
}

void remove_int_set(int_set s, const int k){
  int p, r;

  assert(s);
  assert(k>=0);
  if(k<s->bits){
    p=k2word[k];
    r=k2bit[k];
    
    if(s->data[p] & mask[r]){
      s->data[p] &= ~mask[r];
      s->nelements--;
    }

    if(s->nelements){
      if(k==s->min){
	/*find new min*/
	for(p=k+1;p<s->bits;p++){
	  if(member_int_set(s,p)) { s->min=p; break; }
	}
      }
      else if(k==s->max){
	/*find new max*/
	for(p=k-1;p>0;p--){
	  if(member_int_set(s,p)) { s->max=p; break; }	  
	}
      }
    }
  }
}

short member_int_set(int_set s, const int k){
  int p, r;

  assert(s);
  assert(k>=0);
  if(k>=s->bits) return 0;
  p=k2word[k]; r=k2bit[k];
  return (s->data[p]&mask[r])!=0;
}

void set2string(int_set s, char* str){
  int k; char buffer[10];
  
  assert(s);
  for(k = s->min; k <= s->max; k++)
    if(member_int_set(s,k)) {
      sprintf(buffer, "%d ", k);
      strcat(str, buffer); /*str+=strlen(buffer);*/
    }
}  

void print_int_set(int_set s){
  int k; int first=1;

  assert(s);
  if(s->nelements==0) return;
  for(k = s->min; k <= s->max; k++)
    if(member_int_set(s,k)) {
      if(first) {printf("%d", k); first=0;}
      else {printf(" %d", k);}
    }
}

void print_int_set2(int_set s, char** num_to_name){
  int k; int first=1;

  assert(s);
  if(s->nelements==0) return;
  for(k = s->min; k <= s->max; k++)
    if(member_int_set(s,k)) {
      assert(num_to_name[k]);
      if(first) {printf("%s", num_to_name[k]); first=0;}
      else {printf(" %s", num_to_name[k]);}
    }
}

int choose_int_set(int_set s){
  assert(s);
  return s->min;
}

int_set diffequal_int_set(int_set A, int_set B){
  int i, k, min, max, first_defined_k, last_defined_k;

  assert(A);
  assert(B);

  /*empty sets*/
  if(A->nelements==0 || B->nelements==0) return A;

  /*nw = IS_MIN(A->words, B->words);*/
  min = -1; max = -1; last_defined_k=-1; first_defined_k=-1;

  for(k= k2word[A->min]; k <= k2word[A->max]; k++) {
    A->data[k] -= (B->data[k] & A->data[k]);
    if(A->data[k] && first_defined_k==-1)first_defined_k=k;
    if(A->data[k])last_defined_k=k;
  }
  if(first_defined_k!=-1){
    /*find min*/
    for(i=0;i<IS_WORDBITS;i++)
      if(A->data[first_defined_k]&mask[i]) {
	min=first_defined_k*IS_WORDBITS + i; break;
      }
    /*find max*/
    for(i = IS_WORDBITS-1; i>-1; i--)
      if(A->data[last_defined_k]&mask[i]) {
	max=last_defined_k*IS_WORDBITS + i; break;
      }
  }
  else { 
    /* this means A is now empty*/
    for(k=k2word[A->min]; k <= k2word[A->max]; k++) assert(!A->data[k]);
    A->nelements=0;
    A->min=-1; A->max=-1;
    return A;
  }
  
  A->min=min; A->max=max;
  compute_nelements_int_set(A);
  return A;
}

int_set diff_int_set(int_set A, int_set B){
  
  int_set result;
  int i, k, min, max, first_defined_k, last_defined_k;

  assert(A);
  assert(B);

  result=new_int_set(A->bits);
  if(B->nelements==0) { assign_int_set(result, A); return result; }
  if(A->nelements==0) return result;

  /*nA = A->words;*/
  min = -1; max = -1; last_defined_k=-1; first_defined_k=-1;

  for(k = k2word[A->min]; k <= k2word[A->max]; k++){
    if(k < B->words)
      result->data[k]=A->data[k] - (A->data[k] & B->data[k]);
    else 
      result->data[k]=A->data[k];
    
    if(result->data[k] && first_defined_k==-1)first_defined_k=k;
    if(result->data[k])last_defined_k=k;
  }
  if(first_defined_k!=-1){
    /*find min*/
    for(i=0;i<IS_WORDBITS;i++)
      if(result->data[first_defined_k]&mask[i]) {
	min=first_defined_k*IS_WORDBITS + i; break;
      }
    /*find max*/
    for(i = IS_WORDBITS-1; i>-1; i--)
      if(result->data[last_defined_k]&mask[i]) {
	max=last_defined_k*IS_WORDBITS + i; break;
      }
  }
  else { 
    /* this means result is empty*/
    assert(result->nelements==0);
    assert(result->min==-1 && result->max==-1);
    return result;
  }
  
  result->min=min; result->max=max;
  compute_nelements_int_set(result);
  return result;
}

/*copy B into A, with B untouched*/
int_set assign_int_set(int_set A, int_set B){
  size_t bytes;

  assert(A);
  assert(B);
  A->min=B->min;
  A->max=B->max;
  A->bits=B->bits;
  A->words=B->words;
  A->nelements=B->nelements;
  bytes = IS_WORDBYTES*A->words;
  assert(A->data);
  A->data=(IS_WORD*) realloc(A->data, bytes);
  memcpy(A->data, B->data, bytes);
  return A;
}

/***** PRIVATE *****/
static void resize_int_set(int_set s, const int n){

  int old_nelements, old_words;
  size_t bytes;

  assert(s);
  assert(n>=0 && n<IS_MAXBITS);
  
  old_nelements=s->nelements;
  old_words=s->words;

  s->bits=n; 
  s->words=s->bits/IS_WORDBITS+1;
  
  bytes=IS_WORDBYTES*s->words;
  s->data=realloc(s->data,bytes);
  assert(s->data!=0);
  
  if(s->words>old_words)
    memset(&(s->data[old_words]), '\0', (s->words-old_words)*IS_WORDBYTES);
  
  if(old_nelements)
    compute_nelements_int_set(s);
  assert(old_nelements==s->nelements);
}

static void compute_nelements_int_set(int_set s){
  int k, i;

  assert(s); assert(s->min>=0 && s->max>=0);
  s->nelements=0;
  for(k = k2word[s->min]; k <= k2word[s->max]; k++)
    for(i=0;i<IS_WORDBITS;i++)
      if(s->data[k]&mask[i]) s->nelements++;
}

static void init_static(){
  int i;
  if(!static_inited){
    for(i=0;i<IS_WORDBITS;i++)
      mask[i]=(1<<i);
    for(i=0;i<IS_MAXBITS;i++){
      k2word[i]=i/IS_WORDBITS;
      k2bit[i]=i%IS_WORDBITS;
    }
    static_inited=1;
  }
}

static void init_int_set(int_set s, const int maxsize){
  size_t bytes;

  assert(s);
  assert(1<=maxsize && maxsize<=IS_MAXBITS);
  s->min=-1; s->max=-1;
  s->bits=maxsize;
  s->words=s->bits/IS_WORDBITS+1;
  s->nelements=0;
  bytes=IS_WORDBYTES*s->words;
  s->data=(IS_WORD*)malloc(bytes);
  assert(s->data!=0);
  memset(s->data,'\0',bytes);
}

static void find_min_max(const int_set A, const int_set B, 
		  int_set* min_set, int_set* max_set){
  
  assert(A->nelements>0 && B->nelements>0);

  if(A->min < B->min){
    *min_set = A;
  }
  else {
    *min_set = B;
  }
  
  if(A->max > B->max){
    *max_set = A;
  }
  else {
    *max_set = B;
  }
}