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 /chapter11 | |
| download | dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.tar.xz dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.zip | |
Diffstat (limited to 'chapter11')
| -rw-r--r-- | chapter11/set.h | 94 |
1 files changed, 94 insertions, 0 deletions
diff --git a/chapter11/set.h b/chapter11/set.h new file mode 100644 index 0000000..f65cacd --- /dev/null +++ b/chapter11/set.h @@ -0,0 +1,94 @@ +// FILE: set.h (part of the namespace main_savitch_11)
+// TEMPLATE CLASS PROVIDED: set<Item>
+// (a container template class for a set of items)
+//
+// TYPEDEFS for the set<Item> class:
+// set<Item>::value_type
+// set<Item>::value_type is the data type of the items in the set. It may be
+// any of the C++ built-in types (int, char, etc.), or a class with a
+// default constructor, a copy constructor, an assignment operator, and a
+// less-than operator forming a strict weak ordering.
+//
+// CONSTRUCTOR for the set<Item> class:
+// set( )
+// Postcondition: The set is empty.
+//
+// MODIFICATION MEMBER FUNCTIONS for the set<Item> class:
+// void clear( )
+// Postcondition: The set is empty.
+//
+// bool insert(const Item& entry)
+// Postcondition: If an equal entry was already in the set, the set is
+// unchanged and the return value is false. Otherwise, entry was added
+// to the set and the return value is true. This is slightly different than
+// the C++ Standard Library set (see Appendix H).
+//
+// size_t erase(const Item& target)
+// Postcondition: If target was in the set, then it has been removed from
+// the set and the return value is 1. Otherwise the set is unchanged and the
+// return value is zero.
+//
+// CONSTANT MEMBER FUNCTIONS for the Set<Item> class:
+// size_t count(const Item& target) const
+// Postcondition: Returns the number of items equal to the target
+// (either 0 or 1 for a set).
+//
+// bool empty( ) const
+// Postcondition: Returns true if the set is empty; otherwise returns false.
+//
+// VALUE SEMANTICS for the set<Item> class:
+// Assignments and the copy constructor may be used with set<Item> objects.
+//
+// DYNAMIC MEMORY USAGE by the set<Item> class:
+// If there is insufficient dynamic memory, then the following functions throw
+// bad_alloc:
+// The constructors, insert, and the assignment operator.
+
+#ifndef MAIN_SAVITCH_SET_H
+#define MAIN_SAVITCH_SET_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_11
+{
+ template <class Item>
+ class set
+ {
+ public:
+ // TYPEDEFS
+ typedef Item value_type;
+ // CONSTRUCTORS and DESTRUCTOR
+ set( );
+ set(const set& source);
+ ~set( ) { clear( ); }
+ // MODIFICATION MEMBER FUNCTIONS
+ void operator =(const set& source);
+ void clear( );
+ bool insert(const Item& entry);
+ std::size_t erase(const Item& target);
+ // CONSTANT MEMBER FUNCTIONS
+ std::size_t count(const Item& target) const;
+ bool empty( ) const { return (data_count == 0); }
+ // SUGGESTED FUNCTION FOR DEBUGGING
+ void print(int indent) const;
+ private:
+ // MEMBER CONSTANTS
+ static const std::size_t MINIMUM = 200;
+ static const std::size_t MAXIMUM = 2 * MINIMUM;
+ // MEMBER VARIABLES
+ std::size_t data_count;
+ Item data[MAXIMUM+1];
+ std::size_t child_count;
+ set *subset[MAXIMUM+2];
+ // HELPER MEMBER FUNCTIONS
+ bool is_leaf( ) const { return (child_count == 0); }
+ bool loose_insert(const Item& entry);
+ bool loose_erase(const Item& target);
+ void remove_biggest(Item& removed_entry);
+ void fix_excess(std::size_t i);
+ void fix_shortage(std::size_t i);
+ // NOTE: The implementor may want to have additional helper functions
+ };
+}
+#include "set.template" // Include the implementation.
+
+#endif
|