This class represents a node of the tree, we still take an example E.g. More...

#include <searchtree.h>

Collaboration diagram for SearchTreeNode:

Public Member Functions
	SearchTreeNode ()

	SearchTreeNode (unsigned int depth, nSearchTreeNode parent, nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen)

virtual	~SearchTreeNode ()

nSearchTreeNode	GetParent () const
	return the parent node index More...

void	SetParent (nSearchTreeNode newparent)
	set the parent node index More...

nSearchTreeNode	GetChild (wxChar ch)
	This will loop of the link map of the node, and find the child node with its edge beginning with the single character, return the valid node index then, if no such child node exists, it simply return 0. More...

size_t	GetItemNo (size_t depth)
	the element stored in the item map is currently size_t item number More...

size_t	AddItemNo (size_t depth, size_t itemno)
	set the item value in the item map More...

SearchTreeNode *	GetParent (const BasicSearchTree *tree) const
	get the parent node pointer, this is simply a wrapper function of nSearchTreeNode GetParent() More...

SearchTreeNode *	GetChild (BasicSearchTree *tree, wxChar ch)
	return a child node pointer, this is simply a wrapper function of GetChild(wxChar ch), besides that it use the valid node index to reference a valid node instance address. More...

wxString	GetLabel (const BasicSearchTree *tree) const
	get the incoming edge string of the node, in the above example, it is "hysi" for node(2) More...

wxChar	GetChar (const BasicSearchTree *tree) const
	get first character of the incoming edge, in the above example, it is 'h' for node(2) More...

const wxString &	GetActualLabel (const BasicSearchTree *tree) const
	get the full label string, note the incoming edge is only a sub string of the full label More...

nSearchTreeLabel	GetLabelNo () const
	the index of the full label in tree->m_Labels array More...

unsigned int	GetLabelStart () const
	the first character index in the full label More...

unsigned int	GetLabelLen () const
	the length of the incoming label, in the above example, it is 4 for node"hysi"(2) More...

void	SetLabel (nSearchTreeLabel label, unsigned int labelstart, unsigned int labellen)
	specify the incoming edge of the current node More...

unsigned int	GetDepth () const
	the depth of node is the string length from root node to the last character of the incoming edge More...

void	RecalcDepth (BasicSearchTree *tree)
	Updates the depth by recalculate the m_Depth of the node, this happens the parent node has changed. More...

void	UpdateItems (BasicSearchTree *tree)
	Updates items with parent, move some items upward to its parent node. More...

unsigned int	GetLabelStartDepth () const
	Returns the depth of the start of the node's incoming label In other words, returns the (calculated) parent's depth. More...

bool	IsLeaf () const
	check to see this node is a leaf node. More...

unsigned int	GetDeepestMatchingPosition (BasicSearchTree *tree, const wxString &s, unsigned int StringStartDepth)
	Gets the deepest position where the string matches the edge's label. More...

wxString	Serialize (BasicSearchTree *tree, nSearchTreeNode node_id, bool withchildren=false)
	serialize the node information to a string More...

void	Dump (BasicSearchTree *tree, nSearchTreeNode node_id, const wxString &prefix, wxString &result)
	pretty print the node to a string, used for debugging More...

Static Public Member Functions
static wxString	SerializeString (const wxString &s)

static wxString	U2S (unsigned int u)

static wxString	I2S (int i)

static bool	UnSerializeString (const wxString &s, wxString &result)

static bool	S2U (const wxString &s, unsigned int &u)

static bool	S2I (const wxString &s, int &i)

Protected Attributes
unsigned int	m_Depth
	the string length from the root node to the current node (end of the edge) More...

nSearchTreeNode	m_Parent
	parent node index More...

nSearchTreeLabel	m_Label
	the string index, the edge is a sub-string of the label in the label array More...

unsigned int	m_LabelStart
	label start index in the string More...

unsigned int	m_LabelLen
	label length in the string More...

SearchTreeLinkMap	m_Children
	link to descent nodes, More...

SearchTreeItemsMap	m_Items
	depth->item number map, More...

Friends
class	BasicSearchTree

class	BasicSearchTreeIterator

Detailed Description

This class represents a node of the tree, we still take an example E.g.

- "" (0)
      \- "p" (4)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sychic" (5)

Here, a tree of 6 nodes. Let's look at node (2), its incoming edge is "hysi", it has two child nodes "cs" (1) and "ology" (3). To access child nodes from parent node, we need a link map, here is an example of link map for node (2), note that link map's key is always a single character.

char -> node index
 'c' -> 1
 'o' -> 3

The parent node of the node (2) is the node (4), note that the left most node in the above tree is the root node, the root node has index number 0, because it was the first node created when the tree constructed.

Definition at line 157 of file searchtree.h.

Constructor & Destructor Documentation

◆ SearchTreeNode() [1/2]

SearchTreeNode::SearchTreeNode ( )

Definition at line 225 of file searchtree.cpp.

Referenced by BasicSearchTree::CreateNode().

◆ SearchTreeNode() [2/2]

SearchTreeNode::SearchTreeNode	(	unsigned int	depth,
		nSearchTreeNode	parent,
		nSearchTreeLabel	label,
		unsigned int	labelstart,
		unsigned int	labellen
	)

Definition at line 234 of file searchtree.cpp.

◆ ~SearchTreeNode()

SearchTreeNode::~SearchTreeNode ( )

virtual

Definition at line 244 of file searchtree.cpp.

Member Function Documentation

◆ AddItemNo()

size_t SearchTreeNode::AddItemNo	(	size_t	depth,
		size_t	itemno
	)

set the item value in the item map

Definition at line 264 of file searchtree.cpp.

References m_Items.

◆ Dump()

void SearchTreeNode::Dump	(	BasicSearchTree *	tree,
		nSearchTreeNode	node_id,
		const wxString &	prefix,
		wxString &	result
	)

pretty print the node to a string, used for debugging

Definition at line 495 of file searchtree.cpp.

References _T, wxString::append(), Dump(), GetLabel(), BasicSearchTree::GetNode(), wxString::length(), m_Children, SerializeString(), wxString::substr(), and U2S().

Referenced by Dump().

◆ GetActualLabel()

const wxString & SearchTreeNode::GetActualLabel ( const BasicSearchTree * tree ) const

inline

get the full label string, note the incoming edge is only a sub string of the full label

Definition at line 305 of file searchtree.cpp.

References m_Label, and BasicSearchTree::m_Labels.

Referenced by GetChar(), and GetDeepestMatchingPosition().

◆ GetChar()

wxChar SearchTreeNode::GetChar ( const BasicSearchTree * tree ) const

inline

get first character of the incoming edge, in the above example, it is 'h' for node(2)

Definition at line 297 of file searchtree.cpp.

References GetActualLabel(), m_Depth, and m_LabelStart.

Referenced by BasicSearchTreeIterator::FindNextSibling(), and BasicSearchTreeIterator::FindPrevSibling().

◆ GetChild() [1/2]

nSearchTreeNode SearchTreeNode::GetChild ( wxChar ch )

inline

This will loop of the link map of the node, and find the child node with its edge beginning with the single character, return the valid node index then, if no such child node exists, it simply return 0.

Definition at line 248 of file searchtree.cpp.

References m_Children.

Referenced by BasicSearchTree::FindNode(), and GetChild().

◆ GetChild() [2/2]

SearchTreeNode * SearchTreeNode::GetChild	(	BasicSearchTree *	tree,
		wxChar	ch
	)

inline

return a child node pointer, this is simply a wrapper function of GetChild(wxChar ch), besides that it use the valid node index to reference a valid node instance address.

Definition at line 284 of file searchtree.cpp.

References GetChild(), and BasicSearchTree::GetNode().

◆ GetDeepestMatchingPosition()

unsigned int SearchTreeNode::GetDeepestMatchingPosition	(	BasicSearchTree *	tree,
		const wxString &	s,
		unsigned int	StringStartDepth
	)

inline

Gets the deepest position where the string matches the edge's label.

Let's give an example about the algorithm of GetDeepestMatchingPosition, see the tree below.

0 for 0 characters in the tree matched, 1 for 1 character matched, etc. StringStartDepth is the start label position of the root node

"" (0) - "p" (4) +- "hysi" (2) | +- "cs" (1) | - "ology" (3) - "sychic" (5)

Now, suppose that the label is a long string "0123456789psychic" |@ '|' donates the StringStartDepth position, '@' donates the current Node's start depth. Now, we have a string s = "psychABC", we should actually starting comparing the two string from "s". compare the two strings:

  0123456789psychic
            psychABC
             ^   ~

Here, '^' donates the m_LabelStart of current node, '~' donates the deepest match point.

Definition at line 344 of file searchtree.cpp.

References GetActualLabel(), GetDepth(), GetLabelStartDepth(), wxString::length(), m_LabelLen, and m_LabelStart.

Referenced by BasicSearchTree::FindNode().

◆ GetDepth()

unsigned int SearchTreeNode::GetDepth ( ) const

inline

the depth of node is the string length from root node to the last character of the incoming edge

Definition at line 217 of file searchtree.h.

Referenced by BasicSearchTree::AddNode(), BasicSearchTree::FindNode(), GetDeepestMatchingPosition(), BasicSearchTree::GetString(), RecalcDepth(), BasicSearchTree::SplitBranch(), and UpdateItems().

◆ GetItemNo()

size_t SearchTreeNode::GetItemNo ( size_t depth )

inline

the element stored in the item map is currently size_t item number

Definition at line 256 of file searchtree.cpp.

References m_Items.

Referenced by BasicSearchTree::HasItem().

◆ GetLabel()

wxString SearchTreeNode::GetLabel ( const BasicSearchTree * tree ) const

get the incoming edge string of the node, in the above example, it is "hysi" for node(2)

Definition at line 290 of file searchtree.cpp.

References _T, m_Depth, m_Label, m_LabelLen, BasicSearchTree::m_Labels, and m_LabelStart.

Referenced by Dump(), BasicSearchTree::FindMatches(), and BasicSearchTree::GetString().

◆ GetLabelLen()

unsigned int SearchTreeNode::GetLabelLen ( ) const

inline

the length of the incoming label, in the above example, it is 4 for node"hysi"(2)

Definition at line 211 of file searchtree.h.

Referenced by BasicSearchTree::FindMatches(), and BasicSearchTree::SplitBranch().

◆ GetLabelNo()

nSearchTreeLabel SearchTreeNode::GetLabelNo ( ) const

inline

the index of the full label in tree->m_Labels array

Definition at line 205 of file searchtree.h.

Referenced by BasicSearchTree::AddNode(), and BasicSearchTree::SplitBranch().

◆ GetLabelStart()

unsigned int SearchTreeNode::GetLabelStart ( ) const

inline

the first character index in the full label

Definition at line 208 of file searchtree.h.

Referenced by BasicSearchTree::AddNode(), and BasicSearchTree::SplitBranch().

◆ GetLabelStartDepth()

unsigned int SearchTreeNode::GetLabelStartDepth ( ) const

inline

Returns the depth of the start of the node's incoming label In other words, returns the (calculated) parent's depth.

Definition at line 317 of file searchtree.cpp.

References m_Depth, and m_LabelLen.

Referenced by BasicSearchTree::AddNode(), BasicSearchTree::FindMatches(), GetDeepestMatchingPosition(), BasicSearchTree::GetString(), and BasicSearchTree::SplitBranch().

◆ GetParent() [1/2]

nSearchTreeNode SearchTreeNode::GetParent ( ) const

inline

return the parent node index

Definition at line 170 of file searchtree.h.

Referenced by BasicSearchTreeIterator::FindNextSibling(), BasicSearchTreeIterator::FindPrevSibling(), BasicSearchTreeIterator::FindSibling(), BasicSearchTree::GetString(), RecalcDepth(), and BasicSearchTree::SplitBranch().

◆ GetParent() [2/2]

SearchTreeNode * SearchTreeNode::GetParent ( const BasicSearchTree * tree ) const

inline

get the parent node pointer, this is simply a wrapper function of nSearchTreeNode GetParent()

Definition at line 277 of file searchtree.cpp.

References m_Depth, BasicSearchTree::m_Nodes, m_Parent, and NULL.

◆ I2S()

wxString SearchTreeNode::I2S ( int i )

static

Definition at line 435 of file searchtree.cpp.

References _T, and U2S().

◆ IsLeaf()

bool SearchTreeNode::IsLeaf ( ) const

inline

check to see this node is a leaf node.

Note the label's depth is 0-based

Definition at line 231 of file searchtree.h.

Referenced by BasicSearchTree::AddNode().

◆ RecalcDepth()

void SearchTreeNode::RecalcDepth ( BasicSearchTree * tree )

inline

Updates the depth by recalculate the m_Depth of the node, this happens the parent node has changed.

Definition at line 383 of file searchtree.cpp.

References GetDepth(), GetParent(), m_Depth, and m_LabelLen.

Referenced by BasicSearchTree::AddNode(), and BasicSearchTree::SplitBranch().

◆ S2I()

bool SearchTreeNode::S2I	(	const wxString &	s,
		int &	i
	)

static

Definition at line 984 of file searchtree.cpp.

References _T, wxString::IsEmpty(), S2U(), and wxString::substr().

◆ S2U()

bool SearchTreeNode::S2U	(	const wxString &	s,
		unsigned int &	u
	)

static

Definition at line 962 of file searchtree.cpp.

References _T, and wxString::length().

Referenced by S2I(), and UnSerializeString().

◆ Serialize()

wxString SearchTreeNode::Serialize	(	BasicSearchTree *	tree,
		nSearchTreeNode	node_id,
		bool	withchildren = `false`
	)

serialize the node information to a string

Definition at line 444 of file searchtree.cpp.

References _T, BasicSearchTree::GetNode(), m_Children, m_Depth, m_Items, m_Label, m_LabelLen, m_LabelStart, m_Parent, Serialize(), SerializeString(), and U2S().

Referenced by Serialize().

◆ SerializeString()

wxString SearchTreeNode::SerializeString ( const wxString & s )

static

Definition at line 1010 of file searchtree.cpp.

References _T, wxString::length(), and U2S().

Referenced by Dump(), Serialize(), and BasicSearchTree::SerializeLabel().

◆ SetLabel()

void SearchTreeNode::SetLabel	(	nSearchTreeLabel	label,
		unsigned int	labelstart,
		unsigned int	labellen
	)

inline

specify the incoming edge of the current node

Definition at line 310 of file searchtree.cpp.

References m_Label, m_LabelLen, and m_LabelStart.

Referenced by BasicSearchTree::AddNode(), and BasicSearchTree::SplitBranch().

◆ SetParent()

void SearchTreeNode::SetParent ( nSearchTreeNode newparent )

inline

set the parent node index

Definition at line 173 of file searchtree.h.

Referenced by BasicSearchTree::SplitBranch().

◆ U2S()

wxString SearchTreeNode::U2S ( unsigned int u )

static

Definition at line 415 of file searchtree.cpp.

References _T.

Referenced by Dump(), I2S(), Serialize(), BasicSearchTree::SerializeLabels(), and SerializeString().

◆ UnSerializeString()

bool SearchTreeNode::UnSerializeString	(	const wxString &	s,
		wxString &	result
	)

static

Definition at line 899 of file searchtree.cpp.

References _T, wxString::Clear(), wxString::length(), S2U(), and wxString::substr().

◆ UpdateItems()

void SearchTreeNode::UpdateItems ( BasicSearchTree * tree )

Updates items with parent, move some items upward to its parent node.

Definition at line 392 of file searchtree.cpp.

References GetDepth(), BasicSearchTree::GetNode(), m_Items, and m_Parent.

Referenced by BasicSearchTree::SplitBranch().

Friends And Related Function Documentation

◆ BasicSearchTree

friend class BasicSearchTree

friend

Definition at line 159 of file searchtree.h.

◆ BasicSearchTreeIterator

friend class BasicSearchTreeIterator

friend

Definition at line 160 of file searchtree.h.

Member Data Documentation

◆ m_Children

SearchTreeLinkMap SearchTreeNode::m_Children

protected

link to descent nodes,

See also: SearchTreeLinkMap for details

Definition at line 268 of file searchtree.h.

Referenced by BasicSearchTree::AddNode(), Dump(), BasicSearchTreeIterator::FindNext(), BasicSearchTreeIterator::FindNextSibling(), BasicSearchTreeIterator::FindPrev(), BasicSearchTreeIterator::FindPrevSibling(), BasicSearchTreeIterator::FindSibling(), GetChild(), Serialize(), and BasicSearchTree::SplitBranch().

◆ m_Depth

unsigned int SearchTreeNode::m_Depth

protected

the string length from the root node to the current node (end of the edge)

Definition at line 253 of file searchtree.h.

Referenced by BasicSearchTree::FindMatches(), GetChar(), GetLabel(), GetLabelStartDepth(), GetParent(), RecalcDepth(), and Serialize().

◆ m_Items

SearchTreeItemsMap SearchTreeNode::m_Items

protected

depth->item number map,

See also: SearchTreePoint about how to access items of the node

Definition at line 270 of file searchtree.h.

Referenced by AddItemNo(), BasicSearchTree::FindMatches(), GetItemNo(), Serialize(), and UpdateItems().

◆ m_Label

nSearchTreeLabel SearchTreeNode::m_Label

protected

the string index, the edge is a sub-string of the label in the label array

Definition at line 259 of file searchtree.h.

Referenced by GetActualLabel(), GetLabel(), Serialize(), and SetLabel().

◆ m_LabelLen

unsigned int SearchTreeNode::m_LabelLen

protected

label length in the string

Definition at line 265 of file searchtree.h.

Referenced by GetDeepestMatchingPosition(), GetLabel(), GetLabelStartDepth(), RecalcDepth(), Serialize(), and SetLabel().

◆ m_LabelStart

unsigned int SearchTreeNode::m_LabelStart

protected

label start index in the string

Definition at line 262 of file searchtree.h.

Referenced by GetChar(), GetDeepestMatchingPosition(), GetLabel(), Serialize(), and SetLabel().

◆ m_Parent

nSearchTreeNode SearchTreeNode::m_Parent

protected

parent node index

Definition at line 256 of file searchtree.h.

Referenced by BasicSearchTreeIterator::FindNext(), BasicSearchTreeIterator::FindPrev(), GetParent(), Serialize(), and UpdateItems().

The documentation for this class was generated from the following files:

Public Member Functions

Static Public Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SearchTreeNode() [1/2]

◆ SearchTreeNode() [2/2]

◆ ~SearchTreeNode()

Member Function Documentation

◆ AddItemNo()

◆ Dump()

◆ GetActualLabel()

◆ GetChar()

◆ GetChild() [1/2]

◆ GetChild() [2/2]

◆ GetDeepestMatchingPosition()

◆ GetDepth()

◆ GetItemNo()

◆ GetLabel()

◆ GetLabelLen()

◆ GetLabelNo()

◆ GetLabelStart()

◆ GetLabelStartDepth()

◆ GetParent() [1/2]

◆ GetParent() [2/2]

◆ I2S()

◆ IsLeaf()

◆ RecalcDepth()

◆ S2I()

◆ S2U()

◆ Serialize()

◆ SerializeString()

◆ SetLabel()

◆ SetParent()

◆ U2S()

◆ UnSerializeString()

◆ UpdateItems()

Friends And Related Function Documentation

◆ BasicSearchTree

◆ BasicSearchTreeIterator

Member Data Documentation

◆ m_Children

◆ m_Depth

◆ m_Items

◆ m_Label

◆ m_LabelLen

◆ m_LabelStart

◆ m_Parent