Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2014 » data » projects » dlq0
haas:fall2014:data:projects:dlq0

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:fall2014:data:projects:dlq0 [2014/11/08 11:20] – [Stack library unit tests] wedgehaas: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: 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===== =====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===== =====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==== ====Lists and Nodes====
 So, how does all this list and node stuff play into our queue implementation? 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). 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== ==display() output examples based on mode==
Line 217: Line 212:
 <cli> <cli>
 lab46:~/src/data/dlq0$ make use-test-reference 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. NODE and LIST reference implementation in place, run 'make' to build everything.
 lab46:~/src/data/dlq0$  lab46:~/src/data/dlq0$ 
Line 270: Line 227:
  
 ===Reverting back to using your code=== ===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> <cli>
Line 307: Line 264:
     * ask questions to get clarification!     * 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===== =====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==== ====list library====
Line 356: Line 283:
   [insert] Total:  22, Matches:  22, Mismatches:   0   [insert] Total:  22, Matches:  22, Mismatches:   0
   [obtain] Total:  23, Matches:  23, 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 [findnode] Total:  11, Matches:  11, Mismatches:   0
 [sortlist] Total:   6, Matches:   6, Mismatches:   0 [sortlist] Total:   6, Matches:   6, Mismatches:   0
 [swapnode] Total:   7, Matches:   7, 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$  lab46:~/src/data/dlq0$ 
 </cli> </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==== ====queue library====
Line 401: Line 307:
 [mkqueue] Total:   4, Matches:   4, Mismatches:   0 [mkqueue] Total:   4, Matches:   4, Mismatches:   0
 [cpqueue] Total:   8, Matches:   8, Mismatches:   0 [cpqueue] Total:   8, Matches:   8, Mismatches:   0
 +[rmqueue] Total:   3, Matches:   3, Mismatches:   0
   [purge] Total:   3, Matches:   3, Mismatches:   0   [purge] Total:   3, Matches:   3, Mismatches:   0
 [enqueue] Total:  30, Matches:  30, Mismatches:   0 [enqueue] Total:  30, Matches:  30, Mismatches:   0
 [dequeue] Total:  25, Matches:  25, 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$  lab46:~/src/data/dlq0$ 
haas/fall2014/data/projects/dlq0.1415445609.txt.gz · Last modified: 2014/11/08 11:20 by wedge

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki