From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter8/carwash.cxx | 73 ++++++++++++ chapter8/ch8queueFiles.zip | Bin 0 -> 12208 bytes chapter8/node2.h | 270 +++++++++++++++++++++++++++++++++++++++++++++ chapter8/node2.template | 128 +++++++++++++++++++++ chapter8/pal.cxx | 44 ++++++++ chapter8/pal.exe | Bin 0 -> 95181 bytes chapter8/pal.o | Bin 0 -> 64111 bytes chapter8/queue1.h | 81 ++++++++++++++ chapter8/queue1.template | 55 +++++++++ chapter8/queue2.h | 76 +++++++++++++ chapter8/queue2.template | 88 +++++++++++++++ chapter8/queueFiles.zip | Bin 0 -> 8274 bytes chapter8/washing.cxx | 80 ++++++++++++++ chapter8/washing.h | 113 +++++++++++++++++++ 14 files changed, 1008 insertions(+) create mode 100644 chapter8/carwash.cxx create mode 100644 chapter8/ch8queueFiles.zip create mode 100644 chapter8/node2.h create mode 100644 chapter8/node2.template create mode 100644 chapter8/pal.cxx create mode 100644 chapter8/pal.exe create mode 100644 chapter8/pal.o create mode 100644 chapter8/queue1.h create mode 100644 chapter8/queue1.template create mode 100644 chapter8/queue2.h create mode 100644 chapter8/queue2.template create mode 100644 chapter8/queueFiles.zip create mode 100644 chapter8/washing.cxx create mode 100644 chapter8/washing.h (limited to 'chapter8') diff --git a/chapter8/carwash.cxx b/chapter8/carwash.cxx new file mode 100644 index 0000000..09c074f --- /dev/null +++ b/chapter8/carwash.cxx @@ -0,0 +1,73 @@ +// FILE: carwash.cxx +// A small test program to test the car_wash_simulate function. + +#include // Provides cout +#include // Provides EXIT_SUCCESS +#include // Provides queue +#include "washing.h" // Provides averager, bool_source, washer +using namespace std; +using namespace main_savitch_8A; + +void car_wash_simulate +(unsigned int wash_time, double arrival_prob, unsigned int total_time); +// Precondition: 0 <= arrival_prob <= 1. +// Postcondition: The function has simulated a car wash where wash_time is the +// number of seconds needed to wash one car, arrival_prob is the probability +// of a customer arriving in any second, and total_time is the total number +// of seconds for the simulation. Before the simulation, the function has +// written its three parameters to cout. After the simulation, the function +// has written two pieces of information to cout: (1) The number of +// cars washed, and (2) The average waiting time of a customer. + +int main( ) +{ + // Wash takes 240 seconds + // Customers arrive on average once every 400 seconds + // Total simulation time is 6000 seconds + car_wash_simulate(240, 1.0/400, 6000); + + return EXIT_SUCCESS; +} + +void car_wash_simulate +(unsigned int wash_time, double arrival_prob, unsigned int total_time) +// Library facilities used: iostream, queue, washing.h +{ + queue arrival_times; // Waiting customer’s time stamps + unsigned int next; // A value taken from the queue + bool_source arrival(arrival_prob); + washer machine(wash_time); + averager wait_times; + unsigned int current_second; + + // Write the parameters to cout. + cout << "Seconds to wash one car: " << wash_time << endl; + cout << "Probability of customer arrival during a second: "; + cout << arrival_prob << endl; + cout << "Total simulation seconds: " << total_time << endl; + + for (current_second = 1; current_second <= total_time; ++current_second) + { // Simulate the passage of one second of time. + + // Check whether a new customer has arrived. + if (arrival.query( )) + arrival_times.push(current_second); + + // Check whether we can start washing another car. + if ((!machine.is_busy( )) && (!arrival_times.empty( ))) + { + next = arrival_times.front( ); + arrival_times.pop( ); + wait_times.next_number(current_second - next); + machine.start_washing( ); + } + + // Tell the washer to simulate the passage of one second. + machine.one_second( ); + } + + // Write the summary information about the simulation. + cout << "Customers served: " << wait_times.how_many_numbers( ) << endl; + if (wait_times.how_many_numbers( ) > 0) + cout << "Average wait: " << wait_times.average( ) << " sec" << endl; +} diff --git a/chapter8/ch8queueFiles.zip b/chapter8/ch8queueFiles.zip new file mode 100644 index 0000000..27a7522 Binary files /dev/null and b/chapter8/ch8queueFiles.zip differ diff --git a/chapter8/node2.h b/chapter8/node2.h new file mode 100644 index 0000000..9b0df72 --- /dev/null +++ b/chapter8/node2.h @@ -0,0 +1,270 @@ +// 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); + + // FORWARD ITERATORS to step through the nodes of a linked list + // A node_iterator of can change the underlying linked list through the + // * operator, so it may not be used with a const node. The + // node_const_iterator cannot change the underlying linked list + // through the * operator, so it may be used with a const node. + // WARNING: + // This classes use std::iterator as its base class; + // Older compilers that do not support the std::iterator class can + // delete everything after the word iterator in the second line: + + template + class node_iterator + : public std::iterator + { + public: + node_iterator(node* initial = NULL) + { current = initial; } + Item& operator *( ) const + { return current->data( ); } + node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + node_iterator operator ++(int) // Postfix ++ + { + node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const node_iterator other) const + { return current == other.current; } + bool operator !=(const node_iterator other) const + { return current != other.current; } + private: + node* current; + }; + + template + class const_node_iterator + : public std::iterator + { + public: + const_node_iterator(const node* initial = NULL) + { current = initial; } + const Item& operator *( ) const + { return current->data( ); } + const_node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + const_node_iterator operator ++(int) // Postfix ++ + { + const_node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const const_node_iterator other) const + { return current == other.current; } + bool operator !=(const const_node_iterator other) const + { return current != other.current; } + private: + const node* current; + }; + +} + +#include "node2.template" +#endif diff --git a/chapter8/node2.template b/chapter8/node2.template new file mode 100644 index 0000000..45c3470 --- /dev/null +++ b/chapter8/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; + } +} diff --git a/chapter8/pal.cxx b/chapter8/pal.cxx new file mode 100644 index 0000000..11153e8 --- /dev/null +++ b/chapter8/pal.cxx @@ -0,0 +1,44 @@ +// FILE: pal.cxx +// Program to test whether an input line is a palindrome. Spaces, +// punctuation, and the difference between upper- and lowercase are ignored. + +#include // Provides assert +#include // Provides isalpha, toupper +#include // Provides EXIT_SUCCESS +#include // Provides cout, cin, peek +#include // Provides the queue template class +#include // Provides the stack template class +using namespace std; + +int main( ) +{ + queue q; + stack s; + char letter; + queue::size_type mismatches = 0; // Mismatches between queue and stack + cout << "Enter a line and I will see if it's a palindrome:" << endl; + + while (cin.peek( ) != '\n') + { + cin >> letter; + if (isalpha(letter)) + { + q.push(toupper(letter)); + s.push(toupper(letter)); + } + } + + while ((!q.empty( )) && (!s.empty( ))) + { + if (q.front( ) != s.top( )) + ++mismatches; + q.pop( ); + s.pop( ); + } + + if (mismatches == 0) + cout << "That is a palindrome." << endl; + else + cout << "That is not a palindrome." << endl; + return EXIT_SUCCESS; +} diff --git a/chapter8/pal.exe b/chapter8/pal.exe new file mode 100644 index 0000000..bc9a38f Binary files /dev/null and b/chapter8/pal.exe differ diff --git a/chapter8/pal.o b/chapter8/pal.o new file mode 100644 index 0000000..8bf34b4 Binary files /dev/null and b/chapter8/pal.o differ diff --git a/chapter8/queue1.h b/chapter8/queue1.h new file mode 100644 index 0000000..bbf47b7 --- /dev/null +++ b/chapter8/queue1.h @@ -0,0 +1,81 @@ +// FILE: queue1.h (part of the namespace main_savitch_8B) +// TEMPLATE CLASS PROVIDED: queue (a queue of items) +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack class: +// The template parameter, Item, is the data type of the items in the queue, +// also defined as queue::value_type. It may be any of the C++ built-in +// types (int, char, etc.), or a class with a default constructor, a copy +// constructor, and an assignment operator. The definition +// queue::size_type is the data type of any variable that keeps track of +// how many items are in a queue. The static const CAPACITY is the +// maximum capacity of a queue for this first queue implementation. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions queue::value_type and queue::size_type. +// Otherwise the compiler doesn't have enough information to realize that it +// is the name of a data type. +// +// CONSTRUCTOR for the queue template class: +// queue( ) +// Postcondition: The queue has been initialized as an empty queue. +// +// MODIFICATION MEMBER FUNCTIONS for the queue template class: +// void pop( ) +// Precondition: size( ) > 0. +// Postcondition: The front item of the queue has been removed. +// +// void push(const Item& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been inserted at the rear of the +// queue. +// +// CONSTANT MEMBER FUNCTIONS for the queue template class: +// bool empty( ) const +// Postcondition: The return value is true if the queue is empty. +// +// Item front( ) const +// Precondition: size( ) > 0. +// Postcondition: The return value is the front item of the queue (but the queue is +// unchanged). +// +// size_type size( ) const +// Postcondition: The return value is the total number of items in the queue. +// +// VALUE SEMANTICS for the queue template class: +// Assignments and the copy constructor may be used with queue objects. + +#ifndef MAIN_SAVITCH_QUEUE1_H +#define MAIN_SAVITCH_QUEUE1_H +#include // Provides size_t + +namespace main_savitch_8B +{ + template + class queue + { + public: + // TYPEDEFS and MEMBER CONSTANTS -- See Appendix E if this fails to compile. + typedef std::size_t size_type; + typedef Item value_type; + static const size_type CAPACITY = 30; + // CONSTRUCTOR + queue( ); + // MODIFICATION MEMBER FUNCTIONS + void pop( ); + void push(const Item& entry); + // CONSTANT MEMBER FUNCTIONS + bool empty( ) const { return (count == 0); } + Item front( ) const; + size_type size( ) const { return count; } + private: + Item data[CAPACITY]; // Circular array + size_type first; // Index of item at front of the queue + size_type last; // Index of item at rear of the queue + size_type count; // Total number of items in the queue + // HELPER MEMBER FUNCTION + size_type next_index(size_type i) const { return (i+1) % CAPACITY; } + }; +} + +#include "queue1.template" // Include the implementation. +#endif diff --git a/chapter8/queue1.template b/chapter8/queue1.template new file mode 100644 index 0000000..5feee78 --- /dev/null +++ b/chapter8/queue1.template @@ -0,0 +1,55 @@ +// FILE: queue1.template +// TEMPLATE CLASS IMPLEMENTED: queue (see queue1.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the queue class: +// 1. The number of items in the queue is in the member variable count; +// 2. For a non-empty queue, the items are stored in a circular array +// beginning at data[front] and continuing through data[rear]. +// The array's total capacity of the array is CAPACITY. +// 3. For an empty array, rear is some valid index, and front is +// always equal to next_index(rear). +// + +#include // Provides assert + +namespace main_savitch_8B +{ + template + const typename queue::size_type queue::CAPACITY; + + template + queue::queue( ) + { + count = 0; + first = 0; + last = CAPACITY - 1; + } + + template + Item queue::front( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return data[first]; + } + + template + void queue::pop( ) + // Library facilities used: cassert + { + assert(!empty( )); + first = next_index(first); + --count; + } + + template + void queue::push(const Item& entry) + // Library facilities used: cassert + { + assert(size( ) < CAPACITY); + last = next_index(last); + data[last] = entry; + ++count; + } + +} diff --git a/chapter8/queue2.h b/chapter8/queue2.h new file mode 100644 index 0000000..a9a7003 --- /dev/null +++ b/chapter8/queue2.h @@ -0,0 +1,76 @@ +// FILE: queue2.h (part of the namespace +// TEMPLATE CLASS PROVIDED: queue (a queue of items) +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack class: +// The template parameter, Item, is the data type of the items in the queue, +// also defined as queue::value_type. It may be any of the C++ built-in +// types (int, char, etc.), or a class with a default constructor, a copy +// constructor, and an assignment operator. The definition +// queue::size_type is the data type of any variable that keeps track of +// how many items are in a queue. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions queue::value_type and queue::size_type. +// Otherwise the compiler doesn't have enough information to realize that it +// is the name of a data type. +// +// CONSTRUCTOR for the queue template class: +// queue( ) +// Postcondition: The queue has been initialized as an empty queue. +// +// MODIFICATION MEMBER FUNCTIONS for the queue template class: +// void pop( ) +// Precondition: size( ) > 0. +// Postcondition: The front item of the queue has been removed. +// +// void push(const Item& entry) +// Postcondition: A new copy of entry has been inserted at the rear of the +// queue. +// +// CONSTANT MEMBER FUNCTIONS for the queue template class: +// bool empty( ) const +// Postcondition: The return value is true if the queue is empty. +// +// Item front( ) const +// +// size_type size( ) const +// Postcondition: The return value is the total number of items in the queue. +// +// VALUE SEMANTICS for the queue template class: +// Assignments and the copy constructor may be used with queue objects. + +#ifndef MAIN_SAVITCH_QUEUE2_H // Prevent duplicate definition +#define MAIN_SAVITCH_QUEUE2_H +#include // Provides std::size_t +#include "node2.h" // Node template class + +namespace main_savitch_8C +{ + template + class queue + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + // CONSTRUCTORS and DESTRUCTOR + queue( ); + queue(const queue& source); + ~queue( ); + // MODIFICATION MEMBER FUNCTIONS + void pop( ); + void push(const Item& entry); + void operator =(const queue& source); + // CONSTANT MEMBER FUNCTIONS + bool empty( ) const { return (count == 0); } + Item front( ) const; + size_type size( ) const { return count; } + private: + main_savitch_6B::node *front_ptr; // head_ptr + main_savitch_6B::node *rear_ptr; + size_type count; // Total number of items in the queue + }; +} +#include "queue2.template" // Include the implementation + +#endif diff --git a/chapter8/queue2.template b/chapter8/queue2.template new file mode 100644 index 0000000..d08c1cb --- /dev/null +++ b/chapter8/queue2.template @@ -0,0 +1,88 @@ +// FILE: queue2.template +// TEMPLATE CLASS IMPLEMENTED: Queue (see queue2.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the Queue class: +// 1. The number of items in the queue is stored in the member variable +// count. +// 2. The items in the queue are stored in a linked list, with the front of +// the queue stored at the head node, and the rear of the queue stored at +// the final node. +// 3. The member variable front_ptr is the head pointer of the linked list of +// items. For a non-empty queue, the member variable rear_ptr is the +// tail pointer of the linked list; for an empty list, we don't care +// what's stored in rear_ptr. + +#include // Provides assert +#include "node2.h" // Node template class + +namespace main_savitch_8C +{ + template + queue::queue( ) + { + count = 0; + front_ptr = NULL; + rear_ptr = NULL; + } + + template + queue::queue(const queue& source) + // Library facilities used: node2.h + { + count = source.count; + list_copy(source.front_ptr, front_ptr, rear_ptr); + } + + template + queue::~queue( ) + { + list_clear(front_ptr); + } + + template + void queue::operator =(const queue& source) + // Library facilities used: node2.h + { + if (this == &source) // Handle self-assignment + return; + list_clear(front_ptr); + list_copy(source.front_ptr, front_ptr, rear_ptr); + count = source.count; + } + + template + Item queue::front( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return front_ptr->data( ); + } + + template + void queue::pop( ) + // Library facilities used: cassert, node2.h + { + assert(!empty( )); + list_head_remove(front_ptr); + --count; + } + + template + void queue::push(const Item& entry) + // Library facilities used: node2.h + { + if (empty( )) + { // Insert first entry. + list_head_insert(front_ptr, entry); + rear_ptr = front_ptr; + } + else + { // Insert an entry that is not the first. + list_insert(rear_ptr, entry); + rear_ptr = rear_ptr->link( ); + } + ++count; + } + +} + diff --git a/chapter8/queueFiles.zip b/chapter8/queueFiles.zip new file mode 100644 index 0000000..b1ec1a5 Binary files /dev/null and b/chapter8/queueFiles.zip differ diff --git a/chapter8/washing.cxx b/chapter8/washing.cxx new file mode 100644 index 0000000..d806704 --- /dev/null +++ b/chapter8/washing.cxx @@ -0,0 +1,80 @@ +// FILE: washing.cxx +// CLASSES implemented: bool_source, averager, washer +// +// INVARIANT for the bool_source ADT: +// 1. The member variable probability is the appoximate probability that +// query( ) returns true. +// +// INVARIANT for the averager ADT: +// 1. The member variable count indicates how many numbers the averager has +// been given. +// 2. The member variable sum is the sum of all the numbers that the +// averager has been given. +// +// INVARIANT for the washer class: +// 1. The member variable seconds_for_wash is the number of seconds required +// for one wash. +// 2. The member varible wash_time_left is 0 if the washer is not busy; +// otherwise it is the number of seconds until the washer is free. + +#include // Provides assert +#include // Provides rand, RAND_MAX, size_t +#include "washing.h" // Provides bool_source, averager, washer definitions +using namespace std; + +namespace main_savitch_8A +{ + bool_source::bool_source(double p) + // Library facilities used: cassert + { + assert(p >= 0); + assert(p <= 1); + probability = p; + } + + bool bool_source::query( ) const + // Library facilities used: cstdlib + { + return (rand( ) < probability * RAND_MAX); + } + + averager::averager( ) + { + count = 0; + sum = 0; + } + + void averager::next_number(double value) + { + ++count; + sum += value; + } + + double averager::average( ) const + // Library facilities used: cassert + { + assert(how_many_numbers( ) > 0); + return sum/count; + } + + washer::washer(unsigned int s) + { + seconds_for_wash = s; + wash_time_left = 0; + } + + + void washer::one_second( ) + { + if (is_busy( )) + --wash_time_left; + } + + + void washer::start_washing( ) + // Library facilities used: cassert + { + assert(!is_busy( )); + wash_time_left = seconds_for_wash; + } +} diff --git a/chapter8/washing.h b/chapter8/washing.h new file mode 100644 index 0000000..d019fba --- /dev/null +++ b/chapter8/washing.h @@ -0,0 +1,113 @@ +// FILE: washing.h (part of the namespace main_savitch_8A) +// CLASSES PROVIDED: bool_source, averager, washer. +// +// CONSTRUCTOR for the bool_source class: +// bool_source(double p = 0.5) +// Precondition: 0 <= p <= 1. +// Postcondition: The bool_source has been initialized so that p is the +// approximate probability of returning true in any subsequent activation +// of query( ). +// +// CONSTANT MEMBER FUNCTION for the bool_source class: +// bool query( ) const +// Postcondition: The return value is either true or false, with the +// probability of a true value being approximately p (from the constructor). +// +// CONSTRUCTOR for the averager class: +// averager( ) +// Postcondition: The averager has been initialized so that it +// is ready to accept a sequence of numbers to average. +// +// MODIFICATION MEMBER FUNCTION for the averager class: +// void next_number(double value) +// Postcondition: The averager has accepted value as the next +// number in the sequence of numbers which it is averaging. +// +// CONSTANT MEMBER FUNCTIONS for the averager class: +// size_t how_many_numbers( ) const +// Postcondition: The value returned is a count of how many +// times next_number has been activated. +// +// double average( ) const +// Precondition: how_many_numbers > 0. +// Postcondition: The value returned is the average of all the +// numbers which have been given to the averager. +// +// CONSTRUCTOR for the washer class: +// washer(unsigned int s = 60) +// Precondition: The value of s is the number of seconds needed for +// the completion of one wash cycle. +// Postcondition: The washer has been initialized so that all +// other member functions may be used. +// +// MODIFICATION MEMBER FUNCTIONS for the washer class: +// void one_second( ) +// Postcondition: The washer has recorded (and simulated) the +// passage of one more second of time. +// +// void start_washing( ) +// Precondition: The washer is not busy. +// Postcondition: The washer has started simulating one wash +// cycle. Therefore, is_busy( ) will return true until +// the required number of simulated seconds have occured. +// +// CONSTANT MEMBER FUNCTIONS for the washer class: +// bool is_busy( ) const +// Postcondition: Return value is true if the washer is busy +// (in a wash cycle); otherwise the return value is false. +// +// VALUE SEMANTICS for the bool_source, averager, and washer classes: +// Assignments and the copy constructor may be used with the three classes. +// + +#ifndef MAIN_SAVITCH_WASHING_H +#define MAIN_SAVITCH_WASHING_H +#include // Provides std::size_t + +namespace main_savitch_8A +{ + class bool_source + { + public: + // CONSTRUCTOR + bool_source(double p = 0.5); + // CONSTANT function + bool query( ) const; + private: + double probability; // Probability of query( ) returning true + }; + + class averager + { + public: + // CONSTRUCTOR + averager( ); + // MODIFICATION function + void next_number(double value); + // CONSTANT functions + std::size_t how_many_numbers( ) const { return count; } + double average( ) const; + private: + std::size_t count; // How many numbers have been given to the averager + double sum; // Sum of all the numbers given to the averager + }; + + class washer + { + public: + // CONSTRUCTOR + washer(unsigned int s = 60); + // MODIFICATION functions + void one_second( ); + void start_washing( ); + // CONSTANT function + bool is_busy( ) const { return (wash_time_left > 0); } + private: + unsigned int seconds_for_wash; // Seconds for a single wash + unsigned int wash_time_left; // Seconds until washer no longer busy + }; +} + +#endif + + -- cgit v1.2.3