Differences

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

--- haas:fall2014:data:projects:dlq0 [2014/11/07 22:19] – [stack 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 92: / Line 85: @@
 =====Project Overview=====
-For this project, we're going to be implementing the stack data structure atop of our recently re-implemented linked list (the doubly linked list).
+For this project, we're going to be implementing the queue data structure atop of our recently re-implemented linked list (the doubly linked list).
 ====In inc/queue.h====
@@ Line 126: / Line 119: @@
 This is necessary so that we can free up the return value of **enqueue()** and **dequeue()** to be used for status (ie look out for buffer overruns and underruns).
-**purge()** is being implemented as an exercise to aid in your understanding of queues. Again, avoid their use except is a means of convenience (or to further optimize your code). The general rule of thumb is that the use of **purge()**.
+Also, while nothing is stopping you from doing so, the idea here is that things like **buffer** and the underlying list **qty** in queue transactions will **NOT** be accessed outside of the **enqueue()** and **dequeue()** functions. Just like my warnings about using **qty** in your list solutions (save for **display()** when showing position values in a backwards orientation)-- do not consider **buffer** as a variable for your general use.
-If you cannot think of how to solve a problem without the use of **purge()**, that is a strong clue that you shouldn't be using it.
-Also, while nothing is stopping you from doing so, the idea here is that things like **buffer** and the underlying list **qty** in queue transactions will **NOT** be accessed outside of the **enqueue()** and **dequeue()** functions. Just like my warnings about using **qty** in your list solutions-- do not consider **buffer** as a variable for your general use.
 In object-oriented programming, both **buffer** and **qty** would be **private** member variables of their respective classes, unable to be used by anything other than their respective member functions.
@@ Line 165: / 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 208: @@
 </cli>
-In order to make use of it, you'll need to run **make use-test-reference** from the base of your **dls0** project directory, as follows:
+In order to make use of it, you'll need to run **make use-test-reference** from the base of your **dlq0** project directory, as follows:
 <cli>
-lab46:~/src/data/dls0$ make use-test-reference
+lab46:~/src/data/dlq0$ make use-test-reference
-make[1]: Entering directory '/home/wedge/src/data/dls0/src'
+...
-make[2]: Entering directory '/home/wedge/src/data/dls0/src/list'
-rm -f *.swp *.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/dls0/src/list'
-make[2]: Entering directory '/home/wedge/src/data/dls0/src/node'
-rm -f *.swp *.o cp.o mk.o rm.o core
-make[2]: Leaving directory '/home/wedge/src/data/dls0/src/node'
-make[2]: Entering directory '/home/wedge/src/data/dls0/src/stack'
-rm -f *.swp *.o cp.o isempty.o mk.o peek.o pop.o push.o rm.o core
-make[2]: Leaving directory '/home/wedge/src/data/dls0/src/stack'
-make[1]: Leaving directory '/home/wedge/src/data/dls0/src'
-make[1]: Entering directory '/home/wedge/src/data/dls0/testing'
-make[2]: Entering directory '/home/wedge/src/data/dls0/testing/list'
-make[3]: Entering directory '/home/wedge/src/data/dls0/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/dls0/testing/list/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dls0/testing/list'
-make[2]: Entering directory '/home/wedge/src/data/dls0/testing/node'
-make[3]: Entering directory '/home/wedge/src/data/dls0/testing/node/unit'
-rm -f *.swp *.o ../../../bin/unit-cpnode unit-mknode unit-rmnode core
-make[3]: Leaving directory '/home/wedge/src/data/dls0/testing/node/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dls0/testing/node'
-make[2]: Entering directory '/home/wedge/src/data/dls0/testing/stack'
-make[3]: Entering directory '/home/wedge/src/data/dls0/testing/stack/app'
-rm -f *.swp *.o ../../../bin/palindrome-stack core
-make[3]: Leaving directory '/home/wedge/src/data/dls0/testing/stack/app'
-make[3]: Entering directory '/home/wedge/src/data/dls0/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/dls0/testing/stack/unit'
-make[2]: Leaving directory '/home/wedge/src/data/dls0/testing/stack'
-make[1]: Leaving directory '/home/wedge/src/data/dls0/testing'
 NODE and LIST reference implementation in place, run 'make' to build everything.
-lab46:~/src/data/dls0$
+lab46:~/src/data/dlq0$
 </cli>
@@ Line 259: / Line 220: @@
 <cli>
-lab46:~/src/data/dls0$ make
+lab46:~/src/data/dlq0$ make
 ...
 </cli>
@@ Line 266: / 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>
-lab46:~/src/data/dls0$ make use-your-own-code
+lab46:~/src/data/dlq0$ make use-your-own-code
 Local node/list implementation restored, run 'make clean; make' to build everything.
-lab46:~/src/data/dls0$
+lab46:~/src/data/dlq0$
 </cli>
 ====List Library unit tests====
-As a result of the required changes to **display()** and the incorporation of **qty**, pertinent list unit tests will be enhanced, so you can make use of them to ensure implementation compliance.
+As a result of the required changes to **display()**, an updated unit test will be released (this will mean a different number of total tests for list than previously).
 Be sure to run the various list unit tests and verification scripts to see which functions have fallen out of compliance with the list struct specification changes issued in this project. The **verify-list.sh** script can be especially useful in getting a big picture view of what work is needed.
-====Stack library unit tests====
+====Queue library unit tests====
-In **testing/stack/unit/**, you will find these files:
+In **testing/queue/unit/**, you will find these files:
-  * **unit-mkstack.c** - unit test for **mkstack()** library function
+  * **unit-mkqueue.c** - unit test for **mkqueue()** library function
-  * **unit-cpstack.c** - unit test for **cpstack()** library function
+  * **unit-cpqueue.c** - unit test for **cpqueue()** library function
-  * **unit-rmstack.c** - unit test for **rmstack()** library function
+  * **unit-rmqueue.c** - unit test for **rmqueue()** library function
-  * **unit-push.c** - unit test for **push()** library function
+  * **unit-enqueue.c** - unit test for **enqueue()** library function
-  * **unit-pop.c** - unit test for **pop()** library function
+  * **unit-dequeue.c** - unit test for **dequeue()** library function
-  * **unit-peek.c** - unit test for **peek()** library function
+  * **unit-purge.c**   - unit test for **purge()** library function
-  * **unit-isempty.c** - unit test for **isempty()** library function
 There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent stack functionality.
-These are complete runnable programs (when compiled, and linked against the stack library, which is all handled for you by the **Makefile** system in place).
+These are complete runnable programs (when compiled, and linked against the queue library, which is all handled for you by the **Makefile** system in place).
 Of particular importance, I want you to take a close look at:
@@ Line 304: / Line 264: @@
     * ask questions to get clarification!
-====stack testing applications====
-===palindrome-stack===
-Now that we've completed our stack functionality, we can use these individual functions to piece together solutions to various everyday problems where a stack could be effective (and even compare approaches to when we didn't have the benefit of a stack in solving the problem). After all, that's a big aspect to learning data structures- they open doors to new algorithms and problem solving capabilities.
-Our task (once again) will be that of palindromes (ie words/phrases that, when reversed, spell the same thing).
-This implementation will be considered an extra credit opportunity, so as to offer those who have fallen behind (but working to get caught up) a reprieve on some of the credit they've lost.
-It is also highly recommended to undertake as it will give you further experience working with these concepts.
-Note this is a DIFFERENT approach than you would have taken in the program with sll2- you're to use stack functionality to aid you with the heavy lifting. While you will still make use of list functionality for grabbing the initial input, the actual palindrome comparison processing needs to heavily involve stacks.
 =====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/dls0$ 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/dls0$
-</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 343: / Line 273: @@
 <cli>
-lab46:~/src/data/dls0$ bin/verify-list.sh
+lab46:~/src/data/dlq0$ bin/verify-list.sh
 ====================================================
 =    Verifying Doubly-Linked List Functionality    =
@@ Line 353: / 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/dls0$
+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/dls0$ 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/dls0$
-</cli>
 ====queue library====
@@ Line 398: / Line 307: @@
 [mkqueue] Total:   4, Matches:   4, Mismatches:   0
 [cpqueue] Total:   8, Matches:   8, Mismatches:   0
+[rmqueue] Total:   3, Matches:   3, Mismatches:   0
   [purge] Total:   3, Matches:   3, Mismatches:   0
 [enqueue] Total:  30, Matches:  30, Mismatches:   0
 [dequeue] Total:  25, Matches:  25, Mismatches:   0
 ===================================================
-[RESULTS] Total:  70, Matches:  70, Mismatches:   0
+[RESULTS] Total:  73, Matches:  73, Mismatches:   0
 ===================================================
 lab46:~/src/data/dlq0$
@@ Line 426: / Line 336: @@
   * Track/version the source code in a repository
   * Submit a copy of your source code to me using the **submit** tool (**make submit** will do this) by the deadline.

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools