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 /chapter6 | |
| download | dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.tar.xz dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.zip | |
Diffstat (limited to 'chapter6')
| -rw-r--r-- | chapter6/author.cxx | 63 | ||||
| -rw-r--r-- | chapter6/author.exe | bin | 0 -> 109616 bytes | |||
| -rw-r--r-- | chapter6/author.o | bin | 0 -> 79390 bytes | |||
| -rw-r--r-- | chapter6/bag4.h | 113 | ||||
| -rw-r--r-- | chapter6/bag4.template | 194 | ||||
| -rw-r--r-- | chapter6/bag4demo.cxx | 64 | ||||
| -rw-r--r-- | chapter6/bag5.h | 128 | ||||
| -rw-r--r-- | chapter6/bag5.template | 164 | ||||
| -rw-r--r-- | chapter6/maximal.cxx | 36 | ||||
| -rw-r--r-- | chapter6/maximal.exe | bin | 0 -> 95225 bytes | |||
| -rw-r--r-- | chapter6/maximal.o | bin | 0 -> 65610 bytes | |||
| -rw-r--r-- | chapter6/node2.h | 204 | ||||
| -rw-r--r-- | chapter6/node2.template | 128 |
13 files changed, 1094 insertions, 0 deletions
diff --git a/chapter6/author.cxx b/chapter6/author.cxx new file mode 100644 index 0000000..04156a1 --- /dev/null +++ b/chapter6/author.cxx @@ -0,0 +1,63 @@ +// FILE: author.cxx
+// A demonstration program showing how the bag template class is used.
+// The program reads some words into bags of Strings, and some numbers into
+// a bag of integers. Then a silly story is written using these words.
+
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <string> // Provides string class
+#include "bag4.h" // Provides the bag template class
+using namespace std;
+using namespace main_savitch_6A;
+
+const int ITEMS_PER_BAG = 4; // Number of items to put into each bag
+const int MANY_SENTENCES = 3; // Number of sentences in the silly story
+
+// PROTOTYPE for a function used by this demonstration program
+template <class Item, class SizeType, class MessageType>
+void get_items(bag<Item>& collection, SizeType n, MessageType description)
+// Postcondition: The string description has been written as a prompt to the
+// screen. Then n items have been read from cin and added to the collection.
+// Library facilities used: iostream, bag4.h
+{
+ Item user_input; // An item typed by the program's user
+ SizeType i;
+
+ cout << "Please type " << n << " " << description;
+ cout << ", separated by spaces.\n";
+ cout << "Press the <return> key after the final entry:\n";
+ for (i = 1; i <= n; ++i)
+ {
+ cin >> user_input;
+ collection.insert(user_input);
+ }
+ cout << endl;
+}
+
+int main( )
+{
+ bag<string> adjectives; // Contains adjectives typed by user
+ bag<int> ages; // Contains ages in the teens typed by user
+ bag<string> names; // Contains names typed by user
+ int line_number; // Number of the output line
+
+ // Fill the three bags with items typed by the program's user.
+ cout << "Help me write a story.\n";
+ get_items(adjectives, ITEMS_PER_BAG, "adjectives that describe a mood");
+ get_items(ages, ITEMS_PER_BAG, "integers in the teens");
+ get_items(names, ITEMS_PER_BAG, "first names");
+ cout << "Thank you for your kind assistance.\n\n";
+
+ // Use the items to write a silly story.
+ cout << "LIFE\n";
+ cout << "by A. Computer\n";
+ for (line_number = 1; line_number <= MANY_SENTENCES; ++line_number)
+ cout << names.grab( ) << " was only "
+ << ages.grab( ) << " years old, but he/she was "
+ << adjectives.grab( ) << ".\n";
+ cout << "Life is " << adjectives.grab( ) << ".\n";
+ cout << "The (" << adjectives.grab( ) << ") end\n";
+
+ return EXIT_SUCCESS;
+}
+
diff --git a/chapter6/author.exe b/chapter6/author.exe Binary files differnew file mode 100644 index 0000000..2cb1e66 --- /dev/null +++ b/chapter6/author.exe diff --git a/chapter6/author.o b/chapter6/author.o Binary files differnew file mode 100644 index 0000000..c372ee6 --- /dev/null +++ b/chapter6/author.o 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
diff --git a/chapter6/bag4.template b/chapter6/bag4.template new file mode 100644 index 0000000..6ccccff --- /dev/null +++ b/chapter6/bag4.template @@ -0,0 +1,194 @@ +// FILE: bag4.template
+// TEMPLATE CLASS IMPLEMENTED: bag<Item> (see bag4.h for documentation)
+// NOTE:
+// Since node is a template class, this file is included in node2.h.
+// Therefore, we should not put any using directives in this file.
+// INVARIANT for the bag ADT:
+// 1. The number of items in the bag is in the member variable used;
+// 2. The actual items of the bag are stored in a partially filled array.
+// The array is a dynamic array, pointed to by the member variable data.
+// 3. The size of the dynamic array is in the member variable capacity.
+
+#include <algorithm> // Provides copy
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides rand
+
+namespace main_savitch_6A
+{
+ // MEMBER CONSTANTS *********************************************:
+ template <class Item>
+ const typename bag<Item>::size_type bag<Item>::DEFAULT_CAPACITY;
+
+
+ // CONSTRUCTORS and DESTRUCTORS *********************************:
+ template <class Item>
+ bag<Item>::bag(size_type initial_capacity)
+ {
+ data = new Item[initial_capacity];
+ capacity = initial_capacity;
+ used = 0;
+ }
+
+ template <class Item>
+ bag<Item>::bag(const bag<Item>& source)
+ // Library facilities used: algorithm
+ {
+ data = new Item[source.capacity];
+ capacity = source.capacity;
+ used = source.used;
+ std::copy(source.data, source.data + used, data);
+ }
+
+ template <class Item>
+ bag<Item>::~bag( )
+ {
+ delete [ ] data;
+ }
+
+
+ // MODIFICATION MEMBER FUNCTIONS (alphabetically): ***************:
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::erase(const Item& target)
+ {
+ size_type index = 0;
+ size_type many_removed = 0;
+
+ while (index < used)
+ {
+ if (data[index] == target)
+ {
+ --used;
+ data[index] = data[used];
+ ++many_removed;
+ }
+ else
+ --index;
+ }
+
+ return many_removed;
+ }
+
+ template <class Item>
+ bool bag<Item>::erase_one(const Item& target)
+ {
+ size_type index; // The location of target in the data array
+
+ // First, set index to the location of target in the data array,
+ // which could be as small as 0 or as large as used-1.
+ // If target is not in the array, then index will be set equal to used.
+ for (index = 0; (index < used) && (data[index] != target); ++index)
+ ; // No work in the body of this loop.
+
+ if (index == used) // target isn't in the bag, so no work to do
+ return false;
+
+ // When execution reaches here, target is in the bag at data[index].
+ // So, reduce used by 1 and copy the last item onto data[index].
+ --used;
+ data[index] = data[used];
+ return true;
+ }
+
+ template <class Item>
+ void bag<Item>::insert(const Item& entry)
+ {
+ if (used == capacity)
+ reserve(used+1);
+ data[used] = entry;
+ ++used;
+ }
+
+ template <class Item>
+ void bag<Item>::operator =(const bag<Item>& source)
+ // Library facilities used: algorithm
+ {
+ Item *new_data;
+
+ // Check for possible self-assignment:
+ if (this == &source)
+ return;
+
+ // If needed, allocate an array with a different size:
+ if (capacity != source.capacity)
+ {
+ new_data = new Item[source.capacity];
+ delete [ ] data;
+ data = new_data;
+ capacity = source.capacity;
+ }
+
+ // Copy the data from the source array:
+ used = source.used;
+ std::copy(source.data, source.data + used, data);
+ }
+
+ template <class Item>
+ void bag<Item>::operator +=(const bag<Item>& addend)
+ // Library facilities used: algorithm
+ {
+ if (used + addend.used > capacity)
+ reserve(used + addend.used);
+
+ std::copy(addend.data, addend.data + addend.used, data + used);
+ used += addend.used;
+ }
+
+ template <class Item>
+ void bag<Item>::reserve(size_type new_capacity)
+ // Library facilities used: algorithm
+ {
+ Item *larger_array;
+
+ if (new_capacity == capacity)
+ return; // The allocated memory is already the right size
+
+ if (new_capacity < used)
+ new_capacity = used; // Can't allocate less than we are using
+
+ larger_array = new Item[new_capacity];
+ std::copy(data, data + used, larger_array);
+ delete [ ] data;
+ data = larger_array;
+ capacity = new_capacity;
+ }
+
+
+ // CONST MEMBER FUNCTIONS (alphabetically): *********************:
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::count
+ (const Item& target) const
+ {
+ size_type answer;
+ size_type i;
+
+ answer = 0;
+ for (i = 0; i < used; ++i)
+ if (target == data[i])
+ ++answer;
+ return answer;
+ }
+
+ template <class Item>
+ Item bag<Item>::grab( ) const
+ // Library facilities used: cassert, cstdlib
+ {
+ size_type i;
+
+ assert(size( ) > 0);
+ i = (std::rand( ) % size( )); // i is in the range of 0 to size( ) - 1.
+ return data[i];
+ }
+
+
+ // NON-MEMBER FUNCTIONS: ****************************************:
+ template <class Item>
+ bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
+ {
+ bag<Item> answer(b1.size( ) + b2.size( ));
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+
+}
diff --git a/chapter6/bag4demo.cxx b/chapter6/bag4demo.cxx new file mode 100644 index 0000000..994bb3d --- /dev/null +++ b/chapter6/bag4demo.cxx @@ -0,0 +1,64 @@ +// FILE: bag4demo.cxx
+// Demonstration program for the 4th version of the bag
+// (from bag4.h and bag4.template).
+// This is a the same as the demonstration program for bag1,
+// except that we are now using a template class, and we no longer need to
+// check whether the bag reaches its capacity.
+
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include "bag4.h" // Provides the bag<Item> template class
+using namespace std;
+using namespace main_savitch_6A;
+
+// PROTOTYPES for functions used by this demonstration program:
+void get_ages(bag<int>& ages);
+// Postcondition: The user has been prompted to type in the ages of family
+// members. These ages have been read and placed in the ages bag, stopping
+// when the user types a negative number.
+
+void check_ages(bag<int>& ages);
+// Postcondition: The user has been prompted to type in the ages of family
+// members once again. Each age is removed from the ages bag when it is typed,
+// stopping when the bag is empty.
+
+
+int main( )
+{
+ bag<int> ages;
+
+ get_ages(ages);
+ check_ages(ages);
+ cout << "May your family live long and prosper." << endl;
+ return EXIT_SUCCESS;
+}
+
+
+void get_ages(bag<int>& ages)
+{
+ int user_input; // An age from the user's family
+
+ cout << "Type the ages in your family. ";
+ cout << "Type a negative number when you are done:" << endl;
+ cin >> user_input;
+ while (user_input >= 0)
+ {
+ ages.insert(user_input);
+ cin >> user_input;
+ }
+}
+
+void check_ages(bag<int>& ages)
+{
+ int user_input; // An age from the user's family
+
+ cout << "Type those ages again. Press return after each age:" << endl;
+ while (ages.size( ) > 0)
+ {
+ cin >> user_input;
+ if (ages.erase_one(user_input))
+ cout << "Yes, I've got that age and have removed it." << endl;
+ else
+ cout << "No, that age does not occur!" << endl;
+ }
+}
diff --git a/chapter6/bag5.h b/chapter6/bag5.h new file mode 100644 index 0000000..a71435c --- /dev/null +++ b/chapter6/bag5.h @@ -0,0 +1,128 @@ +// FILE: bag5.h (part of the namespace main_savitch_chapter6)
+// TEMPLATE CLASS PROVIDED:
+// bag<Item> (a collection of items; each item may appear multiple times)
+//
+// TYPEDEFS for the bag<Item> template class:
+// bag<Item>::value_type
+// This is the Item type from the template parameter.
+// It is the data type of the items in the bag. 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 test for equality (x == y).
+//
+// bag<Item>::size_type
+// This is the data type of any variable that keeps track of how many items
+// are in a bag
+//
+// bag<Item>::iterator and bag<Item>::const_iterator
+// Forward iterators for a bag or a const bag.
+//
+// CONSTRUCTOR for the bag<Item> class:
+// bag( )
+// Postcondition: The bag is empty.
+//
+// MODIFICATION MEMBER FUNCTIONS for the bag<Item> 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 from the bag; 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 inserted into the bag.
+//
+// void operator +=(const bag& addend)
+// Postcondition: Each item in addend has been added to this bag.
+//
+// CONSTANT MEMBER FUNCTIONS for the bag<Item> 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: Return value is the total number of items in the bag.
+//
+// STANDARD ITERATOR MEMBER FUNCTIONS (provide a forward iterator):
+// iterator begin( )
+// const_iterator begin( ) const
+// iterator end( )
+// const iterator end( ) const
+//
+// NONMEMBER FUNCTIONS for the bag<Item> 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> class:
+// Assignments and the copy constructor may be used with bag objects.
+//
+// DYNAMIC MEMORY USAGE by the bag<Item>:
+// If there is insufficient dynamic memory, then the following functions throw
+// bad_alloc: The constructors, insert, operator +=, operator +, and the
+// assignment operator.
+
+#ifndef MAIN_SAVITCH_BAG5_H
+#define MAIN_SAVITCH_BAG5_H
+#include <cstdlib> // Provides NULL and size_t and NULL
+#include "node2.h" // Provides node class
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ class bag
+ {
+ public:
+ // TYPEDEFS
+ typedef std::size_t size_type;
+ typedef Item value_type;
+ typedef node_iterator<Item> iterator;
+ typedef const_node_iterator<Item> const_iterator;
+
+ // CONSTRUCTORS and DESTRUCTOR
+ bag( );
+ 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& addend);
+ void operator =(const bag& source);
+
+ // CONST MEMBER FUNCTIONS
+ size_type count(const Item& target) const;
+ Item grab( ) const;
+ size_type size( ) const { return many_nodes; }
+
+ // FUNCTIONS TO PROVIDE ITERATORS
+ iterator begin( )
+ { return iterator(head_ptr); }
+ const_iterator begin( ) const
+ { return const_iterator(head_ptr); }
+ iterator end( )
+ { return iterator( ); } // Uses default constructor
+ const_iterator end( ) const
+ { return const_iterator( ); } // Uses default constructor
+
+ private:
+ node<Item> *head_ptr; // Head pointer for the list of items
+ size_type many_nodes; // Number of nodes on the list
+ };
+
+ // NONMEMBER functions for the bag
+ template <class Item>
+ bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2);
+}
+
+// The implementation of a template class must be included in its header file:
+#include "bag5.template"
+#endif
+
diff --git a/chapter6/bag5.template b/chapter6/bag5.template new file mode 100644 index 0000000..9d22436 --- /dev/null +++ b/chapter6/bag5.template @@ -0,0 +1,164 @@ +// FILE: bag5.template
+// CLASS implemented: bag (see bag5.h for documentation)
+// NOTE:
+// Since bag is a template class, this file is included in node2.h.
+// INVARIANT for the bag class:
+// 1. The items in the bag are stored on a linked list;
+// 2. The head pointer of the list is stored in the member variable head_ptr;
+// 3. The total number of items in the list is stored in the member variable
+// many_nodes.
+
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides NULL, rand
+#include "node2.h" // Provides node
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ bag<Item>::bag( )
+ // Library facilities used: cstdlib
+ {
+ head_ptr = NULL;
+ many_nodes = 0;
+ }
+
+ template <class Item>
+ bag<Item>::bag(const bag<Item>& source)
+ // Library facilities used: node2.h
+ {
+ node<Item> *tail_ptr; // Needed for argument of list_copy
+
+ list_copy(source.head_ptr, head_ptr, tail_ptr);
+ many_nodes = source.many_nodes;
+ }
+
+ template <class Item>
+ bag<Item>::~bag( )
+ // Library facilities used: node2.h
+ {
+ list_clear(head_ptr);
+ many_nodes = 0;
+ }
+
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::count(const Item& target) const
+ // Library facilities used: cstdlib, node2.h
+ {
+ size_type answer;
+ const node<Item> *cursor;
+
+ answer = 0;
+ cursor = list_search(head_ptr, target);
+ while (cursor != NULL)
+ {
+ // Each time that cursor is not NULL, we have another occurrence of
+ // target, so we add one to answer, and move cursor to the next
+ // occurrence of the target.
+ ++answer;
+ cursor = cursor->link( );
+ cursor = list_search(cursor, target);
+ }
+ return answer;
+ }
+
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::erase(const Item& target)
+ // Library facilities used: cstdlib, node2.h
+ {
+ size_type answer = 0;
+ node<Item> *target_ptr;
+
+ target_ptr = list_search(head_ptr, target);
+ while (target_ptr != NULL)
+ {
+ // Each time that target_ptr is not NULL, we have another occurrence
+ // of target. We remove this target using the same technique that
+ // was used in erase_one.
+ ++answer;
+ target_ptr->set_data( head_ptr->data( ) );
+ target_ptr = target_ptr->link( );
+ target_ptr = list_search(target_ptr, target);
+ list_head_remove(head_ptr);
+ }
+ return answer;
+ }
+
+ template <class Item>
+ bool bag<Item>::erase_one(const Item& target)
+ // Library facilities used: cstdlib, node2.h
+ {
+ node<Item> *target_ptr;
+
+ target_ptr = list_search(head_ptr, target);
+ if (target_ptr == NULL)
+ return false; // target isn't in the bag, so no work to do
+ target_ptr->set_data( head_ptr->data( ) );
+ list_head_remove(head_ptr);
+ --many_nodes;
+ return true;
+ }
+
+ template <class Item>
+ Item bag<Item>::grab( ) const
+ // Library facilities used: cassert, cstdlib, node2.h
+ {
+ size_type i;
+ const node<Item> *cursor;
+
+ assert(size( ) > 0);
+ i = (std::rand( ) % size( )) + 1;
+ cursor = list_locate(head_ptr, i);
+ return cursor->data( );
+ }
+
+ template <class Item>
+ void bag<Item>::insert(const Item& entry)
+ // Library facilities used: node2.h
+ {
+ list_head_insert(head_ptr, entry);
+ ++many_nodes;
+ }
+
+ template <class Item>
+ void bag<Item>::operator +=(const bag<Item>& addend)
+ // Library facilities used: node2.h
+ {
+ node<Item> *copy_head_ptr;
+ node<Item> *copy_tail_ptr;
+
+ if (addend.many_nodes > 0)
+ {
+ list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
+ copy_tail_ptr->set_link( head_ptr );
+ head_ptr = copy_head_ptr;
+ many_nodes += addend.many_nodes;
+ }
+ }
+
+ template <class Item>
+ void bag<Item>::operator =(const bag<Item>& source)
+ // Library facilities used: node2.h
+ {
+ node<Item> *tail_ptr; // Needed for argument to list_copy
+
+ if (this == &source)
+ return;
+
+ list_clear(head_ptr);
+ many_nodes = 0;
+
+ list_copy(source.head_ptr, head_ptr, tail_ptr);
+ many_nodes = source.many_nodes;
+ }
+
+ template <class Item>
+ bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
+ {
+ bag<Item> answer;
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+
+}
diff --git a/chapter6/maximal.cxx b/chapter6/maximal.cxx new file mode 100644 index 0000000..aecd5a9 --- /dev/null +++ b/chapter6/maximal.cxx @@ -0,0 +1,36 @@ +// FILE: maximal.cxx
+// A demonstration program for a template function called maximal.
+
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <iostream> // Provides cout
+#include <string> // Provides string class
+using namespace std;
+
+// TEMPLATE FUNCTION used in this demonstration program:
+// Note that some compilers require the entire function definition to appear
+// before its use (rather than a mere prototype). This maximal function is
+// similar to max from <algorithm>.
+template <class Item>
+Item maximal(Item a, Item b)
+// Postcondition: Returns the larger of a and b.
+// Note: Item may be any of the C++ built-in types (int, char, etc.), or a
+// class with the > operator and a copy constructor.
+{
+ if (a > b)
+ return a;
+ else
+ return b;
+}
+
+int main( )
+{
+ string s1("frijoles");
+ string s2("beans");
+
+ cout << "Larger of frijoles and beans: " << maximal(s1, s2) << endl;
+ cout << "Larger of 10 and 20 : " << maximal(10, 20) << endl;
+ cout << "Larger of $ and @ : " << maximal('$', '@') << endl;
+ cout << "It's a large world." << endl;
+
+ return EXIT_SUCCESS;
+}
diff --git a/chapter6/maximal.exe b/chapter6/maximal.exe Binary files differnew file mode 100644 index 0000000..8031ba8 --- /dev/null +++ b/chapter6/maximal.exe diff --git a/chapter6/maximal.o b/chapter6/maximal.o Binary files differnew file mode 100644 index 0000000..fe3b6d4 --- /dev/null +++ b/chapter6/maximal.o diff --git a/chapter6/node2.h b/chapter6/node2.h new file mode 100644 index 0000000..a161683 --- /dev/null +++ b/chapter6/node2.h @@ -0,0 +1,204 @@ +// FILE: node2.h (part of the namespace main_savitch_6B)
+// PROVIDES: A template class for a node in a linked list, and list manipulation
+// functions. The template parameter is the type of the data in each node.
+// This file also defines a template class: node_iterator<Item>.
+// The node_iterator is a forward iterators with two constructors:
+// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
+// to the specified node in a linked list, and (2) a default constructor that
+// creates a special iterator that marks the position that is beyond the end of a
+// linked list. There is also a const_node_iterator for use with
+// const node<Item>* .
+//
+// TYPEDEF for the node<Item> template class:
+// Each node of the list contains a piece of data and a pointer to the
+// next node. The type of the data (node<Item>::value_type) is the Item type
+// from the template parameter. The type may be any of the built-in C++ classes
+// (int, char, ...) or a class with a default constructor, an assignment
+// operator, and a test for equality (x == y).
+// NOTE:
+// Many compilers require the use of the new keyword typename before using
+// the expression node<Item>::value_type. Otherwise
+// the compiler doesn't have enough information to realize that it is the
+// name of a data type.
+//
+// CONSTRUCTOR for the node<Item> class:
+// node(
+// const Item& init_data = Item(),
+// node* init_link = NULL
+// )
+// Postcondition: The node contains the specified data and link.
+// NOTE: The default value for the init_data is obtained from the default
+// constructor of the Item. In the ANSI/ISO standard, this notation
+// is also allowed for the built-in types, providing a default value of
+// zero. The init_link has a default value of NULL.
+//
+// NOTE about two versions of some functions:
+// The data function returns a reference to the data field of a node and
+// the link function returns a copy of the link field of a node.
+// Each of these functions comes in two versions: a const version and a
+// non-const version. If the function is activated by a const node, then the
+// compiler choses the const version (and the return value is const).
+// If the function is activated by a non-const node, then the compiler choses
+// the non-const version (and the return value will be non-const).
+// EXAMPLES:
+// const node<int> *c;
+// c->link( ) activates the const version of link returning const node*
+// c->data( ) activates the const version of data returning const Item&
+// c->data( ) = 42; ... is forbidden
+// node<int> *p;
+// p->link( ) activates the non-const version of link returning node*
+// p->data( ) activates the non-const version of data returning Item&
+// p->data( ) = 42; ... actually changes the data in p's node
+//
+// MEMBER FUNCTIONS for the node<Item> class:
+// const Item& data( ) const <----- const version
+// and
+// Item& data( ) <----------------- non-const version
+// See the note (above) about the const version and non-const versions:
+// Postcondition: The return value is a reference to the data from this node.
+//
+// const node* link( ) const <----- const version
+// and
+// node* link( ) <----------------- non-const version
+// See the note (above) about the const version and non-const versions:
+// Postcondition: The return value is the link from this node.
+//
+// void set_data(const Item& new_data)
+// Postcondition: The node now contains the specified new data.
+//
+// void set_link(node* new_link)
+// Postcondition: The node now contains the specified new link.
+//
+// FUNCTIONS in the linked list toolkit:
+// template <class Item>
+// void list_clear(node<Item>*& head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: All nodes of the list have been returned to the heap,
+// and the head_ptr is now NULL.
+//
+// template <class Item>
+// void list_copy
+// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
+// Precondition: source_ptr is the head pointer of a linked list.
+// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
+// a new list that contains the same items as the list pointed to by
+// source_ptr. The original list is unaltered.
+//
+// template <class Item>
+// void list_head_insert(node<Item>*& head_ptr, const Item& entry)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: A new node containing the given entry has been added at
+// the head of the linked list; head_ptr now points to the head of the new,
+// longer linked list.
+//
+// template <class Item>
+// void list_head_remove(node<Item>*& head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list, with at
+// least one node.
+// Postcondition: The head node has been removed and returned to the heap;
+// head_ptr is now the head pointer of the new, shorter linked list.
+//
+// template <class Item>
+// void list_insert(node<Item>* previous_ptr, const Item& entry)
+// Precondition: previous_ptr points to a node in a linked list.
+// Postcondition: A new node containing the given entry has been added
+// after the node that previous_ptr points to.
+//
+// template <class Item>
+// size_t list_length(const node<Item>* head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: The value returned is the number of nodes in the linked
+// list.
+//
+// template <class NodePtr, class SizeType>
+// NodePtr list_locate(NodePtr head_ptr, SizeType position)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// Precondition: head_ptr is the head pointer of a linked list, and
+// position > 0.
+// Postcondition: The return value is a pointer that points to the node at
+// the specified position in the list. (The head node is position 1, the
+// next node is position 2, and so on). If there is no such position, then
+// the null pointer is returned.
+//
+// template <class Item>
+// void list_remove(node<Item>* previous_ptr)
+// Precondition: previous_ptr points to a node in a linked list, and this
+// is not the tail node of the list.
+// Postcondition: The node after previous_ptr has been removed from the
+// linked list.
+//
+// template <class NodePtr, class Item>
+// NodePtr list_search
+// (NodePtr head_ptr, const Item& target)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: The return value is a pointer that points to the first
+// node containing the specified target in its data member. If there is no
+// such node, the null pointer is returned.
+//
+// DYNAMIC MEMORY usage by the toolkit:
+// If there is insufficient dynamic memory, then the following functions throw
+// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.
+
+#ifndef MAIN_SAVITCH_NODE2_H
+#define MAIN_SAVITCH_NODE2_H
+#include <cstdlib> // Provides NULL and size_t
+#include <iterator> // Provides iterator and forward_iterator_tag
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ class node
+ {
+ public:
+ // TYPEDEF
+ typedef Item value_type;
+ // CONSTRUCTOR
+ node(const Item& init_data=Item( ), node* init_link=NULL)
+ { data_field = init_data; link_field = init_link; }
+ // MODIFICATION MEMBER FUNCTIONS
+ Item& data( ) { return data_field; }
+ node* link( ) { return link_field; }
+ void set_data(const Item& new_data) { data_field = new_data; }
+ void set_link(node* new_link) { link_field = new_link; }
+ // CONST MEMBER FUNCTIONS
+ const Item& data( ) const { return data_field; }
+ const node* link( ) const { return link_field; }
+ private:
+ Item data_field;
+ node *link_field;
+ };
+
+ // FUNCTIONS to manipulate a linked list:
+ template <class Item>
+ void list_clear(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_copy
+ (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
+
+ template <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry);
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry);
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr);
+
+ template <class NodePtr, class SizeType>
+ NodePtr list_locate(NodePtr head_ptr, SizeType position);
+
+ template <class Item>
+ void list_remove(node<Item>* previous_ptr);
+
+ template <class NodePtr, class Item>
+ NodePtr list_search(NodePtr head_ptr, const Item& target);
+
+}
+
+#include "node2.template"
+#endif
diff --git a/chapter6/node2.template b/chapter6/node2.template new file mode 100644 index 0000000..6b3a56a --- /dev/null +++ b/chapter6/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template
+// IMPLEMENTS: The functions of the node template class and the
+// linked list toolkit (see node2.h for documentation).
+//
+// NOTE:
+// Since node is a template class, this file is included in node2.h.
+// Therefore, we should not put any using directives in this file.
+//
+// INVARIANT for the node class:
+// The data of a node is stored in data_field, and the link in link_field.
+
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides NULL and size_t
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ void list_clear(node<Item>*& head_ptr)
+ // Library facilities used: cstdlib
+ {
+ while (head_ptr != NULL)
+ list_head_remove(head_ptr);
+ }
+
+ template <class Item>
+ void list_copy(
+ const node<Item>* source_ptr,
+ node<Item>*& head_ptr,
+ node<Item>*& tail_ptr
+ )
+ // Library facilities used: cstdlib
+ {
+ head_ptr = NULL;
+ tail_ptr = NULL;
+
+ // Handle the case of the empty list
+ if (source_ptr == NULL)
+ return;
+
+ // Make the head node for the newly created list, and put data in it
+ list_head_insert(head_ptr, source_ptr->data( ));
+ tail_ptr = head_ptr;
+
+ // Copy rest of the nodes one at a time, adding at the tail of new list
+ source_ptr = source_ptr->link( );
+ while (source_ptr != NULL)
+ {
+ list_insert(tail_ptr, source_ptr->data( ));
+ tail_ptr = tail_ptr->link( );
+ source_ptr = source_ptr->link( );
+ }
+ }
+
+ template <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry)
+ {
+ head_ptr = new node<Item>(entry, head_ptr);
+ }
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = head_ptr;
+ head_ptr = head_ptr->link( );
+ delete remove_ptr;
+ }
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry)
+ {
+ node<Item> *insert_ptr;
+
+ insert_ptr = new node<Item>(entry, previous_ptr->link( ));
+ previous_ptr->set_link(insert_ptr);
+ }
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr)
+ // Library facilities used: cstdlib
+ {
+ const node<Item> *cursor;
+ std::size_t answer;
+
+ answer = 0;
+ for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
+ ++answer;
+
+ return answer;
+ }
+
+ template <class NodePtr, class SizeType>
+ NodePtr list_locate(NodePtr head_ptr, SizeType position)
+ // Library facilities used: cassert, cstdlib
+ {
+ NodePtr cursor;
+ SizeType i;
+
+ assert(0 < position);
+ cursor = head_ptr;
+ for (i = 1; (i < position) && (cursor != NULL); ++i)
+ cursor = cursor->link( );
+ return cursor;
+ }
+
+ template <class Item>
+ void list_remove(node<Item>* previous_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = previous_ptr->link( );
+ previous_ptr->set_link(remove_ptr->link( ));
+ delete remove_ptr;
+ }
+
+ template <class NodePtr, class Item>
+ NodePtr list_search(NodePtr head_ptr, const Item& target)
+ // Library facilities used: cstdlib
+ {
+ NodePtr cursor;
+
+ for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
+ if (target == cursor->data( ))
+ return cursor;
+ return NULL;
+ }
+}
|