Create an implementation of the Ordered Associative Array API using left-leaning red-black trees. Illustrate the use of the API by refactoring your WordBench as a client of Ordered Associative Array API.

Needs:
oaa.h # the ordered associative array class template
wordbench2.h # defines wordbench refactored to use the OAA API
wordbench2.cpp # implements wordbench2.h

Given:
main2.cpp # driver program for wordbench2
focpp # functionality test for OAA
rantable.cpp # random table file generator

Define and implement the class template OAA, placing the code in the file oaa.h.

Thoroughly test your OAA<> with the distributed test client programs foaa.cpp and moaa.cpp. Be sure to log all test activity.

Define the application WordBench, refactored as a client of OAA, in the header file wordbench2.h, and implement the refactored WordBench in the file wordbench2.cpp

Requirements - Ordered Associative Array
The following definition should be used:

template < typename K , typename D , class P = LessThan >
class OAA
{
public:

typedef K KeyType;
typedef D DataType;
typedef P PredicateType;

OAA ();
explicit OAA (P p);
~OAA ();

DataType& operator [] (const KeyType& k) { return Get(k); }

void Put (const KeyType& k , const DataType& d);
D& Get (const KeyType& k);
void Clear ();

bool Empty () const;
size_t Size () const;
int Height () const;

template
void Traverse (F f) const { RTraverse(root_,f); }

void Display (std::ostream& os, int cw1, int cw2) const;

void Dump (std::ostream& os) const;
void Dump (std::ostream& os, int cw) const;
void Dump (std::ostream& os, int cw, char fill) const;

enum Flags { ZERO = 0x00 , DEAD = 0x01, RED = 0x02 , DEFAULT = RED };
static const char* ColorMap (unsigned char flags)
{
switch(flags)
{
case 0x00: case 0x01: return ANSI_COLOR_BOLD_BLUE; // bits 00, 01
case 0x02: case 0x03: return ANSI_COLOR_BOLD_RED; // bits 10, 11
default: return "unknown color"; // unknown flags
}
}

private: // definitions and relationships

class Node // vertex in the tree structure
{
const KeyType key_;
DataType data_;
Node * lchild_,
* rchild_;
unsigned char flags_;
Node (const KeyType& k, const DataType& d, Flags flags = DEFAULT)
: key_(k), data_(d), lchild_(0), rchild_(0), flags_(flags)
{}
friend class OAA;
bool IsRed () const { return 0 != (RED & flags_); }
bool IsBlack () const { return !IsRed(); }
void SetRed () { flags_ |= RED; }
void SetBlack () { flags_ &= ~RED; }
}; // internal class Node

class PrintNode // function class facilitates Display()
{
public:
PrintNode (std::ostream& os, int cw1, int cw2) : os_(os), cw1_(cw1), cw2_(cw2)
{}
void operator() (const Node * n) const
{
os_ << std::setw(cw1_) << n->key_ << std::setw(cw2_) << n->data_ << ''\n'';
}
private:
std::ostream& os_;
int cw1_, cw2_;
}; // internal function class PrintNode

private: // data
Node * root_;
PredicateType pred_;

private: // methods
static Node * NewNode(const K& k, const D& d, Flags flags = DEFAULT);
static void RRelease(Node* n); // deletes all descendants of n
static size_t RSize(Node * n);
static int RHeight(Node * n);

template < class F >
static void RTraverse (Node * n, F f);

// recursive left-leaning get
Node * RGet(Node* nptr, const K& kval, Node*& location);

// rotations
static Node * RotateLeft(Node * n);
static Node * RotateRight(Node * n);

private: // copy facilitation - do not implement
OAA (const OAA& a); // copy constructor
OAA& operator= (const OAA& a); // assignment operator
}; // class OAA

It is worth pointing out what is NOT in these requirements that would be in a "full" OAA API:

Object comparison operators == and !=
Copy constructor and assignment operator
Iterators and iterator support
Remove or Erase
The remaining portion of the OAA API consist of Get, Put, Clear, constructors and destructor -- arguably the minimal necessary for a useful container.

Note that the AA bracket operator is in the interface and is implemented in-line above with a single call to Get. Also note that Put can be implemented with a single call to Get, which leaves Get as the principal functionality requiring implementation.

The various const methods measure useful characteristics of the underlying BST and provide output useful in the development process as well as offering client programs insight into the AA structure.

The various "private" statements are redundant, but they emphasize the various reasons for using that designation: (1) to have private in-class definitions, such as Node or typedef statements, and to record any friend relationships that might be needed; (2) private data in the form of variables; (3) private methods; and (4) things that are privatized to prevent their use.

Requirements - WordBench
Here is a working header file for the refactored WordBench:

/*
wordbench2.h
*/

#include
#include
#include

class WordBench
{
public:
WordBench ();
virtual ~WordBench ();
bool ReadText (const fsu::String& infile);
bool WriteReport (const fsu::String& outfile, unsigned short c1 = 15, unsigned short c2 = 15) const;
void ShowSummary () const;
void Erase ();

private:
typedef fsu::String KeyType;
typedef size_t DataType;

size_t count_;
fsu::OAA < KeyType , DataType > frequency_;
fsu::List < fsu::String > infiles_;
static void Cleanup (fsu::String& s);
} ;

The set "wordset_" from the original design is replaced with the ordered associative array "frequency_".

Note the private terminology is changed slightly. (Of course, the API is not changed.) The main storage OAA is called frequency_ which makes very readable code of this form:

...
Cleanup(str);
if (str.Length() != 0)
{
++frequency_[str];
++numwords;
} // end if
...

This snippet is the inner core of the processing loop implementing ReadText. The main loop implementing ReadText is now only 5 lines of code.

Another small change is that it is no longer possible to loop through the data to count the words, because we are not defining an Iterator class. We could work out a way to make this count using a traversal with a special function object that retrieves the specific frequencies, but it is simpler just to have a class variable count_ that maintains the total number of words read (and is reset to 0 by Clear()).

Posted Date: 3/23/2012 1:21:23 PM | Location : United States

Ask an Expert

Related Discussions:- Data structures hw help, computer science, Assignment Help, Ask Question on Data structures hw help, computer science, Get Answer, Expert's Help, Data structures hw help, computer science Discussions

Write discussion on Data structures hw help, computer science
Your posts are moderated

Write your message here..

Related Questions

Random reading and writing and Closing a fcb file, The 21H function and the... The 21H function and the 22H function of the 21H interruption are the ones in charge of realizing the random readings and writings in that order. The random register number and the

Read only memory (rom), Read only memory (rom): The problem with RAM is... Read only memory (rom): The problem with RAM is that its memory is volatile, i.e. it loses all its data when the power supply is removed.  A non-volatile memory is a permanent

Enterprise resource planning, ENTERPRISE RESOURCE PLANNING What ... ENTERPRISE RESOURCE PLANNING What has football got to do with it? asks management guru Michael Hammer in his latest best seller Beyond Reengineering. The answer is almos

Dataflow modeling for dsp design, Dataflow Modeling for DSP Design The ... Dataflow Modeling for DSP Design The necessary components in the research of application-specific computer architectures are: 1) a clearly identified set of problems that can b

What is evaluating information system investments, 1. What is Evaluating In... 1. What is Evaluating Information System Investments? 2. Is IS evaluation different to evaluation of other investments? 3. What approaches are used to evaluate IS investments

Networking.., write advantages and disadvantages of private and public netw... write advantages and disadvantages of private and public network

List and explain different types of media, Question 1 List and explain the... Question 1 List and explain the ways used to close an MS Word document Question 2 What is MS-Excel? List the steps involved in starting Microsoft Excel Question 3 What i

Explain the tcp/ip reference model with diagram, Question 1 Define the fol... Question 1 Define the following terms                                   1) Analog Signals and Digital Signals 2) Composite signals Question 2 Define the following terms

Explain the important concepts of modern cpu, Question 1 Explain the impor... Question 1 Explain the important concepts of modern CPU CISC vs. RISC CPUs Circuit Size and Die Size Processor Speed Processor Cooling System Clocks Architect

Mode of nutrition, what type of nutrition,leech is? what type of nutrition,leech is?