Updating before template node branch

5 files changed, 342 insertions, 20 deletions

diff --git a/CST 126/Homework 3/Homework 3.vcxproj b/CST 126/Homework 3/Homework 3.vcxproj
index 21ecb73..e0dff7d 100644
--- a/CST 126/Homework 3/Homework 3.vcxproj
+++ b/CST 126/Homework 3/Homework 3.vcxproj
@@ -17,7 +17,6 @@
       <Configuration>Release</Configuration>
       <Platform>x64</Platform>
     </ProjectConfiguration>
-
   </ItemGroup>
   <PropertyGroup Label="Globals">
     <VCProjectVersion>17.0</VCProjectVersion>
@@ -53,27 +52,24 @@
     <WholeProgramOptimization>true</WholeProgramOptimization>
     <CharacterSet>Unicode</CharacterSet>
   </PropertyGroup>
-
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
   <ImportGroup Label="ExtensionSettings">
   </ImportGroup>
-  <ImportGroup Label="Shared" >
+  <ImportGroup Label="Shared">
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
   </ImportGroup>
-    <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
-      <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
-    </ImportGroup>
-    <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
-      <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
-    </ImportGroup>
-    <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
-      <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
-    </ImportGroup>
-    <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
-      <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
-    </ImportGroup>
-
   <PropertyGroup Label="UserMacros" />
-
   <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
     <ClCompile>
       <WarningLevel>Level3</WarningLevel>
@@ -130,9 +126,14 @@
       <GenerateDebugInformation>true</GenerateDebugInformation>
     </Link>
   </ItemDefinitionGroup>
-
-  <ItemGroup></ItemGroup>
+  <ItemGroup>
+    <ClInclude Include="node.hpp" />
+    <ClInclude Include="SinglyLinkedList.hpp" />
+  </ItemGroup>
+  <ItemGroup>
+    <ClCompile Include="program.cpp" />
+  </ItemGroup>
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
   <ImportGroup Label="ExtensionTargets">
   </ImportGroup>
-</Project>
+</Project>
\ No newline at end of file
diff --git a/CST 126/Homework 3/Homework 3.vcxproj.filters b/CST 126/Homework 3/Homework 3.vcxproj.filters
index a8a6563..b27b6ea 100644
--- a/CST 126/Homework 3/Homework 3.vcxproj.filters
+++ b/CST 126/Homework 3/Homework 3.vcxproj.filters
@@ -14,4 +14,17 @@
       <Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms</Extensions>
     </Filter>
   </ItemGroup>
+  <ItemGroup>
+    <ClInclude Include="SinglyLinkedList.hpp">
+      <Filter>Header Files</Filter>
+    </ClInclude>
+    <ClInclude Include="node.hpp">
+      <Filter>Header Files</Filter>
+    </ClInclude>
+  </ItemGroup>
+  <ItemGroup>
+    <ClCompile Include="program.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
+  </ItemGroup>
 </Project>
\ No newline at end of file
diff --git a/CST 126/Homework 3/SinglyLinkedList.hpp b/CST 126/Homework 3/SinglyLinkedList.hpp
new file mode 100644
index 0000000..e28c142
--- /dev/null
+++ b/CST 126/Homework 3/SinglyLinkedList.hpp
@@ -0,0 +1,256 @@
+#ifndef SINGLY_LINKED_LIST_HPP
+#define SINGLY_LINKED_LIST_HPP
+
+struct ListNode
+{
+	int _data{ 0 };
+	ListNode* _next{ nullptr };
+};
+
+struct SinglyLinkedList
+{
+	size_t _size{ 0 };
+	ListNode* _head{ nullptr };
+};
+
+bool Append(SinglyLinkedList* list, ListNode* node);
+bool Prepend(SinglyLinkedList* list, ListNode* node);
+bool RemoveFirst(SinglyLinkedList* list);
+bool RemoveLast(SinglyLinkedList* list);
+bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node);
+bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node);
+bool Clear(SinglyLinkedList* list);
+ListNode* Extract(SinglyLinkedList* list, const int data);
+bool Empty(SinglyLinkedList* list);
+bool Remove(SinglyLinkedList* list, ListNode* node);
+
+//code
+bool Append(SinglyLinkedList* list, ListNode* node )
+{
+	//we have a list
+	//we need to add a node to the end of the list
+
+	//empty
+	if (Empty(list)) 
+	{
+		list->_head = node;
+		list->_size++;
+		return true;
+	}
+	//Append head
+	if(list->_size == 1)
+	{
+		list->_head->_next = node;
+		list->_size++;
+		return true;
+	}
+	//Down the list
+	ListNode* travel = nullptr;
+	for(travel = list->_head; travel->_next != nullptr;)
+	{
+		travel = travel->_next;
+	}
+	travel->_next = node;
+	list->_size++;
+	return true;
+}
+
+bool Prepend(SinglyLinkedList* list, ListNode* node) 
+{
+	if (Empty(list))
+	{
+		list->_head = node;
+		list->_size++;
+		return true;
+	}
+
+	node->_next = list->_head;
+	list->_head = node;
+
+	list->_size++;
+	return true;
+}
+
+bool RemoveFirst(SinglyLinkedList* list)
+{
+	//check if zero size
+	if (Empty(list)) return true;
+
+	if(list->_size == 1)
+	{
+
+		list->_head = nullptr;
+	}
+	else
+	{
+		ListNode* prev = list->_head;
+		list->_head = list->_head->_next;
+		prev->_next = nullptr;
+	}
+
+	list->_size--;
+
+	return true;
+}
+
+bool RemoveLast(SinglyLinkedList* list)
+{
+	if (Empty(list)) return true;
+
+	if (list->_size == 1)
+	{
+		list->_head = nullptr;
+		return true;
+	}
+	
+	ListNode* travel = list->_head;
+	while(travel->_next->_next != nullptr)
+	{
+		travel = travel->_next;
+	}
+	travel->_next = nullptr;
+	list->_size--;
+	return true;
+	
+}
+
+bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node)
+{
+	//first to find data
+	//thoughts? What if we are inserting at after end.
+	ListNode* travel;
+	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
+	{
+		travel = travel->_next;
+	}
+
+	if (travel->_next == nullptr) 
+	{
+		return Append(list, node);
+	}
+
+	node->_next = travel->_next;
+	travel->_next = node;
+	list->_size++;
+
+	//then insert after data
+	return true;
+}
+
+bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node)
+{
+	if (list->_head->_data == data)
+		return Prepend(list, node);
+
+	ListNode* travel;
+	for (travel = list->_head; travel->_next->_data != data;)
+	{
+		travel = travel->_next;
+	}
+
+	node->_next = travel->_next;
+	travel->_next = node;
+	list->_size++;
+
+	return true;
+	
+}
+
+bool Clear(SinglyLinkedList* list)
+{
+	//consider the head
+	//consider the size
+	//We have to detach every node from each other
+	//start at the head
+	//use a node* to track our position
+
+	if (list->_size == 0) return true;
+
+	ListNode* travel = list->_head;
+	ListNode* prev = travel;
+
+	do
+	{
+		prev = travel;
+		travel = travel->_next;
+		prev->_data = 0;
+		prev->_next = nullptr;
+		
+	} while (travel != nullptr && travel->_next != nullptr);
+
+	list->_size = 0;
+	list->_head = nullptr;
+
+	return true;
+}
+
+ListNode* Extract(SinglyLinkedList* list, const int data)
+{
+	//check if empty, shortcut return
+	ListNode* temp = new ListNode{0, nullptr};
+	ListNode* travel = nullptr;
+
+	if (Empty(list))
+	{
+		return temp;
+	}
+	//Read through list
+	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
+	{
+		travel = travel->_next;
+	}
+	//find the data
+		//pointer to the node
+	temp->_data = travel->_data;
+		//remove node from list
+	if(Remove(list, travel))
+	{
+		return temp;
+	}
+	//or don't find data
+
+	return nullptr;
+}
+
+bool Remove(SinglyLinkedList* list, ListNode* node)
+{
+	//find the node
+	//Read through list
+	ListNode* travel = list->_head;
+	ListNode* prev = travel;
+
+	while(travel != node)
+	{
+		prev = travel;
+
+		travel = travel->_next;
+	}
+	//if first, remove first
+	if(travel == list->_head)
+	{
+		return RemoveFirst(list);
+	}
+	//if last, remove last
+	if(travel->_next == nullptr)
+	{
+		return RemoveLast(list);
+	}
+	//else in middle
+	//remove travel's node
+	//will need previous node
+		//to set previous's next to travel's next
+	prev->_next = travel->_next; //fixing pointer between nodes
+									//removes dangling pointer from prev to travel
+
+	//delete travel
+	travel->_next = nullptr;
+	travel->_data = 0;
+	list->_size--;
+}
+
+bool Empty(SinglyLinkedList* list)
+{
+	return (list->_size == 0 && list->_head == nullptr);
+}
+
+#endif // !SINGLY_LINKED_LIST_HPP
\ No newline at end of file
diff --git a/CST 126/Homework 3/node.hpp b/CST 126/Homework 3/node.hpp
new file mode 100644
index 0000000..ac89141
--- /dev/null
+++ b/CST 126/Homework 3/node.hpp
@@ -0,0 +1,42 @@
+#ifndef NODE_HPP
+#define NODE_HPP
+
+
+
+
+namespace CST126
+{
+	template<typname T>
+	class Node
+	{
+	public:
+		Node() = default;
+		Node(const T& data);
+
+		~Node() = default;
+
+		T& Data();
+		T Value() const;
+		void Data(const T& data);
+
+
+
+	private:
+		T _data;
+	};
+
+
+
+
+	template<typename T>
+	T Node<T>::Data()
+	{
+		return T();
+	}
+
+	template<typename T>
+	void Node<T>::Data(T data)
+	{
+		_data = data;
+	}
+}
\ No newline at end of file
diff --git a/CST 126/Homework 3/program.cpp b/CST 126/Homework 3/program.cpp
new file mode 100644
index 0000000..4d6c025
--- /dev/null
+++ b/CST 126/Homework 3/program.cpp
@@ -0,0 +1,10 @@
+
+
+
+
+void main()
+{
+
+
+
+}
\ No newline at end of file