#include <stdlib.h>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <initializer_list>

using namespace std;

#ifndef CPP11
#define nullptr NULL
#endif

template<typename T>
class arrayset {
public:
	arrayset<T>() : value() {
		ismem = false;
		child = nullptr;
		sibling = nullptr;
		numconstr++;
	}
	~arrayset<T>() {
		if (child!=nullptr) delete child;
		if (sibling!=nullptr) delete sibling;
		numdestr++;
	}
	arrayset<T>(const arrayset<T> &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<T>(arrayset<T> &&s) : value(std::move(s.value)) {
		ismem = s.ismem;
		child = s.child;
		sibling = s.sibling;
		s.child = nullptr;
		s.sibling = nullptr;
		nummove++;
	}
	arrayset<T> &operator==(const arrayset<T> &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<T>(*(s.child));
		if (s.sibling==nullptr) sibling=nullptr;
		else sibling = new arrayset<T>(*(s.sibling));
		numassign++;
	}
	arrayset<T> &operator==(arrayset<T> &&s) {
		if (this==&s) return *this;
		ismem = s.ismem;
		value = std::move(s.value);
		if (child!=nullptr) delete child;
		child = s.child;
		s.child = nullptr;
		if (sibling!=nullptr) delete sibling;
		sibling = s.sibling;
		s.sibling = nullptr;
		nummassign++;
	}

	template<typename It>
	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<typename It>
	bool addmember(const It &begin, const It &end) {
		if (begin==end) { 
			bool ret = !ismem;
			ismem = true;
			return ret;
		} else if (*begin==value) {
			if (child==nullptr) {
				child = new arrayset<T>();
				child->value = *(begin+1);
			}
			return child->addmember(begin+1,end); 
		} else {
			if (sibling==nullptr) {
				sibling = new arrayset<T>();
				sibling->value = *begin;
			}
			return sibling->addmember(begin,end);
		}
	}
	
	static int numconstr,numdestr,numcpy,numassign,nummove,nummassign;
		
private:
	arrayset<T> *sibling;
	arrayset<T> *child;
	char value;
	bool ismem;
};

template<>
int arrayset<char>::numconstr = 0;
template<>
int arrayset<char>::numdestr = 0;
template<>
int arrayset<char>::numcpy = 0;
template<>
int arrayset<char>::numassign = 0;
template<>
int arrayset<char>::nummove = 0;
template<>
int arrayset<char>::nummassign = 0;

// I'm ignoring that the traits or allocator might be non-default
template<typename charT>
class stringset : public arrayset<charT> {
public:
	typedef std::basic_string<charT> str;

// can remove all of these... they are all the default
/*
	stringset<charT>() : arrayset<charT>() {
	}
	~stringset<charT>() {
	}
	stringset<charT>(const stringset<charT> &s) : arrayset<charT>(s) {
	}
	stringset<charT>(stringset<charT> &&s) : arrayset<charT>(std::move(s)) {
	}
	stringset<charT> &operator=(const stringset<charT> &s) {
		if (this==&s) return *this;
		arrayset<charT>::operator=(s);
		return *this;
	}
	stringset<charT> &operator=(stringset<charT> &&s) {
		if (this==&s) return *this;
		arrayset<charT>::operator=(std::move(s));
		return *this;
	}
*/

	bool ismember(const str &s) const {
		return arrayset<charT>::ismember(s.begin(),s.end());
	}
	bool addmember(const str &s) {
		bool ret = arrayset<charT>::addmember(s.begin(),s.end());
		if (ret) size++;
		return ret;
	}
// NEW:
	void addlist(initializer_list<str> l) {
		for(auto s : l) addmember(s);
	}

	int numwords() const { return size; }

	stringset<charT>() : arrayset<charT>() {
		size = 0;
	}

	stringset<charT>(const vector<str> &v) // build from list
		: stringset<charT>() { // delegate to the other constructor first
			// cannot do anything else in this initialization list
			// (like initialize the base class)
		for(auto && s : v)
			addmember(s);
	}

// NEW initializer list constructor:
	stringset<charT>(std::initializer_list<str> strs)
		: stringset<charT>() { // delegate
		for(auto s : strs) 
			addmember(s);
	}

private:
	//int size = 0;
	int size;
};

stringset<char> loaddictionary(const char *filename) {
	ifstream f(filename);
	if (!f.good()) { // should throw exception...
		// but returning something here prevents RVO in g++
		return stringset<char> ();
	}
	stringset<char> ret;
	while(!f.eof()) {
		string s;
		f >> s;
		if (s.size()>0) ret.addmember(s);
	}
	return ret;
}

int main(int argc, char **argv) {
	{
		stringset<char> 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 << "total of " << s.numwords() << " words" << endl;
	}
	{
		stringset<char> s {"one","two","three","many","none"};
		s.addlist({"five","six","seven"});
		cout << "none? " << s.ismember("none") << endl;
		cout << "five?" << s.ismember("five") << endl;

		cout << "total of " << s.numwords() << " words" << endl;
	}
	cout << "-------------------------" << endl;
	cout << "# constructors: " << arrayset<char>::numconstr << endl;
	cout << "# destructors:  " << arrayset<char>::numdestr << endl;
	cout << "# copies:       " << arrayset<char>::numcpy << endl;
	cout << "# assignments:  " << arrayset<char>::numassign << endl;
	cout << "# moves:        " << arrayset<char>::nummove << endl;
	cout << "# m-assigns:    " << arrayset<char>::nummassign << endl;
	return 0;
}