Binary Search Based Encryption

A simple concept, but not so simple execution

Page 1 of 1

2 Replies - 3209 Views - Last Post: 15 October 2010 - 02:16 PM Rate Topic: -----

#1 SamAllmon   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 30
  • Joined: 27-August 09

Binary Search Based Encryption

Posted 14 October 2010 - 08:31 PM

So my professor, henceforth referred to as Hamerly, has assigned us a peculiar use of Binary search trees:
Using a BST as a codebook to encrypt/decrypt messages.
Designing the BST was fairly easy. We didn't even have to AVL balance it; that's next project.

My problem arises with handling the input.
The program is interfaced with as follows:
i word                //inserts "word" into the BST
r word                //removes "word" from the BST
e 'cleartext message' //encrypts the message by returning a path to each of the words in the message,
                      //in the form rX, where r is a literal letter 'r', standing for root, and
                      //X is a series of 1s and 0s, 0 standing for a left-branch, and 1 standing for a 
                      //right branch.
d 'encrpyed message'  //decrypts the message given to it by following the path, and returning a pointer 
                      //to the string it refers to.



you see, I tested my BST and EncryptionTree classes via just straight calls to them, and they did fine. So somewhere in the removing of the single quotes, my decrypt function goes crazy.
Encryption works fine. It returns a series of rX's like it's supposed to.
Decryption just prints a newline.
Which makes me think that it is reading something that makes it return a NULL pointer or something, but I can't see why.

Here's Encryption Tree's Encrypt and Decrpyt functions:
template <class Base>
string EncryptionTree<Base>::encrypt(const Base &item) const{
    string result = "r";
    const BSTNode<Base>* p = root;
    bool found = false;
    bool quit = false;
    while(!found && !quit){
        if(item < p->getData()){
            if(p->getLeft()){
                result += "0";
                p = p->getLeft();
            }
            else{
                result = "?";
                quit = true;
            }
        }
        else if(p->getData() < item){
            if(p->getRight()){
                result += "1";
                p = p->getRight();
            }
            else{
                result = "?";
                quit = true;
            }
        }
        else{
            found = true;
        }
    }
    return result;
}


template <class Base>
const Base *EncryptionTree<Base>::decrypt(const string &path) const{
    const BSTNode<Base>* p = root;
    bool quit = false;
    if(root){
        for(int i = 0; i < path.size() && !quit; i++){
            switch(path[i]){
            case 'r': break;
            case '0':
                if(p->getLeft()){
                    p = p->getLeft();
                }
                else{
                    quit = true;
                }
                break;
            case '1':
                if(p->getRight()){
                    p = p->getRight();
                }
                else{
                    quit = true;
                }
                break;
            default:
                assert(false);
            }
        }
    }
    if(quit)
        return NULL;
    else
        return &p->getData();
}



and here is the driver:
int main(){
    char token;
    string stuff;
    EncryptionTree<string> tree;
    bool done = false;
    bool quit = false;

    while(!quit){
        cin >> token;
        switch(token){
        case 'i':
            cin >> stuff;
            tree.insert(stuff);
            break;
        case 'r':
            cin >> stuff;
            tree.remove(stuff);
            break;
        case 'p':
            tree.printPreorder(cout);
            break;
        case 'q': 
            quit = true;
            break;
        case 'e':
            cin.ignore(2, '\'');
            while(!done){
                cin>> stuff;
                if(stuff[stuff.size()-1] == '\''){
                    stuff.erase(stuff.size()-1);
                    done = true;
                }
                cout << tree.encrypt(stuff) << " ";
            }
            cout << endl;
            break;
        case 'd':
            cin.ignore(2, '\'');
            while(!done){
                cin >> stuff;
                if(stuff[stuff.size()-1] == '\''){
                    stuff.erase(stuff.size()-1);
                    done = true;
                }
                if(tree.decrypt(stuff))
                    cout << *tree.decrypt(stuff) << " ";
            }
            cout << endl;
            break;
        }
    }
    return 0;
}



And here is the implementation of the BST class, from which EncryptionTree is derived:
template <class Base>
BSTNode<Base>::~BSTNode(){
    delete left;
    delete right;
}

template <class Base>
void BSTNode<Base>::printPreorder(ostream &os = cout, string indent = "") const {
    os << indent << data <<endl;
    if(!left)
        os << indent << "  NULL" << endl;
    else
        left->printPreorder(os, indent + "  ");
    if(!right)
        os << indent << "  NULL" << endl;
    else
        right->printPreorder(os, indent + "  ");
}

template <class Base>
const BSTNode<Base> *BSTNode<Base>::minNode() const{
    if(left)
        return left->minNode();
    else
        return this;
}

template <class Base>
const BSTNode<Base> *BSTNode<Base>::maxNode() const{
    if(right)
        return right->maxNode();
    else
        return this;
}



template <class Base>
void BST<Base>::insert(const Base &item){
    BSTNode<Base>* parent = root;
    BSTNode<Base>* child = root;
    if(!root){
        root = new BSTNode<Base>(item, NULL, NULL);
    }
    else{
        if(item < parent->data){
            child = parent->left;
        }
        else if(parent->data < item){
            child = parent->right;
        }
        else{
            parent = NULL;
            child = NULL;
        }
        while(child){
            if(item < child->data){
                parent = child;
                child = parent->left;
            }
            else if(child->data < item){
                parent = child;
                child = parent->right;
            }
            else{
                parent = NULL;
                child = NULL;
            }
        }
        if(parent){
            if(item < parent->data){
                child = new BSTNode<Base>(item, NULL, NULL);
                parent->left = child;
            }
            else{
                child = new BSTNode<Base>(item, NULL, NULL);
                parent->right = child;
            }
        }
    
    }
}

template <class Base>
void BST<Base>::remove(const Base &item){
    BSTNode<Base>* parent = NULL;
    BSTNode<Base>* toRemove = root;
    bool found = false;
    bool quit = false;
    if(root){
        while(!found && !quit){
            if(item < toRemove->data){
                if(toRemove->left){
                    parent = toRemove;
                    toRemove = toRemove->left;
                }
                else{
                    quit = true;
                }
            }
            else if(toRemove->data < item){
                if(toRemove->right){
                    parent = toRemove;
                    toRemove = toRemove->right;
                }
                else{
                    quit = true;
                }
            }
            else{
                found = true;
            }
        }
        //if we found what we needed to remove:
        if(found){
            //no children
            if(toRemove->left == NULL && toRemove->right == NULL){
                if(toRemove == root){
                    root = NULL;
                }
                else if(parent->left == toRemove){
                    parent->left = NULL;
                }
                else{
                    parent->right = NULL;
                }
                delete toRemove;
            }
            //one child, left version.
            else if(toRemove->left && toRemove->right == NULL){
                if(toRemove == root){
                    root = toRemove->left;
                }
                else if(parent->left == toRemove){
                    parent->left = toRemove->left;
                }
                else{
                    parent->right = toRemove->left;
                }
                toRemove->left = NULL;
                delete toRemove;
            }
            //one child, right version
            else if(toRemove->left ==NULL && toRemove->right){
                if(toRemove == root){
                    root = toRemove->right;
                }
                else if(parent->left == toRemove){
                    parent->left = toRemove->right;
                }
                else{
                    parent->right = toRemove->right;
                }
                toRemove->right = NULL;
                delete toRemove;
            }//two kids
            else{
                BSTNode<Base>* min = toRemove->right;
                BSTNode<Base>* minParent = toRemove;
                while(min->left){
                    minParent = min;
                    min = min->left;
                }
                if(toRemove == minParent){
                    min->left = toRemove->left;
                    if(toRemove == root){
                        root = min;
                    }
                    else if(parent->left == toRemove){
                        parent->left = min;
                    }
                    else{
                        parent->right = min;
                    }
                    toRemove->left = NULL;
                    toRemove->right = NULL;
                    delete toRemove;
                }
                else{
                    min->left = toRemove->left;
                    min->right = toRemove->right;
                    if(toRemove == root){
                        root = min;
                    }
                    else if(parent->left == toRemove){
                        parent->left = min;
                    }
                    else{
                        parent->right = min;
                    }
                    minParent->left = NULL;
                    toRemove->left = NULL;
                    toRemove->right = NULL;
                    delete toRemove;
                }
            }
        }
    }
}



There are a few functions in the class definitions, but Hamerly wrote those, and most are just the Get/set functions, so they're trivial.


Any help?
If I'm not clear on anything, ask me to expound, I just have been trying for a while now, and am pretty much stuck. So even if you have a "Hmmm. I dunno try <this>" It'll be helpful. Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Based Encryption

#2 SamAllmon   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 30
  • Joined: 27-August 09

Re: Binary Search Based Encryption

Posted 15 October 2010 - 12:30 PM

AHA!
It's not Decrypt that isn't working. It's whatever happens second.
So My problem is with handling the trailing 's and newlines, etc.

so focusing my efforts is on:
            cin.ignore(2, '\'');
            while(!done){
                cin>> stuff;
                if(stuff[stuff.size()-1] == '\''){
                    stuff.erase(stuff.size()-1);
                    done = true;
                }
                cout << tree.encrypt(stuff) << " ";
            }



And finding another way to get the 's off.

This post has been edited by SamAllmon: 15 October 2010 - 12:32 PM

Was This Post Helpful? 0
  • +
  • -

#3 SamAllmon   User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 30
  • Joined: 27-August 09

Re: Binary Search Based Encryption

Posted 15 October 2010 - 02:16 PM

View PostSamAllmon, on 15 October 2010 - 11:30 AM, said:

AHA!
It's not Decrypt that isn't working. It's whatever happens second.
So My problem is with handling the trailing 's and newlines, etc.

so focusing my efforts is on:
            cin.ignore(2, '\'');
            while(!done){
                cin>> stuff;
                if(stuff[stuff.size()-1] == '\''){
                    stuff.erase(stuff.size()-1);
                    done = true;
                }
                cout << tree.encrypt(stuff) << " ";
            }



And finding another way to get the 's off.


Okay. So. It was ridiculously easy. >.<
I just wasn't resetting the done boolean to False after breaking out of that loop. So it was skipping everything.
Thanks to the 30 some odd people who at least looked at it.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1