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 12:54] – [list library] 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 219: 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 272: 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 311: Line 266:
  
 =====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 346: 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:  20, Matches:  20, 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: 150, Matches: 150, Mismatches:   0+ [RESULTS] Total: 154, Matches: 154, Mismatches:   0
 ==================================================== ====================================================
 lab46:~/src/data/dlq0$  lab46:~/src/data/dlq0$ 
 </cli> </cli>
  
-With the added feature to **display()**, we have 10 additional combinations to test, so this will bump up the total number of list tests by 10, going from the dll0 total of 102 to the dls0 total of 140 to the dlq0 total of 150.+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.
  
 But aside from this change to **display()**, your list implementation can remain 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====
haas/fall2014/data/projects/dlq0.1415451286.txt.gz · Last modified: 2014/11/08 12:54 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