Post-class 02/09

4 files changed, 583 insertions, 11 deletions

diff --git a/02-04.md b/02-04.md
index 6f8cf25..96042bb 100644
--- a/02-04.md
+++ b/02-04.md
@@ -135,17 +135,17 @@ void bag::operator +=(const bag& addend){
 
 ```
 //FUNCTIONS for the linked list toolkit
-std::size_t list_length(const node *head_ptr);
-void list_head_insert(node *& head_ptr, const node::value_type& entry);
-void list_insert(node *previous_ptr, const node::value_type& entry);
-node *list_search(node *head_ptr, const node::value_type& target);
-const node* list_search(const node* head_ptr, const node::value_type& target);
-node *list_locate(node *head_ptr, std::size_t position);
-const node *list_locate(const node *head_ptr, std::size_t position);
-void list_head_remove(node *& head_ptr);
-void list_remove(node *previous_ptr);
-void list_clear(node *& head_ptr);
-void list_copy(const node *source_ptr, node *& head_ptr, node *& tail_ptr);
+std::size_t list_length(const node *head_ptr);                                 //length of the list
+void list_head_insert(node *& head_ptr, const node::value_type& entry);        //insert a new head
+void list_insert(node *previous_ptr, const node::value_type& entry);           //insert a new node after the given node
+node *list_search(node *head_ptr, const node::value_type& target);             //search for a value in the list
+const node* list_search(const node* head_ptr, const node::value_type& target); //search for a node with a certain value in the list
+node *list_locate(node *head_ptr, std::size_t position);                       //return the nth node in the list
+const node *list_locate(const node *head_ptr, std::size_t position);           //const version of previous function
+void list_head_remove(node *& head_ptr);                                       //remove head pointer (head->next becomes the head)
+void list_remove(node *previous_ptr);                                          //remove the pointer after the given pointer
+void list_clear(node *& head_ptr);                                             //remove all nodes in list
+void list_copy(const node *source_ptr, node *& head_ptr, node *& tail_ptr);    //create a copy of a given list
 ```
 
 ### Parameters for Linked Lists
@@ -310,3 +310,7 @@ void list_head_insert(node *& head_ptr, const node::value_type& entry){
 - The linked list toolkit also provides for inserting a new node elsewhere
 - It is easy to remove a node at the front of a list
 - The linked list toolkit also provides a function for removing a node elsewhere - you should read about this function and the other functions of the toolkit
+
+---
+
+[02/09 ->](02-09.md)
diff --git a/02-09.md b/02-09.md
new file mode 100644
index 0000000..f8e0ed9
--- /dev/null
+++ b/02-09.md
@@ -0,0 +1,260 @@
+[\<- 02/04](02-04.md)
+
+# Dynamic Arrays vs. Linked Lists vs. Double Linked Lists
+
+- Many classes can be implemented with either dynamic arrays or linked lists
+- **Which approach is better?**
+
+## Dynamic Array
+
+### Arrays are better at random access
+
+- The term **random access** refers to examining or changing an arbitrary element that is **specified by its position** in a list
+- For example:
+	- What is the 2nd item in the list?
+	- Change the item at position 16 to 4
+- These are **constant time operations** for an array (or dynamic array)
+- In a **linked list**, a search for an item must begin at the head and will take **O(N)** time
+
+### Resizing can be inefficient for a dynamic array
+
+- This is because:
+	- New memory must be allocated
+	- The items are then copied from the old memory to the new memory
+	- The old memory is deleted
+- When the eventual capacity is unknown and a program must continually adjust the capacity, a linked list has advantages
+
+## Linked Lists
+
+### Linked lists are better at insertions/deletions at a cursor
+
+- If class operations take place at a cursor, then a linked list is better than a dynamic array
+- Insertions and deletions at a cursor are generally **linear time (O(N)) for an array** (since items that are after the cursor must be shifted)
+- But these operations are **constant time operations (O(1))** for a linked list
+
+## Doubly Linked Lists
+
+### Doubly linked lists are better for a two-way cursor
+
+- Sometimes list operations require a cursor that can move forward and backward through a list
+	- A **two-way cursor**
+- **Double linked list** is like a simple linked list, except that **each node contains two pointers**: one pointing to the next node and one pointing to the previous node
+
+![diagram](02-09_1.png)
+
+- A possible definition for a doubly linked list of items:
+
+```
+class dnode{
+	public:
+		typedef ____ value_type;
+		...
+
+	private:
+		value_type data_field;
+		dnode *link_fore;
+		dnode *link_back;
+};
+```
+
+- In C++, this is called the `std::list`
+- `link_back` fields points to the previous node
+- `link_fore` points to the next node in the list
+
+### A Class for a Node in a Doubly Linked List
+
+```
+#ifndef SCU_COEN79_DNODE_H
+#define SCU_COEN79_DNODE_H
+#include <cstdlib> //provides size_t and NULL
+namespace scu_coen79_5{
+	class dnode{
+		public:
+			// TYPEDEF
+			typedef double value_type;
+
+			//CONSTRUCTOR
+			dnode(const value_type& init_data = value_type(), dnode *init_fore = NULL, dnode *init_back = NULL){
+				data_field = init_data;
+				link_fore = init_fore;
+				link_back = init_back;
+			}
+
+			//Member functions to set the data and link fields:
+			void set_data(const value_type& new_data) {data_field = new_data;};
+			void set_fore(dnoe *new_fore) {link_fore = new_fore;};
+			void set_back(dnode *new_back) {link_back = new_back;};
+
+			//Const member function to retrieve the current data:
+			value_type data() const {return data_field;};
+
+			//Two slightly different member functions to retrieve each current link:
+			const dnode *fore() const {return link_fore;};
+			dnode *fore() {return link_fore;};
+			const dnode *back() const { return link_back;};
+			dnode *back() {return link_back;};
+
+		private:
+			value_type data_field;
+			dnode *link_fore;
+			dnode *link_back;
+	};
+}
+
+#endif
+```
+
+## Guidelines for Choosing Between a Dynamic Array and a Linked List
+
+|Case                                |Data Structure     |
+|------------------------------------|-------------------|
+|Frequent random access operations   |Use a dynamic array|
+|Operations occur at a cursor        |Use a linked list  |
+|Operations occur at a two-way cursor|Use a linked list  |
+|Frequent resizing may be needed     |Use a linked list  |
+
+## Summary
+
+- A **linked list** consists of node
+	- Each **node** contain data and a pointer to the next node in the list
+- A linked list is accessed througha **head pointer** that points to the *head node*
+- A linked list may have a **tail pointer** that points to the last node
+- A **doubly linked list** has nodes with two pointers: one to the next node and one to the previous node
+	- Enables a cursor to move forward and backward
+- Containers can be implemented in many different ways, such as by using a dynamic array or using a linked list
+- Arrays are better at **random access**
+- Linked lists are better at **insertions/removals at a cursor**
+
+---
+
+# Template Functions
+
+- Introduction of templates, which are C++ feature that easily permits the reuse of existing code for new purposes
+- Shows how to implement and use the simplest kinds of templates: **template functions**
+
+## Finding the Maximum of Two Numbers
+
+### Finding the Maximum of Two Integers
+
+- Here's a small function that you might write to find the maximum of two integers
+
+```
+int maximum(int a, int b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### Finding the Maximum of Two Doubles
+
+- Here's a small function that you might write to find the maximum of two double numbers
+
+```
+int maximum(double a, double b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### Finding the Maximum of Two Knafns
+
+- Here's a small function that you might write to find the maximum of two knafns
+
+```
+int maximum(knafn a, knafn b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### One Hundred Million Functions...
+
+- Suppose your program uses 100,000,000 different data types, and you need maximum function for each...
+
+### A Template Function for Maximum
+
+- This template function can be used with many data types
+
+```
+template<typename Item>
+Item maximum(Item a, Item b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+- When you write a template function, you choose a data type for the function to depend upon...
+- A template prefix is also needed immediately before the function's implementation
+
+### Using a Template Function
+
+- Once a template function is defined, it may be used with any adequate data type in your program...
+
+```
+cout << maximum(1, 2);
+cout << maxiumum(1.3, 0.9);
+```
+
+## Multi Parameter Templates
+
+```
+int array_max(int data[], size_t n){
+	size_t i;
+	int answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
+
+### Solution 1
+
+```
+template <typename Item>
+Item array_max(Item data[], size_t n){
+	size_t i;
+	Item answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
+
+- What are the problems?
+	- `size_t` is not generic, so passing, for example, a `const size_t` will return an error
+
+### Examples
+
+```
+const size_t SIZE = 5;
+double data[SIZE];
+//...
+
+cout << array_max(data, SIZE);
+cout << array_max(data, 5);
+
+template <typename Item>
+Item array_max(Item data[], size_t n);
+```
+
+### Solution 2
+
+```
+template <typename Item, typename Sizetype>
+Item array_max(Item data[], Sizetype n){
+	size_t i;
+	Item answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
diff --git a/02-09_1.png b/02-09_1.png
new file mode 100644
index 0000000..4bb4eeb
--- /dev/null
+++ b/02-09_1.png
diff --git a/02-11.md b/02-11.md
new file mode 100644
index 0000000..5de7745
--- /dev/null
+++ b/02-11.md
@@ -0,0 +1,308 @@
+# Template Functions
+
+- Introduction of templates, which are C++ feature that easily permits the reuse of existing code for new purposes
+- Shows how to implement and use the simplest kinds of templates: **template functions**
+
+## Finding the Maximum of Two Numbers
+
+### Finding the Maximum of Two Integers
+
+- Here's a small function that you might write to find the maximum of two integers
+
+```
+int maximum(int a, int b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### Finding the Maximum of Two Doubles
+
+- Here's a small function that you might write to find the maximum of two double numbers
+
+```
+int maximum(double a, double b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### Finding the Maximum of Two Knafns
+
+- Here's a small function that you might write to find the maximum of two knafns
+
+```
+int maximum(knafn a, knafn b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+### One Hundred Million Functions...
+
+- Suppose your program uses 100,000,000 different data types, and you need maximum function for each...
+
+### A Template Function for Maximum
+
+- This template function can be used with many data types
+
+```
+template<typename Item>
+Item maximum(Item a, Item b){
+	if(a > b) return a;
+	else return b;
+}
+```
+
+- When you write a template function, you choose a data type for the function to depend upon...
+- A template prefix is also needed immediately before the function's implementation
+
+### Using a Template Function
+
+- Once a template function is defined, it may be used with any adequate data type in your program...
+
+```
+cout << maximum(1, 2);
+cout << maxiumum(1.3, 0.9);
+```
+
+## Multi Parameter Templates
+
+```
+int array_max(int data[], size_t n){
+	size_t i;
+	int answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
+
+### Solution 1
+
+```
+template <typename Item>
+Item array_max(Item data[], size_t n){
+	size_t i;
+	Item answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
+
+- What are the problems?
+	- `size_t` is not generic, so passing, for example, a `const size_t` will return an error
+
+### Examples
+
+```
+const size_t SIZE = 5;
+double data[SIZE];
+//...
+
+cout << array_max(data, SIZE);
+cout << array_max(data, 5);
+
+template <typename Item>
+Item array_max(Item data[], size_t n);
+```
+
+### Solution 2
+
+```
+template <typename Item, typename Sizetype>
+Item array_max(Item data[], Sizetype n){
+	size_t i;
+	Item answer;
+
+	assert(n > 0);
+	answer = data[0];
+	for(i = 1; i < n; i++){
+		if(data[i] > answer) answer = data[i];
+	return answer;
+}
+```
+
+---
+
+# Template Classes
+
+- A template function is a function that depends on an underlying data type
+- In a similar way, when a class depends on an underlying data type, the class can be implemented as a **template class**
+- For example, a single program can use a bag of integers, and a bag of characters, and a bag of strings, and...
+- You do not have to determine the data type of a data structure when developing a code
+
+## Bag Example
+
+### Syntax For Template Classes
+
+```
+class bag{
+	public:
+		typedef int value_type;
+		typedef size_t size_type;
+		...
+```
+
+```
+template <typename Item>
+class bag{
+	public:
+		...
+}
+```
+
+- `template <typename Item>` is the template prefix, and it warns the compiler that the following definition will use an unspecified data type called `Item`
+
+### Template Class Functions
+
+- The bag's `value_type` is now dependent on the `Item` type
+- **Outside the template class definition** some rules are required to tell the compiler about the dependency:
+	- The template prefix `template <class Item>` is placed immediately before each function prototype and definition
+	- Outside the template class definition, each use of the class name (such as `bag`) is changed to the template class name (such as `bag<Item>`)
+	- Within a class definition or within a member function, we can still use the bag's type names, such as `value_type` or `size_type`
+	- Outside of a member function, to use a type such as `bag<Item>::size_type`, we must add a new keyword `typename`, writing the expression `typename bag<Item>::size_type`
+
+### Example 1
+
+- For our **original class**, the function's implementation began this way:
+
+```
+bag operator +(const bag& b1, const bag& b2) ...
+```
+
+- For the **template class**, the start of the implementation is shown here:
+
+```
+template <class Item>
+bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2);
+...
+```
+
+### Example 2
+
+```
+bag::size_type bag::count(const value_type& target) const;
+```
+
+- Outside of a member function, you must put the keyword `typename` in front of any member of a template class is the name of a data type
+
+```
+template <class Item>
+typename bag<Item>::size_type bag<Item>::count (const Item& target) const;
+```
+
+## Summary: Item and typename
+
+|In the original Bag class          |In the template bag class    |
+|-----------------------------------|-----------------------------|
+|value_type                         |Item                         |
+|size_type (inside member function) |size_type                    |
+|size_type (outside member function)|typename bag<Item>::size_type|
+
+## Header File Changes
+
+- **In the header file**, you place the documentation and the prototypes of the functions; **then you must include the actual implementations of all the functions**
+	- The reason for the requirement is to make the compiler's job simpler
+	- **An alternative**: You can keep the implementations in a separate implementation file, but place an `include` directive at the bottom of the header file to pick up these implementations
+	- We include the following line at the end of the header file:
+
+```
+#include "bag4.template" //Include the implementation
+```
+
+## Do Not Place using Directive
+
+- Because a template class has its implementation included in the header file, we must not place any `using` directives in the implementation
+- Otherwiser, every program that uses our template class will inadvertently use the `using` directives
+
+## Bag Class Header and Implementation Files
+
+### Header File for the Bag Template Class
+
+```
+#ifndef SCU_COEN79_BAG4_H
+#define SCU_COEN79_BAG4_H
+#include <cstdlib> //Provides size_t
+
+namespace scu_coen79_6A{
+	template <class Item>
+	class bag{
+		public:
+			//TYPEDEFS and MEMBER CONSTANTS
+			typedef std::size_t size_type;
+			static const size_type DEFAULT_CAPACITY = 30;
+
+			//CONSTRUCTORS and DESTRUCTORS
+			bag(size_type initial_capacity = DEFAULT_CAPACITY);
+			bag(const bag& source);
+			~bag();
+
+			//MODIFICATION MEMBER FUNCTIONS
+			size_type erase(const Item& target);
+			bool erase_one(const Item& target);
+			void insert(const Item& entry);
+			void operator =(const bag& source);
+			void operator +=(const bag& addend);
+			void reserve(size_type capacity);
+
+			//CONSTANT MEMBER FUNCTIONS
+			size_type count(const Item& target) const;
+			Item grab() const;
+			size_type size() const {return used;};
+
+		private:
+			Item *data;         //Pointer to partially filled dynamic array
+			size_type used;     //How much of array is being used
+			size_type capacity; //Current capacity of the bag
+	};
+```
+
+- Inside the template class definition: Compiler knows about the dependency on `Item` type
+- Some rules are required outside of the template class definition:
+	- `template<class Item>` is placed immediately before each function prototype and definition
+	- Each use of the class name is changed to the template class name (`bag<Item>`)
+	- We should then include the implementation of the template in the header file (needed by most compilers)
+		- Instead of that: we keep the implementation in a separate file
+
+```
+//NONMEMBER FUNCTIONS
+//originally: bag operator +(const bag& b1, const bag& b2);
+
+template <class Item>
+bag<Item operator +(const bag<Item>& b1, const bag<Item>& b2);
+
+#include "bag4.template"
+#endif
+```
+
+### Implementation File for the Bag Template Class
+
+```
+#include <algorithm> //provides copy
+#include <cassert>   //provides assert
+#include <cstdlib>   //provides rand
+
+namespace SCU_COEN79_6A{
+
+	//MEMBER CONSTANTS
+	template <class Item>
+	const typename bag<Item>::size_type bag<Item>::DEFAULT_CAPACITY;
+```
+
+- Some compilers require the default parameters to be both in the prototype and implementation
+- Remeber that:
+	- To refer to `size_type` outside a member function: `typename bag<Item>::size_type`
+- Each definition is preceded by `template <class Item>`
+
+```
+	//CONSTRUCTORS
+	template <class Item>
+