/*
This file implements an integer set using a hashtable.
Copyright (C) 2004 The University of Texas at Austin

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_hashtable.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<assert.h>

static short EMPTY_ENTRY = -1;
static short REMOVED_ENTRY = -2;

int global_probelength = 0;

void get_entries_int_set(int_set ht, int* entries){
  
  int i, j;

  j = 0;
  assert(ht && entries);
  for(i=0;i<ht->size_;i++)
    if(ht->table_[i]!=EMPTY_ENTRY && ht->table_[i]!=REMOVED_ENTRY)
      entries[j++] = ht->table_[i];
}
  
void assign_int_set(int_set ht1, int_set ht2){
  
  int i;

  assert(ht1 && ht2);

  ht1->nelements = ht2->nelements;
  ht1->size_ = ht2->size_;
  ht1->a1_ = ht2->a1_;
  ht1->a2_ = ht2->a2_;
  ht1->b1_ = ht2->b1_;
  ht1->b2_ = ht2->b2_;
  ht1->probelength_ = ht2->probelength_;
  ht1->h_ = ht2->h_;
  
  assert(ht1->table_);
  free(ht1->table_);

  ht1->table_ = (int*) malloc(ht1->size_ * sizeof(int));
  for(i=0;i<ht1->size_;i++)
    ht1->table_[i] = ht2->table_[i];
}

short equal_int_set(int_set ht1, int_set ht2){
  
  int i; int* ht1_entries; int* ht2_entries;

  assert(ht1 && ht2);
  if(ht1->nelements != ht2->nelements) return 0;

  ht1_entries = (int*) malloc(ht1->nelements * sizeof(int));
  get_entries_int_set(ht1, ht1_entries);

  for(i=0; i < ht1->nelements; i++)
    if(lookup_int_set(ht2, ht1_entries[i]) == EMPTY_ENTRY){
      free(ht1_entries);
      return 0;
      /*printf("probelength=%d\n", ht2->probelength_);*/
    }
  
  free(ht1_entries);
  ht2_entries = (int*) malloc(ht2->nelements * sizeof(int));
  get_entries_int_set(ht2, ht2_entries);
  
  for(i=0; i < ht2->nelements; i++)
    if(lookup_int_set(ht1, ht2_entries[i]) == EMPTY_ENTRY){
      free(ht2_entries);
      return 0;
      /*printf("probelength=%d\n", ht1->probelength_);*/
    }
  
  free(ht2_entries);
  return 1;
}

int_set diff_int_set(int_set ht1, int_set ht2){
  
  int i; int* ht1_entries; int_set result;

  assert(ht1 && ht2);

  global_probelength = 0;
  result=new_int_set(8);

  if(ht1->nelements == 0) return result;
  if(ht2->nelements == 0) { assign_int_set(result, ht1); return result; }
  
  ht1_entries = (int*) malloc(ht1->nelements * sizeof(int));
  get_entries_int_set(ht1, ht1_entries);
  for(i=0; i < ht1->nelements; i++) 
    if(lookup_int_set(ht2, ht1_entries[i]) == EMPTY_ENTRY){
      global_probelength += ht2->probelength_;
      insert_int_set(result, ht1_entries[i]);
      global_probelength += result->probelength_;
    }
    else 
      global_probelength += ht2->probelength_;
    
  free(ht1_entries);

  return result;
}

int_set intersect_int_set(int_set ht1, int_set ht2){
  
  int i; int* ht1_entries; int* ht2_entries;
  int_set result;

  assert(ht1 && ht2);

  result=new_int_set(8);

  if(ht1->nelements == 0 || ht2->nelements == 0) return result;
  
  ht1_entries = (int*) malloc(ht1->nelements * sizeof(int));
  get_entries_int_set(ht1, ht1_entries);
  for(i=0; i < ht1->nelements; i++) 
    if(lookup_int_set(ht2, ht1_entries[i]) != EMPTY_ENTRY)
      insert_int_set(result, ht1_entries[i]);
  free(ht1_entries);

  ht2_entries = (int*) malloc(ht2->nelements * sizeof(int));
  get_entries_int_set(ht2, ht2_entries);
  for(i=0; i < ht2->nelements; i++)
    if(lookup_int_set(ht1, ht2_entries[i]) != EMPTY_ENTRY)
      insert_int_set(result, ht2_entries[i]);
  free(ht2_entries);

  return result;
}

int_set union_int_set(int_set ht1, int_set ht2){
  
  int i; int* ht1_entries; int* ht2_entries;
  int_set result;

  assert(ht1 && ht2);
  
  global_probelength = 0;
  result=new_int_set(8);

  if(ht1->nelements == 0){
    assign_int_set(result, ht2);
    return result;
  }
  else if(ht2->nelements == 0){
    assign_int_set(result, ht1);
    return result;
  }
  
  ht1_entries = (int*) malloc(ht1->nelements * sizeof(int));
  get_entries_int_set(ht1, ht1_entries);
  for(i=0; i < ht1->nelements; i++){
    insert_int_set(result, ht1_entries[i]);
    global_probelength += result->probelength_;
  }
  free(ht1_entries);

  ht2_entries = (int*) malloc(ht2->nelements * sizeof(int));
  get_entries_int_set(ht2, ht2_entries);
  for(i=0; i < ht2->nelements; i++){
    insert_int_set(result, ht2_entries[i]);
    global_probelength += result->probelength_;
  }
  free(ht2_entries);

  return result;
}

short subseteq_int_set(int_set ht1, int_set ht2){
  
  int i; int* ht1_entries;

  assert(ht1 && ht2);
  if(ht1->nelements > ht2->nelements) return 0;
  
  ht1_entries = (int*) malloc(ht1->nelements * sizeof(int));
  get_entries_int_set(ht1, ht1_entries);

  for(i=0; i < ht1->nelements; i++)
    if(lookup_int_set(ht2, ht1_entries[i]) == EMPTY_ENTRY){
      free(ht1_entries);
      return 0;
      /*printf("probelength=%d\n", ht2->probelength_);*/
    }

  free(ht1_entries);
  return 1;
}

void print_int_set(int_set ht){
  int i = 0;
  for(i=0; i < ht->size_; i++)
    if(ht->table_[i]!=EMPTY_ENTRY) printf(" %d", ht->table_[i]);
}

int probelength_int_set(int_set ht){
  assert(ht); return ht->probelength_;
}

void del_int_set(int_set ht){
  assert(ht);
  free(ht->table_);
  free(ht);
}

int_set new_int_set(long sz){
  int i; double x; double lgsz, lg2;
  int_set ht;

  ht = (int_set) malloc(sizeof(struct int_set_struct));
  
  /*setting int_set to be size of power of 2*/
  /*this is required so that proper open addressing can occur,*/
  /*i.e. eventually every entry in the table is considered*/
  lgsz = log(sz); lg2 = log(2);
  if(floor(lgsz/lg2) != ceil(lgsz/lg2)){
    /* which means that sz is not a power of 2*/
    x = ceil(lgsz/lg2);
    sz = pow(2, x+1);
  }

  ht->size_ = sz;
  ht->nelements = 0;

  /* allocate memory for table*/
  ht->table_ = (int*) malloc(ht->size_*sizeof(int));
    
  /* initialize to -1, because 0 is a possible member of the set*/
  for(i = 0; i < ht->size_; i++) ht->table_[i] = EMPTY_ENTRY; 
  ht->P_ = 2147483647; /* initialize P (large prime)*/
  ht->probelength_ = 0;
  
  /*initialize hash1 and hash2 variables*/
  srand(time(0));
  ht->a1_ = rand() * (ht->P_ - 1) + 1;
  ht->a2_ = rand() * (ht->P_ - 1) + 1;
  ht->b1_ = rand() * ht->P_;
  ht->b2_ = rand() * ht->P_;

  return ht;
}

/* This is called before hash1 and hash2. It sets the 
   value of h_ to be used by hash1 and hash2 and saves excessive calls
   to the hash function.*/
unsigned long int_set_hash(int_set ht, int key) {

  assert(ht); assert(key >= 0);

  key += (key << 12);  
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);

  ht->h_ = key;
  return key;
}

unsigned long int_set_hash1(int_set ht) {
  return ((((ht->a1_ * ht->h_) + ht->b1_) % ht->P_) % ht->size_) ;
}

unsigned long int_set_hash2(int_set ht) {
  return ((((ht->a2_ * ht->h_ + ht->b2_) % ht->P_) % (ht->size_ - 3)) | 1);
}

void insert_int_set(int_set ht, int key) {
  unsigned long i;
  int h1, h2;

  assert(ht);
  assert(key >= 0);

  int_set_hash(ht, key);
  h1 = int_set_hash1(ht);
  h2 = int_set_hash2(ht);
  
  ht->probelength_ = 0;
  
  for(i = h1; ht->table_[i] != EMPTY_ENTRY && ht->table_[i] != REMOVED_ENTRY; i = (i + h2) % ht->size_){
    ht->probelength_++;
    if(ht->table_[i] == key) return;
  }
  
  ht->table_[i] = key;
  ht->nelements++;

  if(2*ht->nelements > ht->size_) { 
    resize_int_set(ht, 2*ht->size_);
    /*verifying*/
    /*
    for(i=0; i < ht->size_; i++)
      if(ht->table_[i] != EMPTY_ENTRY)
	assert(lookup_int_set(ht, ht->table_[i])!=EMPTY_ENTRY);
    printf("new size=%d, new elements=%d\n", ht->size_,ht->nelements);
    */
    /**********/
  }

  return;
}

/* assert: key must be present in table*/
void remove_int_set(int_set ht, int key) {
  unsigned long i;
  int h1, h2;

  assert(ht);
  assert(key >= 0);
  assert(lookup_int_set(ht, key) != EMPTY_ENTRY);

  int_set_hash(ht, key);
  h1 = int_set_hash1(ht);
  h2 = int_set_hash2(ht);

  ht->probelength_ = 0;
  
  for(i = h1; ht->table_[i] != EMPTY_ENTRY; i = (i + h2) % ht->size_){
    /* find the key first */
    ht->probelength_++;
    if(ht->table_[i] == key) {
      /* if found mark this entry as removed and not empty */
      ht->nelements--;
      ht->table_[i] = REMOVED_ENTRY;

      if(ht->nelements < ht->size_/4) 
	{
	  resize_int_set(ht, ht->size_/2);
	}
      return;
    }
  }
  assert(0);
  return;
}

void resize_int_set(int_set ht, int newsize){
  
  int* newtable;
  unsigned long i, j;
  int h1, h2, key, oldsize;
  
  assert(ht);
  oldsize = ht->size_;

  newtable=(int*)malloc(newsize*sizeof(int));

  for(i=0; i < newsize; i++) newtable[i]=EMPTY_ENTRY;
  ht->size_ = newsize;
 
  for(i=0; i < oldsize; i++)
    /*for each defined key*/
    if(ht->table_[i] != EMPTY_ENTRY && ht->table_[i] != REMOVED_ENTRY){
      /*hash it*/
      key = ht->table_[i];
      int_set_hash(ht, key); h1=int_set_hash1(ht); h2=int_set_hash2(ht);
      
      /*and then insert it into newtable*/
      for(j = h1; newtable[j] != EMPTY_ENTRY && newtable[j] != REMOVED_ENTRY; j = (j + h2) % ht->size_){
	ht->probelength_++;
	if(newtable[j] == key) break;
      }
      newtable[j] = key;
    }
  
  /*printf("total resize problength=%d\n", ht->probelength_);*/
  free(ht->table_);
  ht->table_ = newtable;
  return;
}

int choose_int_set(int_set ht){

  int i; long double min;
  min = HUGE_VAL;
  
  for(i = 0; i < ht->size_; i++)
    if(ht->table_[i] != EMPTY_ENTRY && ht->table_[i] != REMOVED_ENTRY && ht->table_[i] < min) min = ht->table_[i];
  
  return min;
}

int size_int_set(int_set ht){

  return ht->nelements;

}

int member_int_set(int_set ht, int key){
  if(lookup_int_set(ht, key) == EMPTY_ENTRY) return 0;
  else return 1;
}
  
int lookup_int_set(int_set ht, int key) {
  unsigned long i;
  int h1, h2;
  
  assert(ht); assert(key >= 0);

  int_set_hash(ht, key);
  h1 = int_set_hash1(ht);
  h2 = int_set_hash2(ht);
  
  ht->probelength_ = 0;

  for(i = h1; ht->table_[i] != EMPTY_ENTRY; i = (i + h2) % ht->size_) {
    ht->probelength_++;
    if(ht->table_[i] == key) return key;
  }
  
  return EMPTY_ENTRY;
}

/*verifying*/
/*
  printf("new table size =%d\n", ht->size_);
  for(i=0; i < ht->size_; i++)
  if(ht->table_[i] != EMPTY_ENTRY){
  printf("looking for %d\n", ht->table_[i]);
  assert(lookup_int_set(ht, ht->table_[i])!=EMPTY_ENTRY);
  }
  printf("new size=%d, new elements=%d\n", ht->size_,ht->nelements);
*/
/**********/