#include #include #include #include using namespace std; #ifndef CPP11 #define nullptr NULL #endif template class arrayset { public: arrayset() : value() { ismem = false; child = nullptr; sibling = nullptr; numconstr++; } ~arrayset() { if (child!=nullptr) delete child; if (sibling!=nullptr) delete sibling; numdestr++; } arrayset(const arrayset &s) : value(s.value) { ismem = s.ismem; if (s.child==nullptr) child=nullptr; else child = new arrayset(*(s.child)); if (s.sibling==nullptr) sibling=nullptr; else sibling = new arrayset(*(s.sibling)); numcpy++; } arrayset &operator=(const arrayset &s) { if (this==&s) return *this; if (child!=nullptr) delete child; if (sibling!=nullptr) delete sibling; ismem = s.ismem; value = s.value; if (s.child==nullptr) child=nullptr; else child = new arrayset(*(s.child)); if (s.sibling==nullptr) sibling=nullptr; else sibling = new arrayset(*(s.sibling)); numassign++; } template bool ismember(const It &begin, const It &end) const { if (begin==end) return ismem; if (*begin == value) return child != nullptr && child->ismember(begin+1,end); return sibling != nullptr && sibling->ismember(begin,end); } template void addmember(const It &begin, const It &end) { if (begin==end) ismem = true; else if (*begin==value) { if (child==nullptr) { child = new arrayset(); child->value = *(begin+1); } child->addmember(begin+1,end); } else { if (sibling==nullptr) { sibling = new arrayset(); sibling->value = *begin; } sibling->addmember(begin,end); } } static int numconstr,numdestr,numcpy,numassign; private: arrayset *sibling; arrayset *child; T value; bool ismem; }; template<> int arrayset::numconstr = 0; template<> int arrayset::numdestr = 0; template<> int arrayset::numcpy = 0; template<> int arrayset::numassign = 0; // I'm ignoring that the traits or allocator might be non-default template class stringset : public arrayset { public: typedef std::basic_string str; stringset() : arrayset() { } ~stringset() { } stringset(const stringset &s) : arrayset(s) { } stringset &operator=(const stringset &s) { if (this==&s) return *this; arrayset::operator=(s); return *this; } bool ismember(const str &s) const { return arrayset::ismember(s.begin(),s.end()); } void addmember(const str &s) { arrayset::addmember(s.begin(),s.end()); } }; stringset loaddictionary(const char *filename) { ifstream f(filename); if (!f.good()) { // should throw exception... // but returning something here prevents RVO in g++ return stringset (); } stringset ret; while(!f.eof()) { string s; f >> s; if (s.size()>0) ret.addmember(s); } return ret; } int main(int argc, char **argv) { { stringset s = loaddictionary(argc>1 ? argv[0] : "words"); cout << "bubble? " << s.ismember("bubble") << endl; cout << "downtime? " << s.ismember("downtime") << endl; cout << "existentialism? " << s.ismember("existentialism") << endl; cout << "gobbledygook? " << s.ismember("gobbledygook") << endl; cout << "gobbledygoo? " << s.ismember("gobbledygoo") << endl; cout << "foo? " << s.ismember("foo") << endl; cout << "qwesr? " << s.ismember("qwesr") << endl; } cout << "-------------------------" << endl; cout << "# constructors: " << arrayset::numconstr << endl; cout << "# destructors: " << arrayset::numdestr << endl; cout << "# copies: " << arrayset::numcpy << endl; cout << "# assignments: " << arrayset::numassign << endl; return 0; }