From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001
From: Fuwn <contact@fuwn.me>
Date: Sun, 7 Apr 2024 23:18:32 -0700
Subject: feat: initial commit

---
 chapter6/bag5.template | 164 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 164 insertions(+)
 create mode 100644 chapter6/bag5.template

(limited to 'chapter6/bag5.template')

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;
+    }
+
+}
-- 
cgit v1.2.3