From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter6/author.cxx | 63 +++++++++++++++ chapter6/author.exe | Bin 0 -> 109616 bytes chapter6/author.o | Bin 0 -> 79390 bytes chapter6/bag4.h | 113 +++++++++++++++++++++++++++ chapter6/bag4.template | 194 +++++++++++++++++++++++++++++++++++++++++++++ chapter6/bag4demo.cxx | 64 +++++++++++++++ chapter6/bag5.h | 128 ++++++++++++++++++++++++++++++ chapter6/bag5.template | 164 ++++++++++++++++++++++++++++++++++++++ chapter6/maximal.cxx | 36 +++++++++ chapter6/maximal.exe | Bin 0 -> 95225 bytes chapter6/maximal.o | Bin 0 -> 65610 bytes chapter6/node2.h | 204 ++++++++++++++++++++++++++++++++++++++++++++++++ chapter6/node2.template | 128 ++++++++++++++++++++++++++++++ 13 files changed, 1094 insertions(+) create mode 100644 chapter6/author.cxx create mode 100644 chapter6/author.exe create mode 100644 chapter6/author.o create mode 100644 chapter6/bag4.h create mode 100644 chapter6/bag4.template create mode 100644 chapter6/bag4demo.cxx create mode 100644 chapter6/bag5.h create mode 100644 chapter6/bag5.template create mode 100644 chapter6/maximal.cxx create mode 100644 chapter6/maximal.exe create mode 100644 chapter6/maximal.o create mode 100644 chapter6/node2.h create mode 100644 chapter6/node2.template (limited to 'chapter6') 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 // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include // 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 +void get_items(bag& 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 key after the final entry:\n"; + for (i = 1; i <= n; ++i) + { + cin >> user_input; + collection.insert(user_input); + } + cout << endl; +} + +int main( ) +{ + bag adjectives; // Contains adjectives typed by user + bag ages; // Contains ages in the teens typed by user + bag 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 new file mode 100644 index 0000000..2cb1e66 Binary files /dev/null and b/chapter6/author.exe differ diff --git a/chapter6/author.o b/chapter6/author.o new file mode 100644 index 0000000..c372ee6 Binary files /dev/null and b/chapter6/author.o differ 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 +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the bag class: +// The template parameter, Item, is the data type of the items in the bag, +// also defined as bag::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::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::value_type and bag::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 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 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& 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 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 template class: +// template +// bag operator +(const bag& b1, const bag& b2) +// Postcondition: The bag returned is the union of b1 and b2. +// +// VALUE SEMANTICS for the bag template class: +// Assignments and the copy constructor may be used with bag objects. +// +// DYNAMIC MEMORY USAGE by the bag 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 // Provides size_t + +namespace main_savitch_6A +{ + template + 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 + bag operator +(const bag& b1, const bag& 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 (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 // Provides copy +#include // Provides assert +#include // Provides rand + +namespace main_savitch_6A +{ + // MEMBER CONSTANTS *********************************************: + template + const typename bag::size_type bag::DEFAULT_CAPACITY; + + + // CONSTRUCTORS and DESTRUCTORS *********************************: + template + bag::bag(size_type initial_capacity) + { + data = new Item[initial_capacity]; + capacity = initial_capacity; + used = 0; + } + + template + bag::bag(const bag& 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 + bag::~bag( ) + { + delete [ ] data; + } + + + // MODIFICATION MEMBER FUNCTIONS (alphabetically): ***************: + template + typename bag::size_type bag::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 + bool bag::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 + void bag::insert(const Item& entry) + { + if (used == capacity) + reserve(used+1); + data[used] = entry; + ++used; + } + + template + void bag::operator =(const bag& 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 + void bag::operator +=(const bag& 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 + void bag::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 + typename bag::size_type bag::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 + Item bag::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 + bag operator +(const bag& b1, const bag& b2) + { + bag 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 // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "bag4.h" // Provides the bag template class +using namespace std; +using namespace main_savitch_6A; + +// PROTOTYPES for functions used by this demonstration program: +void get_ages(bag& 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& 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 ages; + + get_ages(ages); + check_ages(ages); + cout << "May your family live long and prosper." << endl; + return EXIT_SUCCESS; +} + + +void get_ages(bag& 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& 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 (a collection of items; each item may appear multiple times) +// +// TYPEDEFS for the bag template class: +// bag::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::size_type +// This is the data type of any variable that keeps track of how many items +// are in a bag +// +// bag::iterator and bag::const_iterator +// Forward iterators for a bag or a const bag. +// +// CONSTRUCTOR for the bag class: +// bag( ) +// Postcondition: The bag is empty. +// +// MODIFICATION MEMBER FUNCTIONS for the bag 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 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 class: +// template +// bag operator +(const bag& b1, const bag& b2) +// Postcondition: The bag returned is the union of b1 and b2. +// +// VALUE SEMANTICS for the bag class: +// Assignments and the copy constructor may be used with bag objects. +// +// DYNAMIC MEMORY USAGE by the bag: +// 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 // Provides NULL and size_t and NULL +#include "node2.h" // Provides node class + +namespace main_savitch_6B +{ + template + class bag + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + typedef node_iterator iterator; + typedef const_node_iterator 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 *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 + bag operator +(const bag& b1, const bag& 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 // Provides assert +#include // Provides NULL, rand +#include "node2.h" // Provides node + +namespace main_savitch_6B +{ + template + bag::bag( ) + // Library facilities used: cstdlib + { + head_ptr = NULL; + many_nodes = 0; + } + + template + bag::bag(const bag& source) + // Library facilities used: node2.h + { + node *tail_ptr; // Needed for argument of list_copy + + list_copy(source.head_ptr, head_ptr, tail_ptr); + many_nodes = source.many_nodes; + } + + template + bag::~bag( ) + // Library facilities used: node2.h + { + list_clear(head_ptr); + many_nodes = 0; + } + + template + typename bag::size_type bag::count(const Item& target) const + // Library facilities used: cstdlib, node2.h + { + size_type answer; + const node *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 + typename bag::size_type bag::erase(const Item& target) + // Library facilities used: cstdlib, node2.h + { + size_type answer = 0; + node *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 + bool bag::erase_one(const Item& target) + // Library facilities used: cstdlib, node2.h + { + node *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 + Item bag::grab( ) const + // Library facilities used: cassert, cstdlib, node2.h + { + size_type i; + const node *cursor; + + assert(size( ) > 0); + i = (std::rand( ) % size( )) + 1; + cursor = list_locate(head_ptr, i); + return cursor->data( ); + } + + template + void bag::insert(const Item& entry) + // Library facilities used: node2.h + { + list_head_insert(head_ptr, entry); + ++many_nodes; + } + + template + void bag::operator +=(const bag& addend) + // Library facilities used: node2.h + { + node *copy_head_ptr; + node *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 + void bag::operator =(const bag& source) + // Library facilities used: node2.h + { + node *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 + bag operator +(const bag& b1, const bag& b2) + { + bag 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 // Provides EXIT_SUCCESS +#include // Provides cout +#include // 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 . +template +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 new file mode 100644 index 0000000..8031ba8 Binary files /dev/null and b/chapter6/maximal.exe differ diff --git a/chapter6/maximal.o b/chapter6/maximal.o new file mode 100644 index 0000000..fe3b6d4 Binary files /dev/null and b/chapter6/maximal.o differ 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. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* 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* . +// +// TYPEDEF for the node 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::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::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 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 *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 *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 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 +// void list_clear(node*& 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 +// void list_copy +// (const node* source_ptr, node*& head_ptr, node*& 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 +// void list_head_insert(node*& 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 +// void list_head_remove(node*& 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 +// void list_insert(node* 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 +// size_t list_length(const node* 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 +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// 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 +// void list_remove(node* 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 +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// 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 // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + 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 + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + 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 // Provides assert +#include // Provides NULL and size_t + +namespace main_savitch_6B +{ + template + void list_clear(node*& head_ptr) + // Library facilities used: cstdlib + { + while (head_ptr != NULL) + list_head_remove(head_ptr); + } + + template + void list_copy( + const node* source_ptr, + node*& head_ptr, + node*& 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 + void list_head_insert(node*& head_ptr, const Item& entry) + { + head_ptr = new node(entry, head_ptr); + } + + template + void list_head_remove(node*& head_ptr) + { + node *remove_ptr; + + remove_ptr = head_ptr; + head_ptr = head_ptr->link( ); + delete remove_ptr; + } + + template + void list_insert(node* previous_ptr, const Item& entry) + { + node *insert_ptr; + + insert_ptr = new node(entry, previous_ptr->link( )); + previous_ptr->set_link(insert_ptr); + } + + template + std::size_t list_length(const node* head_ptr) + // Library facilities used: cstdlib + { + const node *cursor; + std::size_t answer; + + answer = 0; + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + ++answer; + + return answer; + } + + template + 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 + void list_remove(node* previous_ptr) + { + node *remove_ptr; + + remove_ptr = previous_ptr->link( ); + previous_ptr->set_link(remove_ptr->link( )); + delete remove_ptr; + } + + template + 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; + } +} -- cgit v1.2.3