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 /chapter8 | |
| download | dscode-main.tar.xz dscode-main.zip | |
Diffstat (limited to 'chapter8')
| -rw-r--r-- | chapter8/carwash.cxx | 73 | ||||
| -rw-r--r-- | chapter8/ch8queueFiles.zip | bin | 0 -> 12208 bytes | |||
| -rw-r--r-- | chapter8/node2.h | 270 | ||||
| -rw-r--r-- | chapter8/node2.template | 128 | ||||
| -rw-r--r-- | chapter8/pal.cxx | 44 | ||||
| -rw-r--r-- | chapter8/pal.exe | bin | 0 -> 95181 bytes | |||
| -rw-r--r-- | chapter8/pal.o | bin | 0 -> 64111 bytes | |||
| -rw-r--r-- | chapter8/queue1.h | 81 | ||||
| -rw-r--r-- | chapter8/queue1.template | 55 | ||||
| -rw-r--r-- | chapter8/queue2.h | 76 | ||||
| -rw-r--r-- | chapter8/queue2.template | 88 | ||||
| -rw-r--r-- | chapter8/queueFiles.zip | bin | 0 -> 8274 bytes | |||
| -rw-r--r-- | chapter8/washing.cxx | 80 | ||||
| -rw-r--r-- | chapter8/washing.h | 113 |
14 files changed, 1008 insertions, 0 deletions
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 <iostream> // Provides cout
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <queue> // 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<unsigned int> 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 Binary files differnew file mode 100644 index 0000000..27a7522 --- /dev/null +++ b/chapter8/ch8queueFiles.zip 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<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);
+
+ // 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 Item>
+ class node_iterator
+ : public std::iterator<std::forward_iterator_tag, Item>
+ {
+ public:
+ node_iterator(node<Item>* 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<Item>* current;
+ };
+
+ template <class Item>
+ class const_node_iterator
+ : public std::iterator<std::forward_iterator_tag, const Item>
+ {
+ public:
+ const_node_iterator(const node<Item>* 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<Item>* 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 <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;
+ }
+}
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 <cassert> // Provides assert
+#include <cctype> // Provides isalpha, toupper
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <iostream> // Provides cout, cin, peek
+#include <queue> // Provides the queue template class
+#include <stack> // Provides the stack template class
+using namespace std;
+
+int main( )
+{
+ queue<char> q;
+ stack<char> s;
+ char letter;
+ queue<char>::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 Binary files differnew file mode 100644 index 0000000..bc9a38f --- /dev/null +++ b/chapter8/pal.exe diff --git a/chapter8/pal.o b/chapter8/pal.o Binary files differnew file mode 100644 index 0000000..8bf34b4 --- /dev/null +++ b/chapter8/pal.o 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<Item> (a queue of items)
+//
+// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack<Item> class:
+// The template parameter, Item, is the data type of the items in the queue,
+// also defined as queue<Item>::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<Item>::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<Item>::value_type and queue<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 queue<Item> template class:
+// queue( )
+// Postcondition: The queue has been initialized as an empty queue.
+//
+// MODIFICATION MEMBER FUNCTIONS for the queue<Item> 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<Item> 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<Item> template class:
+// Assignments and the copy constructor may be used with queue<Item> objects.
+
+#ifndef MAIN_SAVITCH_QUEUE1_H
+#define MAIN_SAVITCH_QUEUE1_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_8B
+{
+ template <class Item>
+ 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<Item> (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 <cassert> // Provides assert
+
+namespace main_savitch_8B
+{
+ template <class Item>
+ const typename queue<Item>::size_type queue<Item>::CAPACITY;
+
+ template <class Item>
+ queue<Item>::queue( )
+ {
+ count = 0;
+ first = 0;
+ last = CAPACITY - 1;
+ }
+
+ template <class Item>
+ Item queue<Item>::front( ) const
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ return data[first];
+ }
+
+ template <class Item>
+ void queue<Item>::pop( )
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ first = next_index(first);
+ --count;
+ }
+
+ template <class Item>
+ void queue<Item>::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<Item> (a queue of items)
+//
+// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack<Item> class:
+// The template parameter, Item, is the data type of the items in the queue,
+// also defined as queue<Item>::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<Item>::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<Item>::value_type and queue<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 queue<Item> template class:
+// queue( )
+// Postcondition: The queue has been initialized as an empty queue.
+//
+// MODIFICATION MEMBER FUNCTIONS for the queue<Item> 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<Item> 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<Item> template class:
+// Assignments and the copy constructor may be used with queue<Item> objects.
+
+#ifndef MAIN_SAVITCH_QUEUE2_H // Prevent duplicate definition
+#define MAIN_SAVITCH_QUEUE2_H
+#include <cstdlib> // Provides std::size_t
+#include "node2.h" // Node template class
+
+namespace main_savitch_8C
+{
+ template <class Item>
+ class queue
+ {
+ public:
+ // TYPEDEFS
+ typedef std::size_t size_type;
+ typedef Item value_type;
+ // CONSTRUCTORS and DESTRUCTOR
+ queue( );
+ queue(const queue<Item>& source);
+ ~queue( );
+ // MODIFICATION MEMBER FUNCTIONS
+ void pop( );
+ void push(const Item& entry);
+ void operator =(const queue<Item>& source);
+ // CONSTANT MEMBER FUNCTIONS
+ bool empty( ) const { return (count == 0); }
+ Item front( ) const;
+ size_type size( ) const { return count; }
+ private:
+ main_savitch_6B::node<Item> *front_ptr; // head_ptr
+ main_savitch_6B::node<Item> *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<Item> (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 <cassert> // Provides assert
+#include "node2.h" // Node template class
+
+namespace main_savitch_8C
+{
+ template <class Item>
+ queue<Item>::queue( )
+ {
+ count = 0;
+ front_ptr = NULL;
+ rear_ptr = NULL;
+ }
+
+ template <class Item>
+ queue<Item>::queue(const queue<Item>& source)
+ // Library facilities used: node2.h
+ {
+ count = source.count;
+ list_copy(source.front_ptr, front_ptr, rear_ptr);
+ }
+
+ template <class Item>
+ queue<Item>::~queue( )
+ {
+ list_clear(front_ptr);
+ }
+
+ template <class Item>
+ void queue<Item>::operator =(const queue<Item>& 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 <class Item>
+ Item queue<Item>::front( ) const
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ return front_ptr->data( );
+ }
+
+ template <class Item>
+ void queue<Item>::pop( )
+ // Library facilities used: cassert, node2.h
+ {
+ assert(!empty( ));
+ list_head_remove(front_ptr);
+ --count;
+ }
+
+ template <class Item>
+ void queue<Item>::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 Binary files differnew file mode 100644 index 0000000..b1ec1a5 --- /dev/null +++ b/chapter8/queueFiles.zip 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 <cassert> // Provides assert
+#include <cstdlib> // 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 <cstdlib> // 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
+
+
|