Demo entry 6344881

raefrzefe

   

Submitted by anonymous on Jan 26, 2017 at 13:27
Language: C++. Code size: 15.6 kB.

#include <iostream>
#include <map>

///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T>
class List {
protected:
    struct Node {
        T info;
        Node* next;

        Node () {}
        Node (const T& x, Node* s): info(x), next(s) {}
    };
    Node*  head;   // Pointer to first item
    Node* *_last;    // Pointer to next field of last item
    int _size = 0;

public:
    class Iter{
        friend class List;
    public:
        Node* *_current;
        Iter ( Node* *p): _current(p) {}
        Iter (): _current(nullptr) {}          // Singular value

        inline T& operator* () const{
            return (*_current)->info;
        }

        inline Iter& operator++ (){
            _current = &(*_current)->next;
            return *this;
        }

        inline friend bool operator== (const Iter& p1, const Iter& p2) {
            return p1._current == p2._current;
        }

        inline friend bool operator!= (const Iter& p1, const Iter& p2) {
            return p1._current != p2._current;
        }
    };
    // Getters
    Iter begin () {
        return Iter(&head);
    }
    Iter end ()   {
        return Iter(_last);
    }
    int size () const{
        return _size;
    }
    bool empty () const{
        return _size == 0;
    }
    // Constructors
    List (): head(nullptr), _last(&head) {}

    // Updates

    virtual void insert(const T& t){

        if(size()> 1) {

            Iter i = this->begin();
            Iter previous;
            while( i != end() && *i <= t ){
                previous = i;
                ++i;
            }
            // if we insert at the end of the list, update last element
            if (i == end()) {
                Node *toInsert = new Node(t, nullptr);
                _last = &(toInsert->next);
                *(i._current) = toInsert;
                _size++;
                // or if we insert in the begining, update head of the list
            }else if (i == begin()){
                Node* toInsert = new Node(t, head );
                head = toInsert;
                _size++;

                // insertion between 2 nodes
            }else{
                Node* toInsert = new Node(t,*(i._current) );
                (*(previous._current))->next = toInsert;
                _size++;
            }

        }else{
            // if there is still no element in the list
            if(size() == 0) {
                Node *toinsert = new Node(t, nullptr);
                head = toinsert;
                _last = &(toinsert->next);
                _size++;
                // if there is only 1 element in the list, and on wich side should the new element be inserted, head or last ?
            }else if (size() == 1) {
                if (head->info <= t){
                    Node *toinsert = new Node(t, nullptr);
                    head->next = toinsert;
                    _last = &(toinsert->next);
                    _size++;

                }else{
                    Node *toinsert = new Node(t, head);
                    head = toinsert;
                    _size++;
                }
            }
        }
    }

    // iterates through the list, when the desired node is found, memory is dealocateded, and nodes are rearanged
    virtual void remove(const T& t){
        Node* toDelete ;
        Iter i = this->begin();
        bool found = false;
        Iter previous;

        while( i != end() && !found ) {
            if (*i == t) {
                found = true;
            } else {
                previous = i;
                ++i;
            }
        }
        if (found) {
            if (i == this->begin()) {
                toDelete = *(i._current);
                head = (*(i._current))->next;
                delete toDelete;
                _size--;
            } else {
                if ((*(i._current))->next == nullptr){
                    _last = &(*(previous._current))->next;
                }
                toDelete = (*(i._current));
                (*(previous._current))->next = (*(i._current))->next;
                delete toDelete;
                _size--;
            }
        }
    }
    virtual bool search(const T& t){
        for(Iter i = this->begin() ; i != this->end(); ++i ){
            if ( *i == t ){
                return true;
            }
        }
        return false;
    }
    virtual void print(){
        for (Iter i = begin() ; i != end(); ++i){
            std::cout<<"| "<< *i << " ";
        }
        std::cout<<"| "<<std::endl;
    }
};

///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////

class Trie {
public:
    class Node;
    Trie();
    virtual void insert(std::string);
    virtual bool search(std::string);
    virtual void remove(std::string);
    virtual void print();
    Node* getRoot();
    size_t getSize();
protected:
    Node* root;
    size_t size;
    void depthFirstSearch(Node*, std::string);
    Node* searchNode(std::string word);
    void dfsSearch(Node *node, std::string word, std::string tofind,bool &found, Node* &toReturn);
};

class Trie::Node {
public:
    Node(char newLetter, Node* Parent);
    Node();
    ~Node();
    char getLetter();
    bool checkIfWord();
    void setWord(bool word);
    Node *getChild(char letter);
    Node *getParent();
    void deleteChild(char letter);
    std::map<char, Node *> getChildren();
    void addChild(char letter, Node *child);

private:
    char letter;
    bool isWord;
    std::map<char, Node *> children;
    Node* parent;
};


Trie::Trie() {
    root = new Node();
}
bool Trie::search(std::string word){

    if (searchNode(word)){
        return true;
    }
    return false ;
}
void Trie::insert(std::string word) {
    Node *current = root;
    for (int i = 0; i < word.length(); i++) {
        Node *child = current->getChild(word[i]);
        //keep going deeper in the three if the letter exists in the trie
        if (child != NULL) {
            current = child;
            // or else create a new letter
        } else {
            Node *tmp = new Node(word[i], current);
            current->addChild(word[i], tmp);
            current = tmp;
        }
        // mark as new word if all letters have been added to the trie
        if (i == word.length() - 1) {
            current->setWord(true);
            size++;
        }
    }
}
// print trie
void Trie::print() {
    Trie::Node* start = root;
    std::string word = "";
    for(auto iter:start->getChildren()) {
        depthFirstSearch(iter.second, word);
        word = "";
    }
}

void Trie::depthFirstSearch(Trie::Node *node, std::string word) {
    word += node->getLetter();
    std::string save = word;
    if (node->checkIfWord()){
        std::cout<<"| "<< word << " ";
    }
    for(auto iter : node->getChildren()){
        depthFirstSearch(iter.second, word);
        word = save;
    }
}

// remove function still not ready
void Trie::remove(std::string toDel) {
    Trie::Node* current = searchNode(toDel);
    /*
    if (current->getChildren().empty()){
        char lastLetter;
        while (current->getChildren().size() == 1 || current->getChildren().empty()) {
            std::cout << current->getLetter() << " : " << &current << std::endl;
            Node* toDel = current;
            current = current->getParent();
            std::map<char, Trie::Node*>::iterator itr = current->getChildren().find(toDel->getLetter());
            if (itr != current->getChildren().end()){
                delete itr->second;
                current->getChildren().erase(itr);
            }
            std::cout<<current->getChildren().size()<<std::endl;
            std::cout << "DELETED" << std::endl;
        }

    */
    if (current!= NULL){
        (current)->setWord(false);
    }else{
        std::cout<<"Ce mot n'est pas dans le dictionnaire" << std::endl;
    }
}

Trie::Node* Trie::searchNode( std::string word) {
    Trie::Node* start = this->root;
    Trie::Node* toReturn = NULL;
    std::string currentWord = "";
    bool found = false;
    for(auto iter:start->getChildren()) {
        if (!found) {
            dfsSearch(iter.second, currentWord, word, found, toReturn);
            currentWord = "";
        }
    }
    return toReturn;
}

void Trie::dfsSearch(Trie::Node *node, std::string word, std::string tofind,bool &found, Trie::Node* &toReturn) {
    word += node->getLetter();
    std::string save = word;
    if (node->checkIfWord() && word == tofind ){
        found = true;
        toReturn = node;

    }
    if (!found) {
        for (auto iter : node->getChildren()) {
            dfsSearch(iter.second, word, tofind, found, toReturn);
            word = save;
        }
    }
}


// Node methods
Trie::Node::Node() {}
Trie::Node::~Node() {}
Trie::Node::Node(char newLetter, Trie::Node* parent) {
    this->parent = parent;
    this->letter = newLetter;
}

void Trie::Node::addChild(char letter, Trie::Node *child) {
    children[letter] = child;
}

bool Trie::Node::checkIfWord() {
    return this->isWord;
}

Trie::Node* Trie::Node::getChild(char letter) {
    if (children.count(letter)){
        return children[letter];
    }
    return NULL;
}
Trie::Node* Trie::getRoot() {
    return this->root;
}

size_t Trie::getSize() {
    return this->size;
}

char Trie::Node::getLetter() {
    return this->letter;
}

std::map<char, Trie::Node *> Trie::Node::getChildren() {
    return this->children;
}

Trie::Node* Trie::Node::getParent() {
    return this->parent;
}

void Trie::Node::setWord(bool word) {
    this->isWord = word;
}

void Trie::Node::deleteChild(char letter) {
    this->getChildren().erase(letter);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////


class DicoTrie;
class DicoList: public List<std::string> {
private:
    // depth first search for fusion of linked list and trie, for each new word found in the trie,
    // if not already present, it is added to the current dictionnary
    void addTraversal(Trie::Node *node, std::string toInsert,DicoList *dico);
public :
    // traversal of the list until element is found, else return false
    void operator+=(DicoTrie *toFuse);
    void operator+=(DicoList *toFuse);

};


class DicoTrie: public Trie {
private:
    // depth first search for fusion of linked list and trie, for each new word found in the trie,
    // if not already present, it is added to the current dictionnary
    void addTraversal(Node *node, std::string toInsert,DicoTrie *dico);
    void checkTraversal(Node* node,std::string word, bool &found, std::string wordToFind );
public :
    // depth first search to check if word is present
    bool isPresent(std::string wordToFind);
    void operator+=(DicoList *toFuse );
    void operator+=(DicoTrie *toFuse );
};


bool DicoTrie::isPresent(std::string wordToFind) {
    bool found = false;
    std::string currentWord = "";
    Node* start = this->root;

    for(auto iter:start->getChildren()) {
        if(!found) {
            checkTraversal(iter.second, currentWord, found, wordToFind);
            currentWord = "";
        }
    }
    return found;

}

void DicoTrie::checkTraversal(Node *node, std::string word, bool &found, std::string wordToFind) {
    word += node->getLetter();
    std::string save = word;
    if (node->checkIfWord()){
        if(word == wordToFind){
            found = true;
        }
    }
    if(!found) {
        for (auto iter : node->getChildren()) {
            checkTraversal(iter.second, word, found, wordToFind);
            word = save;
        }
    }
}

void DicoTrie::operator+=(DicoList *toFuse) {
    for(DicoList::Iter i = toFuse->begin() ; i != toFuse->end() ; ++i){
        if (!isPresent(*i)){
            this->insert(*i);
        }
    }
}

void DicoTrie::operator+=(DicoTrie *toFuse){
    Trie::Node* start = toFuse->getRoot();
    std::string word = "";
    for(auto iter:start->getChildren()) {
        addTraversal(iter.second, word, this);
        word = "";
    }
}
void DicoTrie::addTraversal(Node *node, std::string toInsert, DicoTrie *dico) {
    toInsert += node->getLetter();
    std::string save = toInsert;
    if (node->checkIfWord() && !search(toInsert)){
        insert(toInsert);
    }
    for(auto iter : node->getChildren()){
        addTraversal(iter.second, toInsert, dico);
        toInsert = save;
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////


void DicoList::operator+=(DicoTrie *toFuse) {
    Trie::Node* start = toFuse->getRoot();
    std::string word = "";
    for(auto iter:start->getChildren()) {
        addTraversal(iter.second, word, this);
        word = "";
    }
}

void DicoList::addTraversal(Trie::Node *node, std::string toInsert,DicoList *dico) {
    toInsert += node->getLetter();
    std::string save = toInsert;
    if (node->checkIfWord() && !search(toInsert)){
        dico->insert(toInsert);
    }
    for(auto iter : node->getChildren()){
        addTraversal(iter.second, toInsert, dico);
        toInsert = save;
    }
}


void DicoList::operator+=(DicoList *toFuse) {
    for(DicoList::Iter i = toFuse->begin() ; i != toFuse->end() ; ++i){
        if (!search(*i)){
            this->insert(*i);
        }
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
void printline(){
    std::cout<<std::endl;
}

int main() {

    DicoTrie *dicoTrie = new DicoTrie();
    DicoList *dicoList = new DicoList();

    std::cout<<"Dictionnary with trie : "<<std::endl;
    printline();

    dicoTrie->insert("hello");
    dicoTrie->insert("every");
    dicoTrie->insert("one");
    dicoTrie->insert("this");
    dicoTrie->insert("is");
    dicoTrie->insert("a");
    dicoTrie->insert("test");
    dicoTrie->print();
    printline();
    printline();



    std::cout<<"Dictionnary with List : "<<std::endl;
    printline();

    dicoList->insert("this");
    dicoList->insert("dictionnary");
    dicoList->insert("is");
    dicoList->insert("implemented");
    dicoList->insert("with");
    dicoList->insert("linkedlists");
    dicoList->print();
    printline();
    printline();
    printline();


    std::cout<<"Dictionnary with List += dictionnary with trie : "<<std::endl;
    printline();

    *dicoList += dicoTrie;

    dicoList->print();
    printline();
    printline();
    printline();




    std::cout<<"New Dictionnarylist wich will be added to the Trie "<<std::endl;
    printline();

    DicoList *addToTrie = new DicoList;
    addToTrie->insert("these");
    addToTrie->insert("words");
    addToTrie->insert("will");
    addToTrie->insert("be");
    addToTrie->insert("addedd");
    addToTrie->insert("to");
    addToTrie->insert("the");
    addToTrie->insert("trie");
    addToTrie->print();

    std::cout<<"Dicotrie += Dicolist"<<std::endl;
    printline();

    *dicoTrie+= addToTrie;
    dicoTrie->print();



    return 0;
}

This snippet took 0.04 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).