CS-217 Data Structures and Algorithms I

Student

R. Scott Linford

Introduction

This package contains an object oriented framework of data structures. In its last delivery it looked like:

original_class_hierarchy.png

Beginning Class Hierarchy

LinkedList was the only working structure. It had a base class called OrderedList. Several other classes were stubbed in and formed the beginning of a class hierarchy with Container as the one common super-class.

The hierarchy has grown. Most of the classes in the package extend Object.

final_class_hierarchy.png

Final Class Hierarchy

The Object super-class was originally created to generate output in a polymorphic manner. I'm used to Java in which all classes ultimately derive from a common super-class.

All of the data structures are unbounded, including the array implementations which expand as needed. All structures use dynamic allocation.

Two doubly-linked lists are implemented, one that maintains a sorted order and one that doesn't. The SortedLinkedList does not except duplicates and the OrderedLinekList does. The common functionality to both linked lists resides in the abstract class LinkedList. As the diagram shows, multiple inheritance is in use.

Two array based lists are implemented, following the same pattern as the linked lists. Most of the common functionality between the two concrete classes resides in ArrayList. The SortedArrayList makes use of binary searching for retrieval and for insertion.

The Queue and Stack implementation can be composed with either a OrderedArrayList or and OrderedLinkedList, using the factory methods provided. QueueImpl contains functionality that demonstrates the difference between deep and shallow copying.

Unit tests have been refactored to take advantage of the polymorphic nature of the framework. As shown in the above diagram, for example, all list classes have a common parent called List (oddly enough). There is a unit test called container_test::List_test that enforces the List contract for all known sub-classes.

list_unit_test_hierarchy.png

Final Class Hierarchy

The unit tests became invaluable during the extensive refactoring. They caught a lot of bugs, and allowed me to make implementation chages with confidence. All I needed to see were the green lines at the bottom of the output I knew that the method contracts were still satisfied.

Project Considerations

Dusting Off the Old Skills

First of all, I haven't done any serious C++ work for 15 years. So this is a good excuse for me to relearn the language and research the new features and coding standards which have evolved during my absence. C++ templates give me a headache but I'll find some way to use them.

A Rough OO Outline

Second, I want to end up with an OO hierarchy of classes. From experience, I know how hard OO design is to do right. First guesses are always wrong. It usually requires an iterative process to discover abstractions and pull them up into a super class. I haven't started from scratch, however, having taken inspiration from the Java collections framework and other sources.

More Rope

Third, Java is an insidious language in its simplicity. All primitive types are passed by value and all user-created types are passed by reference. In Java there's no such thing as a struct residing on the call stack. Instead, the stack only has references to dynamically allocated objects on the heap. Now I'm back to C++ which has too many choices, all this flexibility, i.e., (rope to hang myself with).

So, coming from a Java frame of mind, Container classes will not make copies of the Entity objects stored within them. Only copies of pointer values will be made when an Entity is added. The Container classes will take responsibility of deleting any Entity objects they have a reference to at the time of Container destruction.

Functionality Demonstration

Output for demonstration is weaved into the unit tests.

unit_test_output.png

Sample Output

The unit test output starts with green text (or red for a failure). All the other lines were added to demonstrate that something is actually happening. The test cases are too verbose to easily capture in a screen shot. Here is the full text of the current output:

LinkedList and Entity - Unit Test Output

The unit tests verify and assert more than is being reported in the print statements. For example, two methods from LinkedList_test generated the above output:

linkedlist_example_test_code.png

Normally, unit tests aren't designed for human eyes. They either pass or fail, much like code compilation which either succeeds or fails.

Well written unit tests do not require print statements. When they fail, the output is designed to be sufficient to trace the problem to its source. The googletest framework is good in this respect. Upon failure, it prints line numbers, expected values, actual values, etc, that make print statements superfluous in a real development environment.

Development Environment

I Want My IDE Back

Coming from a Java background, I've attempted to replicate the features found in IDE's like Eclipse and NetBeans. Long ago I had done C and C++ from the command line using tools like vi, make, etc. But now I'm spoiled. I've grown accustomed to code completion, incremental compilation, dependable refactoring tools, and other productivity aids.

For example, with NetBeans you can create a Hello World program with a few clicks and then run it by pressing the big green arrow. This is true for a simple console application, a GUI desktop application, a web application, etc. For a web application, it fires up the web server for you a and pops open a browser running the new code, all with the friendly green arrow. Just press play.

Unit tests are just as easy, right out of the box. Select the class to be tested and NetBeans generates a JUnit class with a stub for each method. All you have to do is fill in the stubs. Unit tests can be run with a click of the mouse and become a natural part of the build process.

Source Control

Another requirement I set for my environment was to continue using Subversion as my code repository. NetBeans integrates with Subversion. The files shown in blue (container.h and Doxyfile) have been locally modified:

project_trees.png

I started using Subversion for CS-114. Access to source code is served up via HTTP from my laptop computer. I have a development environment at home and at work, which serves as protection against loss and forces me to check in code frequently. In doing so, I have a full history of my project since its inception, with useful check-in comments about what was changed any why.

sample_history_for_linkedlist_h.png

The NetBeans integration allows for each line to be traced back to the responsible developer and the revision where the line was last changed. This is not a special read-only view. The following shot is of "live" editable code:

annotated_code_userid_and_version.png

Annotated Code With UserID and Version Number

I experimented with Microsoft's Visual Studio. It has decent code refactoring but there is no built in support for Subversion. Agent SVN looks like a nice plug-in, but $95.95 was not in the budget.

NetBeans and C++?

So after additional research I decided to stick with NetBeans which has a C++ plug-in (crazy). NetBeans becomes a shell for the standard GNU set of tools (gcc, g++, gdb, make, etc.) which have been ported to Cygwin (a Unix-like environment for Windows).

It took me a long time to get NetBeans to compile and run a simple program, partly because it has been so long since I have had to worry about include files, linking, and other concerns that either don't exist in Java or are taken care of by the toolset. Yes, I know, I've grown soft. The first linking error really took me back to the old days, "Oh yeah, these. My favorite."

Unit Test Framework

Then I went in search of a C++ unit-test framework and found that there isn't a de facto standard like JUnit is for the Java world. I settled on googletest because it has the ability to auto-discover unit tests. I downloaded the googletest source code and built it under Cygwin. With scanty documentation it took some time to figure out how to set it up.

I ended up with two NetBeans projects. "Structures" for the actual code and "Structures_test" for the unit tests. The source code in "Structures" has no dependency on the unit tests. It compiles down to a library called "libstructures.a" (no executable).

Project "Structures_test" has a build dependency on "Structures". So with a click of a button all files are compiled, linked, and unit tests are executed. The magic is performed by Google's "gtest_main.a" which has a main function that does the work of finding and executing all unit tests.

Automatic API Documentation

Then I had to have automatic documentation. I'm spoiled, remember? In NetBeans (yes, you guessed it) you click a menu and the Javadoc shows up in a browser. For this project I'm learning Doxygen. To automate the process I added a new target to the Makefile that NetBeans generated. My make utility skills were very rusty.

Sources and Other Inspiration

I started the class without the textbook. It took longer than expected to arrive. I turned to other sources, including Java's collection framework which I have used for years.

I also came across an online text book, "Data Structures and Algorithms with Object-Oriented Design Patterns in C++", by Bruno R. Preiss. It has snippets of code but the source is not available.

Generated on Tue Jun 16 23:12:44 2009 by  doxygen 1.5.9