CSE 100: Data Structures (Autumn 1996)

		Programming Assignment #2
		A Binary Tree Sorting Engine
		Due: Monday, October 28, 1996 11:00 pm

	

In this programming assignment you will implement a binary search tree,
and use it as the basis for a sorting engine.  Your sorting engine will
accept keys of any type, subject to conditions defined below, which
implies that you will implement your binary search tree as a templated
class.  Your search engine must be able to sort keys both in increasing
and decreasing order.

The implementation of your search tree should be efficient, and avoid
the use of recursion. Therefore, you should use THREADS to implement
your tree, as discussed in class (see p. 61 of the notes).  Because of
the added requirement that the traversal engine be capable of performing
a reverse sort, you will need both right and left threads.  Since we
discussed only right-threaded trees in class, you will need to modify
the code described in class and in the text to handle the more general
case of left and right threads.  To present an interface for reverse
sorting, include a member function reverseOrder(), as well as inOrder(),
in your btThrd class.

Test your sort engine on two user defined key types---String and
OrderedPair (of integers), whose definitions are attached---as well as
integers.  These classes are defined below.  Be sure to implement the
comparison operators '<' and '>' for less-than and greater-than,
respectively, and overloaded stream operators '<<' and '>>'.

**********************************************************************

	Class String

Class String implements variable length character strings and was
discussed in lecture (see pp. 12-13 of the class notes.)  Comparison
operators '<' and '>' may be defined in terms of the <string.h>
library function strcmpn(), or you may define your own from scratch.


----------------------------------------------------------------------
// FILE: String.h

#ifndef String_h
#define String_h
#include <iostream.h>
#include <stdlib.h>
#include <strings.h>
class String
{
    unsigned int Buffer_Len;
 	  char *Buffer;
    
public:
//constructors: note that  we can overload the constructors
    String (const char * val = NULL) ;    // const strings " .. "
    String (char * val = NULL) ;          // Dynamically allocated strings    
    String (const String & val) ;         // Copy constructor
 
// Assignment Operator: an instance of operator overloading
     const String & operator = ( const String & val ) ;

// Type cast String to char *
     operator const char * const ( ) const { return Buffer ;}

// Friends

   friend int operator < (const String & Lhs , const String & Rhs);
   friend int operator > (const String & Lhs , const String & Rhs);
   friend ostream& operator << (ostream& st , String& S);
 
 };
// Friends
 ostream& operator << (ostream& st , String& S)
          { st << S.Buffer; return (st);}
#endif
----------------------------------------------------------------------

**********************************************************************

Class OrderedPair

Class OrderedPair implements ordered pairs of integers, and implements
comparison operators '<' and '>' using the definition of
lexicographical ordering defined on page 16 of the class notes (Unit 2).

----------------------------------------------------------------------
// FILE: OrderedPair.h

#ifndef OPAIR_H
#define OPAIR_H
#include <stream.h>
class OrderedPair
{
    int x;
    int y;

public:
    OrderedPair(int i, int j) : x(i), y(j) {}
    OrderedPair(OrderedPair &t) : x(t.x), y(t.y)  { }
    int operator < (OrderedPair& t) const
		    { return ( x < t.x || (( x == t.x) && ( y < t.y )) ); }
    int operator > (OrderedPair& t) const
		     { return ( x > t.x || (( x == t.x ) && (y > t.y ))); }
    OrderedPair& operator = (OrderedPair& t) { x = t.x; y=t.y; return *this;}

    friend ostream& operator << (ostream& st , OrderedPair& O);
};

// Friends
 ostream& operator << (ostream& st , OrderedPair& O)
          { st << '(' << O.x << ',' << O.y << ')' ; return (st);}
#endif

----------------------------------------------------------------------


**********************************************************************
	Turnin Procedure:

PLEASE verify that everything compiles properly before you turnin.

In your turnin package, the only types of files we want are *.C,
*.h, makefile, and any documentation files.  Please do not turnin
executables, *.o files, or anything ending in ~ or % (i.e. editor
files) and ESPECIALLY don't hand in any core files.  Remember to 
include user and logic manuals for the programs (as separate files)
and any README files if appropriate.  

An example main program with some suggested ways to test your
program is also provided in the file public/HW2/example_main.C,
along with the .h files listed above.