Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Aug 28th, 2011  |  syntax: C++  |  size: 6.44 KB  |  views: 894  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <map>
  3. #include <list>
  4. #include <string>
  5. #include <math.h>
  6. #include <cstdlib>
  7. #include <stdlib.h>
  8. #include <string.h>
  9.  
  10. #define MAX_BUF 100000
  11.  
  12. using namespace std;
  13.  
  14. typedef unsigned int uint;
  15.  
  16.  
  17. class Word
  18. {
  19. private:
  20.     string word;
  21.    
  22.    
  23.    
  24. public:
  25.     uint rating;
  26.    
  27.     Word(string w, uint r): word(w), rating(r) {}    
  28.    
  29.     string get_word() { return word;   }
  30.    
  31. };
  32.  
  33. // Comparing function for sorting
  34. bool compare(Word* a, Word* b)
  35. {
  36.     if (a->rating > b->rating) return true;
  37.     else
  38.     {
  39.         if ((a->rating) == (b->rating) && (a->get_word().compare(b->get_word()) < 0))
  40.             return true;
  41.     }
  42.     return false;
  43. }
  44.  
  45.  
  46.  
  47.  
  48. // <dictTree>
  49.  
  50. class TreeNode
  51. {
  52. public:
  53.     TreeNode(): words() { for(int i = 2; i < 10; i++) { allocated[i] = false; } };
  54.     ~TreeNode();
  55.    
  56.     TreeNode* child[10];
  57.     bool allocated[10];
  58.     list<Word*> words;
  59. };
  60.  
  61. TreeNode::~TreeNode()
  62. {
  63.     for(list<Word*>::iterator it = words.begin(); it != words.end(); ++ it)
  64.     {
  65.         delete *it;
  66.     }
  67. }
  68.  
  69. class DictTree
  70. {
  71. private:
  72.     TreeNode *root, *current_node;
  73.     bool walking;
  74.    
  75.     string number_from_word(string);
  76.    
  77.     list<Word*>::iterator get_from_position();    
  78.     list<Word*>::iterator find_position_to_insert(list<Word*>::iterator);
  79.     void visit(TreeNode*);
  80. public:
  81.     DictTree();
  82.     string get_word();
  83.     void   add_word(string, uint);
  84.     void   walk(char);
  85.     void   restart();
  86.     void   sort();
  87.    
  88.    
  89.     uint pos;
  90.    
  91. } tree;
  92.  
  93. DictTree::DictTree()
  94. {
  95.     walking = false;
  96.     pos = 0;
  97.    
  98.     root = new TreeNode();
  99.     root -> words.push_back(new Word(".", 0));
  100.     root -> words.push_back(new Word(",", 0));
  101.     root -> words.push_back(new Word("?", 0));
  102.    
  103.     current_node = root;
  104. }
  105.  
  106.  
  107.  
  108.  
  109. string DictTree::number_from_word(string word)
  110. {
  111.     string number = "";
  112.     //uint n = pow(10, word.length() - 1);
  113.    
  114.     for(uint i = 0; i < word.length(); i++)
  115.     {
  116.         switch(word[i])
  117.         {
  118.             case 'a': case 'b': case 'c':
  119.                 number += "2"; break;
  120.                
  121.             case 'd': case 'e': case 'f':
  122.                 number += "3"; break;
  123.                
  124.             case 'g': case 'h': case 'i':
  125.                 number += "4"; break;
  126.                
  127.             case 'j': case 'k': case 'l':
  128.                 number += "5"; break;
  129.                
  130.             case 'm': case 'n': case 'o':
  131.                 number += "6"; break;
  132.                
  133.             case 'p': case 'q': case 'r': case 's':
  134.                 number += "7"; break;
  135.                
  136.             case 't': case 'u': case 'v':
  137.                 number += "8"; break;
  138.                
  139.             case 'w': case 'x': case 'y': case 'z':
  140.                 number += "9"; break;
  141.         }
  142.     }
  143.    
  144.     return number;
  145. }
  146.  
  147. void DictTree::add_word(string word, uint rating)
  148. {
  149.     string num = number_from_word(word);
  150.        
  151.     char buf[2];
  152.     buf[1] = 0;
  153.    
  154.     TreeNode* node = root;
  155.    
  156.     for (int i = 0; i < num.length(); ++i)
  157.     {
  158.         buf[0] = num[i];
  159.         char n = atoi(buf);
  160.        
  161.         if(!node->allocated[n])
  162.         {
  163.             node->child[n] = new TreeNode();
  164.             node->allocated[n] = true;
  165.         }
  166.        
  167.         node = node -> child[n];
  168.     }
  169.    
  170.     node -> words.push_front(new Word(word, rating));
  171. }
  172.  
  173.  
  174. string DictTree::get_word()
  175. {    
  176.     if(!walking) return "";
  177.     list<Word*>::iterator it = get_from_position();
  178.    
  179.     (*it)->rating += 1;
  180.    
  181.     if(current_node -> words.size() > 1 && current_node != root)
  182.     {
  183.        
  184.         list<Word*>::iterator i_pos = find_position_to_insert(it);
  185.        
  186.         if(it != i_pos)
  187.         {
  188.             current_node -> words.insert(i_pos, *it);
  189.             current_node -> words.erase(it);
  190.         }
  191.     }
  192.     restart();
  193.    
  194.     return (*it)->get_word();
  195. }
  196.  
  197. list<Word*>::iterator DictTree::get_from_position()
  198. {
  199.     list<Word*>::iterator it = current_node -> words.begin();
  200.     uint i = 0;
  201.    
  202.     while (i < pos && it != current_node -> words.end())
  203.     {
  204.         ++ i;
  205.         ++ it;
  206.     }
  207.    
  208.     return it;
  209. }
  210.  
  211.  
  212. list<Word*>::iterator DictTree::find_position_to_insert(list<Word*>::iterator it)
  213. {
  214.     list<Word*>::iterator pos = it;
  215.    
  216.     if(current_node -> words.size() == 2)
  217.     {
  218.         if(pos != current_node -> words.begin() && (*(--pos))->rating > (*it)->rating) return ++pos;
  219.     }
  220.    
  221.    
  222.     while ( (*pos)->rating <= (*it)->rating )
  223.     {
  224.         if (pos == current_node -> words.begin()) return pos;
  225.        
  226.         --pos;
  227.         if ( (*pos) -> rating > (*it) -> rating) return ++pos;
  228.     }
  229.    
  230.    
  231.     return pos;
  232. }
  233.  
  234.  
  235.  
  236. void DictTree::walk(char sym)
  237. {
  238.     char n = atoi(&sym);
  239.     string s;
  240.     if(n == 1)
  241.     {
  242.         s = get_word();
  243.            
  244.         cout << s;
  245.     }
  246.     else
  247.     {
  248.         if(walking && current_node == root)
  249.         {
  250.             s = get_word();
  251.             cout << s;
  252.         }
  253.         if(current_node->allocated[n]) current_node = current_node -> child[n];
  254.         else
  255.         {
  256.             s = get_word();
  257.             cout << s;
  258.            
  259.             current_node = current_node -> child[n];
  260.         }
  261.     }
  262.     walking = true;
  263. }
  264.  
  265.  
  266. void DictTree::restart()
  267. {
  268.     pos = 0;
  269.     walking = false;
  270.     current_node = root;
  271. }
  272.  
  273. void DictTree::sort()
  274. {
  275.     for(int i = 2; i < 10; i++) if(root->allocated[i]) visit(root->child[i]);
  276. }
  277.  
  278. void DictTree::visit(TreeNode* n)
  279. {
  280.     n -> words.sort(compare);
  281.    
  282.     for(int i = 2; i < 10; i++) if(n->allocated[i]) visit(n->child[i]);
  283. }
  284.  
  285.  
  286. // </dictTree>
  287.  
  288.  
  289. int main (int argc, const char * argv[])
  290. {
  291.     uint N;
  292.     cin >> N;
  293.    
  294.    
  295.     string word;
  296.     uint rating;
  297.     for(uint i = 0; i < N; ++i)
  298.     {
  299.         cin >> word >> rating;
  300.        
  301.         tree.add_word(word, rating);
  302.     }
  303.    
  304.     tree.sort();
  305.    
  306.     char str[MAX_BUF];
  307.    
  308.    
  309.     cin.get(); // last \n in from last word
  310.     cin.getline(str, MAX_BUF);
  311.    
  312.    
  313.     for (int i = 0; i < strlen(str); ++i)
  314.     {
  315.         if (isdigit(str[i]))
  316.         {
  317.             tree.walk(str[i]);
  318.         }
  319.         else if (str[i] == '*') ++ tree.pos;
  320.         else if (str[i] == ' ')
  321.         {
  322.             cout << tree.get_word();
  323.            
  324.             cout<<" ";
  325.         }
  326.     }
  327.     cout << tree.get_word();
  328.    
  329.     return 0;
  330. }
clone this paste RAW Paste Data