Priority Queues/Sorted - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:44:40Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:44, 9 October 2019
Line 1:		Line 1:
	==Git Code==		==Git Code==

	Link on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/SortedPQ.java		Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

	==Notes==		==Notes==
Line 46:		Line 46:
	The priority queue interface is a templated/generic type class. It defines the basic methods - we should be able to add and remove items, as well as query the state of the queue. These are enabled through an insert method, a peek minimum method, and a remove minimum method.		The priority queue interface is a templated/generic type class. It defines the basic methods - we should be able to add and remove items, as well as query the state of the queue. These are enabled through an insert method, a peek minimum method, and a remove minimum method.

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/PriorityQueue.java		Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/PriorityQueue.java

	'''PriorityQueue.java'''		'''PriorityQueue.java'''
Line 98:		Line 98:
	The parent type is a priority queue abstract data type. The class does not do a lot of work, but it does establish the technique the Priority Queue will use to sort Items - and it defines the Item class, representing nodes of data in the list.		The parent type is a priority queue abstract data type. The class does not do a lot of work, but it does establish the technique the Priority Queue will use to sort Items - and it defines the Item class, representing nodes of data in the list.

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/AbstractPriorityQueue.java		Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/AbstractPriorityQueue.java

	Runthrough:		Runthrough:
Line 192:		Line 192:
	The entirety of the Sorted Priority Queue class.		The entirety of the Sorted Priority Queue class.

	Link: https://charlesreid1.com~~:3000~~/cs/java/src/master/priority-queues/SortedPQ.java		Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

	<pre>		<pre>

Admin: /* Sorted Priority Queue Class */

2017-06-23T08:05:21Z

Sorted Priority Queue Class

← Older revision		Revision as of 08:05, 23 June 2017
Line 285:		Line 285:

	}		}
			</pre>


			===Making it iterable===

			To make the sorted priority queue class iterable, we can have two things to do:
			* Populate our items/data in a data container that is iterable (already done, since we are using Linked List), and
			* Define a key (or value) iterator class. This is a simple wrapper class around the built in linked list iterator.

			Here, we accomplish the first task:

			<pre>
			protected Iterable<Item<K,V>> items() {
			return data;
			}
			</pre>

			and here we accomplish the second:

			<pre>
			protected class ItemIterator implements Iterator<K> {
			Iterator<Item<K,V>> it;
			public ItemIterator() {
			it = items().iterator();
			}
			public boolean hasNext() { return it.hasNext(); }
			public K next() { return it.next().getKey(); }
			public void remove() { it.remove(); }
			}

			public Iterator<K> iterator() {
			return new ItemIterator();
			}
	</pre>		</pre>

Admin: /* Sorted Priority Queue Class */

2017-06-23T08:03:19Z

Sorted Priority Queue Class

@@ Line 195: / Line 195: @@
 <pre>
 // unsorted priority queue
-public class SortedPQ<K,V> extends AbstractPriorityQueue<K,V> {
+public class SortedPQ<K,V>
 	// primary collection
@@ Line 250: / Line 257: @@
 		return it.getValue();
+	}
 	public int size() {
@@ Line 260: / Line 265: @@
 		return data.toString();
+	}
+}
 </pre>

Admin: /* Insert Method - More Detail */

2017-06-23T06:27:47Z

Insert Method - More Detail

← Older revision		Revision as of 06:27, 23 June 2017
Line 265:		Line 265:
	===Insert Method - More Detail===		===Insert Method - More Detail===

	Let's run through that insert method one more time.		Let's run through that insert method one more time in greater detail.

	<pre>		<pre>

Admin: /* Insert Method */

2017-06-23T06:27:35Z

Insert Method

← Older revision		Revision as of 06:27, 23 June 2017
Line 263:		Line 263:
	</pre>		</pre>

	===Insert Method===		===Insert Method - More Detail===

	Let's run through that insert method one more time.		Let's run through that insert method one more time.

Admin: /* Insert Method */

2017-06-23T06:26:54Z

Insert Method

← Older revision		Revision as of 06:26, 23 June 2017
Line 284:		Line 284:
	</pre>		</pre>

	~~Now~~ we have the Item we are trying to insert into the list, newest~~, and we~~ want to iterate through the list to find the new location to insert the Item. This class uses a built-in LinkedList so we utilize an integer index and the built-in methods of the list to add the item at that location.		At this point, we have the Item we are trying to insert into the list, in a variable called newest. We want to iterate through the list to find the new location to insert the Item. This class uses a built-in LinkedList so we utilize an integer index and the built-in methods of the list to add the item at that location.

			Starting with a descending iterator through the list, we work our way from the back to the front. We already checked for an empty priority queue, so we know there must be at least one item in the container. This allows us to do a fencepost algorithm/pattern, where we examine one item in the list of items (data), then run a while loop.

	<pre>		<pre>
	Iterator<Item<K,V>> iter = data.descendingIterator();		Iterator<Item<K,V>> iter = data.descendingIterator();
Line 294:		Line 296:
	// advance walker left (left = next, descending iterator)		// advance walker left (left = next, descending iterator)
	try {		try {
	walker = iter.next();		walker = iter.next();
	ix--;		ix--;
	} catch(NoSuchElementException e) {		} catch(NoSuchElementException e) {
Line 309:		Line 311:
	}		}
	</pre>		</pre>

			Let's examine the case of a one-item list.

			If there is only one item in the list, we run the while loop one or zero times, depending on the results of the comparison between newest and walker (the last item our iterator removed from the list).
			* If newest is greater than walker, we can add newest to the end of the list. We skip the while loop, and add at index 1 (the value of ix).
			* If newest is less than walker, we need to run through the loop once, advance the iterator back one, and update the insertion index. This will then insert the walker at the beginning of the list. The next time through the while loop, the test returns false because walker is null (we ran next() on an iterator pointing to the beginning of the list).
			* The walker variable is not null, so we add at the front.

			If two items in the list, we might end up running while loop no times (largest item in list), in which case ix = 2, inserting at end of list. We might end up running while loop one time (median of list), in which case ix = 1, and we insert in the middle. Or we might run the while loop twice, ix = 0, and we insert at the beginning. Only in the last case does the walker pointer become null and we execute the data.addFirst method.

	==Flags==		==Flags==

Admin: /* Priority Queue Abstract Data Type */

2017-06-23T06:07:26Z

Priority Queue Abstract Data Type

← Older revision		Revision as of 06:07, 23 June 2017
Line 109:		Line 109:
	<pre>		<pre>
	import java.util.Comparator;		import java.util.Comparator;

	~~/** Define a weird key exception.~~
	* This gets raised when a key cannot be compared to itself.
	* This extends IllegalArgumentException which means it is unchecked. */
	~~class WeirdKey extends IllegalArgumentException {};~~

	/** Priority Queue ADT.		/** Priority Queue ADT.
Line 189:		Line 184:
	return (size()==0);		return (size()==0);
	}		}

	}		}
	</pre>		</pre>

Admin: /* Interface */

2017-06-23T06:05:19Z

Interface

← Older revision		Revision as of 06:05, 23 June 2017
Line 51:		Line 51:

	<pre>		<pre>
			import java.util.Iterator;

			/** Define some exceptions. */
			class Illegal extends IllegalArgumentException {}
			class Empty extends IndexOutOfBoundsException {}

	/** Priority Queue interface.		/** Priority Queue interface.
	*		*
Line 59:		Line 65:
	* Note that Item<K,V> is not defined here, it is defined in your concrete implementation.		* Note that Item<K,V> is not defined here, it is defined in your concrete implementation.
	*/		*/
	public interface PriorityQueue<K,V> extends Iterable<K> {		public interface PriorityQueue<K,V> extends Iterable<K> {
			//extends Iterable<K> {

	/** Returns true if the priority queue was changed. */		/** Returns true if the priority queue was changed. */
	public ~~boolean~~ insert(k,v);		public void insert(K k, V v);

	/** Remove and return the minimum element in this queue. */		/** Remove and return the minimum element in this queue. */
Line 74:		Line 81:

	/** Returns an iterable container with all of the Items in this queue. */		/** Returns an iterable container with all of the Items in this queue. */
	~~public~~ Iterable<Item<K,V>> items();		protected Iterable<Item<K,V>> items();

	/** Returns the number of elements in this queue. */		/** Returns the number of elements in this queue. */
Line 80:		Line 87:

	/** Returns true if there are no elements in this queue. */		/** Returns true if there are no elements in this queue. */
	public isEmpty();		public boolean isEmpty();

			/** Returns a string representation of this priority queue. */
			public String toString();
	}		}
	</pre>		</pre>

Admin: /* Add Method */

2017-06-23T05:29:20Z

Add Method

@@ Line 257: / Line 257: @@
 </pre>
-===Add Method===
+===Insert Method===
 ==Flags==

Admin: /* Abstract type */

2017-06-23T05:20:17Z

Abstract type

@@ Line 84: / Line 84: @@
 </pre>
-===Abstract type===
+===Priority Queue Abstract Data Type===
 The parent type is a priority queue abstract data type. The class does not do a lot of work, but it does establish the technique the Priority Queue will use to sort Items - and it defines the Item class, representing nodes of data in the list.
@@ Line 181: / Line 181: @@
+}
 </pre>
 ==Flags==