Click here to Skip to main content
14,734,748 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
#include <cstdlib>    // Provides size_t

namespace main_savitch_12A
{
    template <class RecordType>
    class table
    {
    public:
        // MEMBER CONSTANT -- See Appendix E if this fails to compile.
        static const std::size_t CAPACITY = 811;
        // CONSTRUCTOR
        table( );
        // MODIFICATION MEMBER FUNCTIONS
        void insert(const RecordType& entry);
        void remove(int key);
        // CONSTANT MEMBER FUNCTIONS
        bool is_present(int key) const;
        void find(int key, bool& found, RecordType& result) const;
        std::size_t size( ) const { return used; }
    private:
        // MEMBER CONSTANTS -- These are used in the key field of special records.
        static const int NEVER_USED = -1;
        static const int PREVIOUSLY_USED = -2;
        // MEMBER VARIABLES
        RecordType data[CAPACITY];
        std::size_t used;
        // HELPER FUNCTIONS
        std::size_t hash(int key) const;
        std::size_t next_index(std::size_t index) const;
        void find_index(int key, bool& found, std::size_t& index) const;
        bool never_used(std::size_t index) const;
        bool is_vacant(std::size_t index) const;
    };
}
<pre>// FILE: table1.template
// TEMPLATE CLASS IMPLEMENTED: table (see table1.h for documentation)
// INVARIANT for the table ADT:
//   1. The number of records in the table is in the member variable used.
//   2. The actual records of the table are stored in the array data, with
//      a maximum of CAPACITY entries. Each used spot in the array has a 
//      non-negative key. Any unused record in the array has a key field of
//      NEVER_USED (if it has never been used) or PREVIOUSLY_USED (if it once
//      was used, but is  now vacant).

#include <cassert>  // Provides assert
#include <cstdlib>  // Provides size_t

namespace main_savitch_12A
{
    template <class RecordType>
    const std::size_t table<RecordType>::CAPACITY; 

    template <class RecordType>
    const int table<RecordType>::NEVER_USED;

    template <class RecordType>
    const int table<RecordType>::PREVIOUSLY_USED;

    template <class RecordType>
    table<RecordType>::table( )
    {
        std::size_t i;

        used = 0;
        for (i = 0; i < CAPACITY; ++i)
            data[i].key = NEVER_USED;  // Indicates a spot that's never been used.
    }

    template <class RecordType>
    void table<RecordType>::insert(const RecordType& entry)
    // Library facilities used: cassert
    {
        bool already_present;   // True if entry.key is already in the table
        std::size_t index;        // data[index] is location for the new entry

        assert(entry.key >= 0);

        // Set index so that data[index] is the spot to place the new entry.
        find_index(entry.key, already_present, index);

        // If the key wasn't already there, then find the location for the new entry.
        if (!already_present)
        {
            assert(size( ) < CAPACITY);
            index = hash1(entry.key);
            while (!is_vacant(index))
                index = next_index(index);
            ++used;
        }

        data[index] = entry;
    }

    template <class RecordType>
    void table<RecordType>::remove(int key)
    // Library facilities used: cassert
    {
        bool found;        // True if key occurs somewhere in the table
        std::size_t index;   // Spot where data[index].key == key

        assert(key >= 0);

        find_index(key, found, index);
        if (found)
        {   // The key was found, so remove this record and reduce used by 1.
            data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
            --used;
        }
    }

    template <class RecordType>
    bool table<RecordType>::is_present(int key) const
    // Library facilities used: assert.h
    {
        bool found;
        std::size_t index;

        assert(key >= 0);

        find_index(key, found, index);
        return found;
    }

    template <class RecordType>
    void table<RecordType>::find(int key, bool& found, RecordType& result) const
    // Library facilities used: cassert.h
    {
        std::size_t index;

        assert(key >= 0);

        find_index(key, found, index);
        if (found)
            result = data[index];
    }

    template <class RecordType>
    inline std::size_t table<RecordType>::hash1(int key) const
    {
        hash1(key) = (key % CAPACITY);
        return hash1(key);
    }
    
    template <class RecordType>
    inline std::size_t table<RecordType>::hash2(int key) const
    {
        hash2(key) = 1 + (key % (CAPACITY - 2));
        return hash2(key);
    }

     template <class RecordType>
     inline std::size_t table<RecordType>::next_index(std::size_t index) const
     //Library facilities used: cstdlib
    {
        return (i + hash2) % CAPACITY;
    }

    template <class RecordType>
    void table<RecordType>::find_index(int key, bool& found, std::size_t& i) const
    // Library facilities used: cstdlib
    {
	std::size_t count; // Number of entries that have been examined

	count = 0;
	i = hash1(key);
	while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))
	{
	    ++count;
	    i = next_index(i);
	}
	found = (data[i].key == key);
    }

    template <class RecordType>
    inline bool table<RecordType>::never_used(std::size_t index) const
    {
	return (data[index].key == NEVER_USED);
    }
	
    template <class RecordType>
    inline bool table<RecordType>::is_vacant(std::size_t index) const
    {
	return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
    }
}


What I have tried:

I tried to edit the template file but all you need to do is edit this header file.
Posted
Updated 12-Nov-20 0:13am
v3

1 solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900