Algorithms Project

by @im_a_muppet on April 22, 2007

For this assignment we have to write a dictionary file using two different data types. The first dictionary will implement a Link List and the second Red Black Trees. We will then compare the performance of each.

The program will get two files and populate the dictionary form one file and see which words in the second file are then in the dictionary.

Dictionary Project assignment description

Solution:

nodes.h

/*
 *  File:    nodes.h
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef NODES
#define NODES
#include <iostream>
using namespace std;

struct node{
    string word;
    node *link;
};

/*
 * TreeNode
 *
 * This is a class representing a node in a Binary Search Tree
 *
 */
class TreeNode {

protected:
//public:
    TreeNode *left;    // Pointer to left subtree.
    TreeNode *right;
    TreeNode *parent;  
public:
    string word;       // The data in this node.
    TreeNode * getParent();
    TreeNode * getRight();
    TreeNode * getLeft();
    void setParent(TreeNode *);
    void setLeft(TreeNode *);
    void setRight(TreeNode *);

}; 

/*
 * RBTreeNode
 *
 * This is a class representing a node in a Red Black Tree
 *
 */
class RBTreeNode : public TreeNode
{
private:
public:
    int color;
    RBTreeNode * getParent();
    RBTreeNode * getRight();
    RBTreeNode * getLeft();
    void setParent(RBTreeNode *);
    void setLeft(RBTreeNode *);
    void setRight(RBTreeNode *);
}; 

#endif

nodes.cpp

/*
 *  File:    nodes.cpp
 *  Prj:    dictionary
 *
 *  Created by Will Mernagh on April/26.
 *  Copyright 2007. All rights reserved.
 *
 */

#include "nodes.h"

TreeNode * TreeNode::getParent(){
    return parent;
}

TreeNode * TreeNode::getRight(){
    return right;
}

TreeNode * TreeNode::getLeft(){
    return left;
}

void TreeNode::setParent(TreeNode *nodein){
    parent = nodein;
}

void TreeNode::setLeft(TreeNode *nodein){
    left = nodein;
}
void TreeNode::setRight(TreeNode *nodein){
    right = nodein;
}

RBTreeNode * RBTreeNode::getParent(){
    return static_cast<RBTreeNode *>(parent);
}

RBTreeNode * RBTreeNode::getRight(){
    return static_cast<RBTreeNode *>(right);
}

RBTreeNode *RBTreeNode::getLeft(){
    return static_cast<RBTreeNode *>(left);
}

void RBTreeNode::setParent(RBTreeNode *nodein){
    parent = nodein;
}

void RBTreeNode::setLeft(RBTreeNode *nodein){
    left = nodein;
}
void RBTreeNode::setRight(RBTreeNode *nodein){
    right = nodein;
}

linklist.h

/*
 *  File:    linklist.h
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef LINKLIST
#define LINKLIST
#include <iostream>
#include "nodes.h"
using namespace std;

/*
 * linklist
 *
 * Class defination of linklist.
 *
 * This class represents a linklist data structure 
 * where the data is to be  stored in a node
 *
 * @see nodes.h
 *
 */
class linklist
{
private:

    node *p, *ptail;

public:

    linklist();

    void display();
    int count();
    void append(string);
    void add_as_first(string);
    void addafter(int, string);
    bool del(string);
    node * head();
    node * tail();
    ~linklist();
};
#endif

linklist.cpp

/*
 *  File:    linklist.cpp
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#include <iostream>
#include "linklist.h"
#include "nodes.h"
using namespace std;


/*
 * linklist() constructor
 *
 */
linklist::linklist()
{
    p=NULL;
}

/*
 * head()
 * 
 * @return    the head of the link list
 *
 */
node * linklist::head()
{
    if(p != NULL){
        return p;
    }else{
        return NULL;
    }
}

/*
 * tail()
 *
 * @return    the tail of the linklist
 *
 */
node * linklist::tail()
{
    if(p != NULL){
        return ptail;
    }else{
        return NULL;
    }
}

/*
 * append()
 *
 * @param    string - the data to encapsulate in a node.
 *
 * The function creates a node and encapsulates the 
 * string in it. It then appends the node to the tail 
 * of the linklist.
 */
void linklist::append(string word)
{
    node *q,*t;

    if( p == NULL )
    {
        p = new node;
        p->word = word;
        p->link = NULL;
        ptail = p;
    }
    else
    {
        q = p;

        //find end of list
        while( q->link != NULL )
            q = q->link;

        t = new node;
        t->word = word;
        t->link = NULL;
        q->link = t;
        ptail = t;
    }
}

/*
 * add_as_first()
 *
 * @param    string - the data to encapsulate in a node.
 *
 * The function creates a node and encapsulates the string 
 * in it. It then adds the node to the head of the 
 * linklist.
 *
 * This is faster than append() since there is not search 
 * for tail
 */
void linklist::add_as_first(string word)
{
    node *q;

    q = new node;
    q->word = word;
    q->link = p;
    p = q;
}

/*
 * addafter()
 *
 * @param    string    - the data to encapsulate in a node.
 * @param    int        - the position to place node -1
 *
 * The function creates a node and encapsulates the string 
 * in it. It then adds the node after the c-th node of the
 * linklist.
 */
void linklist::addafter( int c, string word)
{
    node *q,*t;
    int i;
    for(i=0,q=p;i<c;i++)
    {
        q = q->link;
        if( q == NULL )
        {
           std::cout << "\nThere are less than "<< c <<" elements.";
           return;
        }

    }

    t = new node;
    t->word = word;
    t->link = q->link;
    q->link = t;
    if(t->link == NULL)
    {
        ptail = t;
    }
}

/*
 * del()
 *
 * @param    string    - the data encapsulated in the node to be deleted.
 *
 * @return    bool    - true if the encapsulated node existed in list.
 *
 * The function finds the node that encapsulates the string and removes 
 * it from the linked list
 */
bool linklist::del(string word)
{
    node *q,*r;
    q = p;
    if( q->word == word )
    {
        p = q->link;
        delete q;
        return true;
    }

    r = q;
    while( q!=NULL )
    {
        if( q->word == word )
        {
            r->link = q->link;
            delete q;
            if(r->link == NULL){
                ptail = r;
            }
            return true;
        }

        r = q;
        q = q->link;
    }
    return false;
}

/*
 * display()
 *
 * Display the data encapsulated in the nodes of the linklist
 *
 */
void linklist::display()
{
    node *q;

    for( q = p ; q != NULL ; q = q->link ){
        std::cout<<"\nword: "<< q->word;
    }


}

/*
 * count()
 *
 * Counts the number of nodes in the list.
 *
 */
int linklist::count()
{
    node *q;
    int c=0;
    for( q=p ; q != NULL ; q = q->link )
        c++;

    return c;
}

/*
 * ~linklist()    destructor
 *
 */
linklist::~linklist()
{
    node *q;
    if( p == NULL )
        return;

    while( p != NULL )
    {
        q = p->link;
        delete p;
        p = q;
    }
}

BinarySearchTree.h

/*
 *  File:    BinarySearchTree.h
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef BSTREE
#define BSTREE
#include "nodes.h"
using namespace std;

/*
 * BST
 *
 * Class defination of a Binary Search Tree.
 *
 * This class represents a Binary Search Tree data structure where 
 * the data is to be stored in a node.
 *
 * @see    nodes.h
 *
 */
class BST
{
protected:
    TreeNode *root;
    void  recurseDisplay(TreeNode *);
    TreeNode * findNode(string);
    bool insert(TreeNode *);

public:
        BST();
        bool insert(string); 
        void display(); 
        bool del(string);
        TreeNode * successor(string); 
        bool find(string);
        TreeNode * getRoot();
        void setRoot(TreeNode *);
        ~BST();
};
#endif

BinsrySearchTree.cpp

RedBlackTree.h

/*
 *  File:    RedBlackTree.h
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef RBTREE
#define RBTREE
#include <iostream>
#include "nodes.h"
#include "BinarySearchTree.h"
using namespace std;

/*
 * RedBlackTree
 *
 * Class defination of RedBlackTree.
 *
 * This class represents a Red Black Tree data structure 
 * where the data is to be stored in a node. It is 
 * extended from BinarySearchTree.h
 *
 * @see BinarySearchTree.h, nodes.h
 *
 */
class RedBlackTree : protected BST
{
private:
    //RBTreeNode *root;
    bool rotateLeft(RBTreeNode *);
    bool rotateRight(RBTreeNode *);
    bool insertFix(RBTreeNode *);
    bool delFix(RBTreeNode *);
    void recurseDisplay(RBTreeNode *);
    RBTreeNode * findNode(string);

public:
    RedBlackTree();
    bool insert(string); 
    void display(); 
    bool del(string); 
    RBTreeNode * successor(string); 
    RBTreeNode * getRoot();
    void setRoot(RBTreeNode *);
    ~RedBlackTree();
};
#endif

RedBlackTree.cpp

/*
 *  RedBlackTree.cpp
 *  dictionary
 *
 *  Created by Will Mernagh on April/21.
 *  Copyright 2007. All rights reserved.
 *
 */
#include <iostream>
#include "RedBlackTree.h"

using namespace std;

#define RED 1
#define BLACK 2


/*
 * Constructor
 */
RedBlackTree::RedBlackTree(){
    setRoot(NULL);
}

/*
 * Destructor
 */
RedBlackTree::~RedBlackTree(){


    while(getRoot() != NULL){
        del(getRoot()->word);
    }
}

/*
 * get the root
 */
RBTreeNode * RedBlackTree::getRoot(){
    return static_cast<RBTreeNode *>(BST::getRoot());
}

/*
 * set the root
 */
void RedBlackTree::setRoot(RBTreeNode *rootin){
    BST::setRoot(rootin);
}

/* 
 * Inserts the string into the tree. 
 *
 * @param    String        The string to add to the tree
 * @return    False        if already in the tree
 */
bool RedBlackTree::insert(string word){

    RBTreeNode *rbnode = new RBTreeNode;

    rbnode->color = RED;
    rbnode->word = word;
    rbnode->setLeft(NULL);
    rbnode->setRight(NULL);

    if(BST::insert(rbnode)){
        insertFix(rbnode);
        return true;
    }else{
        delete rbnode;
        return false;
    }

}


/* 
 * Display the items in a tree in order and with color
 *
 * @param    RBTreeNode    The next node to recurse on
 */
void RedBlackTree::recurseDisplay(RBTreeNode *node){

    if(node != NULL){
        recurseDisplay(node->getLeft());
        cout<<node->word<<"";
        cout<<" [";
        if(node->color == RED){cout<<"RED";}
        if(node->color == BLACK){cout<<"BLACK";}
        cout<<"] ";

        if(node->getParent() != NULL){
            cout << "(" << node->getParent()->word<<")\n";
        }else{
            cout<<"\n";
        }

        recurseDisplay(node->getRight());

    }
    return;
}

/* 
 * Display the items in a tree in order
 *
 */
void RedBlackTree::display(){

    recurseDisplay(getRoot());

    return;
}

/* Delete a word from the tree
 * 
 * @param    string    The string to delete
 * @return    bool    False if it does not exist in tree
 */
bool RedBlackTree::del(string word){

    RBTreeNode *x, *y, *z;

    z = findNode(word);

    if(z == NULL){
        return false;
    }

    if((z->getLeft() == NULL) || (z->getRight() == NULL)){
        y = z;
    }else{
        y = successor(z->word);
    }

    if((y != NULL) && (y->getLeft() != NULL)){
        x = y->getLeft();
    }else if(y != NULL){
        x = y->getRight();
    }

    if((y != NULL) && (y->color == BLACK)){

        delFix(x);
    }

    return BST::del(word);
}

/* 
 * Search for the successor of a string and return it if in tree
 *
 * @param    String        The string whose successor to search for
 * @return    RBTreeNode    if string in the tree else return null
 */
RBTreeNode * RedBlackTree::successor(string word){
    TreeNode *tnode;
    tnode = BST::successor(word);
    return static_cast<RBTreeNode *>(tnode);
}

bool RedBlackTree::rotateLeft(RBTreeNode *node_x){

    RBTreeNode *node_y;

    if(node_x->getRight() == NULL){
        return false;
    }

    node_y = node_x->getRight();

    if(node_y->getLeft() != NULL){
        node_y->getLeft()->setParent(node_x);
        node_x->setRight(node_y->getLeft());
    }

    node_y->setParent(node_x->getParent());

    if(node_x->getParent() == NULL){
        setRoot(node_y);
    }else if(node_x == node_x->getParent()->getLeft()){
        node_x->getParent()->setLeft(node_y);
    }else{
        node_x->getParent()->setRight(node_y);
    }
     
    node_x->setRight(node_y->getLeft());
    node_y->setLeft(node_x);
    node_x->setParent(node_y);

    return true;
}

/* 
 * Rotate the tree right on y
 *
 * @param    RBTreeNode    The node to rotate on
 * @return    False        if node to ret on deos not exist
 */
bool RedBlackTree::rotateRight(RBTreeNode *node_y){

    RBTreeNode *node_x;

    if(node_y->getLeft() == NULL){
        return false;
    }

    node_x = node_y->getLeft();

    if(node_x->getRight() != NULL){
        node_x->getRight()->setParent(node_y);
        node_y->setLeft(node_x->getRight());
    }

    node_x->setParent(node_y->getParent());

    if(node_y->getParent() == NULL){
        setRoot(node_x);
    }else if(node_y == node_y->getParent()->getLeft()){
        node_y->getParent()->setLeft(node_x);
    }else{
        node_y->getParent()->setRight(node_x);
    }
     
    node_y->setLeft(node_x->getRight());
    node_x->setRight(node_y);
    node_y->setParent(node_x);

    return true;
}

/* 
 * Maintains the red black tree properties after a node is deleted
 *
 * @param    RBTreeNode    The node that is in violation
 * @return    true        always
 */
bool RedBlackTree::delFix(RBTreeNode *nodein){

    RBTreeNode *x, *w;
    x = nodein;

    while( x != getRoot() && x != NULL && x->color == BLACK){

        if(x->getParent()->getLeft() == x){
    
            w = x->getParent()->getRight();


            if(w != NULL && w->color == RED){
                w->color = BLACK;
                x->getParent()->color = RED;
                rotateLeft(x->getParent());
                w = x->getParent()->getRight();
            }
    
            if((w != NULL && w->getLeft() != NULL) && 
                    (w->getLeft()->color == BLACK) && 
                    (w->getRight() && w->getRight()->color == BLACK)){
        
                w->color = RED;
                x = x->getParent();
        
            }else if(w != NULL && w->getRight()->color == BLACK){
        
                w->getLeft()->color = BLACK;
                w->color = RED;
                rotateRight(w);
                w = x->getParent()->getRight();
            }
    
            if((w != NULL) && (x->getParent() != NULL)){
                w->color = x->getParent()->color;
            }
    
            if(x->getParent() != NULL){
                x->getParent()->color = BLACK;
            }
    
            if(w != NULL && w->getRight() != NULL){
                w->getRight()->color = BLACK;
            }
    
            rotateLeft(x->getParent());
            x = getRoot();

        }else{
    
            w = x->getParent()->getLeft();

            if((w != NULL) && (w->color == RED)){
                w->color = BLACK;
                x->getParent()->color = RED;
                rotateRight(x->getParent());
                w = x->getParent()->getLeft();
            }
    
            if(w != NULL){
                if((w->getRight()->color == BLACK) && 
                   (w->getLeft()->color == BLACK)){
            
                    w->color = RED;
                    x = x->getParent();
            
                }else if(w->getLeft()->color == BLACK){
            
                    w->getRight()->color = BLACK;
                    w->color = RED;
                    rotateLeft(w);
                    w = x->getParent()->getLeft();
                }
            }
            if(w !=NULL){
                w->color = x->getParent()->color;
                w->getLeft()->color = BLACK;
            }
    
            if(x != NULL && x->getParent() != NULL){
                x->getParent()->color = BLACK;
                rotateRight(x->getParent());
            }
            x = getRoot();
    
        }
    }
    if(x != NULL){
        x->color = BLACK;
    }


    return true;

}

/* 
 * Maintains the red black tree properties after a node is inserted
 *
 * @param    RBTreeNode    The node that is in violation
 * @return    true        always
 */
bool RedBlackTree::insertFix(RBTreeNode *nodein){

    RBTreeNode *y, *z;
    z = nodein;

    while((z->getParent() !=NULL) && z->getParent()->color == RED){ 
        if((z->getParent() != NULL) && 
           (z->getParent() == z->getParent()->getParent()->getLeft())){
    
            y = z->getParent()->getParent()->getRight();
    
            if((y != NULL) && (y->color == RED)){
        
                z->getParent()->color = BLACK;
                y->color = BLACK;
                z->getParent()->getParent()->color = RED;
                z = z->getParent()->getParent();
        
            }else if(z == z->getParent()->getRight()){
        
                z = z->getParent();
                rotateLeft(z);
        
            }
    
            if(z->getParent() != NULL){
        
                z->getParent()->color = BLACK;
        
                if(z->getParent()->getParent() != NULL){
            
                    z->getParent()->getParent()->color = RED;
                    rotateRight(z->getParent()->getParent());
                }
            }
    
        }else if(z->getParent() == z->getParent()->getParent()->getRight()){
    
            y = z->getParent()->getParent()->getLeft();
    
            if((y != NULL) && (y->color == RED)){
        
                z->getParent()->color = BLACK;
                y->color = BLACK;
                z->getParent()->getParent()->color = RED;
                z = z->getParent()->getParent();
        
            }else if(z == z->getParent()->getLeft()){
        
                z = z->getParent();
                rotateRight(z);
        
            }
    
            if(z->getParent() != NULL){
        
                z->getParent()->color = BLACK;
        
                if(z->getParent()->getParent() != NULL){    
            
                    z->getParent()->getParent()->color = RED;
                    rotateLeft(z->getParent()->getParent());
        
                }
            }
    
        }

    }

    getRoot()->color = BLACK;
    return true;
}

/* 
 * Search for a node and return true if in tree
 *
 * @param    String        The string encapsulated in node to search for
 * @return    True        if string in the tree
 */
RBTreeNode * RedBlackTree::findNode(string word){
    return static_cast<RBTreeNode *>(BST::findNode(word));
}    

MyDictLL.h

/*
 *  File:    MyDictLL.h
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef MYDICTLL
#define MYDICTLL
#include <iostream>
#include "linklist.h"
using namespace std;

/*
 * MyDictLL
 *
 * Class defination of MyDictLL.
 *
 * This class represents a dictionary data structure where the data is  
 * to be stored in a node. It is extended from linklist.h
 *
 * @see linklist.h
 *
 */
class MyDictLL : protected linklist
{
public:
    bool find(string);
    bool insert(string); 
    bool del(string s);
    void display();
    string min();
    string max(); 
    string successor(string);
};
#endif

MyDictLL.cpp

  
#include "MyDictLL.h"
using namespace std;

bool MyDictLL::insert(string word)
{
    node *q;

    int position = 0;
    q = head();
    if(q == NULL){
        append(word);
        return true;
    }

    if(word < q->word){
        add_as_first(word);
        return true;
    }

    while(word > q->word){
        if(q->link == NULL){
            break;
        }
        q = q->link;
        position++;
    }

    if(word == q->word){
        return false;
    }

    addafter(position, word);

    return true;
}


bool MyDictLL::find(string word)
{
    node *q;
    q = head();

    while( q!=NULL )
    {
        if( q->word == word )
        {
            return true;
        }

        q = q->link;
    }
    return false;
}

string MyDictLL::successor(string word)
{
    node *q;
    q = head();

    while( q!=NULL )
    {
        if( q->word == word )
        {
            if(q->link != NULL){
                return q->link->word;
            }
            return NULL;
        }

        q = q->link;
    }
    return NULL;
}




string MyDictLL::min()
{
    if(head() != NULL){
        return head()->word;
    }else{
        return "";
    }
}

string MyDictLL::max()
{
    if(tail() != NULL){
        return tail()->word;
    }else{
        return "";
    }
}

bool MyDictLL::del(string word)
{
    return linklist::del(word);
}

void MyDictLL::display(){
    linklist::display();
}

MyDictRBT.h

/*
 *  File:    MyDictRBTRBT.h
 *  Prj:    dictionary
 *
 *  Created by Will Mernagh on April/27.
 *  Copyright 2007. All rights reserved.
 *
 */
#ifndef MYDICTRBT
#define MYDICTRBT
#include <iostream>
#include "RedBlackTree.h"
using namespace std;

/*
 * MyDictRBT
 *
 * Class defination of MyDictRBT.
 *
 * This class represents a dictionary data structure where the data 
 * is to be stored in a node. It is extended from RedBlackTree.h
 *
 * @see RedBlackTree.h
 *
 */
class MyDictRBT : protected RedBlackTree
{
public:
    bool find(string);
    bool insert(string); 
    bool del(string s);
    void display();
    string min();
    string max(); 
    string successor(string);
};
#endif
/*
 *  File:    MyDictRBTRBT.cpp
 *  Prj:    dictionary
 *
 *  Created by Will Mernagh on April/27.
 *  Copyright 2007. All rights reserved.
 *
 */

#include "MyDictRBT.h"
using namespace std;

bool MyDictRBT::insert(string word)
{
    return RedBlackTree::insert(word);
}


bool MyDictRBT::find(string word)
{
    return RedBlackTree::find(word);
}

string MyDictRBT::successor(string word)
{
    RBTreeNode * sucsr;
    sucsr = RedBlackTree::successor(word);
    if(sucsr == NULL){
        return "";
    }else{
        return sucsr->word;
    }
}

string MyDictRBT::min()
{
    RBTreeNode *search;

    search = getRoot();

    while(search->getLeft() != NULL){
        search = search->getLeft();
    }

    return search->word;

}

string MyDictRBT::max()
{

    RBTreeNode *search;

    search = getRoot();

    while(search->getRight() != NULL){
        search = search->getRight();
    }

    return search->word;

}

bool MyDictRBT::del(string word)
{
    return RedBlackTree::del(word);
}

void MyDictRBT::display(){
    RedBlackTree::display();
}

main.cpp

/*
 *  File:    main.cpp
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#include <iostream>
#include "MyDictLL.h"
#include "MyDictRBT.h"
#include <stdio.h>
#include <fstream>
#include <string>
using namespace std;
string lowerCase(string& s);
    /* 
 * main
 * 
 * This main function is used to test the data structures linklist and 
 * RedBlackTree
 *
 */
int main(int argc, char *argv[])
{

    MyDictRBT md; 
    //MyDictLL md;
    ifstream inFile1, inFile2;
    string word, cleanword;  // The user's input.
    int n = 0, size = 1000000;
    char *file1, *file2;
    char ok_chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
    int pun_first, pun_last;

        /* read command line */
    if(argc > 3){

        size = atoi(argv[3]);
        file1 = argv[1];
        file2 = argv[2];
 
    }else if(argc > 2){ 

        file1 = argv[1];
        file2 = argv[2];

    }else{

        cout<<"Usage argv[0] <file1> <file2> [optional: <size>]\n";
        exit(2);
    }



    inFile1.open(file1);
    if (!inFile1) {
        cout << "Unable to open file1";
        exit(1); // terminate with error
    }


        /* Read in words until end of file or until size words is reached
     * which ever occurs first
     */
    while (inFile1 >> word && n < size) {

            /* These next few lines make all words lowercase and removes
         * punctuation so that the dictionary will only have words 
         * in one case
         */
        word =  lowerCase(word);

            /* Finds 1st occurance of ok char */
        pun_first = word.find_first_of(ok_chars);

            /* Finds last occurance of ok char */
        pun_last = word.find_last_of(ok_chars);

            /* if a negative number then no good chars */
        if(pun_first >= 0){
                /* cleanword = the substring of good chars, notice that 
               this will allow words of the form "mid-shape" and "john's"
             */
            cleanword = word.substr(pun_first,(pun_last - pun_first + 1));
            md.insert(cleanword);
            n++;
        }

    }

    inFile1.close();

    inFile2.open(file2);
    if (!inFile2) {
        cout << "Unable to open file2";
        exit(1); // terminate with error
    }

        /* Read in words until end of file or until size words is reached
     * which ever occurs first
     */
    while (inFile2 >> word && n < size) {

           /* These next few lines make all words lowercase and removes
        * punctuation so that the dictionary will only have words 
        * in one case
        */
        word = lowerCase(word);

            /* Finds 1st occurance of ok char */
        pun_first = word.find_first_of(ok_chars);

            /* Finds last occurance of ok char */
        pun_last = word.find_last_of(ok_chars);

            /* if a negative number then no good chars */
        if(pun_first >= 0){
                /* cleanword = the substring of good chars, notice that this
             * will allow words of the form "mid-shape" and "john's"
             */
            cleanword = word.substr(pun_first,(pun_last - pun_first + 1));
            md.del(cleanword);
            n++;
        }

    }


    inFile2.close();

    //md.display();
    cout<<"\nThe Max is "<<md.max()<<"\n";
    cout<<"The Min is "<<md.min()<<"\n";
    cout<<"n = "<<n<<"\n";
        /*
    if(md.find("why")){
        cout<<"Searching for 'why' - found \n";
    }
    cout<<"The Successor of Min is "<<md.successor(md.min())<<"\n";
     */

    return 0;


}

/* converts a string to lowercase char at a time */
string lowerCase(string& s) {
    char* buf = new char[s.length()];
    s.copy(buf, s.length());
    for(int i = 0; i < (int) s.length(); i++)
        buf[i] = tolower(buf[i]);
    string r(buf, s.length());
    delete buf;
    return r;
}

Makefile

# --- macros
CC=g++
CFLAGS= -c -O2 -Wall

# --- targets
dictionary: main.o MyDictRBT.o MyDictLL.o linklist.o RedBlackTree.o BinarySearchTree.o nodes.o
    $(CC) -o dictionary -s main.o RedBlackTree.o BinarySearchTree.o linklist.o nodes.o MyDictLL.o MyDictRBT.o

main.o: main.cpp MyDictLL.h MyDictRBT.h
    $(CC) $(CFLAGS) main.cpp

MyDictRBT.o: MyDictRBT.cpp MyDictRBT.h RedBlackTree.h
    $(CC) $(CFLAGS) MyDictRBT.cpp

MyDictLL.o: MyDictLL.cpp MyDictLL.h linklist.h
    $(CC) $(CFLAGS) MyDictLL.cpp

linklist.o: linklist.cpp linklist.h nodes.h
    $(CC) $(CFLAGS) linklist.cpp

RedBlackTree.o: RedBlackTree.cpp RedBlackTree.h nodes.h BinarySearchTree.h
    $(CC) $(CFLAGS) RedBlackTree.cpp

BinarySearchTree.o: BinarySearchTree.cpp BinarySearchTree.h nodes.h
    $(CC) $(CFLAGS) BinarySearchTree.cpp

nodes.o: nodes.cpp nodes.h
    $(CC) $(CFLAGS) nodes.cpp

# --- remove binary and executable files
cleanall:
    rm -f dictionary *.o 
clean:
    rm -f *.o 
blog comments powered by Disqus
Tweet