diff options
Diffstat (limited to 'chapter6/bag4.h')
| -rw-r--r-- | chapter6/bag4.h | 113 |
1 files changed, 113 insertions, 0 deletions
diff --git a/chapter6/bag4.h b/chapter6/bag4.h new file mode 100644 index 0000000..3dfc532 --- /dev/null +++ b/chapter6/bag4.h @@ -0,0 +1,113 @@ +// FILE: bag4.h (part of the namespace main_savitch_6A)
+// TEMPLATE CLASS PROVIDED: bag<item>
+//
+// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the bag<Item> class:
+// The template parameter, Item, is the data type of the items in the bag,
+// also defined as bag<Item>::value_type. It may be any of the C++ built-in
+// types (int, char, etc.), or a class with a default constructor, an
+// assignment operator, and operators to test for equality (x == y) and
+// non-equality (x != y). The definition bag<Item>::size_type is the data type
+// of any variable that keeps track of how many items are in a bag. The static
+// const DEFAULT_CAPACITY is the initial capacity of a bag created by the
+// default constructor.
+// NOTE:
+// Many compilers require the use of the new keyword typename before using
+// the expressions bag<Item>::value_type and bag<Item>::size_type. Otherwise
+// the compiler doesn't have enough information to realize that it is the
+// name of a data type.
+//
+// CONSTRUCTOR for the bag<Item> template class:
+// bag(size_type initial_capacity = DEFAULT_CAPACITY)
+// Postcondition: The bag is empty with an initial capacity given by the
+// parameter. The insert function will work efficiently (without allocating
+// new memory) until this capacity is reached.
+//
+// MODIFICATION MEMBER FUNCTIONS for the bag<Item> template class:
+// size_type erase(const Item& target)
+// Postcondition: All copies of target have been removed from the bag. The
+// return value is the number of copies removed (which could be zero).
+//
+// bool erase_one(const Item& target)
+// Postcondition: If target was in the bag, then one copy of target has
+// been removed; otherwise the bag is unchanged. A true return value
+// indicates that one copy was removed; false indicates that nothing was
+// removed.
+//
+// void insert(const Item& entry)
+// Postcondition: A new copy of entry has been added to the bag.
+//
+// void operator +=(const bag<Item>& addend)
+// Postcondition: Each item in addend has been added to this bag.
+//
+// void reserve(size_type new_capacity)
+// Postcondition: The bag's current capacity is changed to new_capacity
+// (but not less than the number of items currently in the bag). The insert
+// function will work efficiently without allocating new memory) until the
+// capacity is reached.
+//
+// CONSTANT MEMBER FUNCTIONS for the bag<Item> template class:
+// size_type count(const Item& target) const
+// Postcondition: Return value is number of times target is in the bag.
+//
+// Item grab( ) const
+// Precondition: size( ) > 0
+// Postcondition: The return value is a randomly selected item from the bag.
+//
+// size_type size( ) const
+// Postcondition: The return value is the total number of items in the bag.
+//
+// NONMEMBER FUNCTIONS for the bag<Item> template class:
+// template <class Item>
+// bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
+// Postcondition: The bag returned is the union of b1 and b2.
+//
+// VALUE SEMANTICS for the bag<Item> template class:
+// Assignments and the copy constructor may be used with bag objects.
+//
+// DYNAMIC MEMORY USAGE by the bag<Item> template class:
+// If there is insufficient dynamic memory, then the following functions call
+// new_handler: the constructors, resize, insert, operator += , operator +,
+// and the assignment operator.
+
+#ifndef MAIN_SAVITCH_BAG4_H
+#define MAIN_SAVITCH_BAG4_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_6A
+{
+ template <class Item>
+ class bag
+ {
+ public:
+ // TYPEDEFS and MEMBER CONSTANTS
+ typedef Item value_type;
+ typedef std::size_t size_type;
+ static const size_type DEFAULT_CAPACITY = 30;
+ // CONSTRUCTORS and DESTRUCTOR
+ bag(size_type initial_capacity = DEFAULT_CAPACITY);
+ bag(const bag& source);
+ ~bag( );
+ // MODIFICATION MEMBER FUNCTIONS
+ size_type erase(const Item& target);
+ bool erase_one(const Item& target);
+ void insert(const Item& entry);
+ void operator =(const bag& source);
+ void operator +=(const bag& addend);
+ void reserve(size_type capacity);
+ // CONSTANT MEMBER FUNCTIONS
+ size_type count(const Item& target) const;
+ Item grab( ) const;
+ size_type size( ) const { return used; }
+ private:
+ Item *data; // Pointer to partially filled dynamic array
+ size_type used; // How much of array is being used
+ size_type capacity; // Current capacity of the bag
+ };
+
+ // NONMEMBER FUNCTIONS
+ template <class Item>
+ bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2);
+}
+
+#include "bag4.template" // Include the implementation
+#endif
|