3
\$\begingroup\$

I was wondering if anyone could give me a little bit of help with optimizing a tree-structure in C++. I'm currently developing a dictionary program for a school project but want to take it a bit further in my spare time.

A little bit of info: The dictionary is a simple class which contains a node. Each node in the class contains an array of 26 pointers to sub-nodes. Each node can contain a single letter (char) and a single definition (of std::string-type). Traversal is based solely on what letter of the alphabet needs to be looked up.

Basically, if I want to search for the definition of "programming," the dictionary class will look at each letter in the requested word and go directly to a sub-node representing the letter (a=0, b=1, c=2, and so on...). When it finally reaches the final letter "g" in "programming" then it returns a user-defined definition.

What I was wondering was if I could get help in optimizing any of the subroutines in this class. Currently, looking up words is in \$O(n)\$ time (where n is the number of letters in the requested word). Copying words in the dictionary is in \$O(m+n)\$ where 'm' is the number of preexisting words in the destination dictionary and 'n' is the number of words in the source dictionary.

Hopefully the source is easy enough to understand (I'm not used to sharing my code and this site seems to mess up my formatting).

#ifndef DICTIONARY_H
#define DICTIONARY_H
#include <string>
using namespace std;

typedef const char* cstr;
int toLower(char c) {
    //Return a lowercase letter if its within A-Z (65-90) on the ASCII table;
    //Otherwise return 'c' as it is (don't bother with non-alphabetical characters).
    return (c > 64 && c < 91) ? c+26 : c;
}

class dictionary {
    private:
        struct node {
            char    letter;
            string    definition;
            node*    alphabet[26];

            explicit node();
            explicit node(const node& nodeCopy);
            ~node();
            node& operator = (const node& nodeCopy);
            void clear();
            void copy(const node& src);
        };

        node mainNode;

        int getArrayIndex(char c);
        node* iterateToNode(cstr nodeName);

    public:
        dictionary() {}
        dictionary (const dictionary& dictionCopy) {mainNode.copy( dictionCopy.mainNode );}
        ~dictionary() {}
        dictionary& operator = (const dictionary& dictCopy);

        cstr getDefinition        (cstr word);
        void defineWord        (cstr word, cstr inDefinition);
        bool knowWord        (cstr word);
        bool knowDefinition    (cstr word);
        void addWord        (cstr word);
        void clear            () {mainNode.clear();}
};

//-----------------------------------------------------------------------------
//        Node Structure
//-----------------------------------------------------------------------------
dictionary::node::node() :
    letter(0),
    definition("")
{
    //NULL-ify all of the elements in the array
    int iter(26);
    while (iter--) alphabet[iter] = 0;
}

dictionary::node::node(const node& nodeCopy) {
    copy(nodeCopy);
}

 dictionary::node::~node() {
    clear();
}

dictionary::node& dictionary::node::operator = (const node& nodeCopy) {
    copy(nodeCopy);
    return *this;
}

void dictionary::node::clear() {
    int iter(26);
    while (iter--) {
        if (alphabet[iter]) {
            delete alphabet[iter];
            alphabet[ iter ] = 0;
        }
    }
}

void dictionary::node::copy(const node& src) {
    clear();
    letter = src.letter;
    definition = src.definition;

    int iter(26);
    while (iter--) {
        if (src.alphabet[ iter ]) {
            alphabet[ iter ] = new node; //memory-safe operation. The destination node has already been cleared
            alphabet[ iter ]->copy(*src.alphabet[ iter ]); //begin recursive awesomeness!
        }
    }
}

//-----------------------------------------------------------------------------
//        Utilities
//-----------------------------------------------------------------------------
dictionary& dictionary::operator =(const dictionary& dictCopy) {
    mainNode = dictCopy.mainNode;
    return *this;
}

 dictionary::node* dictionary::iterateToNode(cstr nodeName) {
    int pos(0), index(0);
    node* nodeTracker(&mainNode); //dictionary iterator

    do {
        index = getArrayIndex( nodeName[pos] );
        if (index == -1 || !nodeTracker->alphabet[ index ]) return 0;
        nodeTracker = nodeTracker->alphabet[index];
        ++pos;
    } while (nodeName[ pos ]);                    //end the loop when a null-termination is reached
    return nodeTracker;                        //return the position of the requested node
 }

 int dictionary::getArrayIndex(char c) {
     //make sure the letter in question actually is a letter
    if ((c < 'a') && (c > 'Z') || (c < 'A') || (c > 'z')) return -1;
    return (c < 'a') ? c - 'A' : c - 'a';    //convert all uppercase letters to lowercase (See asciitable.com)
    //get the index of the next letter in dictionary::alphabet[]
 }

//-----------------------------------------------------------------------------
//        Definitions
//-----------------------------------------------------------------------------
 cstr dictionary::getDefinition(cstr word) {
    node* nodeTracker( iterateToNode(word) );
    return (nodeTracker) ? nodeTracker->definition.c_str() : '\0';
}

void dictionary::defineWord(cstr word, cstr inDefinition) {
    node* nodeTracker( iterateToNode(word) );
    if (nodeTracker)
        nodeTracker->definition = inDefinition;
}

bool dictionary::knowWord(cstr word) {
    node* nodeTracker( iterateToNode(word) );
    return (nodeTracker) ? true : false;
}

bool dictionary::knowDefinition(cstr word) {
    node* nodeTracker( iterateToNode(word) );
    return (nodeTracker && nodeTracker->definition.size()) ? true : false;
}

void dictionary::addWord(cstr word) {
    int pos(0), index(0);
    node* nodeTracker(&mainNode); //dictionary iterator

    do {
        index = getArrayIndex( word[ pos ] );        //get the index of the next letter in dictionary::alphabet[]
        if (index == -1) return;

        if (nodeTracker->alphabet[ index ] == 0) {
            nodeTracker->alphabet[ index ] = new node;    //add a new word to the dictionary if possible
            nodeTracker->letter = word[ pos ];
        }
        nodeTracker = nodeTracker->alphabet[index];    //move to the next letter in dictionary::alphabet
        ++pos;
    } while (word[ pos ]); //end when a null-termination is reached
}

#endif    /* DICTIONARY_H */

Sample program that I've been using to test everything:

//prototyping a dictionary lookup (uses lowercase ASCII only)

#include <iostream>
#include "dictionary.h"
using namespace std;

int main() {
    dictionary testDict;
    dictionary testDict2;
    string input;
    string def;

    while (true) {
        cout << "What would you like to do?" << endl;
        cout << "\t1. Look up a word" << endl;
        cout << "\t2. Check if a word is in the dictionary" << endl;
        cout << "\t3. Add a word to the dictionary" << endl;
        cout << "\t4. Define a word" << endl;
        cout << "\t5. Quit" << endl;

        getline(cin, input);
        cout << endl;

        if (input == "1") {
            cout << "What would you like to lookup?" << endl;
            getline(cin, input);
            if (testDict.knowDefinition(input.c_str())) {
                cout << "\tThe definition is: " << testDict.getDefinition(input.c_str()) << endl;
            }
            else {
                cout << "\tSorry, I don't know that word's definition." << endl;
            }
        }

        else if (input == "2") {
            cout << "What word would you like to check?" << endl;
            getline(cin, input);
            if (testDict.knowWord(input.c_str())) {
                cout << "\tI have definitely seen that before." << endl;
            }
            else {
                cout << "\tSorry, I don't know that word." << endl;
            }
        }

        else if (input == "3") {
            cout << "What word would you like to add?" << endl;
            getline(cin, input);
            testDict.addWord(input.c_str());
            cout << "\tAdded the word: " << input.c_str() << endl;

            //memory-copying checks
            testDict2 = testDict;
            if (!testDict2.knowWord(input.c_str())) {
                cout << "\tERROR: Unable to copy memory!" << endl;
            }
        }

        else if (input == "4") {
            cout << "What word would you like to define?" << endl;
            getline(cin, input);
            if (!testDict.knowWord(input.c_str())) {
                cout << "I'm sorry, I've never even seen that word" << endl;
                continue;
            }
            cout << "What's the definition of \"" << input.c_str() << "\"?" << endl;
            getline(cin, def);
            testDict.defineWord(input.c_str(), def.c_str());

            cout << "\"" << input << "\" is now defined as: " << endl;
            cout << "\t" << testDict.getDefinition(input.c_str()) << endl;
            def.clear();
        }

        else if (input == "5") {
            cout << "GOODBYE!" << endl;
            break;
        }

        else {
            cout << "I'm sorry, I don't understand that." << endl;
        }

        cout << endl;
        input.clear();
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Your analyses of complexity is wrong; :-) The complexity is O(ln(n)) for both search and insert. As n is based on the size of the dictionary not the word length. I don't think I have a worry about doing 29 inserts floccinaucinihilipilification into the tree when there are 50,000 words in the dictionary. That is pretty good. \$\endgroup\$ – Martin York Aug 31 '12 at 16:57
  • \$\begingroup\$ @LokiAstari I'm not sure I understand where you're coming from. The traversing is based on the characters in the word, not comparing the word to what is already in the tree. Take, icdae's example of programming. You can have a million words in the tree, but programming is still going to be 11 traversals to search for (worst case). O(n) with n defined as the number of characters in a word for searching/inserting sounds correct to me. \$\endgroup\$ – Corbin Aug 31 '12 at 20:05
  • \$\begingroup\$ @Corbin: The complexity of the insert should be related to the data set size (the size of the dictionary) not the size of the word. If the complexity of inserting a word is linear O(n) then you would need to scan through the dictionary from start to end to locate the insertion point. What is happening here is that on each letter you are basically doing a 1/26 chop of the dictionary at each letter this is O(log<26>(n)) => O(ln(n)) operation. Looking at it another way it will take you 11 tests with a million entries that's not linear (linear on average would require 1/2 million tests). \$\endgroup\$ – Martin York Aug 31 '12 at 20:40
  • \$\begingroup\$ If you want to say it is linear over the size of the word sure that is a measurement. But not really a useful measurement. Even if the cost was exponentiation across the size of the word I would not worry that much if the upper bound is only 8 -> 11 characters (longest English word 29 characters (still not worried).en.wikipedia.org/wiki/Longest_word_in_English \$\endgroup\$ – Martin York Aug 31 '12 at 20:44
  • \$\begingroup\$ @LokiAstari I understand that the word length is not a useful metric, but neither is the number of entries already in the tree. With a normal tree, yes, letting n be the number of links, you are cutting n away from the possibilities. In this case though, the number of items in the tree does not affect the current item (unless I'm not understanding the algorithm?). The way I understand it, if we're cosnidering only n, number of items in the tree, then searching is O(1). "dog" for example means you always go root[d]->links[o]->links[g]. That happens no matter what is already in place. \$\endgroup\$ – Corbin Aug 31 '12 at 20:48
5
\$\begingroup\$

Dictionary is a very common word. I am thinking that there may be high possibility of clashing with existing software. I tend to try an make my include guards unique by including the namespace as part of the guard (My base namespace is also my website name so it is unique).

#ifndef DICTIONARY_H
#define DICTIONARY_H

Please stop doing this:

using namespace std;

Never do this in a header file you will pollute the global namespace (potentially without the user knowing) thus causing all sorts of side-affects). Even in source files you should probably not do it so that you don't pollute the global namespace for yourself. The reason it is called std rather than standard is so that it would not be painful to prefix things with it.

std::string x; // A string from the standard namespace.

OK. Not a real problem:

typedef const char* cstr;

But I would prefer not to see it as it implies you are using C-Strings (rather than C++ strings). Whose real type is actually char const* if you get them from literals so this can be a potentially dangerous typedef. Also once the data goes into your dictionary do you expect to mutate it? If not then I would like to see the const in the typedef.

There is already a std::tolower() that does exactly what you expect.

int toLower(char c) {
    //Return a lowercase letter if its within A-Z (65-90) on the ASCII table;
    //Otherwise return 'c' as it is (don't bother with non-alphabetical characters).
    return (c > 64 && c < 91) ? c+26 : c;
}

And is implemented in an optimal way for your platform.

Trying to be too clever and shot your self in the foot.

int iter(26);
while (iter--) alphabet[iter] = 0;

It works. But it is very awkward way of writing it. Thus every maintainer that comes across this code will go "what?". and need to validate that it actually works

Your copy constructor calls copy() which calls clear() which relies on the alphabet array being already initialized with NULL. This is not the case. Thus this will result in undefined behavior.

dictionary::node::node(const node& nodeCopy) {
    copy(nodeCopy);
}

The reason for copy seems that you put common code from the copy constructor and assignment operator in a single place. I would change this up. I would put all the copy code in the copy constructor without the call to clear(). Thenuse the copy and swap idiom to implement the assignment operator (now there is no reason for the copy() method).

Use copy and swap idiom to implement the assignment operator:

dictionary::node& dictionary::node::operator = (const node& nodeCopy) {
    copy(nodeCopy);
    return *this;
}

This implementation is not exception safe (and does not handle self assignment). When doing assignment you need to do in three stages:

1) Copy src (nodeCopy) (without altering the current object).
     If you generate an exception during the copy you need to be able
     to leave the object in a valid state preferably unchanged.
     By doing the copy without altering the current object makes this
     easier.
2) Swap the current data with the copies data.
     `swapping` is an exception safe activity so you can atomically change
     the state of the object without any exceptions being generated.
3) Destroy the old data.
     It does not matter if you generate exceptions now the object is in
     a consistent state.

These three stages are automatically achieved using the copy and swap idiom.

No need to check for NULL before deleting.

    if (alphabet[iter]) {
        delete alphabet[iter];
        alphabet[ iter ] = 0;
    }

Just use the copy constructor here it is much clearer:

        alphabet[ iter ] = new node; //memory-safe operation. The destination node has already been cleared
        alphabet[ iter ]->copy(*src.alphabet[ iter ]); //begin recursive awesomeness!

   // can be written a:
         alphabet[ iter ] = new node(*src.alphabet[iter]);

I will be back with more:

\$\endgroup\$
  • \$\begingroup\$ I always thought the delete operator required a non-NULL pointer, but after looking at the C++ standard, I can remove that "if" statement in the clear() function. Thanks for the help, I implemented those changes you pointed out and the code definitely looks much cleaner (copy() function replaced with the "=" operator, NULL-ifying values in the construction). \$\endgroup\$ – icdae Sep 1 '12 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.