[ create a new paste ] login | about

Link: http://codepad.org/yIAblSDN    [ raw code | output | fork ]

C++, pasted on Mar 11:
template <class T>
struct c_ptr_oct_tree
{
	struct node{};

	struct branch : public node
	{
		node* m_child_array[2][2][2];
	};

	struct leaf : public node
	{
		T* m_p_data;
	};

	int m_size;
	node* m_p_root_node;

	c_ptr_oct_tree(int size) : m_size(size), m_p_root_node(0)
	{
		// Make sure size is power of two.
		assert( ((m_size - 1) & m_size) == 0 );
	}
	~c_ptr_oct_tree()
	{
		remove_node_recursive(m_p_root_node, m_size);
	}

	void remove_node_recursive(node* p_node, int size)
	{
		if(p_node)
		{
			size /= 2;
			if(size > 1)
			{
				for(int x = 0; x < 2; x++)
				{
					for(int y = 0; y < 2; y++)
					{
						for(int z = 0; z < 2; z++)
						{
							if(static_cast<branch*>(p_node)->m_child_array[x][y][z])
							{
								remove_node_recursive(static_cast<branch*>(p_node)->m_child_array[x][y][z], size);
							}
						}
					}
				}
			}
			else
			{
				delete static_cast<leaf*>(p_node)->m_p_data;
			}
			delete p_node;
		}
	}

	T* get(int x, int y, int z)
	{
		assert(x >= 0 && x < m_size);
		assert(y >= 0 && y < m_size);
		assert(z >= 0 && z < m_size);

		node* p_node = m_p_root_node;
		int size = m_size;

		while(size > 1)
		{
			if(p_node == 0)
			{
				return 0;
			}
			size /= 2;
			p_node = static_cast<branch*>(p_node)->m_child_array[!!(x & size)][!!(y & size)][!!(z & size)];
		}
		if(p_node)
		{
			return static_cast<leaf*>(p_node)->m_p_data;
		}
		return 0;
	}

	void reset(int x, int y, int z, T* p_object)
	{
		assert(x >= 0 && x < m_size);
		assert(y >= 0 && y < m_size);
		assert(z >= 0 && z < m_size);

		if(p_object == 0)
		{
			zero(x, y, z);
			return;
		}

		node** pp_node = &m_p_root_node;
		int size = m_size;

		while(size > 1)
		{
			if(*pp_node == 0)
			{
				branch* p_branch = new branch;
				memset(p_branch, 0, sizeof(branch));
				*pp_node = p_branch;
			}
			size /= 2;
			pp_node = &static_cast<branch*>(*pp_node)->m_child_array[!!(x & size)][!!(y & size)][!!(z & size)];
		}
		if(*pp_node)
		{
			delete static_cast<leaf*>(*pp_node)->m_p_data;
			static_cast<leaf*>(*pp_node)->m_p_data = 0;
		}
		else
		{
			*pp_node = new leaf;
		}
		static_cast<leaf*>(*pp_node)->m_p_data = p_object;
	}

	void zero(int x, int y, int z)
	{
		assert(x >= 0 && x < m_size);
		assert(y >= 0 && y < m_size);
		assert(z >= 0 && z < m_size);

		std::vector<node**> branch_container;

		node** pp_node = &m_p_root_node;
		int size = m_size;

		while(size > 1)
		{
			if(*pp_node == 0)
			{
				break;
			}
			branch_container.push_back(pp_node);
			size /= 2;
			pp_node = &static_cast<branch*>(*pp_node)->m_child_array[!!(x & size)][!!(y & size)][!!(z & size)];
		}
		if(*pp_node)
		{
			if(size == 1)
			{
				delete static_cast<leaf*>(*pp_node)->m_p_data;
				static_cast<leaf*>(*pp_node)->m_p_data = 0;
				delete *pp_node;
				*pp_node = 0;
				while(branch_container.empty() == false)
				{
					for(int x = 0; x < 2; x++)
					{
						for(int y = 0; y < 2; y++)
						{
							for(int z = 0; z < 2; z++)
							{
								if(static_cast<branch*>(*branch_container.back())->m_child_array[x][y][z])
								{
									return;
								}
							}
						}
					}
					delete *branch_container.back();
					*branch_container.back() = 0;
					branch_container.pop_back();
				}
			}
		}
	}
};

int main()
{
c_ptr_oct_tree<int> my_tree(8);
my_tree.reset(1,1,1,new int(5));
int* p_my_int = my_tree.get(1,1,1);
cout << *p_my_int << '\n';
my_tree.zero(1,1,1);
cout << "address of my int : " << p_my_int;
return 0;
}


Output:
1
2
5
address of my int : 0x8057438


Create a new paste based on this one


Comments: