#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

template <class base, class arg>
class ClassificationTree {
	private:
		typedef ClassificationTree<base,arg> mytype;

		string name;
		vector<mytype> children;
		bool (*accept)(arg);
		base* (*create)(arg);

	public:
		ClassificationTree (const char *n, bool (*ac)(arg), base* (*cr)(arg))
			: name(n),accept(ac),create(cr) {  }

		ClassificationTree () {  }

		void insert (mytype cl) {
			string::size_type idx = cl.name.find ("::");
			// Base class??
			if (idx == string::npos) {
				// Is there already a base??
				if (name.size() != 0) {
					// Can't be two base classes
					throw "Cannot be two base classes";
				} else {
					// Base class
					*this = cl;
				}
			} else {
				// Is this a subclass of this class??
				if (cl.name.substr (0,idx) != name) {
					// Not a subclass of this class, error
					throw "Not a subclass of this class";
				}
				// Strip cl's class name of the first class
				cl.name = cl.name.substr (idx+2);
				// Is there another subclass??
				idx = cl.name.find ("::");
				if (idx == string::npos) {
					// Insert this class as a child
					children.push_back (cl);
					return;
				} else {
					// Find the correct child and insert it there
					typename vector<mytype>::iterator pos;
					for (pos = children.begin(); pos != children.end(); ++pos) {
						if (pos->name == cl.name.substr (0,idx)) {
							pos->insert (cl);
							return;
						}
					}
					// No correct subclass, error
					throw "No correct subclass";
				}
			}
		}

		base* classify (arg a) {
			// Can I accept??
			if (!accept (a))  return 0;
			// Can any of the children accept?
			typename vector<mytype>::iterator pos;
			for (pos = children.begin(); pos != children.end(); ++pos) {
				if (pos->accept(a))  return pos->classify(a);
			}
			// None of the children will work, return an instance of this class
			return create(a);
		}

		void print (int level=0) {
			for (int i=0; i < level; i++)  cout << " ";
			cout << name << endl;

			typename vector<mytype>::iterator pos;
			for (pos = children.begin(); pos != children.end(); ++pos)
				pos->print (level+1);
		}
};

class cl1to10 {
	public:
		virtual char *identify() { return "cl1to10"; }
		static bool accept (int num) {
			if (num >= 1 && num <= 10)
				return true;
			else
				return false;
		}
		static cl1to10* create (int num) {
			if (accept(num)) {
				return new cl1to10(num);
			} else {
				return 0;
			}
		}
		
		cl1to10 (int num=0)
			: number(num) {  }

	protected:
		int number;
};

class cl6to10 : public cl1to10 {
	public:
		virtual char *identify() { return "cl1to10::6to10"; }
		static bool accept (int num) {
			if (num >= 6 && num <= 10)
				return true;
			else
				return false;
		}
		static cl1to10* create (int num) {
			if (accept(num)) {
				return new cl6to10;
			} else {
				return 0;
			}
		}

		cl6to10 (int num=0)
			: cl1to10(num) {  }
};

class cl7 : public cl6to10 {
	public:
		virtual char *identify() { return "cl1to10::6to10::cl7"; }
		static bool accept (int num) {
			if (num == 7)
				return true;
			else
				return false;
		}
		static cl1to10* create (int num) {
			if (accept(num)) {
				return new cl7(num);
			} else {
				return 0;
			}
		}

		cl7 (int num=0)
			: cl6to10(num) {  }
};

class cl9 : public cl6to10 {
	public:
		virtual char *identify() { return "cl1to10::6to10::cl9"; }
		static bool accept (int num) {
			if (num == 9)
				return true;
			else
				return false;
		}
		static cl1to10* create (int num) {
			if (accept(num)) {
				return new cl9(num);
			} else {
				return 0;
			}
		}

		cl9 (int num=0)
			: cl6to10(num) {  }
};

int main () {
	typedef ClassificationTree<cl1to10,int> cltree;
	try {
		cltree ct;
		ct.insert (cltree("cl1to10", cl1to10::accept, cl1to10::create));
		ct.insert (cltree("cl1to10::cl6to10", cl6to10::accept, cl6to10::create));
		ct.insert (cltree("cl1to10::cl6to10::cl7", cl7::accept, cl7::create));
		ct.insert (cltree("cl1to10::cl6to10::cl9", cl9::accept, cl9::create));
		ct.print ();

		for (int i = 1; i <= 11; i++) {
			cl1to10* cl = ct.classify(i);
			cout << i << "\t";
			if (cl) {
				cout << cl->identify();
				delete cl;
			} else  cout << "noclass";
			cout << endl;
		}
	} catch (const char *msg) {
		cout << "Caught exception: " << msg << endl;
	}
}