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 22:28] – [Reference Implementation] 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 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 241: 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.1416263283.txt.gz · Last modified: 2014/11/17 22:28 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