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/16 16:47] – [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 19: Line 47:
 A **tree** is our first foray into the realm of non-linear data structures. While it still consists of nodes, and those nodes are linked together, they are not linked together in a way providing a contiguous succession as we have in a list. A **tree** is our first foray into the realm of non-linear data structures. While it still consists of nodes, and those nodes are linked together, they are not linked together in a way providing a contiguous succession as we have in a list.
  
-The simplest tree is one which has a minimum of two connections- often these are called 'binary' trees. We will use that description interchangeably here with 'doubly linked trees'.+Truth be told, the simplest tree is merely a list- the underlying data structure we've worked with all semester. But now, under this new light, we can start to look at a list as merely a procession of singled childed nodes. The more things are different, the more they are the same... 
 + 
 +The simplest conceptual tree is one which has a minimum of two connections- often these are called 'binary' trees. We will use that description interchangeably here with 'doubly linked trees'.
  
 The premise behind a tree is that of a parent-child relationship. Each node can be a parent (of two child nodes), and each child can in turn be its own parent (of two child nodes). This creates a connection between relationships of nodes (ie a parent and its descendants), and ends up offering some interesting and useful algorithmic opportunities, along with implementation experience. The premise behind a tree is that of a parent-child relationship. Each node can be a parent (of two child nodes), and each child can in turn be its own parent (of two child nodes). This creates a connection between relationships of nodes (ie a parent and its descendants), and ends up offering some interesting and useful algorithmic opportunities, along with implementation experience.
Line 38: 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 81: 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 105: 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+Tree *copytree_s(Tree *         );  // copy/duplicate given tree (stack-based) 
 +Tree *copytree_r(Tree *         );  // copy/duplicate given tree (recursion) 
 +Tree *copytree_i(Tree *         );  // copy/duplicate given tree (iterative) 
 + 
 +Node *searchtree(Tree *, char   );  // find node in tree
  
-Node *findnode_s(Tree *, char   );  // stack-based find +Tree *grabnode_s(Tree *, Node **);  // stack-based grabnode 
-Node *findnode_r(Tree *, char   );  // recursive find +Tree *grabnode_r(Tree *, Node **);  // recursive grabnode 
-Node *findnode_i(Tree *, char   );  // iterative find+Tree *grabnode_i(Tree *, Node **);  // iterative grabnode
  
-Tree *getnode_s (Tree *, Node **);  // stack-based getnode +List *traverse_s(Tree *, char   );  // stack-based traverse (in mode) 
-Tree *getnode_r (Tree *, Node **);  // recursive getnode +List *traverse_r(Tree *, char   );  // recursive traverse (in mode) 
-Tree *getnode_i (Tree *, Node **);  // iterative getnode+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 128: Line 161:
 </code> </code>
  
-====list library==== 
-One more enhancement is in store for our venerable **display()** function, and that is described below: 
  
-===display() enhancements=== +====tree library==== 
-You are also to implement an additional feature (resulting in 8 additional modes) to the **display()** function.  +In **src/tree/**, you will find skeletons of the above prototyped functions, hollowed out in anticipation of being made operational.
- +
-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==== +
-In **src/queue/**, you will find skeletons of the above prototyped functions, hollowed out in anticipation of being made operational.+
  
 Figure out what is going on, the connections, and make sure you understand it. Figure out what is going on, the connections, and make sure you understand it.
  
-Again, your queue is to utilize the list for its underlying data storage operations. This is what the queue's **data** list pointer is to be used for. +Of particular focus in this project, in addition to the important tree concepts, is that of implementation. Until now we've only bothered to just get it done and working... now, not only do we care about functionality, but we look more closely at how we got there (ie the three different implementation approaches).
 ====Reference Implementation==== ====Reference Implementation====
 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 214: 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 226: 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 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. 
 +====Tree library unit tests==== 
 +In **testing/tree/unit/**, you will //eventually// find these files:
  
-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. +  * **unit-addnode.c** - unit test for the various **addnode()** library function 
-====Queue library unit tests==== +  * **unit-searchtree.c** - unit test for the various **searchtree()** library function 
-In **testing/queue/unit/**, you will find these files:+  * **unit-grab.c** - unit test for **grabnode_*()** library functions 
 +  * **unit-set_mode.c** - unit test for **set_mode()** library function 
 +  * **unit-balance.c** - unit test for **balance()** 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
  
-  * **unit-mkqueue.c** - unit test for **mkqueue()** library function +**NOTE**: At the time of project release, unit tests are not yet available; so they will be released as they are developed. 
-  * **unit-cpqueue.c** - unit test for **cpqueue()** library function +
-  * **unit-rmqueue.c** - unit test for **rmqueue()** library function +
-  * **unit-enqueue.c** - unit test for **enqueue()** library function +
-  * **unit-dequeue.c** - unit test for **dequeue()** library function +
-  * **unit-purge.c**   - unit test for **purge()** library function+
  
-There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent stack functionality.+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 queue library, which is all handled for you by the **Makefile** system in place).+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 272: 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 327: 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.1416156475.txt.gz · Last modified: 2014/11/16 16:47 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