diff options
| author | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
|---|---|---|
| committer | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
| commit | c1b6ffe70bd281c6c230fd63fabcaac2aff47514 (patch) | |
| tree | e8af3b1782a7cd0754590ed618fddc1bdb9b7385 /chapter12/table1.h | |
| download | dscode-main.tar.xz dscode-main.zip | |
Diffstat (limited to 'chapter12/table1.h')
| -rw-r--r-- | chapter12/table1.h | 84 |
1 files changed, 84 insertions, 0 deletions
diff --git a/chapter12/table1.h b/chapter12/table1.h new file mode 100644 index 0000000..180ede7 --- /dev/null +++ b/chapter12/table1.h @@ -0,0 +1,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
|