//Programed by NAS6
//NAS6_tree_clct.h

#pragma once
#ifndef NAS6_RELEASE_BLD
#define NAS6_TREE_CLCT_TEST
#endif

#include <iostream>
#include <sstream>
#include "NAS6_cntn_ptr.h"

namespace NAS6_Utl {

	template<typename T>
	class NAS6_tree_clct : public NAS6_cntn_ptr<T> {
	protected:
		bool m_destructor;
		static string m_dummystr;
		NAS6_tree_clct<T>* m_parent;
		NAS6_cntn_ptr<NAS6_tree_clct<T>*> m_child;
		NAS6_cntn_ptr<string> m_key;

		virtual bool isdestructing() {
			if (m_destructor) return true;
			if (m_parent != nullptr) return m_parent->isdestructing();
			return false;
		}
		virtual NAS6_tree_clct<T>& setparent(NAS6_tree_clct<T>* rh) { m_parent = rh; return (*this); }
		virtual string& getuniquekey(string& rs) {
			if (m_parent == nullptr) {
				rs = "0" + rs;
				return rs;
			}
			int n = childnum();
			stringstream ss;
			ss << n;
			rs = ":" + ss.str() + rs;
			return m_parent->getuniquekey(rs);
		}
		//root以下、delete
		virtual NAS6_tree_clct<T>& recursiveDestroy(NAS6_tree_clct<T>* root) {
			bool parent;
			string s = "";
			if (&root->recursiveInit() == nullptr) return (*root);
			NAS6_tree_clct<T>* crnt = root;
			while (!crnt->recursiveIsEnd(root)) {
				parent = false;
				crnt = &(crnt->recursiveNext(root, parent));

				if (crnt != nullptr) {
					if ((crnt->m_child[crnt->m_child.current() - 1]) != nullptr) {
						s = (crnt->m_child[crnt->m_child.current() - 1])->thiskey();
					}
				}

				if (parent) {
					if ((crnt->m_child[crnt->m_child.current() - 1]) != nullptr) {
						delete (crnt->m_child[crnt->m_child.current() - 1]);
						(crnt->m_child[crnt->m_child.current() - 1]) = nullptr;
#ifdef NAS6_TREE_CLCT_TEST
						cout << "called NAS6_tree_clct::recursiveDestroy Next > " << s << endl;
#endif
					}
				}
			}

			return (*root);
		}
		virtual NAS6_tree_clct<T>& resetkey(NAS6_tree_clct<T>* root, string key = "") {
			bool parent;
			string s = "";
			int n;
			bool b = false;
			n = root->childnum();
			if (n < 0) { if (&root->recursiveInit() == nullptr) return (*root); }
			else { b = true; root = root->m_parent; if (&root->recursiveInit(n) == nullptr) return (*root); }
			NAS6_tree_clct<T>* crnt = root;
			if (!b && crnt != nullptr) {
				n = crnt->childnum();
				if (0 <= n) {
					s = crnt->thiskey();
					int loc = string::npos;
					string tok = " > ";
					string fk = "";
					string ss = "";
					ss = crnt->getuniquekey(ss);
					loc = s.find(tok, 0);
					if (loc != string::npos) {
						fk = s.substr(loc, s.length() - loc);
						ss = ss + fk;
					}
					crnt->m_parent->m_key[n] = ss + " > " + key;
				}
			}
			while (!crnt->recursiveIsEnd(root)) {
				parent = false;
				crnt = &(crnt->recursiveNext(root, parent));

				if (!parent) {
					if (crnt != nullptr) {
						int n = crnt->childnum();
						if (0 <= n) {
							s = crnt->thiskey();
							int loc = string::npos;
							string tok = " > ";
							string fk = "";
							string ss = "";
							ss = crnt->getuniquekey(ss);
							loc = s.find(tok, 0);
							if (loc != string::npos) {
								fk = s.substr(loc, s.length() - loc);
								ss = ss + fk;
							}
							if (b) { b = false; crnt->m_parent->m_key[n] = ss + " > " + key; }
							else crnt->m_parent->m_key[n] = ss;
						}
					}
				}
			}
			return (*root);
		}
	public:
		//コンストラクタ、デストラクタ
		//NAS6_cntn_ptr<T>への設定
		//peeper = true : 覗き見ポインタ
		//delptr = true : 自動メモリ解放
		//len : サイズ
		NAS6_tree_clct(bool peeper = false, bool delptr = true) : NAS6_cntn_ptr<T>(peeper, delptr), m_child(peeper, delptr), m_key(peeper, delptr) {
			m_destructor = false;
			m_parent = nullptr; 
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::constructor" << endl;
#endif
		}
		NAS6_tree_clct(int len, bool delptr = true) : NAS6_cntn_ptr<T>(len, delptr), m_child(false, delptr), m_key(false, delptr) {
			m_destructor = false;
			m_parent = nullptr;
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::constructor" << endl;
#endif
		}
		//コピーコンストラクタはピーパー
		NAS6_tree_clct(NAS6_tree_clct<T>* rh) : NAS6_tree_clct(*rh) { ; }
		NAS6_tree_clct(NAS6_tree_clct<T>& rh) : NAS6_cntn_ptr<T>(rh), m_child(true), m_key(true) { 
			m_destructor = false; 
			tc_peepTo(&rh);
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::copy constructor" << endl;
#endif
		}
		virtual ~NAS6_tree_clct() {
			if (!isdestructing()) {
				int n;
				if (m_parent != nullptr) {
					n = childnum();
					if (n < 0) return;
				}

				string s = thiskey();
				m_destructor = true;
				recursiveDestroy(this);
				if (m_parent != nullptr) {
					m_parent->m_child.remove(n);
					m_parent->m_key.remove(n);
				}

				m_destructor = false;
#ifdef NAS6_TREE_CLCT_TEST
				cout << "called NAS6_tree_clct::destructor > " << s << endl;
#endif
			}
		}

		//祖先かどうか
		virtual bool isancestor(NAS6_tree_clct<T>* rh) {
			if (m_parent != nullptr) {
				if (m_parent->m_ptr == rh->m_ptr) return true;
				return m_parent->isancestor(rh);
			}
			return false;
		}
		//ルート
		virtual NAS6_tree_clct<T>& getroot() { if (m_parent != nullptr) { getroot(); } return (*this); }
		//キー
		virtual NAS6_cntn_ptr<string>& key() { return (m_key); }
		virtual string& key(int rh) { return (m_key[rh]); }
		virtual string& thiskey() { 
			m_dummystr = ""; if (m_parent == nullptr) { m_dummystr = "0 > root"; return m_dummystr; } 
			int n = childnum(); if (n < 0) { m_dummystr = "peeper > root"; return m_dummystr; }
			return (m_parent->m_key[n]);
		}
		//親
		virtual NAS6_tree_clct<T>& parent() { return *(m_parent); }
		//子
		virtual NAS6_cntn_ptr<NAS6_tree_clct<T>*>& child() { return (m_child); }
		virtual NAS6_tree_clct<T>& child(int rh) { return *(m_child[rh]); }
		virtual NAS6_tree_clct<T>*& childptr(int rh) { return (m_child[rh]); }
		//何番目の子か
		virtual int childnum() {
			if (m_parent == nullptr) return -1;
			int i = 0;
			while ((m_parent->m_child[i]) != this) {
				if ((m_parent->m_child[i]) == this) break;
				i++;
				if (i == m_parent->m_child.size()) return -2;
			}
			return i;
		}
		//キーの一致 : 一致したら、キー内の何文字目かを返し、一致しなかったら、string::nposを返す
		virtual int conformkey(NAS6_tree_clct<T>* rh, string fk) {
			int loc = string::npos;
			string s = rh->thiskey();
			loc = s.find(fk, 0);
			return loc;
		}
		//コピー＆リサイズ＆メモリ所有権新規取得 : peeper = true : rhを覗き見ポインタにする : peeper = false : rhをアクセス不可にする
		virtual NAS6_tree_clct<T>& tc_copyFrom(NAS6_tree_clct<T>* rh, bool peeper = true, bool b = true) {
			int ncrnt = 0;
			NAS6_tree_clct<T>* crnt = this;
			NAS6_tree_clct<T>* crntrh = rh;
			if (rh == nullptr) return (*this);
			string srh = ""; srh = rh->thiskey();
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::tc_copyFrom > " << srh << endl;
#endif
			crnt->copyFrom(*crntrh, -1, peeper, !peeper);
			if (!peeper) crntrh->setparent(nullptr);
			if (b) crnt->setparent(nullptr);
			crnt->m_child.copyFrom(crntrh->m_child);
			crnt->m_key.copyFrom(crntrh->m_key, -1, peeper, !peeper);

			if (crntrh->child().size() == ncrnt) { return *(rh->m_parent); }
			while (crntrh->child().size() != ncrnt) {
				ncrnt++;
				NAS6_tree_clct<T>* crnt_c = &(crntrh->child(ncrnt - 1));
				NAS6_tree_clct<T>* crntch = new NAS6_tree_clct<T>();
				crnt->childptr(ncrnt - 1) = crntch;
				crnt->child(ncrnt - 1).setparent(crnt);
				crntch->tc_copyFrom(crnt_c, peeper, false);
			}
			return (*rh);
		}
		//rhを覗き見する
		virtual NAS6_tree_clct<T>& tc_peepTo(NAS6_tree_clct<T>* rh, bool b = true) {
			int ncrnt = 0;
			if (rh == nullptr) return (*this);
			string srh = ""; srh = rh->thiskey();
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::tc_peepTo > " << srh << endl;
#endif
			NAS6_tree_clct<T>* crnt = this;
			NAS6_tree_clct<T>* crntrh = rh;
			crnt->setpeeper(true);
			crnt->m_child.setpeeper(false);
			crnt->m_key.setpeeper(true);
			crnt->NAS6_cntn_ptr<T>::operator=(*crntrh);
			if(b) crnt->setparent(nullptr);
			crnt->m_child.copyFrom(crntrh->m_child);
			crnt->m_key= crntrh->m_key;

			if (crntrh->m_child.size() == ncrnt) { return *(rh->m_parent); }
			while (crntrh->m_child.size() != ncrnt) {
				ncrnt++;
				NAS6_tree_clct<T>* crnt_c = &(crnt->child(ncrnt - 1));
				NAS6_tree_clct<T>* crntch = new NAS6_tree_clct<T>(true);
				crnt->childptr(ncrnt - 1) = crntch;
				crnt->child(ncrnt - 1).setparent(crnt);
				crntch->tc_peepTo(crnt_c, false);
			}
			return (*rh);
		}

		//子生成
		//n : n番目に子を追加生成する : -1 : 一番後ろに追加する
		//resetkey = true : rhのキーのリセット
		virtual NAS6_tree_clct<T>& deliver(string key = "", int n = -1, NAS6_tree_clct<T>* rh = nullptr, bool resetkey = true) {
			bool b = false;
			string s = "";
			string ss = "";
			if (n < 0) n = m_child.size();
			if (rh != nullptr) {
				if (!isancestor(rh)) {
					string srh = ""; srh = rh->thiskey();
					NAS6_tree_clct<T>* rh2 = new NAS6_tree_clct<T>();
					rh2->tc_copyFrom(rh, true);
					rh2->setparent(this);
					m_child.add(n, rh2);
					m_key.add(n, ss);
					int loc = string::npos;
					string tok = " > root";
					loc = srh.find(tok, 0);
					if (loc != string::npos) { srh = srh.substr(0, loc); }
					m_key[n] = srh;
					if (resetkey) m_child[n]->resetkey(m_child[n], key);
					else {
						if (key != "") { m_key[n] = srh + " > " + key; }
						else { m_key[n] = srh; }
					}
				}
				else { b = true; }
			}
			else { b = true; }
			if(b){
				NAS6_tree_clct<T>* t = new NAS6_tree_clct<T>();
				m_child.add(n, t);
				m_child[n]->setparent(this);
				m_key.add(n, ss);
				s = m_child[n]->getuniquekey(s);
				if (key != "") { m_key[n] = s + " > " + key; }
				else { m_key[n] = s; }
			}
			m_child.at(n);
#ifdef NAS6_TREE_CLCT_TEST
			cout << "called NAS6_tree_clct::deliver" << endl;
#endif
			return *(*m_child);
		}

		//再帰全検索
		virtual NAS6_tree_clct<T>&  recursiveInit(int rh = 0) {
			int crnt = 0;
			m_child.at(rh);
			if (m_child.size() == crnt) { return (*m_parent); }
			while (m_child.size() != crnt) {
				crnt++;
				((m_child[crnt - 1])->recursiveInit());
			}
			return (*this);
		}
		virtual bool recursiveIsEnd(NAS6_tree_clct<T>* root) {
			return (root == this && m_child.size() == m_child.current());
		}
		virtual NAS6_tree_clct<T>& recursiveNext(NAS6_tree_clct<T>* root, bool& parent) {
			if (recursiveIsEnd(root)) { return (*root); }
			if (m_child.size() == m_child.current()) { parent = true; m_child.begin(); return (*m_parent); }
			m_child++;
			return (*(m_child[m_child.current() - 1]));
		}
		//キー検索
		virtual NAS6_tree_clct<T>& recursiveKeyNext(NAS6_tree_clct<T>* root, const string fk, bool& parent) {
			string s = "";
			if (recursiveIsEnd(root)) { return (*root); }
			if (m_child.size() == m_child.current()) { parent = true; m_child.begin(); return m_parent->recursiveKeyNext(root, fk, parent); }
			parent = false;
			m_child++;
			NAS6_tree_clct<T>* crnt = (m_child[m_child.current() - 1]);
			while (!crnt->recursiveIsEnd(root)) {
				if (crnt->conformkey(crnt, fk) != string::npos) {
					return *crnt;
				}
				if (crnt->m_child.size() == crnt->m_child.current()) { parent = true; crnt->m_child.begin(); return crnt->m_parent->recursiveKeyNext(root, fk, parent); }
				parent = false;
				crnt = &(crnt->recursiveNext(root, parent));
			}
			return (*root);
		}

		//演算子にゃむにゃむ
		virtual NAS6_tree_clct<T>& operator =(NAS6_tree_clct<T>& rh) {	
//使わない
//			NAS6_cntn_ptr<T>::operator=(rh);
//			m_parent = rh.m_parent;
//			m_child = rh.m_child;
//			m_key = rh.m_key;
//			m_destructor = rh.m_destructor;
			return *this;
		}
	};
	//ダミー実体
	template<typename T>
	string NAS6_tree_clct<T>::m_dummystr;

/*///

	//再帰構文例1
	template<typename T>
	void recHoge1(NAS6_tree_clct<T>* root, string fk) {
		bool parent = false;
		if (&root->recursiveInit() == nullptr) return;
		NAS6_tree_clct<T>* crnt = root;
		//crnt = root; の時のcrntに適用の処理
		//or : //if (crnt->conformkey(crnt, fk) != string::npos) //{...} //キー検索の時
		while (!crnt->recursiveIsEnd(root)) {
			parent = false;
			crnt = &(crnt->recursiveNext(root), parent);
			//or : //crnt = &(crnt->recursiveKeyNext(root, fk, parent));
			//if(!parent) //{...} //crnt = Next; の時のcrntに適用の処理
			//else //{...} //親に戻った時の処理
		}
	}

	//再帰構文例2
	{	//other scope
		bool b = false;
		recHoge2(&tree_c, b);	//call
	}
	template<typename T>
	NAS6_tree_clct<T>& recHoge2(NAS6_tree_clct<T>* rh, bool& parent) {
		int ncrnt = 0;
		// rhに適用の処理 // if(!parent){...}else{...}
		if (rh->child().size() == ncrnt) { parent = true; return (rh->parent()); }
		while (rh->child().size() != ncrnt) {
			ncrnt++;
			parent = false;
			recHoge2(&(rh->child(ncrnt - 1)), parent);
		}
		return (*rh);
	}

//*///
}