/*
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
*/
#ifndef INT_SET
#define INT_SET

typedef struct int_set_struct* int_set;

struct int_set_struct { 
  
  /*number of elements in table*/
  int nelements;

  /*size is size of table*/
  long size_;

  /*number of collisions before empty slot is found*/
  int probelength_;
  
  /* hash sets this value.  it is used in hash1 and hash2
     to avoid calling hash again (efficiency reasons) */
  unsigned long h_;
  
  /*random values used in hash functions.*/
  unsigned long a1_, a2_, b1_, b2_, P_;
  
  int* table_;
};

/*hash functions*/
unsigned long int_set_hash(int_set ht, int key);
inline unsigned long int_set_hash1 (int_set ht);
inline unsigned long int_set_hash2 (int_set ht);

/*dictionary operations*/
void  insert_int_set (int_set ht, int key);
int lookup_int_set (int_set ht, int key);
void remove_int_set (int_set ht, int key);
void resize_int_set (int_set ht, int newsize);
int probelength_int_set(int_set ht);
short equal_int_set(int_set ht1, int_set ht2);
void assign_int_set(int_set ht1, int_set ht2);
short subseteq_int_set(int_set ht1, int_set ht2);
int_set union_int_set(int_set ht1, int_set ht2);
int_set intersect_int_set(int_set ht1, int_set ht2);
int_set diff_int_set(int_set ht1, int_set ht2);
int member_int_set(int_set ht, int key);
int choose_int_set(int_set ht);
int size_int_set(int_set ht);

/*constructor*/
int_set new_int_set(long sz);             

/*destructor*/
void del_int_set(int_set ht);

/*misc*/
void print_int_set(int_set ht);

/*private*/
void get_entries_int_set(int_set ht, int* entries);

#endif