find.hpp

   1 /**********************************************************************
   2  * Title: Anagram
   3  * Description: Application for finding anagrams of a word
   4  * Author: Agnibho Mondal
   5  * Website: http://code.agnibho.com/anagram
   6  **********************************************************************
   7    Copyright (c) 2013-2015 Agnibho Mondal
   8    All rights reserved
   9  **********************************************************************
  10    This file is part of Anagram.
  11
  12    Anagram is free software: you can redistribute it and/or modify
  13    it under the terms of the GNU General Public License as published by
  14    the Free Software Foundation, either version 3 of the License, or
  15    (at your option) any later version.
  16
  17    Anagram is distributed in the hope that it will be useful,
  18    but WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20    GNU General Public License for more details.
  21
  22    You should have received a copy of the GNU General Public License
  23    along with Anagram.  If not, see <http://www.gnu.org/licenses/>.
  24  **********************************************************************/
  25 #ifndef FIND
  26 #define FIND
  27
  28 #define DICT_PATH "/usr/local/share/anagram/dictionary"
  29
  30 /*
  31  *Provides the functions for finding anagrams from a dictionary
  32  *Uses is_palindrome from check.h
  33  */
  34
  35 #include <iostream> //For showing progress on console
  36 #include <string> //For string
  37 #include <vector> //For vector data
  38 #include <algorithm> //For transform
  39 #include <fstream> //For reading dictionary files
  40 #include "check.hpp" //For is_anagram
  41
  42 using namespace std;
  43
  44 //Single word anagrams
  45 vector<string> find_anagram(string word){ //Finds anagrams from dictionary
  46   vector<string> file_name; //Make container to hold dictionary filenames to search
  47   vector<string> anagram_list; //Make container for holding anagrams
  48   int len=word.length(); //Find word length. Used to construct names of files to search through.
  49   //Loop over word to construct filenames (C++11)
  50   for(char i : word){
  51     string j=DICT_PATH"/"+string(1,i)+to_string(len)+".txt"; //Constructs filenames from word. (C++11)
  52     if(find(file_name.begin(), file_name.end(), j)==file_name.end()){ //Check if filename is already registered
  53       file_name.push_back(j); //Register filename
  54     }
  55   }
  56   //Loop over files to collect anagrams. (C++11)
  57   for(string i : file_name){
  58     ifstream infile(i); //Makes the file reader
  59     string line; //Variable to hold each line from the file
  60     while(getline(infile, line)){ //Loops over the file
  61       transform(line.begin(), line.end(), line.begin(), ::tolower);//Converts to lowercase
  62       if(is_anagram(word, line)){ //Checks if the read string is an anagram of the word.
  63         anagram_list.push_back(line); //Saves the found anagram
  64       }
  65     }
  66   }
  67   return anagram_list;
  68 }
  69
  70 //Multiple word anagrams
  71 vector<string> find_anagram_multiword(string word){ //Finds multiword anagrams from dictionary
  72   word.erase(remove_if(word.begin(), word.end(), ::isspace), word.end()); //Remove spaces from string
  73   vector<string> file_name; //Make container to hold dictionary filenames to search
  74   vector<string> anagram_list; //Make container for holding anagrams
  75   int len=word.length(); //Find word length. Used to construct names of files to search through.
  76   //Loop from 1 to len
  77   for(int l=1; l<=len; l++){
  78     //Loop over word to construct filenames (C++11)
  79     for(char i : word){
  80       string j=DICT_PATH"/"+string(1,i)+to_string(l)+".txt"; //Constructs filenames from word. (C++11)
  81       if(find(file_name.begin(), file_name.end(), j)==file_name.end()){ //Check if filename is already registered
  82         file_name.push_back(j); //Register filename
  83       }
  84     }
  85   }
  86   //Loop over files to collect potential words. (C++11)
  87   vector<string> word_list; //Container to hold potential words
  88   for(string i : file_name){
  89     ifstream infile(i); //Makes the file reader
  90     string line; //Variable to hold each line from the file
  91     while(getline(infile, line)){ //Loops over the file
  92       transform(line.begin(), line.end(), line.begin(), ::tolower); //Converts to lowercase
  93       bool flag=true; //flag` is used to mark if `line` is allowed as a potential anagram word
  94       for(char i : line){ //Loops over line by each character
  95         if(word.find(i)==string::npos){ //If any character of `line` is not present in `word` mark `flag` as false
  96           flag=false;
  97         }
  98       }
  99       if(flag){ //If `line` is a potential candidate save `line` to the word list
 100         word_list.push_back(line);
 101       }
 102     }
 103   }
 104   //Construct sentences from the word list
 105   vector<int> index; //Holds the word index while cycling through the list
 106   string holder; //Temporarily holds the sentence during construction
 107   int tmplen; //Holds potential sentence length temporarily
 108   index.push_back(0); //Initiate first index
 109   //Progress variables
 110   int progress_total=100;
 111   int progress_current=0;
 112   int progress_percent=0;
 113   if(word_list.size()>=3){
 114     progress_total=word_list.size()*3;
 115   }
 116   else{
 117     progress_total=word_list.size();
 118   }
 119
 120   while(index.at(0)<word_list.size()){ //Until first index exceeds list length
 121     tmplen=0; //Resets `tmplen`
 122     for(int i : index){ //Loops over index
 123       tmplen+=word_list.at(i).size(); //Calculates combined length of all indexed words
 124     }
 125
 126     if(tmplen<word.size()){ //If temporary sentence length is less than actual word length, add another index
 127       index.push_back(0);
 128     }
 129     else if(tmplen>word.size()){ //If temporary sentence length is more than actual word length, remove last index and increment the previous index
 130       index.pop_back(); //Remove last index
 131       //Remove all indices exceeding list length
 132       while(index.back()>=word_list.size()-1){
 133         index.pop_back();
 134       }
 135       if(index.empty()){ //Exit loop if all indices are removed
 136         break;
 137       }
 138       index.back()++; //Increment new last index
 139     }
 140     else if(tmplen==word.size()){ //If temporary sentence length is equal to actual word length, increment last index
 141       //Construct temporary sentence to be checked from the indexed words
 142       holder=""; //Reset holder
 143       for(int i : index){ //Concatenate all indexed words
 144         holder+=word_list.at(i)+" ";
 145       }
 146       if(is_anagram(word, holder)){ //Checks if the constructed string is an anagram of the word
 147         anagram_list.push_back(holder); //Saves the found anagram
 148       }
 149
 150       //Remove all indices exceeding list length
 151       while(index.back()>=word_list.size()-1){
 152         index.pop_back();
 153       }
 154       if(index.empty()){ //Exit loop if all indices are removed
 155         break;
 156       }
 157       index.back()++; //Increment new last index
 158     }
 159     //Calculate progress using first 3 indices
 160     if(index.size()>=3){ //Use first 3 if indices more than 3
 161       progress_total=word_list.size()*100+word_list.size()*10+word_list.size();
 162       progress_current=index.at(0)*100+index.at(1)*10+index.at(2);
 163     }
 164     if(index.size()==2){ //If 2 indices
 165       progress_total=word_list.size()*10+word_list.size();
 166       progress_current=index.at(0)*10+index.at(1);
 167     }
 168     else{ //If only 1 index
 169       progress_total=word_list.size();
 170       progress_current=index.at(0);
 171     }
 172     progress_percent=progress_current*100/progress_total; //Calculate progess percentage
 173     cerr<<progress_percent<<"% completed\t"<<anagram_list.size()<<" anagrams found.\r"; //Print progress
 174   }
 175   return anagram_list;
 176 }
 177
 178 #endif //FIND