Part 1 of Template Data-structure Tutorial (Part2 Available)

[NickCullen]

Hey guys,
Made a tutorial detailing template data structures aimed at intermediate programmers. Part 1 explains template classes, set up and adding and removing nodes from a template list. Part 2 (when complete) will walk-through iterating over elements on the template list.

You can find it here:
http://blog.nickcullen.net/2015/01/template-list-datastructure-part-1.html

EDIT: Part 2 complete:
http://blog.nickcullen.net/2015/01/template-list-datastructure-part-2.html

[prestokeys]

I too like this topic very much. I wrote a similar data structure Menu<T>. The options in the menu can themselves be a Menu<T> (i.e. a submenu), and there is no limit to the number of nested submenus. The real task for me was to write a deep copy of the Menu<T>, e.g. needed when a Menu<T> is created by an assignment of another Menu<T> and the original one later gets deleted. The tricky part for me was to ensure that all the nested submenus (no matter how deeply nested) were also deep copied. Here is my (simplified) code, for anyone who is interested.

[prestokeys]

#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <memory>
#define show(variable) std::cout << #variable << " = " << variable << std::endl;

const int NOT_FOUND = -1, END_OF_MENU = -1;
const std::string EMPTY = "", NEW = "  ";

template <typename T> 
inline std::string toString (const T& t) {
    std::ostringstream os;
    os << t;
    return os.str();
}

template <typename T = int>
inline T ReadType (const std::string& prompt = EMPTY) {
    T n;
	while ( (std::cout << prompt) && !(std::cin >> n) ) {
        std::cout << "You must enter an integer." << std::endl;
        std::cin.clear();
        std::cin.ignore (1000, '\n');
	}
	return n;
}

template <typename T>
class Menu {
	private:
		class Option {
			private:
				const std::string name;
				const T item;
				Menu* submenu;
				Option* next;
				friend class Menu<T>;
				Option (const std::string& itemName, const T& t, Menu<T>* menu = nullptr) : name(itemName), item(t), submenu(menu), next(nullptr) {}
				~Option() {if (submenu) delete submenu;}  // Delete only if submenu != nullptr, else there may be double deletion crashes.
				inline T choose() const;
				inline void print (int n) const;
		};
		Option* first = nullptr;  // first option in the menu
		Menu<T>* parent = nullptr;
		Option* parentOption = nullptr;  // If this menu is a submenu, parentOption is the Option* whose 'submenu' data member is 'this'.
		enum ChoosingType {Normal, Remove};
	public:
		Menu() = default;
		Menu (const Menu<T>&);
		Menu& operator = (const Menu<T>&);
		~Menu();
		inline void insert (const std::string& itemName, const T& t, Menu<T>* submenu = nullptr, int pos = END_OF_MENU);  
		T choose() const {return chosenItem().first;}
		inline int print() const;
	private:
		inline std::pair<T, int> chosenItem (ChoosingType = Normal) const;
		inline Option* deepCopy (const Option*);
};

template <typename T>
Menu<T>::~Menu() {
	std::cout << "Menu<T> destructor called\n";
	if (!first) return;  // Important.  Otherwise the menu may be destroyed twice, causing a crash.
	Menu::Option *current, *next;
	for (current = first;  current;  current = next) {
		next = current->next;
		delete current;
	}
	first = nullptr;  // Necessary to prevent a menu from being destroyed twice.
	if (parentOption)
		parentOption->submenu = nullptr;  // Must set parentOption->submenu to nullptr so that this submenu is not deleted twice, causing a crash.
}

template <typename T>
inline void Menu<T>::Option::print (int n) const {
	if (!submenu)
		std::cout << std::left << toString (n) + ". " + name;
	else
		std::cout << toString (n) + ". " + name << "-> (submenu)";
	std::cout << std::endl;
} 

template <typename T>
inline T Menu<T>::Option::choose() const {
	if (!submenu)
		return item;
	std::cout << std::endl << "Submenu entered." << std::endl;
	return submenu->choose();
}

template <typename T>
inline void Menu<T>::insert (const std::string& itemName, const T& t, Menu<T>* submenu, int pos) {  // submenu = nullptr, pos = END_OF_MENU = -1 by default (pos = 0 is the first position)
	Menu::Option *newOption = new Menu::Option (itemName, t, submenu);
	if (submenu) submenu->parentOption = newOption;
	Menu::Option *current, *prev = nullptr;
	int currentPosition = 0;
	for (current = first;  current && currentPosition++ != pos;  current = current->next)
		prev = current;
	if (!prev) {
		newOption->next = first;
		first = newOption;
	}
	else {
		newOption->next = current;
		prev->next = newOption;
	}
}

template <typename T>
inline std::pair<T, int> Menu<T>::chosenItem (ChoosingType) const {
	int n, choiceNumber;
	Menu::Option *current = first;
	while (true) {
		n = print();
		choiceNumber = ReadType();
		if (choiceNumber >= 1 && choiceNumber <= n)
			break;
		std::cout << std::endl << "You must choose from the above list of choices." << std::endl;
	}
	n = 1;  // we start at n=1 now because the menu numbers begin with 1, so 1 is the first possible value of choice
	for (current = first;  (n != choiceNumber) && current;  current = current->next)  // move to the chosen option
		++n;
	const T choice = current->choose();  // choose the option
	return std::make_pair(choice, n);
}

template <typename T>
inline int Menu<T>::print() const {
	int n = 0;
	Menu::Option *current = first;
	for (current = first;  current;  current = current->next)
		current->print (++n);
	return n;
}

template <typename T>
Menu<T>::Menu (const Menu<T>& other) {  // Copy constructor.
	std::cout << "Menu<T> copy constructor called." << std::endl;
	if (!other.first)  // This check is needed (tested).
		first = nullptr;
	else
		first = deepCopy (other.first);
}

template <typename T>
Menu<T>& Menu<T>::operator = (const Menu<T>& other) {  // Assignment operator.
	std::cout << "Menu<T> assignment operator called." << std::endl;
	if (this == &other)
		return *this;
	if (!other.first)  // This check is needed (tested).
		first = nullptr;
	else
		first = deepCopy (other.first);
	return *this;	
}

template <typename T>
inline typename Menu<T>::Option* Menu<T>::deepCopy (const typename Menu<T>::Option* other) {
	Option* clone = new Option(*other);  // clone is a new Option that has all the values of 'other', but its 'next' pointer is unfortunately the same address as other's next.  This must be corrected.
	Option* corrector = clone;
	const auto createClonedSubmenu = [this](Option* o, Menu<T>* submenuFound) {
		o->submenu = new Menu<T>;
		o->submenu->parentOption = o;	
		if (submenuFound->first)
			o->submenu->first = deepCopy (submenuFound->first);		
	};
	if (clone->submenu)
		createClonedSubmenu (corrector, clone->submenu);
	for (Option* current = clone->next;  current;  current = current->next) {
		corrector->next = new Option(*current);
		if (current->submenu)
			createClonedSubmenu (corrector->next, current->submenu);
		corrector = corrector->next;
	}
	corrector = nullptr;
	return clone;
}

int main() {
	{
		Menu<int> newMenu;
		{
			Menu<int> menu, submenu, subsubmenu1, subsubmenu2, subsubsubmenu;
			menu.insert("ChoiceA", 1);  menu.insert("ChoiceB", 2);  menu.insert("ChoiceC", 3);
			submenu.insert("ChoiceD", 4);
			subsubmenu1.insert("ChoiceG", 7);  subsubmenu1.insert("ChoiceH", 8);  subsubmenu1.insert("ChoiceI", 9);
			submenu.insert ("SubSubmenu1", NOT_FOUND, &subsubmenu1);		
			submenu.insert("ChoiceE", 5);  submenu.insert("ChoiceF", 6);
			subsubsubmenu.insert("ChoiceM", 13);  subsubsubmenu.insert("ChoiceN", 14);  subsubsubmenu.insert("ChoiceO", 15);
			subsubmenu2.insert("ChoiceJ", 10);  subsubmenu2.insert("ChoiceK", 11);  subsubmenu2.insert("ChoiceL", 12);
			subsubmenu2.insert("SubSubSubmenu", NOT_FOUND, &subsubsubmenu);
			submenu.insert ("SubSubmenu2", NOT_FOUND, &subsubmenu2);
			menu.insert ("Submenu", NOT_FOUND, &submenu);
			newMenu = menu;  // Calls assignment operator.
		}   // menu, submenu, subsubmenu1, subsubmenu2, subsubsubmenu are all destroyed at this point, but thanks to the deep copying, there is no crash in the upcoming lines.
		const int choice = newMenu.choose();
		std::cout << "You chose choice #" << choice << ".\n\n\n";
		
		Menu<int>* temp = new Menu<int>;  *temp = newMenu;
		Menu<int> menuFromCopyConstructor = *temp;  // Calls copy constructor.
		delete temp;
		const int choice2 = menuFromCopyConstructor.choose();  // This still works fine even though 'temp' has been deleted, thanks to the deep copying.
		
		std::cout << "You chose choice #" << choice2 << ".\n";
	}
	std::cout << "End of test." << std::endl;
	std::cin.get();  std::cin.get();
}

[NickCullen]

Yeah template programming is quite cool :) And that is a nice example! I can see some uses of that system in the game engine I am building!

Also, thanks for the comment!

[prestokeys]

Even more cool is data structures with variadic templates. But it is extremely tough! For example, my Menu<T> class above does not support submenus whose items are of a different type than T. This extra feature would be very handy, if say, the main menu had Action as the type for its options, and then one of the options is "Take out weapon", whose submenu would ideally like to have Weapon as its options, but as it is right now, the submenu would again have to have Action as its options.

I'm currently working on this below to get the above desired features, but it is extremely tough and I might have to hire JLBorges to help me with this project:

template <typename T, typename U, typename... Rest>
class Menu {  // Menu with T as its option types.
	private:
		class Option {
			private:
				const std::string name;
				const T item;
				Menu<U, Rest...>* submenu;  // Submenu with U as its option types.
				Option* next = nullptr;
				friend class Menu<T, U, Rest...>;
				Option (const std::string& itemName, const T& t, Menu<U, Rest...>* menu = nullptr) : name(itemName), item(t), submenu(menu) {}
				~Option() {if (submenu) delete submenu;}
				inline T choose() const;
				inline void print (int n) const;
		};
		Option* first = nullptr;  // first option in the menu
//		template <typename P> Menu<P, U, Rest...>* parent = nullptr;  // This I have to think about.
		Option* parentOption = nullptr;  // If this menu is a submenu, parentOption is the Option* whose 'submenu' data member is 'this'.
		std::list<Menu<U, Rest...>*> submenus;
		static const int PAUSE_TO_LOOK_UP_INFO = 0;
		static const int GO_BACK = -1;
		enum ChoosingType {Normal, Remove};
	public:
		Menu() = default;
		Menu (const Menu<U, Rest...>&);
		Menu& operator = (const Menu<U, Rest...>&);
		Menu (Menu<U, Rest...>&&);
		Menu& operator = (Menu<U, Rest...>&&);
		~Menu();
		struct RemoveByValue {};
		inline void insert (const std::string& itemName, const T& t, Menu<U, Rest...>* submenu = nullptr, int pos = END_OF_MENU);  
		T choose() const {return this->chosenItem().first;}
		inline T chooseAndRemove();
		inline void deleteItem (int pos = END_OF_MENU);
		inline void deleteItem (const T&, RemoveByValue);
		inline void deleteItem (Menu<U, Rest...>* emptySubmenu);
		template <typename Container> inline void deleteAllItemsExcept (const Container&);
		inline int print() const;
		inline int numOptions() const;
		inline int numSubmenus() const;
		bool empty() const {return first == nullptr;}
		template <typename Container> Container convertToSTLContainer() const;
		T firstItem() const {return first->item;}
	private:
		inline std::pair<T, int> chosenItem (ChoosingType = Normal) const;
		void addToSubmenus (Menu<U, Rest...>* submenu) {submenus.emplace_back(submenu);}
//		void setParent (Menu<?...>* parentMenu) {parent = parentMenu;}  // A tough one!
		void removeSubmenu (Menu<U, Rest...>* submenu) {submenus.remove(submenu);  submenu->parentOption = nullptr;}
		inline Option* deepCopy (const Option*);
};

The problem with the above design is that

int main() {
	Menu<int, std::string> menu;
}

whereby I'm trying to create a simple menu of int options with submenus of string options, won't even compile because then the submenus are of type Menu<std::string> which does not match the class template. It also doesn't make sense because Menu<int, std::string> is to return int from its choose() function, but going into its submenu will then return a string. boost::variant or boost::any needed here? I would really like to see a tutorial on how to design a data structure of this nature.

[NickCullen]

Hmm that does sound interesting yet quite complex! I'm a game programmer myself with a full time job so I don't have much time on my hands to research personal projects in my spare time. But that is interesting, I'll have a dig around as much as I can and see if I can come up with a solution!

Btw I just uploaded part 2 of the tutorial :)

http://blog.nickcullen.net/2015/01/template-list-datastructure-part-2.html