Differences

This shows you the differences between two versions of the page.

--- haas:fall2014:data:projects:dlq0 [2014/11/08 11:22] – [queue library] wedge
+++ haas:fall2014:data:projects:dlq0 [2014/11/19 14:43] (current) – [Errata] wedge
@@ Line 11: / Line 11: @@
 This section will document any updates applied to the project since original release:
-  * __revision #__: <description> (DATESTRING)
+  * __revision 1__: I noticed some typos and omissions that while not causing any problems, could cause confusion and compiler warnings. (20141116)
+    * **unit-enqueue.c** had a bunch of references to "Dequeueing" in its printfs() where it actually meant to say "Enqueueing" (FIXED).
+    * the prototype for **rmqueue()** was missing from the **inc/queue.h** header. This was causing implicit function declaration warnings during compile. (FIXED).
+  * __revision 2__: unit-mkqueue tweaks and verify-queue.sh enhancements (20141119)
+    * While I was debugging some code I noticed that the **unit-mkqueue.c** logic was not flexible enough in handling implementations where front was pointing to the end of the list. I have added logic to enable proper checking of back/front, regardless of underlying list orientation (FIXED).
+    * verify-queue.sh enhanced to show absolute totals, even if improper implementations cause the unit test not to perform the full run.
 =====Objective=====
-In this project, resume our conceptual journey and explore another data structure: stacks.
+In this project, resume our conceptual journey and explore another data structure: queues.
 =====Background=====
-A **stack** is considered one of the most important data structures, along with **queues** (next week's project) and trees. And it is largely because of how often we find them playing out in nature or our day-to-day lives.
+A **queue** is considered one of the most important data structures, along with **stack** (last week's project) and trees. And it is largely because of how often we find them playing out in nature or our day-to-day lives.
-The word "stack" is [[https://www.google.com/search?&q=define%3Astack&ie=utf-8&oe=utf-8|defined]] as:
+The word "queue" is [[https://www.google.com/search?&q=define%3Aqueue&ie=utf-8&oe=utf-8|defined]] as:
-  * (generically): a pile of objects, typically one that is neatly arranged
-  * (computing): a set of storage locations that store data in such a way that the most recently stored item is the first to be retrieved
-Additionally, when viewing it as a verb (an action), we also find some positive computing application (bolded) in a less reputable cardplaying usage:
-  * shuffle or **arrange** (a deck of cards) dishonestly **so as to gain** an unfair **advantage**
-Or, to distill it out:
-  * arrange so as to gain advantage
-Combining with our previous definitions, we have:
-  * a set of storage locations that are arranged in such a way so as to give us an advantage- the most recently stored item (the last to be placed onto the stack) is the first to be retrieved.
+  * (generically): a line or sequence of items awaiting their turn to be attended to or to proceed
+  * (computing): a list of data items, commands, etc., stored so as to be retrievable in a definite order, usually the order of insertion
 ====Lists and Nodes====
 So, how does all this list and node stuff play into our queue implementation?
@@ Line 161: / Line 154: @@
 For sane implementation purposes, for our current 8 (so modes 0-7), those will be considered to be WITH_ARROWS... whereas the remaining 8 combinations (8-15) will be WITHOUT_ARROWS. All other mode features will map in place (if you recognize the binary pattern I've been following you'll hopefully see how trivial this change (and the previous one) will be).
+Also, when not displaying arrows, no NULL values will be displayed at all; this means that in the event we are running **display()** on a NULL or empty list, nothing but a newline should be displayed.
 ==display() output examples based on mode==
@@ Line 217: / Line 212: @@
 <cli>
 lab46:~/src/data/dlq0$ make use-test-reference
-make[1]: Entering directory '/home/wedge/src/data/dlq0/src'
+...
-make[2]: Entering directory '/home/wedge/src/data/dlq0/src/list'
-rm -f .*.sw[op] *.swp *.save* *~ *.o append.o cp.o display.o insert.o mk.o obtain.o rm.o search.o sort.o swap.o core
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/src/list'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/src/node'
-rm -f .*.sw[op] *.swp *.save* *~ *.o cp.o mk.o rm.o core
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/src/node'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/src/queue'
-rm -f .*.sw[op] *.swp *.save* *~ *.o cp.o dequeue.o enqueue.o mk.o purge.o rm.o core
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/src/queue'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/src/stack'
-rm -f .*.sw[op] *.swp *.save* *~ *.o cp.o isempty.o mk.o peek.o pop.o push.o rm.o core
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/src/stack'
-make[1]: Leaving directory '/home/wedge/src/data/dlq0/src'
-make[1]: Entering directory '/home/wedge/src/data/dlq0/testing'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/testing/list'
-make[3]: Entering directory '/home/wedge/src/data/dlq0/testing/list/unit'
-rm -f *.swp *.o ../../../bin/unit-append unit-cplist unit-display unit-findnode unit-insert unit-mklist unit-obtain unit-rmlist unit-sortlist unit-swapnode core
-make[3]: Leaving directory '/home/wedge/src/data/dlq0/testing/list/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/testing/list'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/testing/node'
-make[3]: Entering directory '/home/wedge/src/data/dlq0/testing/node/unit'
-rm -f *.swp *.o ../../../bin/unit-cpnode unit-mknode unit-rmnode core
-make[3]: Leaving directory '/home/wedge/src/data/dlq0/testing/node/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/testing/node'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/testing/queue'
-make[3]: Entering directory '/home/wedge/src/data/dlq0/testing/queue/unit'
-rm -f .*.sw[op] *.swp *.save* *~ *.o ../../../bin/unit-cpqueue unit-dequeue unit-enqueue unit-mkqueue unit-purge unit-rmqueue core
-make[3]: Leaving directory '/home/wedge/src/data/dlq0/testing/queue/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/testing/queue'
-make[2]: Entering directory '/home/wedge/src/data/dlq0/testing/stack'
-make[3]: Entering directory '/home/wedge/src/data/dlq0/testing/stack/app'
-rm -f *.swp *.o ../../../bin/palindrome-stack core
-make[3]: Leaving directory '/home/wedge/src/data/dlq0/testing/stack/app'
-make[3]: Entering directory '/home/wedge/src/data/dlq0/testing/stack/unit'
-rm -f *.swp *.o ../../../bin/unit-cpstack unit-isempty unit-mkstack unit-peek unit-pop unit-push unit-rmstack core
-make[3]: Leaving directory '/home/wedge/src/data/dlq0/testing/stack/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dlq0/testing/stack'
-make[1]: Leaving directory '/home/wedge/src/data/dlq0/testing'
 NODE and LIST reference implementation in place, run 'make' to build everything.
 lab46:~/src/data/dlq0$
@@ Line 270: / Line 227: @@
 ===Reverting back to using your code===
-If you were trying out the reference implementation to verify stack functionality, and wanted to revert back to your own code, it is as simple as:
+If you were trying out the reference implementation to verify queue functionality, and wanted to revert back to your own code, it is as simple as:
 <cli>
@@ Line 309: / Line 266: @@
 =====Expected Results=====
-To assist you in verifying a correct implementation, a fully working implementation of the node, list, and stack libraries should resemble the following (when running the respective verify script):
+To assist you in verifying a correct implementation, a fully working implementation of the list and queue libraries should resemble the following (when running the respective verify script):
-====node library====
-Here is what you should get for node:
-<cli>
-lab46:~/src/data/dlq0$ bin/verify-node.sh
-====================================================
-=    Verifying Doubly-Linked Node Functionality    =
-====================================================
-  [mknode] Total:   5, Matches:   5, Mismatches:   0
-  [cpnode] Total:   6, Matches:   6, Mismatches:   0
-  [rmnode] Total:   2, Matches:   2, Mismatches:   0
-====================================================
- [RESULTS] Total:  13, Matches:  13, Mismatches:   0
-====================================================
-lab46:~/src/data/dlq0$
-</cli>
-As no coding changes were needed in the node library, these results should be identical to that of a fully functioning node implementation from the **dll0** project.
 ====list library====
@@ Line 344: / Line 283: @@
   [insert] Total:  22, Matches:  22, Mismatches:   0
   [obtain] Total:  23, Matches:  23, Mismatches:   0
- [display] Total:  10, Matches:  10, Mismatches:   0
+ [display] Total:  24, Matches:  24, Mismatches:   0
 [findnode] Total:  11, Matches:  11, Mismatches:   0
 [sortlist] Total:   6, Matches:   6, Mismatches:   0
 [swapnode] Total:   7, Matches:   7, Mismatches:   0
 ====================================================
- [RESULTS] Total: 140, Matches: 140, Mismatches:   0
+ [RESULTS] Total: 154, Matches: 154, Mismatches:   0
 ====================================================
 lab46:~/src/data/dlq0$
 </cli>
-Due to the re-introduction of **qty** into list (impacting actions performed by **mklist()**, **append()**, **insert()**, and **obtain()**), along with feature additions to **display()**, those functions saw additional tests performed, so our original max total of **102** from **dll0** has now changed to **140** (ie various **qty** and **display()**-related tests adding to the previous total).
+With the added feature to **display()**, we have 10 additional combinations to test, plus I added in 4 explicit tests of invalid modes, so this will bump up the total number of list tests by 10+4, going from the dll0 total of 102 to the dls0 total of 140 to the dlq0 total of 154.
-Remember though- aside from the minor change of adding **qty** and enhancing **display()**, all remaining list functions need no change (and **mklist()/append()/insert()/obtain()** remained largely unchanged).
+But aside from this change to **display()**, your list implementation can remain unchanged.
-====stack library====
-Here is what you should get for stack:
-<cli>
-lab46:~/src/data/dlq0$ bin/verify-stack.sh
-===================================================
-=   Verifying Doubly-Linked Stack Functionality   =
-===================================================
-[mkstack] Total:   3, Matches:   3, Mismatches:   0
-[cpstack] Total:   8, Matches:   8, Mismatches:   0
-[rmstack] Total:   3, Matches:   3, Mismatches:   0
-   [push] Total:  30, Matches:  30, Mismatches:   0
-    [pop] Total:  25, Matches:  25, Mismatches:   0
-   [peek] Total:  24, Matches:  24, Mismatches:   0
-[isempty] Total:  13, Matches:  13, Mismatches:   0
-===================================================
-[RESULTS] Total: 106, Matches: 106, Mismatches:   0
-===================================================
-lab46:~/src/data/dlq0$
-</cli>
 ====queue library====

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools