AVLtree.cpp

#include "AVLtree.h"
#include <iostream>

void AVLTree::set_height(Node* node){
    if(!node){
        node->height = 0;
        return;
    }
    if(!node->left || !node->right){
        if(node->left){
            node->height = node->left->height + 1;
        }
        if(node->right){
            node->height = node->right->height + 1;
        }
    }
    int height = (node->left->height > node->right->height) ? node->left->height : node->right->height;
    node->height = height + 1;
}

int AVLTree::get_balance(Node* node){
    if(node){
        if(!node->left || !node->right){
            if(node->left){
                return node->left->height;
            }
            if(node->right){
                return -node->right->height;
            }
        }
        return node->left->height - node->right->height;
    }
    return 0;
}

Node* AVLTree::rotate_left(Node* node){
    Node* rightNode = node->right;
    Node* rightLeftNode = rightNode->left;
    root->right = rightLeftNode;
    rightNode->left = root;
    set_height(node);
    set_height(rightNode);
    return rightNode;
}

Node* AVLTree::rotate_right(Node* node){
    Node* leftNode = node->left;
    Node* leftRightNode = leftNode->right;
    leftNode->right = node;
    node->left = leftRightNode;
    set_height(node);
    set_height(leftNode);
    return leftNode;
}

Node* AVLTree::insert(Node* node, std::string value){
    if(!node){
        //Node(value);
        std::cout << "Making node with value:" << value << std::endl;
        //return new Node(value);
    }
    else if(compareFunction(node->word, value) == 1){
        // Word bigger than val
        node->left = insert(node->left, value);
    }
    else if(compareFunction(node->word, value) == -1){
        // Word smaller than val
        node->right = insert(node->right, value);
    }
    else{
        // Word is the same, add count
        node->count++;
        return node;
    }

    set_height(node);
    int balanceFactor = get_balance(node);
    if(balanceFactor > 1 && compareFunction(node->left->word, value) == 1){
        return rotate_right(node);
    }
    if(balanceFactor > 1 && compareFunction(node->left->word, value) == -1){
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }
    if(balanceFactor < -1 && compareFunction(node->right->word, value) == -1){
        return rotate_left(node);
    }
    if(balanceFactor < -1 && compareFunction(node->right->word, value) == 1){
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }
    return node;
}

Node* getSmallestValue(Node* node){
    while(node->left){
        node = node->left;
    }
    return node;
}

Node* AVLTree::remove(Node* node, std::string value){
    if(!node){
        return node;
    }
    if(compareFunction(node->word, value) == 1){
        node->left = remove(node->left, value);
    }
    else if(compareFunction(node->word, value) == -1){
        node->right = remove(node->right, value);
    }
    else{
        // node has right or left subtree
        if(!node->left || !node->right){
            Node* temp = node->left != nullptr ? node->left : node->right;
            if(temp){
                *node = *temp;
            }
            // Node is leaf node
            else{
                temp = node;
                node = nullptr;
            }
            //delete temp;
        }
        // Node has both left and right subtrees
        else{
            Node* temp = getSmallestValue(node->right);
            node->word = temp->word;
            node->right = remove(node->right, temp->word);
        }
    }
    if(!node){
        return node;
    }
    set_height(node);
    int balanceFactor = get_balance(node);
    if(balanceFactor > 1 && get_balance(node->left) >= 0){
        return rotate_right(node);
    }
    if(balanceFactor > 1 && get_balance(node->left) < 0){
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }
    if(balanceFactor < -1 && get_balance(node->right) <= 0){
        return rotate_left(node);
    }
    if(balanceFactor < -1 && get_balance(node->right) > 0){
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }
    return node;
}

void AVLTree::get(Node* node, std::string value){
    if(!node){
        std::cout << "(" << value << "," << 0 << ")" << std::endl;
        return;
    }
    if(compareFunction(node->word, value) == 1){
        return get(node->left, value);
    }
    else if(compareFunction(node->word, value) == -1){
        return get(node->right, value);
    }
    else{
        std::cout << "(" << node->word << "," << node->count << ")" << std::endl;
        return;
    }
}

void AVLTree::locate(Node* node, std::string value){
    std::string path = "*";
    if(!node){
        std::cout << "N" << std::endl;
        return;
    }
    if(compareFunction(node->word, value) == 1){
        path += 'L';
        return locate(node->left, value);
    }
    else if(compareFunction(node->word, value) == -1){
        path += 'R';
        return locate(node->right, value);
    }
    else{
        std::cout << path << std::endl;
        return;
    }
}

bool isUpper(char n){
    if((int)n > 64 && (int)n < 91){
        return true;
    }
    return false;
}


int lexicographicalCompare(std::string word, std::string otherWord){
    // return 0 if same
    // return 1 if word > otherWord
    // return -1 if word < otherWord
    int maxLength = (word.length() > otherWord.length()) ? word.length() : otherWord.length();

    for(int i = 0; i < maxLength; i++){
        if(isUpper(word[i]) && !isUpper(otherWord[i])){
            if(word[i] != (char)(otherWord[i] - 32)){
                if(word[i] > (char)(otherWord[i] - 32)){
                    return 1;
                }
                return -1;
            }
            else{
                return -1;
            }
        }
        else if(!isUpper(word[i]) && isUpper(otherWord[i])){
            if((char)(word[i] - 32) != otherWord[i]){
                if((char)(word[i] - 32) > otherWord[i]){
                    return 1;
                }
                return -1;
            }
            else{
                return 1;
            }
        }
        else{
            if(word[i] != otherWord[i]){
                if(word[i] > otherWord[i]){
                    return 1;
                }
                return -1;
            }
        }
    }
    if(word.length() != otherWord.length()){
        return (word.length() == maxLength) ? -1 : 1;
    }
    return 0;
}

int shortlexCompare(std::string word, std::string otherWord){
    // Returns 1 if string word comes after otherWord
    if(word.size() > otherWord.size()){
        return 1;
    }
    // Returns -1 if string word comes before otherWord
    if(word.size() < otherWord.size()){
        return -1;
    }
    // Returns 0 if string word is the same length otherWord
    return lexicographicalCompare(word, otherWord);
}

// bool isSuffix(std::string word, std::string otherWord){
//     int padding = otherWord.length() - word.length();
//     for(int i = word.length(); i >= 0; i--){
//         if(word[i] != otherWord[i + padding]){
//             return false;
//         }
//     }
//     return true;
// }

int colexCompare(std::string word, std::string otherWord){
    int shortestLength = word.length() < otherWord.length() ? word.length() : otherWord.length();
    for(int i = 0; i < shortestLength; i++){
        if(isUpper(word[word.length() - i]) && !isUpper(otherWord[otherWord.length() - i])){
            if(word[word.length() - i] != (char)(otherWord[otherWord.length() - i] - 32)){
                if(word[word.length() - i] > (char)(otherWord[otherWord.length() - i] - 32)){
                    return 1;
                }
                return -1;
            }
            else{
                return -1;
            }
        }
        else if(!isUpper(word[word.length() - i]) && isUpper(otherWord[otherWord.length() - i])){
            if((char)(word[word.length() - i] - 32) != otherWord[otherWord.length() - i]){
                if((char)(word[word.length() - i] - 32) > otherWord[otherWord.length() - i]){
                    return 1;
                }
                return -1;
            }
            else{
                return 1;
            }
        }
        else{
            if(word[word.length() - i] != otherWord[otherWord.length() - i]){
                if(word[word.length() - i] > otherWord[otherWord.length() - i]){
                    return 1;
                }
                return -1;
            }
        }
    }
    if(word.length() != otherWord.length()){
        return (word.length() == shortestLength) ? -1 : 1;
    }
    return 0;
}

AVLtree.h

#include "node.h"

class AVLTree{
public:
    Node* root;
    AVLTree(){};
    int (*compareFunction)(std::string, std::string);
    void set_height(Node* node);
    int get_balance(Node* node);
    Node* rotate_left(Node* node);
    Node* rotate_right(Node* node);
    Node* insert(Node* root, std::string value);
    Node* remove(Node* node, std::string value);
    void get(Node* node, std::string value);
    void locate(Node* node, std::string value);

};

bool isUpper(char n);
int lexicographicalCompare(std::string word, std::string otherWord);
int shortlexCompare(std::string word, std::string otherWord);
int colexCompare(std::string word, std::string otherWord);

input.txt

COLEX
I abate abatija abats abats abi abinieki abonoments
G abats
G abi
E abinieki abpus abra
G abinieki
L abi
L abats
L abi
F

main.cpp

#include <iostream>
#include <sstream>
#include "AVLtree.h"

using namespace std;

int main(){
    string line, mode;
    AVLTree myTree;
    int lineCounter = 2;
    cin >> mode;
    cout << "Got mode: " << mode << endl;
    if(mode == "COLEX"){
        myTree.compareFunction = &colexCompare;
    }
    else if(mode == "LEX"){
        myTree.compareFunction = &lexicographicalCompare;
    }
    else if(mode == "SHORTLEX"){
        myTree.compareFunction = &shortlexCompare;
    }
    while(getline(cin, line)){
        string word;
        istringstream lineInputStream(line);
        char action;
        lineInputStream >> action;
        cout << "action is: " << action << endl;
        if(action == 'I'){
            while(lineInputStream >> word){
                myTree.root = myTree.insert(myTree.root, word);
            }
        }
        if(action == 'E'){
            while(lineInputStream >> word){
                myTree.root = myTree.remove(myTree.root, word);
            }
        }
        if(action == 'G'){
            lineInputStream >> word;
            cout << lineCounter << " ";
            myTree.get(myTree.root, word);
        }
        if(action == 'L'){
            lineInputStream >> word;
            cout << lineCounter << " ";
            myTree.locate(myTree.root, word);
        }
        if(action == 'D'){
            // Not implemented
        }
        if(action == 'F'){
            break;
        }
        lineCounter++;
    }
    return 0;
}

node.h

#include <string>

struct Node{
    Node(std::string value): count(1),
    left(NULL), right(NULL), height(0){word = value;};
    int count;
    std::string word;
    Node* left;
    Node* right;
    int height;
};