Tree.hpp V2.2
Q: 为什么更这么慢啊？
A: 不到啊
不管了，反正能用
（其实std::Tree用不了）
把Tree_node修了一下，自己试试
// HEADER:Tree.hpp
/**
* A header to implement hierarchical structure.
* It gives the implement of both the node and the whole structure.
*/
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <exception>
#include <algorithm>
#include <iterator>
#include <initializer_list>
#include <memory>
#include <queue>
#include <unordered_set>
#include <bits/c++config.h>
#include <bits/stl_pair.h>
#include <stack>
// #include <functional>
#include <iostream>
namespace std
{
#define __tree_version__ 2.2
template <typename _Tp, typename _Skidtp = void>
class tree_node
{
static_assert(is_same<remove_cv<_Tp>, _Tp>::value, "_Tp must be a non-const, non-volatile type!");
private:
tree_node() = default;
};
template <typename _Tp>
class tree_node<_Tp, void>
{
public:
typedef size_t size_type;
typedef _Tp value_type;
typedef tree_node<value_type, void> self_type;
typedef self_type *self_ptr;
private:
self_ptr par;
value_type val;
string id;
protected:
tree_node(self_ptr par = nullptr, value_type val = value_type(), string id = "")
: par(par == nullptr ? this : par), val(val), id(id)
{
if (!is_root_node())
par->insert_kid(par->kid_amount(), this);
}
tree_node(const tree_node &t_n)
: par(t_n.is_root_node() ? this : t_n.get_par()), val(t_n.get_val()), id(t_n.get_id())
{
if (!is_root_node())
par->insert_kid(par->kid_amount(), this);
}
virtual ~tree_node() = default;
string &id_reference()
{
return id;
}
value_type &val_reference()
{
return val;
}
self_ptr &par_reference()
{
return par;
}
virtual void set_kid_without_result(vector<self_ptr> kid_list) = 0;
public:
string get_id()
{
return id;
}
value_type get_val()
{
return val;
}
self_ptr get_par()
{
return par;
}
string set_id(string id)
{
return this->id = id;
}
value_type set_val(value_type val)
{
return this->val = val;
}
self_ptr set_par(self_ptr par)
{
return this->par = par;
}
virtual vector<self_ptr> get_kid_as_vector() = 0;
virtual list<self_ptr> get_kid_as_list()
{
vector<self_ptr> kid_vec = get_kid_as_vector();
return list<self_ptr>(kid_vec.begin(), kid_vec.end());
}
virtual deque<self_ptr> get_kid_as_deque()
{
vector<self_ptr> kid_vec = get_kid_as_vector();
return deque<self_ptr>(kid_vec.begin(), kid_vec.end());
}
#define throw_oor_with_two(n, size) \
throw out_of_range( \
string("std::tree_node::set_kid_list: n (which is ") \
.append(to_string(n)) \
.append(") >= kid_list.size() (which is ") \
.append(to_string(size)) \
.append(")"))
#define throw_oor_with_three(fir, n, size) \
throw out_of_range( \
string("std::tree_node::set_kid_list: fir (which is ") \
.append(to_string(fir)) \
.append(") + n (which is ") \
.append(to_string(n)) \
.append(") >= kid_list.size() (which is ") \
.append(to_string(size)) \
.append(")"))
virtual vector<self_ptr> set_kid_list(vector<self_ptr> kid_list)
{
set_kid_without_result(kid_list);
return get_kid_as_vector();
}
virtual vector<self_ptr> set_kid_list(vector<self_ptr> kid_list, size_type n)
{
if (n >= kid_list.size())
throw_oor_with_two(n, kid_list.size());
return set_kid_list(vector<self_ptr>(kid_list.begin(), kid_list.begin() + n));
}
virtual vector<self_ptr> set_kid_list(vector<self_ptr> kid_list, size_type fir, size_type n)
{
if (fir + n >= kid_list.size())
throw_oor_with_three(fir, n, kid_list.size());
return set_kid_list(vector<self_ptr>(kid_list.begin() + fir, kid_list.begin() + fir + n));
}
virtual list<self_ptr> set_kid_list(list<self_ptr> kid_list)
{
set_kid_without_result(vector<self_ptr>(kid_list.begin(), kid_list.end()));
return get_kid_as_list();
}
virtual list<self_ptr> set_kid_list(list<self_ptr> kid_list, size_type n)
{
if (n >= kid_list.size())
throw_oor_with_two(n, kid_list.size());
return set_kid_list(list<self_ptr>(kid_list.begin(), kid_list.begin() + n));
}
virtual list<self_ptr> set_kid_list(list<self_ptr> kid_list, size_type fir, size_type n)
{
if (fir + n >= kid_list.size())
throw_oor_with_three(fir, n, kid_list.size());
return set_kid_list(list<self_ptr>(kid_list.begin() + fir, kid_list.begin() + fir + n));
}
virtual deque<self_ptr> set_kid_list(deque<self_ptr> kid_list)
{
set_kid_list(vector<self_ptr>(kid_list.begin(), kid_list.end()));
return get_kid_as_deque();
}
virtual deque<self_ptr> set_kid_list(deque<self_ptr> kid_list, size_type n)
{
if (n >= kid_list.size())
throw_oor_with_two(n, kid_list.size());
return set_kid_list(deque<self_ptr>(kid_list.begin(), kid_list.begin() + n));
}
virtual deque<self_ptr> set_kid_list(deque<self_ptr> kid_list, size_type fir, size_type n)
{
if (fir + n >= kid_list.size())
throw_oor_with_three(fir, n, kid_list.size());
return set_kid_list(deque<self_ptr>(kid_list.begin() + fir, kid_list.begin() + fir + n));
}
#undef throw_oof_with_two
#undef throw_oof_with_three
virtual size_type kid_amount() = 0;
virtual self_ptr insert_kid(size_type pos, initializer_list<self_ptr> init_list)
{
return insert_kid(pos, vector<self_ptr>(init_list));
}
virtual self_ptr insert_kid(size_type pos, self_ptr kid_ptr)
{
return insert_kid(pos, vector<self_ptr>(1, kid_ptr));
}
virtual self_ptr insert_kid(size_type pos, vector<self_ptr> kid_list) = 0;
virtual self_ptr insert_kid(size_type pos, list<self_ptr> kid_list)
{
return insert_kid(pos, vector<self_ptr>(kid_list.begin(), kid_list.end()));
}
virtual self_ptr insert_kid(size_type pos, deque<self_ptr> kid_list)
{
return insert_kid(pos, vector<self_ptr>(kid_list.begin(), kid_list.end()));
}
virtual void erase_kid(size_type pos) = 0;
virtual void erase_kid(size_type first, size_type last)
{
for (; first < last; first++)
erase_kid(first);
}
virtual self_ptr &get_kid(size_type pos) = 0;
virtual size_type find_kid(self_ptr kid_ptr) = 0;
virtual void set_to_leaf() = 0;
void set_to_root()
{
par = this;
}
virtual bool is_leaf_node() = 0;
bool is_root_node()
{
return par == this;
}
virtual bool kid_is_invalid() = 0;
bool par_is_invalid()
{
return par == nullptr;
}
virtual bool is_usable()
{
return !(par_is_invalid() && kid_is_invalid());
}
void repair_par()
{
if (par_is_invalid())
par = this;
}
virtual void repair_kid() = 0;
virtual bool repair()
{
repair_par();
repair_kid();
return is_usable();
}
};
template <typename _Tp>
using tree_node_base = tree_node<_Tp, void>;
template <typename _Tp>
using vectree_node_Skidtp = vector<tree_node_base<_Tp> *>;
template <typename _Tp>
class tree_node<_Tp, vectree_node_Skidtp<_Tp>> : public tree_node_base<_Tp>
{
public:
typedef _Tp value_type;
typedef tree_node<value_type, vectree_node_Skidtp<value_type>> self_type;
typedef tree_node_base<value_type> base_type;
typedef typename base_type::size_type size_type;
typedef typename base_type::self_ptr node_ptr;
typedef vector<node_ptr> store_kid_type;
private:
store_kid_type kid;
node_ptr &par = (node_ptr &)base_type::par_reference();
protected:
void set_kid_without_result(store_kid_type kid_list)
{
kid = kid_list;
}
public:
tree_node() : base_type(), kid(store_kid_type(1, this)) {}
tree_node(const tree_node &t_n) : base_type(t_n), kid(store_kid_type(1, this)) {}
tree_node(node_ptr par, value_type val = value_type(), string id = "", store_kid_type kid_list = {},
bool change_kid_par = false)
: base_type(par, val, id), kid(!change_kid_par || kid_list.empty() ? store_kid_type(1, this) : kid_list)
{
if (change_kid_par && !is_leaf_node())
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
{
if (!(*it)->is_root_node())
((node_ptr)(*it)->get_par())->erase_kid(*it);
(*it)->set_par(this);
}
}
tree_node(const base_type &t_n, bool change_kid_par)
: base_type(t_n), kid(!change_kid_par || t_n.is_leaf_node() ? store_kid_type(1, this) : t_n.get_kid_as_vector())
{
if (change_kid_par && !is_leaf_node())
{
t_n.set_to_leaf();
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(this);
}
}
~tree_node()
{
bool is_not_root = !is_root_node(), is_not_leaf = !is_leaf_node();
if (is_not_root)
{
par->erase_kid(par->find_kid(this));
if (is_not_leaf)
par->insert_kid(par->kid_amount(), kid);
}
if (is_not_leaf)
if (is_not_root)
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(par);
else
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_to_root();
cout << '!';
}
vector<node_ptr> get_kid_as_vector()
{
return kid;
}
node_ptr &get_kid(size_type pos)
{
return kid.at(pos);
}
node_ptr front()
{
return kid.front();
}
node_ptr back()
{
return kid.back();
}
template <typename... _Args>
void kid_emplace_back(_Args &&...args)
{
kid.emplace_back(forward<_Args>(args)...);
}
void kid_push_back(node_ptr kid_ptr)
{
if (kid_ptr == nullptr || kid_ptr == this)
return;
kid.push_back(kid_ptr);
}
template <typename... _Args>
size_type kid_emplace(size_type pos, _Args &&...args)
{
return kid.emplace(kid.begin() + pos, forward<_Args>(args)...) - kid.begin();
}
node_ptr insert_kid(size_type pos, initializer_list<node_ptr> init_list)
{
return *kid.insert(kid.begin() + pos, init_list);
}
template <typename _InputIterator>
node_ptr insert_kid(size_type pos, _InputIterator first, _InputIterator last)
{
return *kid.insert(kid.begin() + pos, first, last);
}
node_ptr insert_kid(size_type pos, store_kid_type kid_list)
{
return *kid.insert(kid.begin() + pos, kid_list.begin(), kid_list.end());
}
node_ptr insert_kid(size_type pos, node_ptr kid_ptr)
{
return *kid.insert(kid.begin() + pos, kid_ptr);
}
node_ptr insert_kid(size_type pos, list<node_ptr> kid_list)
{
return *kid.insert(kid.begin() + pos, kid_list.begin(), kid_list.end());
}
node_ptr insert_kid(size_type pos, deque<node_ptr> kid_list)
{
return *kid.insert(kid.begin() + pos, kid_list.begin(), kid_list.end());
}
void erase_kid(size_type pos)
{
kid.erase(kid.begin() + pos);
}
void erase_kid(size_type first, size_type last)
{
kid.erase(kid.begin() + first, kid.begin() + last);
}
void erase_kid(node_ptr nptr)
{
kid.erase(find(kid.begin(), kid.end(), nptr));
}
void kid_pop_back()
{
kid.pop_back();
}
size_type kid_list_capacity()
{
return kid.capacity;
}
size_type kid_list_max_size()
{
return kid.max_size();
}
void reserve_kid_list(size_type n)
{
kid.reserve(n);
}
void resize_kid_list(size_type new_size)
{
kid.resize(new_size);
}
void shrink_kid_list()
{
return kid.shrink_to_fit();
}
void reverse_kid_list()
{
reverse(kid.begin(), kid.end());
}
size_type find_kid(node_ptr kid_ptr)
{
return find(kid.begin(), kid.end(), kid_ptr) - kid.begin();
}
void swap_kid(size_type a_pos, size_type b_pos)
{
swap(kid.at(a_pos), kid.at(b_pos));
}
size_type kid_amount()
{
return kid.size();
}
bool no_kid()
{
return kid.empty();
}
bool single_kid()
{
return kid.size() == 1;
}
bool multiple_kid()
{
return kid.size() > 1;
}
using base_type::set_to_root;
void set_to_leaf()
{
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(*it);
kid.assign(1, this);
}
using base_type::is_root_node;
bool is_leaf_node()
{
return kid.front() == this;
}
using base_type::par_is_invalid;
bool kid_is_invalid()
{
return kid.empty() ||
find(kid.begin(), kid.end(), nullptr) != kid.end() ||
kid.size() > 1 && find(kid.begin(), kid.end(), this) != kid.end();
}
bool is_usable()
{
return !(par_is_invalid() && kid_is_invalid());
}
using base_type::repair_par;
void repair_kid()
{
if (kid_is_invalid())
if (kid.size() <= 1)
kid.assign(1, this);
else
{
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
while (it != kid.end() && *it == nullptr || *it == this)
kid.erase(it);
}
}
bool repair()
{
repair_par();
repair_kid();
return is_usable();
}
};
template <typename _Tp>
using vectree_node = tree_node<_Tp, vectree_node_Skidtp<_Tp>>;
template <typename>
struct __is_vaild_tree_node_type_helper : public false_type
{
};
template <typename _Tp>
struct __is_vaild_tree_node_type_helper<vectree_node<_Tp>> : public true_type
{
};
template <typename _Tp>
struct is_vaild_tree_node_type : public __is_vaild_tree_node_type_helper<typename remove_cv<_Tp>::type>::type
{
};
/**
* @brief A container which implements hierarchical structure, which shaped like an inverted tree.
*
* @tparam _Tp Type of the value in a %tree_node.
* @tparam _NodeTp A type of the nodes, defaults to vectree_node<_Tp>.
* @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
*/
template <typename _Tp,
typename _NodeTp = vectree_node<_Tp>,
// typename _Hash = hash<_Tp>,
// typename _Pred = equal_to<_Tp>,
typename _Alloc = allocator<_NodeTp>>
class tree
{
static_assert(is_vaild_tree_node_type<_NodeTp>::value, "_NodeTp is invaild!");
static_assert(is_same<remove_cv<_NodeTp>, _NodeTp>::value, "_NodeTp must be a non-const, non-volatile type!");
public:
typedef _Tp value_type;
typedef _NodeTp node_type;
typedef size_t size_type;
typedef typename node_type::store_kid_type node_kid_type;
typedef vector<pair<node_type *, size_type>> store_dynamic_type;
/**
* An enum which represents the order of traveling a %tree
*/
enum tree_sequence
{
preorder,
inorder,
postorder,
levorder,
rpreorder,
rinorder,
rpostorder,
rlevorder
};
private:
node_type *rot;
size_type nodeAmount;
bool has_insert;
_Alloc alloc;
store_dynamic_type dynamicT_n;
public:
/**
* @brief Creates a %tree with a root node.
* @param val The value of the root node.
* @param kid A %vector of pointers to kid nodes of the root node.
* @param id The id of the root node.
*
* This constructor constructs a root node by given @a val or default value of @a value_type,
* @a par or a pointer to root node itself, @a kid or no kids and @a id or default id: "0:root",
* and creates a %tree with the constructed root node.
*/
tree(value_type val = value_type(), node_type *par = nullptr, node_kid_type kid = {}, string id = "0:root")
: rot(alloc.allocate(1)), nodeAmount(1), has_insert(false)
{
dynamicT_n.push_back({rot, 1});
alloc.construct(rot, par, kid, val, id);
}
tree(node_type *t_n, node_type ¤t) : rot(t_n), nodeAmount(1)
{
*rot = current;
}
/**
* @brief Creates a %tree with a given root node.
* @param t_n A pointer to a tree node.
* @param kid A %vector of pointers to kid nodes of the root node.
* @param id The id of the root node.
*
* This constructor assign @a kid and @a id to the given tree node @a t_n,
* and set @a t_n to the root node a %tree
*/
tree(node_type *t_n, node_kid_type kid, string id) : rot(t_n), nodeAmount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_id(id);
}
tree(node_type *t_n, value_type val, node_kid_type kid, string id)
: rot(t_n), nodeAmount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_id(id);
}
/**
* @brief A destructor.
*
* The destructor only erases the elements,
* and if the elements themselves are pointers, the pointed-to memory is not touched in any way.
* Managing the pointer is the user's responsibility.
*/
~tree()
{
for (typename store_dynamic_type::iterator it = dynamicT_n.begin(); !dynamicT_n.empty(); it = dynamicT_n.begin())
{
alloc.destroy(it->first);
alloc.deallocate(it->first, it->second);
dynamicT_n.erase(it);
}
dynamicT_n.clear();
}
/**
* @brief Return a pointer to the root node of a %tree.
* @return A pointer to the root node of a %tree.
*
* This function returns a pointer to the root of a %tree.
*/
node_type *get_root()
{
return rot;
}
/**
* @brief Return the number of elements in a %tree.
* @return An interger giving the number of elements in a %tree.
*
* This function returns the number of elements in a %tree.
*/
size_type size()
{
// if (has_insert)
// {
// queue<node_type *> search_que;
// unordered_set<node_type *> node_store(nodeAmount);
// nodeAmount = 1;
// search_que.push(rot);
// node_store.insert(rot);
// while (!search_que.empty())
// {
// search_que.front()->repair_kid();
// node_kid_type kid_list = search_que.front()->get_kid_list();
// search_que.pop();
// newAmount += kid_list.size();
// for (typename node_kid_type::iterator it = kid_list.begin(); it != kid_list.end(); it++)
// {
// if (node_store.find(*it) != end())
// throw runtime_error("Become a graph!");
// search_que.push(*it);
// node_store.insert(*it);
// }
// }
// }
// return nodeAmount;
}
/**
* @brief Get a pointer to a %tree_node in a %tree.
* @param dep The depth of a %tree_node which is wanted to find.
* @param ord The sequence number of a %tree_node which is wanted to find.
* @return A pointer to a %tree_node or nullptr if not find.
*
* This function tries to get the %tree_node at the designated position.
* If successful it returns a pointer to the %tree_node.
* If unsuccessful it returns nullptr.
*/
node_type *at(size_type dep, size_type ord)
{
queue<node_type *> que;
que.push(rot);
while (dep-- > 0)
{
size_type i = que.size();
while (que.size() - i <= ord && i > 0)
{
node_kid_type kid = que.front()->get_kid_list();
que.pop();
i--;
for (typename node_kid_type::iterator it = kid.begin(); it < kid.end() && que.size() - i <= ord; it++)
if (dep == 0 || !(*it)->is_leaf_node())
que.push(*it);
}
while (i-- > 0)
que.pop();
if (que.size() == 0)
return nullptr;
}
return que.size() <= ord ? nullptr : que.back();
}
typename node_kid_type::iterator insert_kid(node_type *par, node_type *t_n, size_type index = 0xffffffffffffffffULL)
{
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
parKid.insert(index == 0xffffffffffffffffULL ? parKid.end() : parKid.begin() + index, t_n);
return index == 0xffffffffffffffffULL ? --parKid.end() : parKid.begin() + index;
}
node_type *emplace_kid(node_type *par, value_type val = value_type(), node_kid_type kid = {}, string code = "",
size_type index = 0xffffffffffffffffULL)
{
// If index > the size of the kid list of the parent node return nullptr
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (index != 0xffffffffffffffffULL && index > parKid.size())
return nullptr;
// Check if the parent node is also the leave node.
if (par->is_leaf_node())
parKid.clear();
// Try to allocate a new tree node.
node_type *ptr = alloc.allocate(1);
// If unsuccessful return nullptr.
if (ptr == nullptr)
return nullptr;
// If successful push ptr into dynamicT_n and construct ptr.
dynamicT_n.push_back({ptr, 1});
nodeAmount++;
alloc.construct(ptr, par, kid, val, code);
// Insert ptr into parKid.
parKid.insert(index == 0xffffffffffffffffULL ? parKid.end() : parKid.begin() + index, ptr);
// Return ptr.
return ptr;
}
/**
* @brief Emplace a new %tree_node into a %tree below a %tree_node in the %tree.
* @param par A pointer to the parent %tree_node of the new %tree_node.
* @param extra_kid A %vector including pointers to extra kid %tree_nodes of the new %tree_node.
* @param val The value of the new %tree_node.
* @param code A %string giving the code of the new %tree_node.
* @return A pointer to the new %tree_node, or nullptr if unsuccessful.
*
* This function tries to create a %tree_node with the given data and emplace it below @a par.
* If successful it returns a pointer to the new %tree_node.
* If unsuccessful it returns nullptr.
*/
tree_node<value_type> *emplace_below(tree_node<value_type> *par, vector<tree_node<value_type> *> extra_kid = {},
value_type val = value_type(), string code = string())
{
// Try to allocate a new tree node.
tree_node<value_type> *ptr = alloc.allocate(1);
// If unsuccessful return nullptr.
if (ptr == nullptr)
return nullptr;
// If successful push ptr into dynamicT_n.
dynamicT_n.push_back({ptr, 1});
nodeAmount++;
// Check if par is also the leave node.
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Construct the new tree node.
for (typename node_kid_type::iterator it = parKid.begin(); it != parKid.end(); it++)
extra_kid.push_back(*it);
alloc.construct(ptr, par, extra_kid, val, code);
// Set the parent nodes of the extra kid nodes and the kid nodes of par to the new tree node.
for (typename node_kid_type::iterator it = extra_kid.begin(); it != extra_kid.end(); it++)
(*it)->set_par(ptr);
// Set the new node to the kid node of par.
parKid.assign(1, ptr);
// Return the pointer to the new node.
return ptr;
}
/**
* @brief Insert a %tree_node below into a %tree below a %tree_node in the %tree.
* @param t_n A pointer to a %tree_node that the user want to put it below @a par.
* @param par A pointer to the parent %tree_node of @a t_n.
* @param extra_kid A %vector including pointers to extra kid %tree_nodes of @a t_n.
* @param change_val A boolean, changes the value of @a t_n to @a val if true.
* @param val The new value of @a t_n.
* @param change_val A boolean, changes the code of @a t_n to @a code if true.
* @param code A new %string giving the code of @a t_n.
* @return A pointer to @a t_n.
*
* This function inserts @a t_n into a %tree below @a par, assigns the given data to @a t_n and
* returns a pointer to @a t_n.
*/
node_type *insert_below(tree_node<value_type> *t_n, tree_node<value_type> *par, node_kid_type extra_kid = {},
bool change_val = false, value_type val = value_type(),
bool change_code = false, string code = string())
{
// Check if par is also the leave node.
// parKid: A reference to a %vector of child nodes of par.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Assign t_n
for (typename node_kid_type::iterator it = parKid.begin(); it != parKid.end(); it++)
extra_kid.push_back(*it);
t_n->kid_list() = extra_kid;
if (change_val)
t_n->set_val(val);
if (change_code)
t_n->set_code(code);
// Set the parent nodes of the extra kid nodes and the kid nodes of par to t_n.
for (typename node_kid_type::iterator it = extra_kid.begin(); it != extra_kid.end(); it++)
(*it)->set_par(t_n);
// Set t_n to the only kid node of par.
parKid.assign(1, t_n);
// Return t_n.
return t_n;
}
/**
* @brief Find the first %tree_node that occurs of a val or a %string giving a code in a %tree.
* @param val The val to find.
* @param order Find order(not include inorder and rinorder).
* @param check_order If true, the function will check @a order.
* @param find_by_val If true, the function will find by @a val, or it will find by @a code.
* @param code A %string giving a code to find.
* @return The first %tree_node pointer ptr in a %tree such that
* ptr->get_val() == @a val or ptr->get_code() == @a code, or nullptr if no such pointer exists.
* @throw If choose to check order and @a order is invalid, the function will throw std::invalid_argument.
*
* The function finds the first %tree_node that occurs of @a val or @a code in a %tree.
* If find a %tree_node like this, it will return a pointer to this %tree_node, or it will return nullptr.
* Also, if there is something wrong while looking for the target %tree_node
* (one is that @a order is "inorder" or "rinorder"), it will return nullptr.
* However, if the user choose to check @a order and @a order is indeed invalid,
* the function will throw std::invalid_argument.
*/
node_type *find(value_type val, tree_sequence order = tree_sequence::preorder, bool check_order = false,
bool find_by_val = true, string code = "")
{
// Record the order.
char tord = -1;
switch (order)
{
case preorder:
case rpreorder:
tord = 0;
break;
case postorder:
case rpostorder:
tord = 1;
break;
case levorder:
case rlevorder:
tord = 2;
break;
default:
// Check order if the user wants to.
if (check_order)
{
string wrong_type = "unknown type";
// Determine if it is "inorder" or "rinorder".
switch (order)
{
case inorder:
wrong_type = "inorder";
break;
case rinorder:
wrong_type = "rinorder";
}
// Throw an invalid argument error.
throw invalid_argument("std::tree::find_first() -> Invalid argument: argument \"order\"(" +
wrong_type + ") is invalid.");
}
}
// Record whether there is a prefix 'r'.
bool r__ = false;
switch (order)
{
case rpreorder:
case rpostorder:
case rlevorder:
r__ = true;
}
// Find the node by given information.
switch (tord)
{
// Preorder & reperorder &
// Postorder & rpostorder.
case 0:
case 1:
{
stack<pair<node_type *, size_type>> sta;
sta.push({rot, 0});
while (!sta.empty())
{
node_type *t_n = sta.top().first;
if (tord == 0 && find_by_val && val == t_n->get_val() || !find_by_val && code == t_n->get_id())
return t_n;
node_kid_type kid = t_n->get_kid_list();
if (r__)
reverse(kid.begin(), kid.end());
if (!t_n->is_leaf_node() && sta.top().second < kid.size())
{
int index = sta.top().second;
sta.pop();
sta.push({t_n, index + 1});
sta.push({kid.at(index), 0});
}
else
{
if (tord == 1 && find_by_val && val == t_n->get_val() || !find_by_val && code == t_n->get_id())
return t_n;
sta.pop();
}
}
break;
}
// Levorder & rlevorder.
case 2:
{
if (find_by_val && val == rot->get_val() || !find_by_val && code == rot->get_id())
return rot;
queue<node_type *> que;
que.push(rot);
while (!que.empty())
{
node_kid_type kid = que.front()->get_kid_list();
if (r__)
reverse(kid.begin(), kid.end());
for (typename node_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
{
if (find_by_val && (*it)->get_val() == val || !find_by_val && (*it)->get_id() == code)
return *it;
if (!(*it)->is_leaf_node())
que.push(*it);
}
que.pop();
}
}
}
// If unseccessful return nullptr.
return nullptr;
}
};
}