diff options
| author | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
|---|---|---|
| committer | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
| commit | c1b6ffe70bd281c6c230fd63fabcaac2aff47514 (patch) | |
| tree | e8af3b1782a7cd0754590ed618fddc1bdb9b7385 /chapter6/bag5.template | |
| download | dscode-main.tar.xz dscode-main.zip | |
Diffstat (limited to 'chapter6/bag5.template')
| -rw-r--r-- | chapter6/bag5.template | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/chapter6/bag5.template b/chapter6/bag5.template new file mode 100644 index 0000000..9d22436 --- /dev/null +++ b/chapter6/bag5.template @@ -0,0 +1,164 @@ +// FILE: bag5.template
+// CLASS implemented: bag (see bag5.h for documentation)
+// NOTE:
+// Since bag is a template class, this file is included in node2.h.
+// INVARIANT for the bag class:
+// 1. The items in the bag are stored on a linked list;
+// 2. The head pointer of the list is stored in the member variable head_ptr;
+// 3. The total number of items in the list is stored in the member variable
+// many_nodes.
+
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides NULL, rand
+#include "node2.h" // Provides node
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ bag<Item>::bag( )
+ // Library facilities used: cstdlib
+ {
+ head_ptr = NULL;
+ many_nodes = 0;
+ }
+
+ template <class Item>
+ bag<Item>::bag(const bag<Item>& source)
+ // Library facilities used: node2.h
+ {
+ node<Item> *tail_ptr; // Needed for argument of list_copy
+
+ list_copy(source.head_ptr, head_ptr, tail_ptr);
+ many_nodes = source.many_nodes;
+ }
+
+ template <class Item>
+ bag<Item>::~bag( )
+ // Library facilities used: node2.h
+ {
+ list_clear(head_ptr);
+ many_nodes = 0;
+ }
+
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::count(const Item& target) const
+ // Library facilities used: cstdlib, node2.h
+ {
+ size_type answer;
+ const node<Item> *cursor;
+
+ answer = 0;
+ cursor = list_search(head_ptr, target);
+ while (cursor != NULL)
+ {
+ // Each time that cursor is not NULL, we have another occurrence of
+ // target, so we add one to answer, and move cursor to the next
+ // occurrence of the target.
+ ++answer;
+ cursor = cursor->link( );
+ cursor = list_search(cursor, target);
+ }
+ return answer;
+ }
+
+ template <class Item>
+ typename bag<Item>::size_type bag<Item>::erase(const Item& target)
+ // Library facilities used: cstdlib, node2.h
+ {
+ size_type answer = 0;
+ node<Item> *target_ptr;
+
+ target_ptr = list_search(head_ptr, target);
+ while (target_ptr != NULL)
+ {
+ // Each time that target_ptr is not NULL, we have another occurrence
+ // of target. We remove this target using the same technique that
+ // was used in erase_one.
+ ++answer;
+ target_ptr->set_data( head_ptr->data( ) );
+ target_ptr = target_ptr->link( );
+ target_ptr = list_search(target_ptr, target);
+ list_head_remove(head_ptr);
+ }
+ return answer;
+ }
+
+ template <class Item>
+ bool bag<Item>::erase_one(const Item& target)
+ // Library facilities used: cstdlib, node2.h
+ {
+ node<Item> *target_ptr;
+
+ target_ptr = list_search(head_ptr, target);
+ if (target_ptr == NULL)
+ return false; // target isn't in the bag, so no work to do
+ target_ptr->set_data( head_ptr->data( ) );
+ list_head_remove(head_ptr);
+ --many_nodes;
+ return true;
+ }
+
+ template <class Item>
+ Item bag<Item>::grab( ) const
+ // Library facilities used: cassert, cstdlib, node2.h
+ {
+ size_type i;
+ const node<Item> *cursor;
+
+ assert(size( ) > 0);
+ i = (std::rand( ) % size( )) + 1;
+ cursor = list_locate(head_ptr, i);
+ return cursor->data( );
+ }
+
+ template <class Item>
+ void bag<Item>::insert(const Item& entry)
+ // Library facilities used: node2.h
+ {
+ list_head_insert(head_ptr, entry);
+ ++many_nodes;
+ }
+
+ template <class Item>
+ void bag<Item>::operator +=(const bag<Item>& addend)
+ // Library facilities used: node2.h
+ {
+ node<Item> *copy_head_ptr;
+ node<Item> *copy_tail_ptr;
+
+ if (addend.many_nodes > 0)
+ {
+ list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
+ copy_tail_ptr->set_link( head_ptr );
+ head_ptr = copy_head_ptr;
+ many_nodes += addend.many_nodes;
+ }
+ }
+
+ template <class Item>
+ void bag<Item>::operator =(const bag<Item>& source)
+ // Library facilities used: node2.h
+ {
+ node<Item> *tail_ptr; // Needed for argument to list_copy
+
+ if (this == &source)
+ return;
+
+ list_clear(head_ptr);
+ many_nodes = 0;
+
+ list_copy(source.head_ptr, head_ptr, tail_ptr);
+ many_nodes = source.many_nodes;
+ }
+
+ template <class Item>
+ bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
+ {
+ bag<Item> answer;
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+
+}
|