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 "jben.h"
  26 #include "string_utils.h"
  27 #include "errorlog.h"
  28 #include <list>
  29 #include <sstream>
  30 #include <iostream>
  31 using namespace std;
  32
  33 VocabList::VocabList() {
  34 /*      vocabList.reserve(1000); */ /* We might want to do this later...? */
  35 }
  36
  37 /* "BinarySearch" searches for a query string and returns its index.
  38    If the string is not found, it returns the index at which the query
  39    should be inserted.  matchFound indicates whether the return value is
  40    a match or merely an insertion point. */
  41 int VocabList::BinarySearch(const wstring& query, bool* matchFound) {
  42         int listLength = vocabList.size();
  43         int lowBound = 0, highBound = listLength-1;
  44         int compareVal=0, index=0;
  45
  46         /* Special case: empty list */
  47         if(listLength<=0) {
  48                 if(matchFound) *matchFound = false;
  49                 return 0;
  50         }
  51
  52         /* Search for a match.  Return when found. */
  53         while(lowBound <= highBound) {
  54                 index = (lowBound+highBound)/2;
  55                 compareVal = query.compare(vocabList[index]);
  56                 if(compareVal==0) {
  57                         if(matchFound) *matchFound = true;
  58                         return index;
  59                 } else if(compareVal<0) {
  60                         highBound = index-1;
  61                 } else {
  62                         lowBound = index+1;
  63                 }
  64         }
  65
  66         /* Match was not found.  "index" will be our insertion point, and
  67            matchFound is false. */
  68         if(matchFound) *matchFound = false;
  69         if(compareVal>0) index++; /* If query is greater than the final item we
  70                                                                  looked at, then we want to insert
  71                                                                  afterwards. */
  72         return index;
  73 }
  74
  75 /* "Add" inserts an item into the study list.
  76    It uses a custom binary search function to find an insertion point for the
  77    string, and to check if the string is already in the list.
  78    No duplicate strings are allowed in the list, and such duplicates are quietly
  79    discarded. */
  80 bool VocabList::Add(const wstring& s) {
  81         bool matchFound;
  82         int insertPoint;
  83
  84         insertPoint = BinarySearch(s, &matchFound);
  85         if(!matchFound) {
  86                 vocabList.insert(vocabList.begin() + insertPoint, s);
  87                 return true;
  88         }
  89         return false;
  90 }
  91
  92 int VocabList::AddList(const wstring& s) {
  93         list<wstring> t = StrTokenize<wchar_t>(s, L"\n");
  94         wstring token;
  95         int count = 0;
  96         int duplicates = 0;
  97         while(t.size()>0) {
  98                 token = t.front();
  99                 if(token.length()>0) {
 100                         if(Add(token)) count++;
 101                         else duplicates++;
 102                 }
 103                 t.pop_front();
 104         }
 105         if(duplicates>0) {
 106                 ostringstream os;
 107                 os << duplicates
 108                    << " duplicate entries were detected, and were therefore ommitted.";
 109                 el.Push(EL_Info, os.str(), (void *)this);
 110         }
 111         return count;
 112 }
 113
 114 wstring VocabList::ToString(wchar_t separator) {
 115                 wstring result;
 116
 117                 vector<wstring>::iterator it = vocabList.begin();
 118                 if(it!=vocabList.end()) {
 119                         result.append(*it);
 120                         it++;
 121                         for(; it!=vocabList.end(); it++) {
 122                                 result.append(1, separator);
 123                                 result.append(*it);
 124                         }
 125                 }
 126
 127                 return result;
 128 }
 129
 130 void VocabList::Clear() {
 131         vocabList.clear();
 132 }
 133
 134 int VocabList::Size() {return vocabList.size();}
 135
 136 const wstring& VocabList::operator[](unsigned int index) {
 137         return vocabList[index];
 138 }
 139
 140 int VocabList::GetIndexByWord(const wstring& s) {
 141         /* Index returned should be 0-based. -1 indicates not found. */
 142         bool found;
 143         int index = BinarySearch(s, &found);
 144 #ifdef DEBUG
 145         printf("GetIndexByWord: BinarySearch (%ls) returned found=%d and index=%d.\n", s.c_str(), (int)found, index);
 146 #endif
 147         if(!found) return -1;
 148         return index;
 149 }
 150
 151 vector<wstring>& VocabList::GetVocabList() {return vocabList;}