2-3-4 tree node class More...

Collaboration diagram for data_structures::tree_234::Node:

Public Member Functions
	Node (int64_t item)
	Node constructor.

int8_t	GetCount ()
	Get the item count that current saved in the node.

void	SetCount (int8_t c)
	Set the item count of the node.

bool	IsLeaf ()
	Check if node is a leaf.

bool	IsFull ()
	Check if node is a full (4-node)

bool	Is2Node ()
	Check if node is a 2-node.

bool	Is34Node ()
	Check if node is a 3-node or 4-node, this is useful when we delete item from 2-3-4 tree.

bool	Contains (int64_t item)
	Check if item is in the node.

int8_t	GetItemIndex (int64_t item)
	Get the index of the item in the node, 0-based.

int64_t	GetMaxItem ()
	Get max item (rightmost) in the current node.

int64_t	GetMinItem ()
	get min item (leftmost) in the current node

int64_t	GetItem (int8_t index)
	Get item of the \index index.

void	SetItem (int8_t index, int64_t new_item)
	Set item value at position of index.

int	InsertItem (int item)
	Insert item to the proper position of the node and return the position index.

void	InsertItemByIndex (int8_t index, int64_t item, Node *with_child, bool to_left=true)
	Insert a value to the index position.

Node *	RemoveItemByIndex (int8_t index, bool keep_left)
	Insert a value to the index position.

int8_t	GetChildIndex (Node *child)
	Get the child's index of the children array.

Node *	GetChild (int8_t index)
	Get the child pointer at position of index.

void	SetChild (int8_t index, Node *child)
	Set child pointer to the position of index.

Node *	GetRightmostChild ()
	Get rightmose child of the current node.

Node *	GetLeftmostChild ()
	Get leftmose child of the current node.

Node *	GetItemLeftChild (int8_t item_index)
	Get left child of item at item_index.

Node *	GetItemRightChild (int8_t item_index)
	Get right child of item at item_index.

Node *	GetNextPossibleChild (int64_t item)
	Get next node which is possibly contains item.

Private Attributes
std::array< int64_t, 3 >	items
	store items

std::array< Node *, 4 >	children
	store the children pointers

int8_t	count = 0
	track the current item count

Detailed Description

2-3-4 tree node class

Definition at line 35 of file tree_234.cpp.

Constructor & Destructor Documentation

◆ Node()

data_structures::tree_234::Node::Node ( int64_t item )

inlineexplicit

Node constructor.

Parameters

item	the first value we insert to the node

Definition at line 41 of file tree_234.cpp.

        : count(1),
          items({{item, 0, 0}}),
          children({{nullptr, nullptr, nullptr, nullptr}}) {}

Member Function Documentation

◆ Contains()

bool data_structures::tree_234::Node::Contains ( int64_t item )

inline

Check if item is in the node.

Parameters

item	item to check

Returns: true if item in the node, otherwise false

Definition at line 92 of file tree_234.cpp.

                                {
        for (int8_t i = 0; i < count; i++) {
            if (item == items[i]) {
                return true;
            }
        }
        return false;
    }

◆ GetChild()

Node * data_structures::tree_234::Node::GetChild ( int8_t index )

inline

Get the child pointer at position of index.

Parameters

index index of child to get

Returns: the child pointer

Definition at line 252 of file tree_234.cpp.

252{ return children[index]; }

◆ GetChildIndex()

int8_t data_structures::tree_234::Node::GetChildIndex ( Node * child )

inline

Get the child's index of the children array.

Parameters

child child pointer of which to get the index

Returns: the index of child

Definition at line 237 of file tree_234.cpp.

                                      {
        for (int8_t i = 0; i < count + 1; i++) {
            if (children[i] == child) {
                return i;
            }
        }
 
        return -1;
    }

◆ GetCount()

int8_t data_structures::tree_234::Node::GetCount ( )

inline

Get the item count that current saved in the node.

Returns: item count

Definition at line 50 of file tree_234.cpp.

50{ return count; }

◆ GetItem()

int64_t data_structures::tree_234::Node::GetItem ( int8_t index )

inline

Get item of the \index index.

Parameters

index the item index to get

Returns: the item

Definition at line 133 of file tree_234.cpp.

133{ return items[index]; }

◆ GetItemIndex()

int8_t data_structures::tree_234::Node::GetItemIndex ( int64_t item )

inline

Get the index of the item in the node, 0-based.

Parameters

item	item to check

Returns: 0-based index of the item in the node, if not in the node, -1 is returned

Definition at line 107 of file tree_234.cpp.

                                      {
        for (int8_t i = 0; i < count; i++) {
            if (items[i] == item) {
                return i;
            }
        }
        return -1;
    }

◆ GetItemLeftChild()

Node * data_structures::tree_234::Node::GetItemLeftChild ( int8_t item_index )

inline

Get left child of item at item_index.

Parameters

item_index index of the item whose left child to be get

Returns: left child of items[index]'s

Definition at line 278 of file tree_234.cpp.

                                              {
        if (item_index < 0 || item_index > count - 1) {
            return nullptr;
        }
 
        return children[item_index];
    }

◆ GetItemRightChild()

Node * data_structures::tree_234::Node::GetItemRightChild ( int8_t item_index )

inline

Get right child of item at item_index.

Parameters

item_index index of the item whose right child to be get

Returns: right child of items[index]'s

Definition at line 291 of file tree_234.cpp.

                                               {
        if (item_index < 0 || item_index > count - 1) {
            return nullptr;
        }
 
        return children[item_index + 1];
    }

◆ GetLeftmostChild()

Node * data_structures::tree_234::Node::GetLeftmostChild ( )

inline

Get leftmose child of the current node.

Returns: the leftmost child

Definition at line 271 of file tree_234.cpp.

271{ return children[0]; }

◆ GetMaxItem()

int64_t data_structures::tree_234::Node::GetMaxItem ( )

inline

Get max item (rightmost) in the current node.

Returns: max item

Definition at line 120 of file tree_234.cpp.

120{ return items[count - 1]; }

◆ GetMinItem()

int64_t data_structures::tree_234::Node::GetMinItem ( )

inline

get min item (leftmost) in the current node

Returns: min item

Definition at line 126 of file tree_234.cpp.

126{ return items[0]; }

◆ GetNextPossibleChild()

Node * data_structures::tree_234::Node::GetNextPossibleChild ( int64_t item )

inline

Get next node which is possibly contains item.

Parameters

item	item to search

Returns: the next node that possibly contains item

Definition at line 304 of file tree_234.cpp.

                                             {
        int i = 0;
        for (i = 0; i < count; i++) {
            if (items[i] > item) {
                break;
            }
        }
        return children[i];
    }

◆ GetRightmostChild()

Node * data_structures::tree_234::Node::GetRightmostChild ( )

inline

Get rightmose child of the current node.

Returns: the rightmost child

Definition at line 265 of file tree_234.cpp.

265{ return children[count]; }

◆ InsertItem()

int data_structures::tree_234::Node::InsertItem ( int item )

inline

Insert item to the proper position of the node and return the position index.

This is a helper function we use during insertion. Please mind that when insert a item, we aslo need to take care of two child pointers. One is the original child pointer at the insertion position. It can be placed as new item's either left child or right child. And the other is the new child that should be added. For our dedicated situation here, we choose to use the original child as the new item's left child, and add a null pointer to its right child. So after use the function, please update these two children pointer manually.

Parameters

item	value to be inserted to the node

Returns: index where item is inserted, caller can use this index to update its left and right child

Definition at line 163 of file tree_234.cpp.

                             {
        assert(!IsFull());
 
        if (Contains(item)) {
            return -1;
        }
 
        int8_t i = 0;
        for (i = 0; i < count; i++) {
            if (items[i] > item) {
                break;
            }
        }
 
        InsertItemByIndex(i, item, nullptr, true);
        return i;
    }

◆ InsertItemByIndex()

void data_structures::tree_234::Node::InsertItemByIndex	(	int8_t	index,
		int64_t	item,
		Node *	with_child,
		bool	to_left = true )

inline

Insert a value to the index position.

Parameters

index	index where to insert item
item	value to insert
with_child	new added child pointer
to_left	true indicate adding with_child to new item's left child, otherwise to right child

Definition at line 189 of file tree_234.cpp.

                                                {
        assert(count < 3 && index >= 0 && index < 3);
 
        for (int8_t i = count - 1; i >= index; i--) {
            items[i + 1] = items[i];
        }
 
        items[index] = item;
 
        int8_t start_index = to_left ? index : index + 1;
 
        for (int8_t i = count; i >= start_index; i--) {
            children[i + 1] = children[i];
        }
 
        children[start_index] = with_child;
 
        count++;
    }

◆ Is2Node()

bool data_structures::tree_234::Node::Is2Node ( )

inline

Check if node is a 2-node.

Returns: true if node is 2-node, otherwise false

Definition at line 79 of file tree_234.cpp.

79{ return count == 1; }

◆ Is34Node()

bool data_structures::tree_234::Node::Is34Node ( )

inline

Check if node is a 3-node or 4-node, this is useful when we delete item from 2-3-4 tree.

Returns: true if node is 3-node or 4-node, false otherwise

Definition at line 85 of file tree_234.cpp.

85{ return count == 2 || count == 3; }

◆ IsFull()

bool data_structures::tree_234::Node::IsFull ( )

inline

Check if node is a full (4-node)

Returns: true if node is full (4-node), false otherwise

Definition at line 73 of file tree_234.cpp.

73{ return count == 3; }

◆ IsLeaf()

bool data_structures::tree_234::Node::IsLeaf ( )

inline

Check if node is a leaf.

Returns: true if node is leaf, false otherwise

Definition at line 67 of file tree_234.cpp.

67{ return children[0] == nullptr; }

◆ RemoveItemByIndex()

Node * data_structures::tree_234::Node::RemoveItemByIndex	(	int8_t	index,
		bool	keep_left )

inline

Insert a value to the index position.

Parameters

index	index of the item to remove
keep_left	which child of the item to keep, true keep the left child, false keep the right child

Returns: the removed child pointer

Definition at line 217 of file tree_234.cpp.

                                                          {
        assert(index >= 0 && index < count);
        Node *removed_child = keep_left ? children[index + 1] : children[index];
        for (int8_t i = index; i < count - 1; i++) {
            items[i] = items[i + 1];
        }
 
        for (int8_t i = keep_left ? index + 1 : index; i < count; i++) {
            children[i] = children[i + 1];
        }
 
        count--;
        return removed_child;
    }

◆ SetChild()

void data_structures::tree_234::Node::SetChild	(	int8_t	index,
		Node *	child )

inline

Set child pointer to the position of index.

Parameters

index	children index
child	pointer to set

Definition at line 259 of file tree_234.cpp.

259{ children[index] = child; }

◆ SetCount()

void data_structures::tree_234::Node::SetCount ( int8_t c )

inline

Set the item count of the node.

This is only used when we spliting and merging node where we need to do some raw operation manually. In common inserting and removing operation the count is maintained automatically.

Parameters

c	the count to set

Definition at line 61 of file tree_234.cpp.

61{ count = c; }

◆ SetItem()

void data_structures::tree_234::Node::SetItem	(	int8_t	index,
		int64_t	new_item )

inline

Set item value at position of index.

Parameters

index	the index of the item to set
new_item	item value

Definition at line 140 of file tree_234.cpp.

                                                 {
        assert(index >= 0 && index <= 2);
 
        items[index] = new_item;
    }

Member Data Documentation

◆ children

std::array<Node *, 4> data_structures::tree_234::Node::children

private

store the children pointers

Definition at line 317 of file tree_234.cpp.

◆ count

int8_t data_structures::tree_234::Node::count = 0

private

track the current item count

Definition at line 319 of file tree_234.cpp.

◆ items

std::array<int64_t, 3> data_structures::tree_234::Node::items

private

store items

Definition at line 315 of file tree_234.cpp.

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

data_structures/tree_234.cpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Node()

Member Function Documentation

◆ Contains()

◆ GetChild()

◆ GetChildIndex()

◆ GetCount()

◆ GetItem()

◆ GetItemIndex()

◆ GetItemLeftChild()

◆ GetItemRightChild()

◆ GetLeftmostChild()

◆ GetMaxItem()

◆ GetMinItem()

◆ GetNextPossibleChild()

◆ GetRightmostChild()

◆ InsertItem()

◆ InsertItemByIndex()

◆ Is2Node()

◆ Is34Node()

◆ IsFull()

◆ IsLeaf()

◆ RemoveItemByIndex()

◆ SetChild()

◆ SetCount()

◆ SetItem()

Member Data Documentation

◆ children

◆ count

◆ items