Lab46 Wiki

User Tools

Site Tools

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

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:dlt0 [2014/11/17 20:17] – [In inc/tree.h] wedgehaas:fall2014:data:projects:dlt0 [2014/11/22 14:51] (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__: various bugfixes and new unit tests added (20141120) 
 +    * unit-addnode had a typo where it was expecting an empty tree to have a height of 0 instead of -1 (FIXED) 
 +    * unit-traverse had a number of typos, and saw some increased ruggedness: 
 +      * missing semi-colon on line 15 (FIXED) 
 +      * invalid variable reference (myList instead of tmpList) on/around line 52 (FIXED) 
 +      * extra checks to test invalid modes 
 +    * unit-set_mode has been deployed 
 +      * valid and invalid modes are checked 
 +    * unit-searchtree has been deployed 
 +      * NULL, empty, and non-empty tree searches of valid and invalid values 
 +    * verify-node.sh has been updated to show absolute totals 
 +    * verify-tree.sh has been updated to include new unit tests in its totals 
 +  * __revision 2__: new unit tests and verify scripts added (20141121) 
 +    * unit-balance has been deployed 
 +      * corresponding verify-balance.sh has been deployed 
 +      * the unit test for balance assumes a pivot based on the middle (if odd), or left-middle (if even) node 
 +    * unit-grabnode has been deployed 
 +      * corresponding verify-grabnode.sh has been deployed 
 +      * the grabnode unit test, like traverse, tests all 3 implementations in one unit test 
 +    * verify-tree.sh has been updated to include new unit tests 
 +  * __revision 3__: tweaks, comments, and new unit tests and verify script added (20141122) 
 +    * unit-grabnode may not have been working truly as intended. FIXED 
 +      * also added a specific test for grabbing from a single node tree 
 +      * performs 6 tests in total- NULL, empty, one-node, one node grabbed, two nodes grabbed, three nodes grabbed 
 +    * unit-addnode has added tests (looks like 35 in total when correctly implemented) 
 +    * unit-copytree has been deployed 
 +      * corresponding verify-copytree.sh has been deployed 
 +      * we perform 6 tests- NULL, empty, one-node, populated, populated and balanced, populated and node grabbed 
 +    * verify-tree.sh has been updated to include new unit test
  
 =====Objective===== =====Objective=====
Line 40: Line 68:
   * a tree has a **root** which forms the basis or starting point of the structure; all nodes are reachable (and related through means of descendance) from the root.   * a tree has a **root** which forms the basis or starting point of the structure; all nodes are reachable (and related through means of descendance) from the root.
   * to put an item on the tree, we insert or **add** it (which you will have 3 separate opportunities to implement in this project!). When we add a node to the tree, it gets positioned in the appropriately available child link off some parent node.   * to put an item on the tree, we insert or **add** it (which you will have 3 separate opportunities to implement in this project!). When we add a node to the tree, it gets positioned in the appropriately available child link off some parent node.
-  * to get an item off of the tree, we **get** it. Just as with a list, disconnecting a node from the structure can involve a lot of work to maintain connections and overall integrity of the data structure.+  * to get an item off of the tree, we **grab** it (my term- often times it is referred to as deleting a node from the tree). Just as with a list, disconnecting a node from the structure can involve a lot of work to maintain connections and overall integrity of the data structure. 
 +  * an important action that will be taking place is the traversal of the tree- ie walking it in certain orders to achieve desired results (sorting/ordering of values, among other things).
  
 As we will be placing nodes in the tree according to their stored values (lesser values go to the left, or previous; greater values go to the right, or next), our tree will naturally sort our data for us. As we will be placing nodes in the tree according to their stored values (lesser values go to the left, or previous; greater values go to the right, or next), our tree will naturally sort our data for us.
Line 98: Line 127:
     char  max_height;               // max height of tree (0 = unlimited)     char  max_height;               // max height of tree (0 = unlimited)
     char  height;                   // current height of tree     char  height;                   // current height of tree
-    Node *(*copy)(Tree *         ); // copy tree (function pointer)+    Tree *(*copy)(Tree *         ); // copy tree (function pointer)
     Tree *(*grab)(Tree *, Node **); // grab node (function pointer)     Tree *(*grab)(Tree *, Node **); // grab node (function pointer)
-    List *(*walk)(Tree *, Node * ); // walk tree (function pointer)+    List *(*walk)(Tree *, char   ); // walk tree (function pointer)
 }; };
  
Line 113: Line 142:
 Tree *copytree_i(Tree *         );  // copy/duplicate given tree (iterative) Tree *copytree_i(Tree *         );  // copy/duplicate given tree (iterative)
  
-Node *findnode  (Tree *, char   );  // find node in tree+Node *searchtree(Tree *, char   );  // find node in tree
  
 Tree *grabnode_s(Tree *, Node **);  // stack-based grabnode Tree *grabnode_s(Tree *, Node **);  // stack-based grabnode
Line 142: Line 171:
 As the layers and complexities rise, narrowing down the source of errors becomes increasingly important. As the layers and complexities rise, narrowing down the source of errors becomes increasingly important.
  
-If your tree addnode_i() isn't working, is it because of a problem with your tree? Or might it be in an underlying node operation it relies upon?+If your tree copytree_i() isn't working, is it because of a problem with your tree? Or might it be in an underlying node operation it relies upon?
  
 To aid you in your development efforts, you now have the ability to import functioning node, list, and stack implementations into your project for the purposes of testing your tree functionality. To aid you in your development efforts, you now have the ability to import functioning node, list, and stack implementations into your project for the purposes of testing your tree functionality.
Line 177: Line 206:
  
 ===Reverting back to using your code=== ===Reverting back to using your code===
-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:+If you were trying out the reference implementation to verify tree functionality, and wanted to revert back to your own code, it is as simple as:
  
 <cli> <cli>
Line 188: Line 217:
  
 Be sure to run the various node unit tests and verification scripts to see which functions have fallen out of compliance with the node struct specification changes issued in this project. The **verify-node.sh** script can be especially useful in getting a big picture view of what work is needed. Be sure to run the various node unit tests and verification scripts to see which functions have fallen out of compliance with the node struct specification changes issued in this project. The **verify-node.sh** script can be especially useful in getting a big picture view of what work is needed.
-====Queue library unit tests==== +====Tree library unit tests==== 
-In **testing/tree/unit/**, you will find these files:+In **testing/tree/unit/**, you will //eventually// find these files:
  
-  * **unit-add.c** - unit test for the various addnode_*() library functions +  * **unit-addnode.c** - unit test for the various **addnode()** library function 
-  * **unit-find.c** - unit test for the various findnode_*() library functions +  * **unit-searchtree.c** - unit test for the various **searchtree()** library function 
-  * **unit-get.c** - unit test for getnode_*() library functions+  * **unit-grab.c** - unit test for **grabnode_*()** library functions
   * **unit-set_mode.c** - unit test for **set_mode()** library function   * **unit-set_mode.c** - unit test for **set_mode()** library function
   * **unit-balance.c** - unit test for **balance()** library function   * **unit-balance.c** - unit test for **balance()** library function
-  * **unit-treeops.c**   - unit test for {mk,cp,rm}tree library functions +  * **unit-treeops.c**   - unit test for {mk,rm}tree library functions 
-  * **unit-show.c** - unit test for tree displaying functions+  * **unit-traverse.c** - unit test for **traverse_*()** library functions 
 +  * **unit-print.c** - unit test for displaying tree structure 
 + 
 +**NOTE**: At the time of project release, unit tests are not yet available; so they will be released as they are developed. 
  
 There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent tree functionality. There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent tree functionality.
Line 217: Line 249:
  
 =====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 node and tree libraries should resemble the following (when running the respective verify script):
  
  
Line 224: Line 256:
  
 <cli> <cli>
-lab46:~/src/data/dlt0$ bin/verify-list.sh +lab46:~/src/data/dlt0$ bin/verify-node.sh 
 ==================================================== ====================================================
-=    Verifying Doubly-Linked List Functionality    =+=    Verifying Doubly-Linked Node Functionality    =
 ==================================================== ====================================================
-  [mklist] Total:   6, Matches:   6, Mismatches:   0 +  [mknode] Total:   6, Matches:   6, Mismatches:   0 
-  [cplist] Total:  30, Matches:  30, Mismatches:   0 +  [cpnode] Total:   8, Matches:   8, Mismatches:   0 
-  [rmlist] Total:   3, Matches:   3, Mismatches:   0 +  [rmnode] Total:   2, Matches:   2, 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+ [RESULTS] Total:  16, Matches:  16, Mismatches:   0
 ==================================================== ====================================================
 lab46:~/src/data/dlt0$  lab46:~/src/data/dlt0$ 
Line 248: Line 273:
  
 ====tree library==== ====tree library====
-Here is what you should get for queue:+Here is what you should get for tree:
  
 <cli> <cli>
 lab46:~/src/data/dlt0$ bin/verify-tree.sh  lab46:~/src/data/dlt0$ bin/verify-tree.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/dlt0$  lab46:~/src/data/dlt0$ 
 </cli> </cli>
haas/fall2014/data/projects/dlt0.1416255462.txt.gz · Last modified: 2014/11/17 20:17 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