Question

Can someone explain to me whats happening for every method in this code and the breakdown of everything. I added the p2.h file for any reference needed and i need the Implementation of the tree ADT in the p2.h file explained and why it was implemented in that file and not p2.cpp.

p2.cpp

#include 
#include "p2.h"
#include "recursive.h"

using namespace std;

static int sum_helper(list_t list, int total) {

    if(list_isEmpty(list))

    {

                return total;

        }

     else

        return sum_helper(list_rest(list), total + list_first(list));

}

int sum(list_t list) {

    return sum_helper(list, 0);

}

static int product_helper(list_t list, int total) {

    if(list_isEmpty(list))

    {

                return total;

        }

    else

        return (product_helper(list_rest(list), total * list_first(list)));

}

int product(list_t list) {

    return product_helper(list, 1);

}

static int accumulate_helper(list_t list, list_t otherList, int result, int (*fn)(int, int), int identity) {

    if(list_isEmpty(list)) return identity;

    else if(list_isEmpty(otherList))return result;

    else

    {

        result = fn(list_first(otherList), result);

        return accumulate_helper(list, list_rest(otherList), result, fn, identity);

    }

}

int accumulate(list_t list, int (*fn)(int, int), int identity) {

    return accumulate_helper(list, list, identity, fn, identity);

}

static list_t reverse_helper(list_t list, list_t reverse) {

    if(list_isEmpty(list)) return reverse;

    else return reverse_helper(list_rest(list), list_make(list_first(list), reverse));

}

list_t reverse(list_t list)

{

    return reverse_helper(list, list_make());

}

static list_t append_helper(list_t first, list_t second, list_t reverse_first, list_t result) {

    if(list_isEmpty(first) && list_isEmpty(second)) return list_make();

    else if(list_isEmpty(first))return second;

    else if(list_isEmpty(second))return first;

    else

    {

        if(list_isEmpty(reverse_first))return result;

        else

        {

                 return append_helper(first, second, list_rest(reverse_first), list_make(list_first(reverse_first), result));

        }

    }

}

list_t append(list_t first, list_t second) {

    return append_helper(first, second, reverse(first), second);

}

static list_t filter_odd_helper(list_t list, list_t result) {

    if(list_isEmpty(list))return result;

    else

    {

            if (!(list_first(list)%2))

                return filter_odd_helper(list_rest(list), result);

            else return filter_odd_helper(list_rest(list), list_make(list_first(list), result));

    }

}

list_t filter_odd(list_t list) {

    return filter_odd_helper(list, list_make());

}

static list_t filter_even_helper(list_t list, list_t result) {

    if(list_isEmpty(list))return result;

                else

                {

            if (list_first(list)%2)

                {return filter_even_helper(list_rest(list), result);}

            else 

                {return filter_even_helper(list_rest(list), list_make(list_first(list), result));}

                }

}

list_t filter_even(list_t list) {

    return filter_even_helper(list, list_make());

}

static list_t filter_helper(list_t list1, list_t otherList, bool (*fn)(int), list_t result) {

    if(list_isEmpty(list1)) return result;

    else if(list_isEmpty(otherList)) return result;

    else if(fn(list_first(otherList)))

    {

          result = list_make(list_first(otherList), result);

          return filter_helper(list1, list_rest(otherList), fn, result);

    }

    else return filter_helper(list1, list_rest(otherList), fn, result);

}

list_t filter(list_t list, bool (*fn)(int)) {

    return reverse(filter_helper(list, list, fn, list_make()));

}

static list_t rotate_helper(list_t result, unsigned int n){

    if(n == 0 || list_isEmpty(result))return result;

    else return rotate_helper(reverse(list_make(list_first(result), reverse(list_rest(result)))), n-1);

}

list_t rotate(list_t list, unsigned int n)

{

    return rotate_helper(list, n);

}

static list_t insert_list_helper(list_t inFirst, list_t first, list_t fir1, list_t fir2, list_t second, unsigned int n2, unsigned int n1) {

      if (list_isEmpty(inFirst) || list_isEmpty(second) || n2==0)

     {

      if(n2==0)return append(second, inFirst);

          else return append(inFirst, second);

     } else {

        if (n1>0) 

          {return insert_list_helper(inFirst, list_rest(first), list_make(list_first(first),fir1),list_rest(first),second,n2,n1-1);}

            else

              return append(reverse(fir1), append(second, fir2));

      }

}

list_t insert_list(list_t first, list_t second, unsigned int n) {

       return insert_list_helper(first, first, list_make(), list_make(), second, n, n);

}

static list_t chop_helper(list_t numl, unsigned int n) {

      if(list_isEmpty(numl) || n==0) return numl;

      else return chop_helper(list_rest(numl), n-1);

}

list_t chop(list_t l, unsigned int n) {

    return reverse(chop_helper(reverse(l), n));

}

int fib(int n) {

    if(n==0) return 0;

    else if (n==1) return 1;

    else return (fib(n-1) + fib(n-2));

}

static int fib_tail_helper(int a, int counter, int b, int c) {

    if(a==0)return 0;

    else if(a==1)return 1;

    else

    {

         if(counter

else if(a%2) return c; 

         else return b;

    }

}

int fib_tail(int n) {

    if (!(n%2)) return fib_tail_helper(n, 0, 0, 1);

    else return fib_tail_helper(n, 1, 0, 1);

}

int tree_sum(tree_t tree)

{

     if(tree_isEmpty(tree)) return 0;

     else if(tree_isEmpty(tree_left(tree))&& tree_isEmpty(tree_right(tree)))return tree_elt(tree);

     else if(tree_isEmpty(tree_left(tree)))return (tree_elt(tree) + tree_sum(tree_right(tree)));

     else if(tree_isEmpty(tree_right(tree)))return (tree_elt(tree) + tree_sum(tree_left(tree)));

     else return(tree_elt(tree) + tree_sum(tree_left(tree)) + tree_sum(tree_right(tree)));

}

list_t traversal(tree_t tree)

{

      list_t ord_list = list_make();

      if(tree_isEmpty(tree))return ord_list;

                else

                {

           list_t elt = list_make(tree_elt(tree),list_make());

           if(!(tree_isEmpty(tree_right(tree))))

                ord_list = append(traversal(tree_right(tree)), elt);

           if(!(tree_isEmpty(tree_left(tree))))

                 ord_list = append(traversal(tree_left(tree)), elt);

           return ord_list;

                }

}
bool contained_by(tree_t A, tree_t B)

{

      if(tree_isEmpty(A)) return true;

      else if(!(tree_isEmpty(A) && tree_isEmpty(B))) return false;

                else

                {

            if(list_first(traversal(A)) == list_first(traversal(B)))

                  return contained_by(traversal(A), traversal(B));

            else

                  return(contained_by(tree_right(A), tree_right(B)) && contained_by(tree_left(A), tree_left(B)));

                }

}

tree_t insert_tree(int elt, tree_t tree)

{

      if(tree_isEmpty(tree))return tree_make(elt, tree_make(),tree_make());

                else

                {

            if(elt

return tree_make(tree_elt(tree), insert_tree(elt, tree_left(tree)), tree_right(tree)); 

            else

                  return tree_make(tree_elt(tree), tree_left(tree), insert_tree(elt, tree_right(tree)));

                }

}

the implementation in the p2.h file is below.

const unsigned int  tree_node_id = 0x45ee45ee;
const unsigned int  tree_empty_id = 0x56ff56ff;

struct tree_node 

{

    unsigned int       tn_id;    // Are we really a tree_node?
    int                tn_elt;   // This element
    struct tree_node  *tn_left;  // left subtree
    struct tree_node  *tn_right; // right subtree

};
static struct tree_node *
tree_checkValid(tree_t tree)

    // MODIFIES: cerr

    // EFFECTS: assert if tnp does not appear to be a valid tree, 

    //          writing an appropriate error message to cerr.

{

    struct tree_node *tnp = (struct tree_node *)tree;

    if ((tnp->tn_id != tree_node_id) && (tnp->tn_id != tree_empty_id)) {
        std::cerr << "Error: user pass invalid tree\n";
        //assert(0);

    }

    return tnp;

}

static void
tree_checkNonEmpty(tree_t tree)

{

  if (tree_isEmpty(tree))  {
      std::cerr << "Error: user pass empty tree\n";
     // assert(0);

    }

}

bool
tree_isEmpty(tree_t tree)

{

    struct tree_node *tnp = tree_checkValid(tree);
    return (tnp->tn_id == tree_empty_id);

}

tree_t

tree_make()

{

    struct tree_node *tnp = 0;

    try 

    {

      tnp = new struct tree_node;

    } 

        catch (std::bad_alloc a) 

    {

      //not_allocated();

    }
    tnp->tn_id = tree_empty_id;
    tnp->tn_left = NULL;
    tnp->tn_right = NULL;
    return tnp;

}
tree_t
tree_make(int elt, tree_t left, tree_t right)

{

    struct tree_node *tnp = 0;

    try 

    {

        tnp = new struct tree_node;

    } 

        catch (std::bad_alloc a) 

    {

        //not_allocated();

    }

    if (!tree_isEmpty(left)) 

    {

      tree_checkValid(left);

    }

    if (!tree_isEmpty(right)) 

    {

      tree_checkValid(right);

    }
    tnp->tn_id = tree_node_id;
    tnp->tn_elt = elt;
    tnp->tn_left = (struct tree_node *)left;
    tnp->tn_right = (struct tree_node *)right;
    return tnp;

}

int
tree_elt(tree_t tree)

{

    tree_checkNonEmpty(tree);
    struct tree_node *tnp = tree_checkValid(tree);
    return tnp->tn_elt;

}

tree_t
tree_left(tree_t tree)

{

    tree_checkNonEmpty(tree);
    struct tree_node *tnp = tree_checkValid(tree);
    return tnp->tn_left;

}
tree_t
tree_right(tree_t tree)

{

    tree_checkNonEmpty(tree);

    struct tree_node *tnp = tree_checkValid(tree);

    return tnp->tn_right;

}

static void
print_spaces(int spaces)

    // MODIFIES: cout
    // EFFECTS: prints n spaces

{

  while (spaces--) 

 {

      std::cout << "  ";

    }

}

static void
tree_print_internal(tree_t tree, int spaces)

    // MODIFIES: cout
    // EFFECTS: prints tree contents recursively, with newlines 
    //          for each node, with each level indented

{

  print_spaces(spaces);

    if (tree_isEmpty(tree)) 

    {
       std::cout << "( )\n";

    } else {

      std::cout << "(" << tree_elt(tree) << "\n";
        tree_print_internal(tree_left(tree), spaces+1);
        tree_print_internal(tree_right(tree), spaces+1);
        print_spaces(spaces);
        std::cout << " )\n";

    }

}
void
tree_print(tree_t tree)

{

  tree_print_internal(tree, 0);

}

Answer 1

Functions:

1. sum_helper :

It is a recursive function to find the sum of a list. In base condition, if list is empty, total will be passed as 0 so, value returned will be 0 Otherwise the same function will be called with the updated value of total and reduced size of list.

2. sum

Function to find the sum of a list. It calls the sum_helper function && passes initial value as 0.

Note: 0 is a additive identity.

3. product_helper :

It is a recursive function to find the product of elements of a list. It is similar to a function sum_helper but instead of '+ operator, '* operator is used  for multiplication purpose.

4. product :

Function to find the product of a list. It calls the product_helper function && passes initial value as 1.

Note: 1 is a multiplicative identity.

5. accumulate_helper :

This is a generalized helper function which can be used to perform any operation (in-built or used defined function) on the given lists by passing the identities and result variables. Please see below for more details about input parameters and return type.

parameter Name	Description	Note
list & other_list	List on which the operation will be performed.	-
result	Output value obtained by performing the operation on list	Initial, result value will be equal to identity.
fn	Function to be performed on the list	Examples - sum, product etc.
identity	As usual identity of function/operation.	Example - Identity = 0 for sum, 1 for product.

6. accumulate:

The Function used to call accumulate helper to accumulate the value from the list.

For example, To find the sum of a list (denoted by '+ operator), we can call helper function in this way:

int sum = accumulate_helper(list, list, 0, '+, 0);

To find the product of a list (denoted by '* operator), we can call helper function in this way:

int product = accumulate_helper(list, list, 1, '*, 1);

7. reverse_helper

A helper function used to reverse a list by the help of list_make.

list_make(): Takes one number & list as an input and return the new list after adding the number into the list.

In recursive call, we reduced size of original list by 1, and called list_make() to add it at first.

8. reverse

The function which uses reverse_helper to reverse a list.

It will pass the original list as an input and one empty list (considered as output in each recurive call).

9. append_helper :

This is a helper function to append the two list and return a new obtained list.

parameter Name	Description	Note
first	First list to be appended	-
second	second list to be appended
reverse_first	Reduced list first after adding elements to list second.	Initially, reverse_first = reverse(first).
result	Resultant list formed by appending two lists.	Initial, list result is equal to list second.

Note: The first three conditions are base conditions which includes,

1.) If both the lists are empty, return empty list.

2.) If list first is empty, resultant list is the list second.

3.) If list second is empty, resultant list is the list first.

This function recursively call to itself with after appending one element from list first to resultant list.

10. append

A function used to call the append_helper function to append two lists.

11. filter_odd_helper :

A helper function used to filter the list and return a list of odd elements (not divisible by 2) in it. If current element is an odd element then it will be added in the resultant list and recursively call itself for the remaining list. and if it not an odd element then it will call recursively without adding the current element to the resultant list.

12. filter_odd

A function used to filter the odd elements from a list.

13. filter_even_helper :

A helper function used to filter the list and return a list of even elements (divisible by 2) in it. If current element is an even element then it will be added in the resultant list and recursively call itself for the remaining list. and if it not an even element then it will call recursively without adding the current element to the resultant list.

14. filter_even

A function used to filter the even elements from a list.

15. filter_helper

This is a generalized helper function which can be used to filter the elements from a list by using a function (in-built or used defined function). Function parameter fn is used to decide whether the current element has to be included or not based on the purpose. For example

To filter odd elements, fn can be

int fn (int num){

if (num%2==0)

return 0;

else

return 1;

}

To filter even elements, fn can be

int fn (int num){

if (num%2==0)

return 1;

else

return 0;

}

16. rotate_helper :

A helper function to rotate a list by some number n.

For example- Rotate a list '(1, 2 , 3 , 4, 6) by 2 then, output list is '(3, 4, 6, 2, 1).

17. rotate

A function to rotate a list by some number n. If n = 0 then, the same list will be returned.

18. fib

A function to calculate the Fibonacci number recursively.

Fib(n) = Fib(n-1) + Fib(n-2)

19. tree_sum

A function to return the sum of node values of a tree.

Base condition: if tree is null, sum=0;

Recursive call: Sum of a tree = sum of current node + sum of left subtree + sum of right subtree.

20. traversal :

A function to traverse a tree in Pre-order traversal. i.e. first current node will be added into the resultant list and then left subtree and right subtree.

Base condition: If node is null, just return the resultant list.

Recursive call: Add current element into the resultant list, visit the left subtree & then right subtree.

21. Contained tree:

A function to see if a tree is a contained in the another tree.

Note: Each and every element of a tree should appear in the same order in the subtree of other tree.

22. insert_tree:

Insert a new element as the root node.

It uses a tree_make() function defined in p2.h to make a new tree after adding an element.

p2.h is a header file which contains the data structure tree && it's usual functions. These functions can be added in to the p2.c but header files are recommended inorder to reuse them without writting the same code again and again. They offers reusability of code & makes functions of a data structure apart from our logic.