/*
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