Inital commitHEADmaster

3 files changed, 358 insertions, 0 deletions

diff --git a/labs/lab03_dll/DLinkedList.java b/labs/lab03_dll/DLinkedList.java
new file mode 100644
index 0000000..ef0f495
--- /dev/null
+++ b/labs/lab03_dll/DLinkedList.java
@@ -0,0 +1,190 @@
+
+public class DLinkedList<T>
+{
+	private Node firstNode;
+	private Node lastNode;
+	private Node middleNode;
+	private int numberOfEntries;
+	private int middlePosition;
+	
+	public DLinkedList()
+	{
+		firstNode = null;
+		lastNode = null;
+		middleNode = null;
+		numberOfEntries = 0;
+		middlePosition = 0;
+	}
+	
+	public void add(T newEntry)
+	{
+		if(firstNode == null)
+		{
+			firstNode = new Node(null, newEntry, null);
+			lastNode = firstNode;
+		}
+		else
+		{
+			Node newNode = new Node(lastNode, newEntry, null);
+			lastNode.next = newNode;
+			lastNode = newNode;
+		}
+		
+		numberOfEntries++;
+		
+		if(numberOfEntries % 2 == 1)
+		{
+			if(middleNode == null)
+			{
+				middleNode = firstNode;
+			}
+			else
+			{
+				middleNode = middleNode.next;
+			}
+			middlePosition++;
+		}
+	}
+	
+	public T getEntry(int givenPosition)
+	{
+		T result = null;
+		
+		if((givenPosition >= 1) && (givenPosition <= numberOfEntries))
+		{
+			result = (getNodeAt(givenPosition)).data;
+		}
+		
+		return result;
+	}
+	
+	private Node getNodeAt(int givenPosition)
+	{
+		Node currentNode = firstNode;
+		
+		for(int counter = 1; counter < givenPosition; counter++)
+		{
+			currentNode = currentNode.next;
+		}
+		
+		return currentNode;
+	}
+	
+	public T getEntry1(int givenPosition)
+	{
+		T result = null;
+		
+		if((givenPosition >= 1) && (givenPosition <= numberOfEntries))
+		{
+			result = (getNodeAt1(givenPosition)).data;
+		}
+		
+		return result;
+	}
+	
+	/**
+	 * Modify this method according to the Solution 1
+	 */
+	private Node getNodeAt1(int givenPosition)
+	{
+		if(givenPosition > middlePosition)
+		{
+			//start from end, go backwars
+			Node temp = lastNode;
+			for(int i = 0;i<numberOfEntries - givenPosition;i++)
+			{
+				temp = temp.previous;
+			}
+			return temp;
+		}
+		else
+		{
+			//start from front, forwards
+			Node temp = firstNode;
+			for(int i = 1; i < givenPosition;i++)
+			{
+				temp = temp.next;
+			}
+			return temp;
+		}
+	}
+
+	public T getEntry2(int givenPosition)
+	{
+		T result = null;
+		
+		if((givenPosition >= 1) && (givenPosition <= numberOfEntries))
+		{
+			result = (getNodeAt2(givenPosition)).data;
+		}
+		
+		return result;
+	}
+	
+	/**
+	 * Modify this method according to the Solution 2
+	 */
+	private Node getNodeAt2(int givenPosition)
+	{
+		if(givenPosition < middlePosition)
+		{
+			if(givenPosition < middlePosition/2)
+			{
+				//STart from the front, go forwards
+				Node temp = firstNode;
+				for(int i = 1;i < givenPosition;i++)
+				{
+					temp = temp.next;
+				}
+				return temp;
+			}
+			else
+			{
+				//Start from the middle, backwards
+				Node temp = middleNode;
+				for(int i = middlePosition; i > givenPosition;i--)
+				{
+					temp = temp.previous;
+				}
+				return temp;
+			}
+		}
+		else
+		{
+			if(givenPosition < numberOfEntries*(3.0/4))
+			{
+				//Start from the middle, go forwards
+				Node temp = middleNode;
+				for(int i = middlePosition; i < givenPosition; i++)
+				{
+					temp = temp.next;
+				}
+				return temp;
+			}
+			else
+			{
+				//Start from the end, go backwards
+				Node temp = lastNode;
+				for(int i = numberOfEntries; i >givenPosition; i--)
+				{
+					temp = temp.previous;
+				}
+				return temp;
+			}
+		}
+	}
+	
+	private class Node
+	{
+		private Node previous;
+		private T data;
+		private Node next;
+		
+		private Node(Node previousNode, T aData, Node nextNode)
+		{
+			previous = previousNode;
+			data = aData;
+			next = nextNode;
+		}
+	}
+}
diff --git a/labs/lab03_dll/DLinkedListTester.java b/labs/lab03_dll/DLinkedListTester.java
new file mode 100644
index 0000000..b583e84
--- /dev/null
+++ b/labs/lab03_dll/DLinkedListTester.java
@@ -0,0 +1,168 @@
+import java.util.Random;
+
+public class DLinkedListTester
+{
+	public static void main(String[] args)
+	{
+		// Construct a list and add entries
+		
+		int numberOfData = 100000;	// number of data to add to the list
+		int maxDataValue = 10000;	// number of different values to add to the list
+		int numSampling = 10000;	// number of calling the method getEntry
+		int dryRunReps = numSampling / 1000;
+		
+		DLinkedList<Integer> list = new DLinkedList<Integer>();
+		
+		Random rand = new Random();
+		rand.setSeed(System.nanoTime());
+		
+		System.out.print("Adding data into the list: ");
+		
+		for(int i = 0; i < numberOfData; i++)
+		{
+			list.add(rand.nextInt(maxDataValue));
+		}
+		
+		System.out.println("DONE");
+		
+		int[] positions = new int[numSampling];
+		int[] returnValues = new int[numSampling];
+
+		System.out.print("Dry run for the method getEntry(): ");
+		
+		// Dry run for the method getEntry1 (no timer)
+		// Also store all result for testing the method getEntry2()
+		
+		for(int i = 0; i < numSampling; i++)
+		{
+			int aPosition = rand.nextInt(numberOfData) + 1;
+			positions[i] = aPosition;
+			returnValues[i] = list.getEntry(aPosition);
+		}
+		
+		System.out.println("DONE");
+		
+		double startTime;	// Start time millisecond
+		double endTime;		// End time millisecond
+
+		System.out.print("Time the method getEntry(): ");
+		
+		// Timing the method getEntry()
+		
+		startTime = System.currentTimeMillis();
+		
+		for(int i = 0; i < numSampling; i++)
+		{
+			if(returnValues[i] != list.getEntry(positions[i]))
+			{
+				System.out.println("There is something wrong.");
+				System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + ".");
+				System.out.println("But the method getEntry(" + positions[i] + ") returns " + list.getEntry(positions[i]) + ".");
+				System.out.println("Fix the method getNodeAt() first.");
+				return;
+			}
+		}
+		
+		endTime = System.currentTimeMillis();
+		
+		double getEntryTime = endTime - startTime;
+		
+		System.out.println("DONE");
+
+		// getEntry1() - Solution 1
+
+		// Dry run (no timer)
+
+		System.out.print("Dry run for the method getEntry1(): ");
+		
+		for(int i = 0; i < dryRunReps; i++)
+		{
+			if(returnValues[i] != list.getEntry1(positions[i]))
+			{
+				System.out.println("There is something wrong.");
+				System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + ".");
+				System.out.println("But the method getEntry1(" + positions[i] + ") returns " + list.getEntry1(positions[i]) + ".");
+				System.out.println("Fix the method getNodeAt1() first.");
+				return;
+			}
+		}
+
+		System.out.println("DONE");
+		
+		// Timing the method getEntry1()
+		
+		System.out.print("Time the method getEntry1(): ");
+		
+		startTime = System.currentTimeMillis();
+		
+		for(int i = 0; i < numSampling; i++)
+		{
+			if(returnValues[i] != list.getEntry1(positions[i]))
+			{
+				System.out.println("There is something wrong.");
+				System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + ".");
+				System.out.println("But the method getEntry1(" + positions[i] + ") returns " + list.getEntry1(positions[i]) + ".");
+				System.out.println("Fix the method getNodeAt1() first.");
+				return;
+			}
+		}
+		
+		endTime = System.currentTimeMillis();
+		
+		double getEntry1Time = endTime - startTime;
+		
+		System.out.println("DONE");
+	
+		// getEntry2() - Solution 2
+
+		// Dry run (no timer)
+
+		System.out.print("Dry run for the method getEntry2(): ");
+		
+		for(int i = 0; i < dryRunReps; i++)
+		{
+			if(returnValues[i] != list.getEntry2(positions[i]))
+			{
+				System.out.println("There is something wrong.");
+				System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + ".");
+				System.out.println("But the method getEntry2(" + positions[i] + ") returns " + list.getEntry2(positions[i]) + ".");
+				System.out.println("Fix the method getNodeAt2() first.");
+				return;
+			}
+		}
+
+		System.out.println("DONE");
+		
+		// Timing the method getEntry2()
+		
+		System.out.print("Time the method getEntry2(): ");
+		
+		startTime = System.currentTimeMillis();
+		
+		for(int i = 0; i < numSampling; i++)
+		{
+			if(returnValues[i] != list.getEntry2(positions[i]))
+			{
+				System.out.println("There is something wrong.");
+				System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + ".");
+				System.out.println("But the method getEntry2(" + positions[i] + ") returns " + list.getEntry2(positions[i]) + ".");
+				System.out.println("Fix the method getNodeAt2() first.");
+				return;
+			}
+		}
+		
+		endTime = System.currentTimeMillis();
+		
+		double getEntry2Time = endTime - startTime;
+		
+		System.out.println("Done\n");
+		
+		
+		System.out.println("The method getEntry() took " + getEntryTime + " millisecond.");
+		System.out.println("The method getEntry1() took " + getEntry1Time + " millisecond.");
+		System.out.println("The method getEntry2() took " + getEntry2Time + " millisecond.\n");
+		
+		System.out.println("If getEntry1() took roughly about half the time of getEntry(), you get 5 points.");
+		System.out.println("If getEntry2() took roughly about a quarter the time of getEntry(), you get 5 points.");
+	}
+}
diff --git a/labs/lab03_dll/lab03_dll.pdf b/labs/lab03_dll/lab03_dll.pdf
new file mode 100644
index 0000000..8789c66
--- /dev/null
+++ b/labs/lab03_dll/lab03_dll.pdf