RBLL Trees and ADT-Based Iterators

ADT-based Iterators for BSTs.

Educational Objectives: After completing this assignment, the student should be able to accomplish the following:

• Describe and explain in detail the concept forward and bidirectional iterators on Set and Map container classes.
• Implement Stack-based bidirectional "in-order", "pre-order", and "post-order" iterators for binary trees
• Implement Queue-based forward "level-order" iterators for binary trees
• Explain the utility of iterators on Sets and Maps
• Give examples of of Set and Map applications that are simple with iterators but difficult without iterators.
• Explain what the runtime and other efficiency considerations are between RBLL Trees and BSTs.
• Explain what the runtime and other efficiency considerations are between ADT-based iterators and threaded iterators.

Operational Objectives: Implement class templates InorderBTIterator and LevelorderBTIterator and use these classes to complete the implementations of the class templates BST_ADT and RBLLT_ADT.

Deliverables: Four files:

bt2iter_adt.h   # contains the iterator class templates
bst_adt.h       # class BST_ADT
rbllt_adt.h     # class RBLLT_ADT
log.txt         # your project work log

Discussion

To create the various classes from "scratch" (or "whole cloth") is a large and somewhat open-ended project that is not at all beyond the capabilities of students at your level. But it would be much too much work. Therefore you have the task of completing an implementation that has been worked out and for which many of the technical details have been supplied. This leaves you with a different, but more manageable, two-part mission:

1. Understand the overall design as well as the implementation in complete detail.
2. Supply missing implementations of some key methods.

Regarding I. There are several classes involved that are inter-related, as follows:

1. The iterator classes - these are all started in the file bt2iter_adt.start and you are required to complete them in the deliverable file bt2iter_adt.h:

   template < class C > InorderBTIterator;
   template < class C > PreorderBTIterator;
   template < class C > PostorderBTIterator;
   template < class C > LevelorderBTIterator;
   

   These take a parameter C that is treated as a binary tree class built from nodes with certain properties. Any class C that has an interface and structure assumed by the iterator classes will work with them.

   The iterator class InorderBTIterator is a fully functional bidirectional iterator type (see notes on Iterators). The class LevelorderIterator is a fully functional forward iterator type.

2. The container classes, in various files:

   template < typename T , class P > BST_BASE;     // in file bst_base.h
   template < typename T , class P > BST_ADT;      // started in file bst_adt.start, delivered in file bst_adt.h
   template < typename T , class P > RBLLT_ADT;    // started in file rbllt_adt.start, delivered in file rbllt_adt.h
   

   These classes are all variations on BST. The separation of many of the functionalities into the base class BST_BASE serves mainly (and not insignificantly!) as a code re-use mechanism. BST_BASE does not define its own Iterator type. The two derived class offer variations on choice of Iterator. Note that BST_ADT is derived from BST_BASE amd RBLLT_ADT is derived from BST_ADT. Opportunities for code re-use are thus maximized.

3. Because rbllt_adt.start has a complete implementation of RBLLT_ADT, except for a few typedef enhancements, we will postpone releasing that file until the deadline for project 4 is passed. All preliminary testing can be done with BST_ADT, and it should not require much time to encompass RBLLT_ADT in final testing at that time.

Procedural Requirements

1. The official development/testing/assessment environment is specified in the Course Organizer.

2. Create and work within a separate subdirectory cop4530/proj5.

3. Begin by copying all files in the directory LIB/proj5 into your proj5 directory. At this point you should see these files in your directory:

   bt2iter_adt.start    # BT iterator classes [w partial implementations]
   bst_adt.start        # class BST_ADT, derived from BST_BASE  [partial implementation]
   rbllt_adt.start      # class RBLLT_ADT, derived from BST_ADT [partial implementation]
   fbst.cpp             # test harness for all the BST classes
   ranstring.cpp        # random string generator
   ranuint.cpp          # random uint generator
   makefile.adt         # builds test exectuables and utilities
   deliverables.adt     # submission configuration file
   

   Then copy these relevant executables from LIB/area51/:

   fbst*.x
   frbllt*.x
   mbst*.x
   mrbllt*.x
   

4. Create the files bt2iter_adt.h, bst_adt.h, rbllt_adt.h containing the template classes.

5. Test thoroughly.

6. Submit the assignment using the command submit.sh.
   
   Warning: Submit scripts do not work on the program and linprog servers. Use shell.cs.fsu.edu to submit assignments. If you do not receive the second confirmation with the contents of your assignment, there has been a malfunction.

Code Requirements and Specifications

1. Begin by copying the start files to the code files:

   cp bt2iter_adt.start  bt2iter_adt.h
   cp bst_adt.start      bst_adt.h
   cp rbllt_adt.start    rbllt_adt.h
   

   Then modify these copies into the deliverable code files.

2. Don't change the code already supplied in the start files.

3. Complete the implementations where there is missing code.

4. Do not copy/paste code, even from supplied sources such as lecture notes. All code used in completing implementations should be typed by your own hands.

Hints

• Note that fbst.cpp has 4 possible ElementType definitions and 4 possible BST definitions that can be selected by the comment/uncomment technique. You need to use that technique to proliferate fbst.cpp to these tests:

  fbst_adt_CHAR.cpp       # BST = BST_ADT,   ElementType = CHAR
  fbst_adt_int.cpp        # BST = BST_ADT,   ElementType = int
  fbst_adt_String.cpp     # BST = BST_ADT,   ElementType = fsu::String
  frbllt_adt_CHAR.cpp     # BST = RBLLT_ADT, ElementType = CHAR
  frbllt_adt_int.cpp      # BST = RBLLT_ADT, ElementType = int
  frbllt_adt_String.cpp   # BST = RBLLT_ADT, ElementType = fsu::String
  

  Similarly, mbst.cpp proliferates to

  mbst_adt_int.cpp        # BST = BST_ADT,   ElementType = int
  mbst_adt_String.cpp     # BST = BST_ADT,   ElementType = fsu::String
  mrbllt_adt_int.cpp      # BST = RBLLT_ADT, ElementType = int
  mrbllt_adt_String.cpp   # BST = RBLLT_ADT, ElementType = fsu::String
  

  You need to create these tests, each of which is required by the makefile

Attachment:- proj.zip