Untitled
unknown
plain_text
8 months ago
8.7 kB
4
Indexable
Never
#pragma once
#include "cstring"
#include "sstream"
#include "string"
#include "exception"
#include "vector"
#include "queue"
namespace cs251
{
typedef int handle;
class invalid_handle : public std::runtime_error {
public: invalid_handle() : std::runtime_error("Invalid handle!") {} };
class recycled_node : public std::runtime_error {
public: recycled_node() : std::runtime_error("Node is recycled!") {} };
template<typename tree_node_data>
class tree_node {
//Friend class grant private access to another class.
template<typename tnd>
friend class tree;
//TODO: You may add private members/methods here.
/**
* The handle of current node, should be the index of current node within the vector array in tree.
*/
handle m_handle = -1;
/**
* Whether the node is recycled.
*/
bool m_recycled = true;
/**
* The content of the node.
*/
tree_node_data m_data = {};
/**
* The handle of the parent node.
*/
handle m_parentHandle = -1;
/**
* List of handles to all children.
*/
std::vector<handle> m_childrenHandles{};
public:
/**
* \brief Retrieve the data for this node.
* \return The modifiable reference to the node's data.
*/
tree_node_data& ref_data();
/**
* \brief Check if the node is recycled.
* \return Whether this node is recycled or not.
*/
bool is_recycled() const;
/**
* \brief Get the handle of this node.
* \return The handle of this node.
*/
handle get_handle() const;
/**
* \brief Get the handle of this node's parent.
* \return The handle of this node's parent.
*/
handle get_parent_handle() const;
/**
* \brief Get the list of handles of this node's children.
* \return The list of handles of this node's children.
*/
const std::vector<handle>& peek_children_handles() const;
};
template<typename tree_node_data>
class tree
{
public:
/**
* \brief The constructor of the tree class. You should allocate the root node here.
*/
tree();
/**
* \brief Allocate a new node as root from pool or creating a new one.
* \return The handle of the new node.
*/
handle allocate(handle parentHandle);
/**
* \brief Remove (recycle) a node. Remove all descendent nodes.
* \param handle The handle of the target node to be removed.
*/
void remove(handle handle);
/**
* \brief Attach a node to another node as its child.
* \param targetHandle The handle of the target node as child.
* \param parentHandle The handle of the parent node.
*/
void set_parent(handle targetHandle, handle parentHandle);
/**
* \brief Return the constant reference to the list of nodes.
* \return Constant reference to the list of nodes.
*/
const std::vector<tree_node<tree_node_data>>& peek_nodes() const;
/**
* \brief Retrieve the node with its handle.
* \param handle The handle of the target node.
* \return The reference to the node.
*/
tree_node<tree_node_data>& ref_node(handle handle);
private:
//TODO: You may add private members/methods here.
/**
* The storage for all nodes.
*/
std::vector<tree_node<tree_node_data>> m_nodes {};
/**
* The pool that keep track of the recycled nodes.
*/
std::queue<handle> m_node_pool {};
};
template <typename tree_node_data>
tree_node_data& tree_node<tree_node_data>::ref_data()
{
//TODO: Remove following line and add your implementation here.
if (m_recycled) {
throw recycled_node();
}
return m_data;
}
template <typename tree_node_data>
bool tree_node<tree_node_data>::is_recycled() const
{
//TODO: Remove following line and add your implementation here.
return m_recycled;
}
template <typename tree_node_data>
handle tree_node<tree_node_data>::get_handle() const
{
//TODO: Remove following line and add your implementation here.
return m_handle;
}
template <typename tree_node_data>
handle tree_node<tree_node_data>::get_parent_handle() const
{
//TODO: Remove following line and add your implementation here.
if (m_recycled)
throw recycled_node();
return m_parentHandle;
}
template <typename tree_node_data>
const std::vector<handle>& tree_node<tree_node_data>::peek_children_handles() const
{
//TODO: Remove following line and add your implementation here.
if (m_recycled)
throw recycled_node();
return m_childrenHandles;
}
template <typename tree_node_data>
tree<tree_node_data>::tree()
{
//TODO: Remove following line and add your implementation here.
tree_node<tree_node_data> root_node;
root_node.m_handle = 0;
root_node.m_recycled = false;
root_node.m_parentHandle = -1;
m_nodes.emplace_back(root_node);
}
template <typename tree_node_data>
handle tree<tree_node_data>::allocate(handle parentHandle)
{
//TODO: Remove following line and add your implementation here.
if (parentHandle >= m_nodes.size() ) {
throw invalid_handle();
}
if (m_nodes[parentHandle].m_recycled) {
throw recycled_node();
}
handle newNodeHandle;
if (!m_node_pool.empty()) {
newNodeHandle = m_node_pool.front();
m_node_pool.pop();
m_nodes[newNodeHandle].m_recycled = false;
} else {
newNodeHandle = m_nodes.size();
tree_node<tree_node_data> node_new;
node_new.m_handle = newNodeHandle;
node_new.m_recycled = false;
node_new.m_parentHandle = parentHandle;
m_nodes.emplace_back(node_new);
}
auto& newNode = m_nodes[newNodeHandle];
newNode.m_handle = newNodeHandle;
newNode.m_parentHandle = parentHandle;
m_nodes[parentHandle].m_childrenHandles.emplace_back(newNodeHandle);
return newNodeHandle;
}
template <typename tree_node_data>
void tree<tree_node_data>::remove(const handle handle)
{
//TODO: Remove following line and add your implementation here.
if (handle < 0 || handle >= m_nodes.size())
throw invalid_handle();
if (m_nodes[handle].m_recycled)
throw recycled_node();
auto child_handle = m_nodes[handle].m_childrenHandles;
for (int i=0; i < child_handle.size(); i++) {
remove(m_nodes[handle].m_childrenHandles[0]);
}
if (m_nodes[handle].m_parentHandle >= 0 || m_nodes[handle].m_parentHandle < m_nodes.size()) { // Check if not root
auto& parent = m_nodes[m_nodes[handle].m_parentHandle];
auto& children = parent.m_childrenHandles;
if(parent.m_recycled) {
throw recycled_node();
}
// Find and remove the handle from parent's children array
for (size_t i = 0; i < children.size(); i++) {
if (children[i] == handle) {
children.erase(children.begin() + i);
break; // Stop searching once handle is found and removed
}
}
}
m_nodes[handle].m_recycled = true;
m_node_pool.push(handle);
m_nodes[handle].m_parentHandle = -1; // No parent
}
template <typename tree_node_data>
void tree<tree_node_data>::set_parent(const handle targetHandle, const handle parentHandle)
{
//TODO: Remove following line and add your implementation here.
if (targetHandle >= m_nodes.size() || parentHandle >= m_nodes.size()) {
throw invalid_handle();
}
if (m_nodes[targetHandle].m_recycled || m_nodes[parentHandle].m_recycled) {
throw recycled_node();
}
if (m_nodes[targetHandle].m_parentHandle == parentHandle) {
return;
}
auto& parentChildren = m_nodes[m_nodes[targetHandle].m_parentHandle].m_childrenHandles;
bool found = false;
if (m_nodes[targetHandle].m_parentHandle != -1) {
for (size_t i = 0; i < parentChildren.size(); ++i) {
if (parentChildren[i] == targetHandle) {
parentChildren.erase(parentChildren.begin() + i);
found = true;
break;
}
}
}
if (!found) {
m_nodes[parentHandle].m_childrenHandles.push_back(targetHandle);
}
m_nodes[targetHandle].m_parentHandle = parentHandle;
//check if parentHandle has targetHandle as kid, if not, then push targethandle to children array of parentHandle
}
template <typename tree_node_data>
const std::vector<tree_node<tree_node_data>>& tree<tree_node_data>::peek_nodes() const
{
//TODO: Remove following line and add your implementation here.
return m_nodes;
}
template <typename tree_node_data>
tree_node<tree_node_data>& tree<tree_node_data>::ref_node(handle handle)
{
//TODO: Remove following line and add your implementation here.
if (handle >= m_nodes.size() || m_nodes[handle].m_recycled)
throw invalid_handle();
return m_nodes[handle];
}
}
Leave a Comment