Wednesday, February 22, 2017

Seeking your input for the next edition of Data Structures and Abstractions with Java

We have begun the 5th edition of Data Structures and Abstractions with Java. Do you have suggestions about how to improve our presentation? I welcome suggestions from both students and instructors. You can post them here or email me directly at carrano@cs.uri.edu. This new edition will be available early in 2018.

Sunday, February 12, 2017

Wednesday, December 28, 2016

A way to learn more when you study

"You can truly understand a topic when you have to teach it." Many teachers have heard and agreed with this statement. The Feynman Technique for studying is based on this advice. Check it out!

Wednesday, November 30, 2016

Tree traversals and C++11 lambda functions

One of our readers of Walls and Mirrors 7th edition had a problem with the traversal operation for TreeDictionary, which is described in section 18.2.2 of Chapter 18 (page 559). My co-author, Tim Henry, fielded the question, and I’m happy to share his response with you. The problem involves the data type of the traversal’s parameter, and the solution involves lambda functions, a feature of C++11 but one that we do not cover in the current edition of our book.

PROBLEM:

Recall that TreeDictionary stores its key-value entries in a binary search tree. The traversal operation is declared as follows:

/** Traverses the entries in this dictionary in sorted search-key order
    and calls a given client function once for the value in each entry. */
void TreeDictionaryValueType>::traverse(void visit(ValueType&)) const;

This function has a single parameter, which is a function whose only parameter is of type ValueType.

Our BinarySearchTree, as described in Chapter 16, stores entries of type ItemType, and declares the operation inorderTraverse as

void BinarySearchTree::inorderTraverse(void visit(ItemType&)) const;

TreeDictionary stores key-value pairs as objects of type Entry into the binary search tree entryTree. When you call TreeDictionary::traverse, the visit function you pass to it expects an argument of type ValueType. But when TreeDictionary::traverse calls BinarySearchTree::inorderTraverse using the statement

entryTree.inorderTraverse(visit);

visit expects an argument of type Entry. Therefore, the wrong type of argument is passed, and we get a compilation error.

GOAL: 

Find a way to “convert” visit into a function whose parameter is of type Entry  so we can pass it to inorderTraverse. Maybe a function something like this:

void someFunction(EntryValueType>& someEntry)
{
   auto someItem = someEntry.getItem(); // Must have an address for someItem
   visit(someItem);
}

But how do we give the function access to visit without changing its signature?

SOLUTION:

Lambda functions! Here is the new implementation for TreeDictionary::traverse:

TreeDictionary::traverse(void visit(ValueType&)) const
{
   auto treeVisit = [=](EntryValueType>& someEntry)
   {
      auto someItem = someEntry.getItem();
      visit(someItem);
   };
   entryTree.inorderTraverse(treeVisit);
}

The meaning of the previous lambda syntax follows:

[] means a lambda definition will follow. 
Only [] indicates to not “capture” or access local variables from the parent local environment. 
[&] means to access local variables as pass-by-reference. (This works for our scenario also.)
[=] means to access local variables as pass-by-copy (value). 

After the square brackets is the parameter list for the lambda function. In our case, it is the parameter type our tree needs: 
(EntryValueType>& someEntry)

Then we have the function implementation inside a pair of braces { } followed by a semicolon.

This works when the lambda function does not capture any local variables. 

BUT . . . 

We need to capture the local variable/parameter visit.

So we must use a more formal definition for the function parameters in the tree classes. (We could do this in TreeDictionary also, but it works without that change).

In BinaryTreeInterface.h, add:

#include

Then in the tree files

BinaryTreeInterface.h
BinaryNodeTree.h
BinaryNodeTree.cpp
BinarySearchTree.h
BinarySearchTree.cpp

change the signature of inorderTraverse so that it has the following parameter in red:

inorderTraverse(std::function visit)

This change relaxes some restrictions on how the lambda function can be passed as an argument. 

In BinaryNodeTree.h and BinaryNodeTree.cpp, you should also change the protected function inorder:

void inorder(std::function visit
                   std::shared_ptr> treePtr) const;


Make analogous changes to inorderTraverse and postorderTraverse.

Tuesday, October 18, 2016

Wednesday, October 12, 2016

Why Walls and Mirrors:C++ uses templates.

Our data structures book with C++ (Data Abstraction and Problem Solving with C++: Walls and Mirrors 7th ed.) covers and uses templates from the beginning. We do so in a simple straightforward way. The code that we present enables a student to create a data structure that stores data of any one data type (all strings, all Car objects, and so on). As we state in the book, "Templates enable the programmer to separate the functionality of an implementation from the type of data used in the class." We feel that introducing and using templates as we do is not difficult. 

Code that creates the same kinds of data structures as just described and that does not use templates is inflexible, since it is hardwired for one particular data type. Changing the type of data to be stored would be an error-prone process and take a substantial amount of work. Such code would not look like the code that a student is likely to see in the standard libraries or in the real world.