Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2015 » data » projects » dll1
haas:fall2015:data:projects:dll1

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:fall2015:data:projects:dll1 [2015/10/31 13:03] – [Submission Criteria] wedgehaas:fall2015:data:projects:dll1 [2015/11/02 10:41] (current) – [List library unit tests] wedge
Line 30: Line 30:
 As such, new function prototypes have been added to the list.h header file: As such, new function prototypes have been added to the list.h header file:
  
-<code> +<code c> 
-code_t  rmlist (List **);                  // deallocate empty list+code_t  obtain  (List **, Node **);         // disconnect node  from list
  
-code_t  obtain (List **, Node **);         // disconnect node  from list+code_t  empty   (List **);                  // empty an existing list 
 +code_t  rmlist  (List **);                  // deallocate empty list
  
-code_t  compare(List  *, List *, ulli  *); // compare two lists +code_t  compare (List  *, List *, ulli  *); // compare two lists
-code_t  empty  (List **);                  // empty an existing list+
  
-code_t  sort   (List **, int);             // sort list by mode +code_t  sortlist(List **, int);             // sort list by mode 
-code_t  swap   (List **, Node *, Node  *); // swap nodes in list+code_t  swapnode(List **, Node *, Node  *); // swap nodes in list
 </code> </code>
  
 These functions will also make use of the status/error codes introduced in dll0. Additional effort has gone into identifying likely codes applied in various conditions. Be sure to reference the provided comments as well as the unit tests for more information. These functions will also make use of the status/error codes introduced in dll0. Additional effort has gone into identifying likely codes applied in various conditions. Be sure to reference the provided comments as well as the unit tests for more information.
 +
 +The recommended order of implementation is:
 +
 +  - **obtain()**
 +  - **empty()**
 +  - **rmlist()**
 +  - **compare()**
 +  - **swapnode()**
 +  - **sortlist()** (although note that sorting doesn't necessarily need swapping)
 +
 +Implementing them out of order will likely result in unnecessary duplication of efforts, and I really don't want to see a half dozen half-baked **obtain()** implementations dribbled throughout your code.
 ====list operation status codes==== ====list operation status codes====
-You'll notice the presence of a set of #define's in the list header file. These are intended to be used to report on various states of list status after performing various operations.+Just as with dll0, you'll notice the presence of a set of #define's in the **data.h** file. These are intended to be used to report on various states of list status after performing various operations.
  
 They are not exclusive- in some cases, multiple states can be applied. The intent is that you will OR together all pertinent states and return that from the function. They are not exclusive- in some cases, multiple states can be applied. The intent is that you will OR together all pertinent states and return that from the function.
Line 63: Line 74:
  
 ALL THREE states must be returned from the function in question should such an occurrence take place. ALL THREE states must be returned from the function in question should such an occurrence take place.
 +
 +===compare status codes===
 +dll1 introduces additional status codes for one of its functions: **compare()**
 +
 +Those codes are as follows:
 +
 +<code c>
 +//////////////////////////////////////////////////////////////////////
 +//
 +// Status codes for the doubly-linked list compare() function
 +//
 +#define  CMP_EQUALITY        0x00
 +#define  CMP_L1_NULL         0x01
 +#define  CMP_L1_EMPTY        0x02
 +#define  CMP_L1_GREATER      0x04
 +#define  CMP_L1_LESS         0x08
 +#define  CMP_L2_NULL         0x10
 +#define  CMP_L2_EMPTY        0x20
 +#define  CMP_L2_GREATER      0x40
 +#define  CMP_L2_LESS         0x80
 +</code>
 ====list library==== ====list library====
 In **src/list/**, you will find the addition of a new set of skeletons of the above prototyped functions, hollowed out in anticipation of being made operational. In **src/list/**, you will find the addition of a new set of skeletons of the above prototyped functions, hollowed out in anticipation of being made operational.
Line 71: Line 103:
  
 ====List library unit tests==== ====List library unit tests====
-In **testing/list/unit/**, you will find these new files:+In **unit/list/**, you will find these new files:
  
-  * **unit-rmlist.c** - unit test for **rmlist()** library function 
   * **unit-obtain.c** - unit test for **obtain()** library function   * **unit-obtain.c** - unit test for **obtain()** library function
-  * **unit-compare.c** - unit test for **compare()** library function 
   * **unit-empty.c** - unit test for **empty()** library function   * **unit-empty.c** - unit test for **empty()** library function
-  * **unit-sort.c** - unit test for **sort()** library function +  * **unit-rmlist.c** - unit test for **rmlist()** library function 
-  * **unit-swap.c** - unit test for **swap()** library function+  * **unit-compare.c** - unit test for **compare()** library function 
 +  * **unit-swap.c** - unit test for **swapnode()** library function 
 +  * **unit-sort.c** - unit test for **sortlist()** library function
  
 Enhancements to these unit tests may be provided via dll1 project updates. Enhancements to these unit tests may be provided via dll1 project updates.
Line 98: Line 130:
     * ask questions to get clarification!     * ask questions to get clarification!
  
 +Also note that, while considerable effort was made to ensure a broad range of tests were incorporated into each unit test, they are by no means a complete nor exhaustive battery of tests. There may be scenarios the unit tests do not currently check for. You are welcome and encouraged to perform additional tests to ensure your implementation is as rock solid as it can be.
 +
 +====List library applications====
 +
 +===palindrome===
 +Now that we've completed our doubly-linked list functionality, we can use these individual functions to piece together solutions to various everyday problems where a list could be effective. After all, that's a big aspect to learning data structures- they open doors to new algorithms and problem solving capabilities.
 +
 +Our endeavor here will be to revisit 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.
 =====Expected Results===== =====Expected Results=====
 To assist you in verifying a correct implementation, a fully working implementation of the node and list 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 node and list libraries should resemble the following (when running the respective verify script):
Line 106: Line 150:
  
 <cli> <cli>
-lab46:~/src/data/dll1$ bin/verify-list.sh  +lab46:~/src/data/dll1$ make check 
-==================================================== +====================================================== 
-=    Verifying Doubly-Linked List Functionality    = +=    Verifying Doubly-Linked  List Functionality     = 
-==================================================== +====================================================== 
-  [mklist] Total:  11, Matches:  11, Mismatches:   0 +    [obtain] Total:  57, Matches:  57, Mismatches:   0 
-  [cplist] Total:  17, Matches:  17, Mismatches:   0 +     [empty] Total:   7, Matches:   7, Mismatches:   0 
-  [append] Total:  22, Matches:  22, Mismatches:   0 +    [rmlist] Total:   7, Matches:   7, Mismatches:   0 
-  [insert] Total:  22, Matches:  22, Mismatches:   0 +   [compare] Total:  12, Matches:  12, Mismatches:   0 
- [display] Total:  12, Matches:  12, Mismatches:   0 +  [swapnode] Total:  31, Matches:  31, Mismatches:   0 
-    [find] Total:  28, Matches:  28, Mismatches:   0 +  [sortlist] Total:  48, Matches:  48, Mismatches:   0 
- [compare] Total:  18, Matches:  18, Mismatches:   0 +====================================================== 
-   [empty] Total:   6, Matches:   6, Mismatches:   0 +   [RESULTS] Total: 162, Matches: 162, Mismatches:   0 
-  [rmlist] Total:   6, Matches:   6, Mismatches:   0 +======================================================
-  [obtain] Total:  57, Matches:  57, Mismatches:   0 +
-    [swap] Total:   9, Matches:   9, Mismatches:   0 +
-    [sort] Total:  42, Matches:  42, Mismatches:   0 +
-==================================================== +
- [RESULTS] Total: 250, Matches: 250, Mismatches:   0 +
-====================================================+
 lab46:~/src/data/dll1$  lab46:~/src/data/dll1$ 
 </cli> </cli>
haas/fall2015/data/projects/dll1.1446296603.txt.gz · Last modified: 2015/10/31 13:03 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