src/vocablist.cpp

   1 /*
   2 Project: J-Ben
   3 Author:  Paul Goins
   4 Website: http://www.vultaire.net/software/jben/
   5 License: GNU General Public License (GPL) version 2
   6          (http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt)
   7
   8 File: vocablist.cpp
   9
  10 This program is free software; you can redistribute it and/or modify
  11 it under the terms of the GNU General Public License as published by
  12 the Free Software Foundation; either version 2 of the License, or
  13 (at your option) any later version.
  14
  15 This program is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with this program.  If not, see <http://www.gnu.org/licenses/>
  22 */
  23
  24 #include "vocablist.h"
  25 #include "string_utils.h"
  26 #include "errorlog.h"
  27 #include <list>
  28 #include <sstream>
  29 #include <iostream>
  30 using namespace std;
  31
  32 VocabList::VocabList() {
  33 /*      vocabList.reserve(1000); */ /* We might want to do this later...? */
  34 }
  35
  36 /* "BinarySearch" searches for a query string and returns its index.
  37    If the string is not found, it returns the index at which the query
  38    should be inserted.  matchFound indicates whether the return value is
  39    a match or merely an insertion point. */
  40 int VocabList::BinarySearch(const wstring& query, bool* matchFound) {
  41         int listLength = vocabList.size();
  42         int lowBound = 0, highBound = listLength-1;
  43         int compareVal=0, index=0;
  44
  45         /* Special case: empty list */
  46         if(listLength<=0) {
  47                 if(matchFound) *matchFound = false;
  48                 return 0;
  49         }
  50
  51         /* Search for a match.  Return when found. */
  52         while(lowBound <= highBound) {
  53                 index = (lowBound+highBound)/2;
  54                 compareVal = query.compare(vocabList[index]);
  55                 if(compareVal==0) {
  56                         if(matchFound) *matchFound = true;
  57                         return index;
  58                 } else if(compareVal<0) {
  59                         highBound = index-1;
  60                 } else {
  61                         lowBound = index+1;
  62                 }
  63         }
  64
  65         /* Match was not found.  "index" will be our insertion point, and
  66            matchFound is false. */
  67         if(matchFound) *matchFound = false;
  68         if(compareVal>0) index++; /* If query is greater than the final item we
  69                                                                  looked at, then we want to insert
  70                                                                  afterwards. */
  71         return index;
  72 }
  73
  74 /* "Add" inserts an item into the study list.
  75    It uses a custom binary search function to find an insertion point for the
  76    string, and to check if the string is already in the list.
  77    No duplicate strings are allowed in the list, and such duplicates are quietly
  78    discarded. */
  79 bool VocabList::Add(const wstring& s) {
  80         bool matchFound;
  81         int insertPoint;
  82
  83         insertPoint = BinarySearch(s, &matchFound);
  84         if(!matchFound) {
  85                 vocabList.insert(vocabList.begin() + insertPoint, s);
  86                 return true;
  87         }
  88         return false;
  89 }
  90
  91 int VocabList::AddList(const wstring& s, void* srcObj) {
  92         list<wstring> t = StrTokenize<wchar_t>(s, L"\n");
  93         wstring token;
  94         int count = 0;
  95         int duplicates = 0;
  96         while(t.size()>0) {
  97                 token = t.front();
  98                 if(token.length()>0) {
  99                         if(Add(token)) count++;
 100                         else duplicates++;
 101                 }
 102                 t.pop_front();
 103         }
 104         if(duplicates>0) {
 105                 ostringstream os;
 106                 os << duplicates
 107                    << " duplicate entries were detected, and were therefore ommitted.";
 108                 el.Push(EL_Info, os.str(), srcObj);
 109         }
 110         return count;
 111 }
 112
 113 wstring VocabList::ToString(wchar_t separator) {
 114                 wstring result;
 115
 116                 vector<wstring>::iterator it = vocabList.begin();
 117                 if(it!=vocabList.end()) {
 118                         result.append(*it);
 119                         it++;
 120                         for(; it!=vocabList.end(); it++) {
 121                                 result.append(1, separator);
 122                                 result.append(*it);
 123                         }
 124                 }
 125
 126                 return result;
 127 }
 128
 129 void VocabList::Clear() {
 130         vocabList.clear();
 131 }
 132
 133 int VocabList::Size() {return vocabList.size();}
 134
 135 const wstring& VocabList::operator[](unsigned int index) {
 136         return vocabList[index];
 137 }
 138
 139 int VocabList::GetIndexByWord(const wstring& s) {
 140         /* Index returned should be 0-based. -1 indicates not found. */
 141         bool found;
 142         int index = BinarySearch(s, &found);
 143 #ifdef DEBUG
 144         printf("GetIndexByWord: BinarySearch (%ls) returned found=%d and index=%d.\n", s.c_str(), (int)found, index);
 145 #endif
 146         if(!found) return -1;
 147         return index;
 148 }
 149
 150 vector<wstring>& VocabList::GetVocabList() {return vocabList;}