//---------------------------------------------------------------------
// File: htable.h
// Name: Sharon M. Tuttle
// last modified: 2-10-05
//
// Class name: htable
//
// Description: a simple hash table of non-negative integers
//    with a fixed capacity.
//---------------------------------------------------------------------

#ifndef HTABLE_H
#define HTABLE_H

class htable
{
    public:
        /****************************************************/
        /* TYPEDEFS and MEMBER CONSTANTS                    */
        /****************************************************/

        // capacity is a constant in this particular
        //    implementation
        //
        // better if it is prime, remember! And C. E. Radke's
        //    1970 study suggests a prime of the form 4k + 3...
        //
        static const int HTABLE_CAP = 23;

        static const int NEVER_USED = -1;
        static const int PREVIOUSLY_USED = -2;

        /*****************************************************/
        /* CONSTRUCTOR                                       */
        /*****************************************************/

        // postcondition: creates an empty htable instance with a
        //    fixed capacity
        //
        htable();

        /*************************************************************/
        /* ACCESSORS and other constant member functions (observers) */
        /*************************************************************/

        // postcondition: returns true if htable is empty, and 
        //    returns false otherwise 
        //
        bool is_empty( ) const;

        // postcondition: returns true if htable is full (if it contains 
	//    number of items equal to its capacity), and returns
        //    false otherwise
        //
        bool is_full( ) const;

        // precondition: target >= 0
        //
        // postcondition: returns true if <target> is in htable;
        //    returns false otherwise.
        //
        bool is_in_table(int target) const;

        // postcondition: returns the capacity of the htable (how many
        //    items it CAN hold)
        //
        int get_capacity( ) const;

        // postcondition: returns the number of elements currently 
        //    in the htable
        //
        int get_size( ) const;

        /*****************************************************/
        /* MODIFIERS and other modifying member functions    */
        /*****************************************************/

        // preconditions: 
        //    *   is_full() == false
        //    *   entry >= 0
        //
        // postconditions:
        //    *   if <entry> is already in htable, returns false
        //        and htable remains unchanged
        //    *   if <entry> is not already in htable, adds it to
        //        htable and returns true
        //
        bool insert(int entry);

        // precondition: entry >= 0 
        //
        // postconditions: 
        //    *   if <entry> is not in htable, returns false and
        //        htable remains unchanged
        //    *   if <entry> is in htable, removes it from htable
        //        and returns true
        //
	bool remove(int entry);

        /*****************************************************/
        /* OTHER MEMBER FUNCTIONS                            */
        /*****************************************************/

        // KLUGY --- normally would not include... BUT, for our 
        //    purposes...
        //
        // postcondition: prints the htable's contents to the
        //    screen, separating each element with at least one 
        //    blank and printing NU for never-used slots and PU 
        //    for previously-used slots. 
        //
        void print_guts();

    private:

        /*****************************************************/
        /* DATA FIELDS                                       */
        /*****************************************************/

	int table[HTABLE_CAP]; // array to hold the htable contents
	int used;	        // how much of array contains htable
			        //    elements

	/*****************************************************/
        /* PRIVATE MEMBER FUNCTIONS                          */
        /*****************************************************/

	// method: hash
	//
	// preconditions: target >= 0
	//
	// postconditions: returns an index between 0 and
        //    (HTABLE_CAP-1)
	//
	// Examples: [REPLACE these with tests suitable for YOUR hash!!!]
	//    hash(27) == 4
	//    hash(23) == 0
	//    hash(4) == 4
        //
        int hash(int target) const;

        // method: get_index - a private helper method to obtain
        //    the actual location in table of <target>
	//
	// preconditions: target >= 0
	//
	// postconditions: returns -1 if target is not in table,
        //    return index where target is located otherwise
	//
	// Examples: [REPLACE these with tests suitable for YOUR hash!]
        //    for int table[] containing target 24 at index 1,
        //        get_index(24) == 1      [test: right whr hashed]
	//    for int table[] containing target 553 at index 2, 
        //        get_index(553) == 2     [test: whr have to linear probe]
        //    for int table[] not containing target 227,
        //        get_index(227) == -1    [test: whr NOT in htable]
	//
        int get_index(int target) const;
};

#endif