Trie Class Reference

String-trie class for storing reserved words. More...

#include <Trie.h>

Collaboration diagram for Trie:

Public Member Functions
	Trie ()
	Default constructor.
	Trie (const Trie &)=delete
	There is no copy constructor for this class.
	~Trie ()
	Destructor.
void	add (std::string::iterator itBeg, std::string::iterator itEnd, TrieNode *start=nullptr)
	Adding a new word to the trie.
TrieNode *	find (std::string::iterator itBeg, std::string::iterator itEnd, TrieNode *start=nullptr)
	Searching for a string in the trie.
void	clear ()
	Full trie clearing.
int	get_size ()
	Gets the number of rows added to the trie.

Private Attributes
TrieNode *	_root

Detailed Description

String-trie class for storing reserved words.

Definition at line 67 of file Trie.h.

Constructor & Destructor Documentation

Trie() [1/2]

Trie::Trie

(

)

Default constructor.

Definition at line 30 of file Trie.cpp.

References _root.

Trie() [2/2]

Trie::Trie ( const Trie & )

delete

There is no copy constructor for this class.

~Trie()

Trie::~Trie

(

)

Destructor.

Calls root node destructor, causing all trie nodes to be removed.

Definition at line 33 of file Trie.cpp.

References _root.

Member Function Documentation

add()

void Trie::add	(	std::string::iterator	itBeg,
		std::string::iterator	itEnd,
		TrieNode *	start = nullptr )

Adding a new word to the trie.

Recursively adds a string to the tree. Asymptotics of the operation O(|S|), where |S| is the length of the input string.

Parameters

itBeg	Iterator to the beginning of the string
itEnd	Iterator to the end of the string
start	Pointer to the node from which to start adding the string. If equal to nullptr, the addition will start from the root node.

Definition at line 37 of file Trie.cpp.

References _root, add(), TrieNode::get_count(), TrieNode::get_ends(), and TrieNode::get_next().

Referenced by add(), and LexicalAnalyzer::LexicalAnalyzer().

clear()

void Trie::clear

(

)

Full trie clearing.

Definition at line 71 of file Trie.cpp.

References _root.

find()

TrieNode * Trie::find	(	std::string::iterator	itBeg,
		std::string::iterator	itEnd,
		TrieNode *	start = nullptr )

Searching for a string in the trie.

Recursively finds the given string in boron. The asymptotics of the operation is O(|SS|), where |S| is the length of the input string.

Parameters

itBeg	Iterator to the beginning of the string
itEnd	Iterator to the end of the string
start	Pointer to the node from which to start finding the string. If equal to nullptr, the finding will start from the root node.

Returns

A pointer to the last string node found in the tree, or nullptr if there is no such string.

Definition at line 57 of file Trie.cpp.

References _root, find(), TrieNode::get_ends(), and TrieNode::get_next().

Referenced by find(), and LexicalAnalyzer::is_service().

get_size()

int Trie::get_size

(

)

Gets the number of rows added to the trie.

Returns

The number of rows in the tree.

Definition at line 75 of file Trie.cpp.

References _root, and TrieNode::get_count().

Member Data Documentation

_root

TrieNode* Trie::_root

private

Definition at line 116 of file Trie.h.

Referenced by add(), clear(), find(), get_size(), Trie(), and ~Trie().

---

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

• D:/GitHub/AALanguage2/AALanguage/Trie.h
• D:/GitHub/AALanguage2/AALanguage/Trie.cpp