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 12:54] – [queue library] 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 83: Line 112:
 #define _TREE_H #define _TREE_H
  
-#include "node.h"+#include "list.h"
  
-#define  RECURSIVE      0 +#define  RECURSIVE     0 
-#define  STACK_BASED    1 +#define  STACK_BASED   1 
-#define  ITERATIVE      2+#define  ITERATIVE     2
  
-#define  IN-ORDER       0 +#define  INORDER       0 
-#define  PRE-ORDER      1 +#define  PREORDER      1 
-#define  POST-ORDER     2+#define  POSTORDER     2
  
 +typedef struct tree Tree;
 struct tree { struct tree {
     Node *root;                     // pointer to root node of tree     Node *root;                     // pointer to root node of tree
-    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 
-    Tree *(*add) (Tree *, Node * ); // addnode node (function pointer) +    Tree *(*copy)(Tree *         ); // copy tree (function pointer) 
-    Node *(*find)(Tree *, char   ); // find value (function pointer) +    Tree *(*grab)(Tree *, Node **); // grab node (function pointer) 
-    Tree *(*get) (Tree *, Node **); // get node (function pointer)+    List *(*walk)(Tree *, char   ); // walk tree (function pointer)
 }; };
-typedef struct tree Tree; 
  
 Tree *mktree    (char           );  // create new tree Tree *mktree    (char           );  // create new tree
Line 107: Line 136:
 Tree *set_mode  (Tree *, char   );  // set tree mode (recurse, stack, iter) Tree *set_mode  (Tree *, char   );  // set tree mode (recurse, stack, iter)
  
-Tree *addnode_s (Tree *, Node * );  // stack-based addnode +Tree *addnode   (Tree *, Node * );  // add given node to tree
-Tree *addnode_r (Tree *, Node * );  // recursive addnode +
-Tree *addnode_i (Tree *, Node * );  // iterative addnode+
  
-Node *findnode_s(Tree *, char   );  // stack-based find +Tree *copytree_s(Tree *         );  // copy/duplicate given tree (stack-based) 
-Node *findnode_r(Tree *, char   );  // recursive find +Tree *copytree_r(Tree *         );  // copy/duplicate given tree (recursion) 
-Node *findnode_i(Tree *, char   );  // iterative find+Tree *copytree_i(Tree *         );  // copy/duplicate given tree (iterative)
  
-Tree *getnode_s (Tree *, Node **);  // stack-based getnode +Node *searchtree(Tree *, char   );  // find node in tree 
-Tree *getnode_r (Tree *, Node **);  // recursive getnode + 
-Tree *getnode_i (Tree *, Node **);  // iterative getnode+Tree *grabnode_s(Tree *, Node **);  // stack-based grabnode 
 +Tree *grabnode_r(Tree *, Node **);  // recursive grabnode 
 +Tree *grabnode_i(Tree *, Node **);  // iterative grabnode 
 + 
 +List *traverse_s(Tree *, char   );  // stack-based traverse (in mode) 
 +List *traverse_r(Tree *, char   );  // recursive traverse (in mode) 
 +List *traverse_i(Tree *, char   );  // iterative traverse (in mode)
  
-Tree *cptree    (Tree *         );  // copy/duplicate given tree 
 Tree *rmtree    (Tree *         );  // purge and deallocate tree Tree *rmtree    (Tree *         );  // purge and deallocate tree
  
-Tree *balance   (Tree *         );  // rebalanced tree (root is midpochar)+Tree *balance   (Tree *         );  // rebalanced tree (root is midpoint)
  
-void  show_tree (Tree *, char   );  // display tree contents (in mode) 
 void  print_tree(Tree *         );  // display tree structure (to STDOUT) void  print_tree(Tree *         );  // display tree structure (to STDOUT)
  
Line 140: 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 stack push() isn't working, is it because of a problem in push()? Or might it be in an underlying list operation it relies upon? Or perhaps even the lowest-level node functions..+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 a functioning node and list implementation into your project for the purposes of testing your stack 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.
  
-This also provides another opportunity for those who have fallen behind to stay current, as they can work on this project without having needed to successfully get full list functionality.+This also provides another opportunity for those who have fallen behind to stay current, as they can work on this project without having needed to successfully get full node or stack (and by extension- list) functionality.
  
 ===Using the test reference implementation=== ===Using the test reference implementation===
Line 156: Line 187:
 </cli> </cli>
  
-In order to make use of it, you'll need to run **make use-test-reference** from the base of your **dlq0** project directory, as follows:+In order to make use of it, you'll need to run **make use-test-reference** from the base of your **dlt0** project directory, as follows:
  
 <cli> <cli>
-lab46:~/src/data/dlq0$ make use-test-reference+lab46:~/src/data/dlt0$ make use-test-reference
 ... ...
-NODE and LIST reference implementation in place, run 'make' to build everything. +NODE, LIST, and STACK reference implementation in place, run 'make' to build everything. 
-lab46:~/src/data/dlq0$ +lab46:~/src/data/dlt0$ 
 </cli> </cli>
  
Line 168: Line 199:
  
 <cli> <cli>
-lab46:~/src/data/dlq0$ make+lab46:~/src/data/dlt0$ make
 ... ...
 </cli> </cli>
  
-**__Debugging__:** When using the test reference implementation, you will not be able to debug the contents of the node and list functions (the files provided do not have debugging symbols added), so you'll need to take care not to step into these functions (it would be just like stepping into **printf()**. You can still compile the project with debugging support and debug (as usual) those compiled functions (ie the stack functions).+**__Debugging__:** When using the test reference implementation, you will not be able to debug the contents of the node, list, and stack functions (the files provided do not have debugging symbols added), so you'll need to take care not to step into these functions (it would be just like stepping into **printf()**. You can still compile the project with debugging support and debug (as usual) those compiled functions (ie the stack functions).
  
 ===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>
-lab46:~/src/data/dlq0$ make use-your-own-code +lab46:~/src/data/dlt0$ make use-your-own-code 
-Local node/list implementation restored, run 'make clean; make' to build everything. +Local node/list/stack implementation restored, run 'make clean; make' to build everything. 
-lab46:~/src/data/dlq0$ +lab46:~/src/data/dlt0$ 
 </cli> </cli>
-====List Library unit tests==== +====Node 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).+As a result of the addition of **other**, an updated set of unit tests 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. +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/queue/unit/**, you will find these files:+In **testing/tree/unit/**, you will //eventually// find these files:
  
-  * **unit-mkqueue.c** - unit test for **mkqueue()** library function +  * **unit-addnode.c** - unit test for the various **addnode()** library function 
-  * **unit-cpqueue.c** - unit test for **cpqueue()** library function +  * **unit-searchtree.c** - unit test for the various **searchtree()** library function 
-  * **unit-rmqueue.c** - unit test for **rmqueue()** library function +  * **unit-grab.c** - unit test for **grabnode_*()** library functions 
-  * **unit-enqueue.c** - unit test for **enqueue()** library function +  * **unit-set_mode.c** - unit test for **set_mode()** library function 
-  * **unit-dequeue.c** - unit test for **dequeue()** library function +  * **unit-balance.c** - unit test for **balance()** library function 
-  * **unit-purge.c**   - unit test for **purge()** library function+  * **unit-treeops.c**   - unit test for {mk,rm}tree library functions 
 +  * **unit-traverse.c** - unit test for **traverse_*()** library functions 
 +  * **unit-print.c** - unit test for displaying tree structure
  
-There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent stack functionality.+**NOTE**: At the time of project release, unit tests are not yet available; so they will be released as they are developed. 
  
-These are complete runnable programs (when compiled, and linked against the queue library, which is all handled for you by the **Makefile** system in place).+There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent tree functionality. 
 + 
 +These are complete runnable programs (when compiled, and linked against the tree library, which is all handled for you by the **Makefile** system in place).
  
 Of particular importance, I want you to take a close look at: Of particular importance, I want you to take a close look at:
Line 214: 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):
  
  
-====list library==== +====node library==== 
-Here is what you should get for list:+Here is what you should get for node:
  
 <cli> <cli>
-lab46:~/src/data/dlq0$ 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/dlq0$ +lab46:~/src/data/dlt0$ 
 </cli> </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.+With the addition of the **other** pointer, we have a few additional combinations to test.
  
-But aside from this change to **display()**, your list implementation can remain unchanged. 
  
-====queue library==== +====tree library==== 
-Here is what you should get for queue:+Here is what you should get for tree:
  
 <cli> <cli>
-lab46:~/src/data/dlq0$ bin/verify-queue.sh  +lab46:~/src/data/dlt0$ bin/verify-tree.sh  
-=================================================== +coming soon 
-=   Verifying Doubly-Linked Queue Functionality   = +lab46:~/src/data/dlt0$ 
-=================================================== +
-[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$ +
 </cli> </cli>
  
Line 269: Line 285:
  
   * Project must be submit on time, by the posted deadline.   * Project must be submit on time, by the posted deadline.
-    * Late submissions will lose 25% credit per day, with the submission window closing on the 4th day following the deadline.+    * As this project is due at the very end of the semester, there is no late window. It is either submitted, or it is not.
   * All code must compile cleanly (no warnings or errors)   * All code must compile cleanly (no warnings or errors)
     * all requested functions must be implemented in the related library     * all requested functions must be implemented in the related library
haas/fall2014/data/projects/dlt0.1416228847.txt.gz · Last modified: 2014/11/17 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