Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » spring2015 » data » projects » dlq0
haas:spring2015: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:spring2015:data:projects:dlq0 [2015/04/17 12:41] – [the queue] wedgehaas:spring2015:data:projects:dlq0 [2015/04/29 18:48] (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> (DATESTAMP)+  * __revision 1__: typo in unit-dequeue (20150425) 
 +    * lacking a leading '0x' on the status code (FIXED) 
 +    * also, a few erroneous mentions of "Popping"; should say "Dequeueing" (FIXED) 
 +  * __revision 2__: typo in unit-purge (20150427) 
 +    * "should be:" lines were saying "NOT EMPTY" when they should say "EMPTY" (FIXED) 
 +  * __revision 3__: typo in unit-dequeue (20150429) 
 +    * unit-dequeue was dequeueing backwards (FIXED) 
  
 =====Objective===== =====Objective=====
Line 82: Line 89:
  
 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). 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/data.h====
 +Building on the **data.h** header file introduced in dls0, a section of status codes has been added for queues:
 +
 +<code c>
 +// Status codes for the queue implementation
 +//
 +#define  DLQ_SUCCESS        256
 +#define  DLQ_CREATE_FAIL    512
 +#define  DLQ_NULL           1024
 +#define  DLQ_EMPTY          2048
 +#define  DLQ_OVERRUN        4096
 +#define  DLQ_UNDERRUN       8192
 +#define  DLQ_DEFAULT_FAIL   16384
 +#define  DLQ_FAIL           32768
 +</code>
 +
 +You may notice that they equate to the same numerical values as the stack; that is because, for the purposes of our stack and queue implementations, there will be no overlap in functionality (stacks won't be accessing queue operations, and queues will not be accessing stack operations).
  
 ====In inc/queue.h==== ====In inc/queue.h====
Line 89: Line 114:
 #define _QUEUE_H #define _QUEUE_H
  
-#include "list.h"                  // queue relies on list to work +#include "data.h"                   // helpful #defines 
-                                   // (which relies on node)+#include "list.h"                   // queue relies on list to work 
 +                                    // (which relies on node)
 struct queue { struct queue {
-    List *data;                    // pointer to list containing data +    List *data;                     // pointer to list containing data 
-    Node *front;                   // pointer to node at front of queue +    Node *front;                    // pointer to node at front of queue 
-    Node *back;                    // pointer to node at back of queue +    Node *back;                     // pointer to node at back of queue 
-    int   buffer;                  // maximum queue size (0 is unbounded)+    uli   buffer;                   // maximum queue size (0 is unbounded)
 }; };
-typedef struct queue Queue;        // because we deserve nice things+typedef struct queue Queue;         // because we deserve nice things
  
-Queue *mkqueue(int              ); // create new queue (of max size) +code_t mkqueue(Queue **, uli     ); // create new queue (of max size) 
-Queue *cpqueue(Queue *          ); // create a copy of an existing queue +code_t cpqueue(Queue  *, Queue **); // create a copy of an existing queue 
-Queue *rmqueue(Queue *          ); // clear and de-allocate an existing queue+code_t rmqueue(Queue **          ); // clear and de-allocate a queue
  
-Queue *purge(Queue *            ); // empty a given queue+code_t purge  (Queue **          ); // clear and de-allocate an existing queue
  
-int    enqueue(Queue **, Node * ); // add new node to the back of queue +code_t enqueue(Queue **, Node  * ); // add new node to the back of queue 
-int    dequeue(Queue **, Node **); // take off node at front of queue+code_t dequeue(Queue **, Node ** ); // take off node at front of queue
  
 #endif #endif
Line 118: Line 144:
  
 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. 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.
-====list library==== 
-One more enhancement is in store for our venerable **display()** function, and that is described below: 
- 
-===display() enhancements=== 
-You are also to implement an additional feature (resulting in 8 additional modes) to the **display()** function.  
- 
-This means you'll need to expand the current modulus divide by 8 to one of 16. 
- 
-The current modes are as follows: 
- 
-<code c> 
-//       modes: 0 display the list forward, no positional values 
-//              1 display the list forward, with positional values 
-//              2 display the list backwards, no positional values 
-//              3 display the list backwards, with positional values 
-//              4 display the list forward, no positional values, in ASCII 
-//              5 display the list forward, with positional values, in ASCII 
-//              6 display the list backwards, no positional values, in ASCII 
-//              7 display the list backwards, with positional values, in ASCII 
-</code> 
- 
-The new feature is to toggle the display of the individual arrows (and the terminating NULL value) and much of the natural spacing we've used so far. It should also ditch, when in ASCII mode, the quotes we have been placing around the ASCII characters. 
- 
-The idea here is, when combined with the ASCII representation of the list, **display()** can become a pretty useful function for displaying strings, which could come in handy. 
- 
-Also, when dealing with numeric values, we could make use of this in applications where we are handling the construction of a numeric value (such as a bignum).  
- 
-For positioned displays, this would seem to have less utility, but by having a space displayed before the position value, we can salvage the output nicely. 
- 
-So for each of the above 8 modes, you'll have a WITH_ARROWS mode, and then a WITHOUT_ARROWS mode (leaving us with a total of 16 possible combinations). 
- 
-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== 
-Let's say we have a list with the following elements: 
- 
-  start -> 51 -> 49 -> 51 -> 51 -> 55 -> NULL 
- 
-==mode "8": forward, no positions, as numbers, without arrows== 
-<cli> 
-5149515155 
-</cli> 
- 
-==mode "9": forward, with positions, as numbers, without arrows== 
-<cli> 
- [0]51 [1]49 [2]51 [3]51 [4]55 
-</cli> 
- 
-==mode "12": forward, no positions, in ASCII, without arrows== 
-<cli> 
-31337 
-</cli> 
- 
-==mode "13": forward, with positions, in ASCII, without arrows== 
-<cli> 
- [0]3 [1]1 [2]3 [3]3 [4]7 
-</cli> 
  
 ====queue library==== ====queue library====
Line 230: Line 197:
 lab46:~/src/data/dlq0$  lab46:~/src/data/dlq0$ 
 </cli> </cli>
-====List Library unit tests==== 
-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. 
 ====Queue library unit tests==== ====Queue library unit tests====
 In **testing/queue/unit/**, you will find these files: In **testing/queue/unit/**, you will find these files:
Line 262: Line 226:
  
 =====Expected Results===== =====Expected Results=====
-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): +To assist you in verifying a correct implementation, a fully working implementation of the queue library should resemble the following (when running the respective verify script):
- +
- +
-====list library==== +
-Here is what you should get for list: +
- +
-<cli> +
-lab46:~/src/data/dlq0$ bin/verify-list.sh  +
-==================================================== +
-=    Verifying Doubly-Linked List Functionality    = +
-==================================================== +
-  [mklist] Total:   6, Matches:   6, Mismatches:   0 +
-  [cplist] Total:  30, Matches:  30, Mismatches:   0 +
-  [rmlist] Total:   3, Matches:   3, Mismatches:   0 +
-  [append] Total:  22, Matches:  22, Mismatches:   0 +
-  [insert] Total:  22, Matches:  22, Mismatches:   0 +
-  [obtain] Total:  23, Matches:  23, 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: 154, Matches: 154, Mismatches:   0 +
-==================================================== +
-lab46:~/src/data/dlq0$  +
-</cli>+
  
-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. 
  
 ====queue library==== ====queue library====
Line 298: Line 235:
 <cli> <cli>
 lab46:~/src/data/dlq0$ bin/verify-queue.sh  lab46:~/src/data/dlq0$ bin/verify-queue.sh 
-=================================================== +coming soon...
-=   Verifying Doubly-Linked Queue Functionality   = +
-=================================================== +
-[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:  73, Matches:  73, Mismatches:   0 +
-===================================================+
 lab46:~/src/data/dlq0$  lab46:~/src/data/dlq0$ 
 </cli> </cli>
haas/spring2015/data/projects/dlq0.1429274462.txt.gz · Last modified: 2015/04/17 12:41 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