Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <list>
- #include <string>
- #include <math.h>
- #include <cstdlib>
- #include <stdlib.h>
- #include <string.h>
- #define MAX_BUF 100000
- using namespace std;
- typedef unsigned int uint;
- class Word
- {
- private:
- string word;
- public:
- uint rating;
- Word(string w, uint r): word(w), rating(r) {}
- string get_word() { return word; }
- };
- // Comparing function for sorting
- bool compare(Word* a, Word* b)
- {
- if (a->rating > b->rating) return true;
- else
- {
- if ((a->rating) == (b->rating) && (a->get_word().compare(b->get_word()) < 0))
- return true;
- }
- return false;
- }
- // <dictTree>
- class TreeNode
- {
- public:
- TreeNode(): words() { for(int i = 2; i < 10; i++) { allocated[i] = false; } };
- ~TreeNode();
- TreeNode* child[10];
- bool allocated[10];
- list<Word*> words;
- };
- TreeNode::~TreeNode()
- {
- for(list<Word*>::iterator it = words.begin(); it != words.end(); ++ it)
- {
- delete *it;
- }
- }
- class DictTree
- {
- private:
- TreeNode *root, *current_node;
- bool walking;
- string number_from_word(string);
- list<Word*>::iterator get_from_position();
- list<Word*>::iterator find_position_to_insert(list<Word*>::iterator);
- void visit(TreeNode*);
- public:
- DictTree();
- string get_word();
- void add_word(string, uint);
- void walk(char);
- void restart();
- void sort();
- uint pos;
- } tree;
- DictTree::DictTree()
- {
- walking = false;
- pos = 0;
- root = new TreeNode();
- root -> words.push_back(new Word(".", 0));
- root -> words.push_back(new Word(",", 0));
- root -> words.push_back(new Word("?", 0));
- current_node = root;
- }
- string DictTree::number_from_word(string word)
- {
- string number = "";
- //uint n = pow(10, word.length() - 1);
- for(uint i = 0; i < word.length(); i++)
- {
- switch(word[i])
- {
- case 'a': case 'b': case 'c':
- number += "2"; break;
- case 'd': case 'e': case 'f':
- number += "3"; break;
- case 'g': case 'h': case 'i':
- number += "4"; break;
- case 'j': case 'k': case 'l':
- number += "5"; break;
- case 'm': case 'n': case 'o':
- number += "6"; break;
- case 'p': case 'q': case 'r': case 's':
- number += "7"; break;
- case 't': case 'u': case 'v':
- number += "8"; break;
- case 'w': case 'x': case 'y': case 'z':
- number += "9"; break;
- }
- }
- return number;
- }
- void DictTree::add_word(string word, uint rating)
- {
- string num = number_from_word(word);
- char buf[2];
- buf[1] = 0;
- TreeNode* node = root;
- for (int i = 0; i < num.length(); ++i)
- {
- buf[0] = num[i];
- char n = atoi(buf);
- if(!node->allocated[n])
- {
- node->child[n] = new TreeNode();
- node->allocated[n] = true;
- }
- node = node -> child[n];
- }
- node -> words.push_front(new Word(word, rating));
- }
- string DictTree::get_word()
- {
- if(!walking) return "";
- list<Word*>::iterator it = get_from_position();
- (*it)->rating += 1;
- if(current_node -> words.size() > 1 && current_node != root)
- {
- list<Word*>::iterator i_pos = find_position_to_insert(it);
- if(it != i_pos)
- {
- current_node -> words.insert(i_pos, *it);
- current_node -> words.erase(it);
- }
- }
- restart();
- return (*it)->get_word();
- }
- list<Word*>::iterator DictTree::get_from_position()
- {
- list<Word*>::iterator it = current_node -> words.begin();
- uint i = 0;
- while (i < pos && it != current_node -> words.end())
- {
- ++ i;
- ++ it;
- }
- return it;
- }
- list<Word*>::iterator DictTree::find_position_to_insert(list<Word*>::iterator it)
- {
- list<Word*>::iterator pos = it;
- if(current_node -> words.size() == 2)
- {
- if(pos != current_node -> words.begin() && (*(--pos))->rating > (*it)->rating) return ++pos;
- }
- while ( (*pos)->rating <= (*it)->rating )
- {
- if (pos == current_node -> words.begin()) return pos;
- --pos;
- if ( (*pos) -> rating > (*it) -> rating) return ++pos;
- }
- return pos;
- }
- void DictTree::walk(char sym)
- {
- char n = atoi(&sym);
- string s;
- if(n == 1)
- {
- s = get_word();
- cout << s;
- }
- else
- {
- if(walking && current_node == root)
- {
- s = get_word();
- cout << s;
- }
- if(current_node->allocated[n]) current_node = current_node -> child[n];
- else
- {
- s = get_word();
- cout << s;
- current_node = current_node -> child[n];
- }
- }
- walking = true;
- }
- void DictTree::restart()
- {
- pos = 0;
- walking = false;
- current_node = root;
- }
- void DictTree::sort()
- {
- for(int i = 2; i < 10; i++) if(root->allocated[i]) visit(root->child[i]);
- }
- void DictTree::visit(TreeNode* n)
- {
- n -> words.sort(compare);
- for(int i = 2; i < 10; i++) if(n->allocated[i]) visit(n->child[i]);
- }
- // </dictTree>
- int main (int argc, const char * argv[])
- {
- uint N;
- cin >> N;
- string word;
- uint rating;
- for(uint i = 0; i < N; ++i)
- {
- cin >> word >> rating;
- tree.add_word(word, rating);
- }
- tree.sort();
- char str[MAX_BUF];
- cin.get(); // last \n in from last word
- cin.getline(str, MAX_BUF);
- for (int i = 0; i < strlen(str); ++i)
- {
- if (isdigit(str[i]))
- {
- tree.walk(str[i]);
- }
- else if (str[i] == '*') ++ tree.pos;
- else if (str[i] == ' ')
- {
- cout << tree.get_word();
- cout<<" ";
- }
- }
- cout << tree.get_word();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement