1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
// FILE: table1.h (part of the namespace main_savitch_12A)
// TEMPLATE CLASS PROVIDED: table<RecordType> (a table of records with keys).
// This class is a container template class for a table of records.
// The template parameter, RecordType, is the data type of the records in the
// table. It may be any of the bulit-in C++ types (int, char, etc.), or a
// class with a default constructor, an assignment operator, and an integer
// member variable called key.
//
// MEMBER CONSTANT for the table<RecordType> class:
// static const size_type CAPACITY = ________
// table<RecordType>::CAPACITY is the maximum number of records held by a table.
//
// CONSTRUCTOR for the table<RecordType> template class:
// table( )
// Postcondition: The table has been initialized as an empty table.
//
// MODIFICATION MEMBER FUNCTIONS for the table<RecordType> class:
// void insert(const RecordType& entry)
// Precondition: entry.key >= 0. Also if entry.key is not already a key in
// the table, then the table has space for another record
// (i.e., size( ) < CAPACITY).
// Postcondition: If the table already had a record with a key equal to
// entry.key, then that record is replaced by entry. Otherwise, entry has
// been added as a new record of the table.
//
// void remove(int key)
// Postcondition: If a record was in the table with the specified key, then
// that record has been removed; otherwise the table is unchanged.
//
// CONSTANT MEMBER FUNCTIONS for the table<RecordType> class:
// bool is_present(const Item& target) const
// Postcondition: The return value is true if there is a record in the
// table with the specified key. Otherwise, the return value is false.
//
// void find(int key, bool& found, RecordType& result) const
// Postcondition: If a record is in the table with the specified key, then
// found is true and result is set to a copy of the record with that key.
// Otherwise found is false and the result contains garbage.
//
// size_type size( ) const
// Postcondition: Return value is the total number of records in the
// table.
//
// VALUE SEMANTICS for the table<RecordType> template class:
// Assignments and the copy constructor may be used with table objects.
#ifndef TABLE1_H
#define TABLE1_H
#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;
};
}
#include "table1.template" // Include the implementation.
#endif
|