source: find.hpp

Last change on this file was f6c467d, checked in by Agnibho Mondal <mail@…>, 4 years ago

Rewritten in C++

  • Property mode set to 100644
File size: 7.3 KB
Line 
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
42using namespace std;
43
44//Single word anagrams
45vector<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
71vector<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
Note: See TracBrowser for help on using the repository browser.