diff options
Diffstat (limited to 'chapter5/bag3.cxx')
| -rw-r--r-- | chapter5/bag3.cxx | 154 |
1 files changed, 154 insertions, 0 deletions
diff --git a/chapter5/bag3.cxx b/chapter5/bag3.cxx new file mode 100644 index 0000000..ef3465d --- /dev/null +++ b/chapter5/bag3.cxx @@ -0,0 +1,154 @@ +// FILE: bag3.cxx
+// CLASS implemented: bag (see bag3.h for documentation)
+// INVARIANT for the bag ADT:
+// 1. The items in the bag are stored on a linked list;
+// 2. The head pointer of the list is stored in the member variable head_ptr;
+// 3. The total number of items in the list is stored in the member variable
+// many_nodes.
+
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides NULL, rand, size_t
+#include "node1.h" // Provides node and the linked list functions
+#include "bag3.h"
+using namespace std;
+
+namespace main_savitch_5
+{
+
+ bag::bag( )
+ // Library facilities used: cstdlib
+ {
+ head_ptr = NULL;
+ many_nodes = 0;
+ }
+
+ bag::bag(const bag& source)
+ // Library facilities used: node1.h
+ {
+ node *tail_ptr; // Needed for argument of list_copy
+
+ list_copy(source.head_ptr, head_ptr, tail_ptr);
+ many_nodes = source.many_nodes;
+ }
+
+ bag::~bag( )
+ // Library facilities used: node1.h
+ {
+ list_clear(head_ptr);
+ many_nodes = 0;
+ }
+
+ bag::size_type bag::count(const value_type& target) const
+ // Library facilities used: cstdlib, node1.h
+ {
+ size_type answer;
+ const node *cursor; // Use const node* since we don't change the nodes.
+
+ 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;
+ }
+
+ bag::size_type bag::erase(const value_type& target)
+ // Library facilities used: cstdlib, node1.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.
+ target_ptr->set_data( head_ptr->data( ) );
+ target_ptr = target_ptr->link( );
+ target_ptr = list_search(target_ptr, target);
+ list_head_remove(head_ptr);
+ --many_nodes;
+ ++answer;
+ }
+ return answer;
+ }
+
+ bool bag::erase_one(const value_type& target)
+ // Library facilities used: cstdlib, node1.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;
+ }
+
+ bag::value_type bag::grab( ) const
+ // Library facilities used: cassert, cstdlib, node1.h
+ {
+ size_type i;
+ const node *cursor; // Use const node* since we don't change the nodes.
+
+ assert(size( ) > 0);
+ i = (rand( ) % size( )) + 1;
+ cursor = list_locate(head_ptr, i);
+ return cursor->data( );
+ }
+
+ void bag::insert(const value_type& entry)
+ // Library facilities used: node1.h
+ {
+ list_head_insert(head_ptr, entry);
+ ++many_nodes;
+ }
+
+ void bag::operator +=(const bag& addend)
+ // Library facilities used: cstdlib, node1.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;
+ }
+ }
+
+ void bag::operator =(const bag& source)
+ // Library facilities used: node1.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;
+ }
+
+ bag operator +(const bag& b1, const bag& b2)
+ {
+ bag answer;
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+
+}
|