Trie Class Reference

This class represent a general Trie. More...

#include <Trie.hpp>

Collaboration diagram for Trie:

[legend]List of all members.

Public Member Functions
	Trie (Trie *parent_trie, const unsigned long init_counter)
const Trie *	is_included (const set< itemtype > &an_itemset, set< itemtype >::const_iterator item_it) const
	It decides whether the given itemset is included in the trie or not.
void	find_candidate (const vector< itemtype > &basket, const itemtype distance_from_candidate, vector< itemtype >::const_iterator it_basket, const unsigned long counter_incr=1)
	Increases the counter for those itemsets that is contained by the given basket.
void	delete_infrequent (const double min_occurrence, const itemtype distance_from_candidate)
	Deletes the tries that represent infrequent itemsets.
void	show_content_preorder () const
	Shows the content in a preorder manner.
	~Trie ()
Private Member Functions
void	max_path_set ()
	Sets the maximal path value.
void	add_empty_state (const itemtype item, const unsigned long init_counter=0)
	Adds an empty state to the trie.
Private Attributes
Trie *	parent
	parent stores the address of the parent of the Trie.
unsigned long	counter
	counter stores the occurrence of the itemset represented by the Trie
vector< Edge >	edgevector
	edgevector stores the edges of the root the trie.
itemtype	maxpath
	maxpath stores the length of the longest path starting from the root node.
Friends
class	MSApriori_Trie

---

Detailed Description

This class represent a general Trie.

We can regard the trie as a recursive data structure. It has a root node and a list of (sub)trie. We can reach a subtree by a labeled edge (link). Since the root of the trie represents an itemset the counter stands for the occurrence. For the sake of fast traversal we also store the parent of a trie, the length of the maximal path starting from the root, and the edges are stored ordered according to their label.

Definition at line 44 of file Trie.hpp.

---

Constructor & Destructor Documentation

Trie::Trie (  Trie *  parent_trie, const unsigned long  init_counter )

Parameters: parent_trie  The pointer to the parent of the new trie init_counter  The initial counter of the new trie Definition at line 24 of file Trie.cpp. Referenced by add_empty_state().

Trie::~Trie (   )

Definition at line 128 of file Trie.cpp. References edgevector.

---

Member Function Documentation

void Trie::add_empty_state (  const itemtype  item, const unsigned long  counter = 0 )  [private]

Adds an empty state to the trie. Parameters: item  The label of the new edge counter  The initial counter of the new state Definition at line 150 of file Trie.cpp. References edgevector, itemtype, Edge::label, Edge::subtrie, and Trie(). Referenced by MSApriori_Trie::candidate_generation_assist(), and MSApriori_Trie::insert_frequent_items().

void Trie::delete_infrequent (  const double  min_occurrence, const itemtype  distance_from_candidate_parent )

Deletes the tries that represent infrequent itemsets. Parameters: min_occurrence  The occurence threshold distance_from_candidate_parent  The length of the path from the root of the actual tre to a root of the trie that represents the parent of a candidate Definition at line 89 of file Trie.cpp. References edgevector, itemtype, max_path_set(), maxpath, and parent.

void Trie::find_candidate (  const vector< itemtype > &  basket, const itemtype  distance_from_candidate, vector< itemtype >::const_iterator  it_basket, const unsigned long  counter_incr = 1 )

Increases the counter for those itemsets that is contained by the given basket. Parameters: basket  the given basket distance_from_candidate  The length of the path from the actual trie to a trie that represents a candidate it_basket  *it_basket lead to the actual Trie. Only items following this item in the basket need to be considered counter_incr  The number times this basket occurs Definition at line 58 of file Trie.cpp. References counter, edgevector, and itemtype. Referenced by MSApriori_Trie::find_candidate().

const Trie * Trie::is_included (  const set< itemtype > &  an_itemset, set< itemtype >::const_iterator  item_it )  const

It decides whether the given itemset is included in the trie or not. Parameters: an_itemset  The given itemset. item_it  This iterator shows the element of the basket that has to be processed. Returns: NULL, if the itemset is not included, otherwise the trie, that represents the itemset. Definition at line 38 of file Trie.cpp. References Edge_point_less(), and edgevector. Referenced by MSApriori_Trie::assoc_rule_find(), and MSApriori_Trie::is_all_subset_frequent().

void Trie::max_path_set (   )  [private]

Sets the maximal path value. Definition at line 134 of file Trie.cpp. References edgevector, itemtype, maxpath, and parent. Referenced by MSApriori_Trie::candidate_generation_assist(), delete_infrequent(), and MSApriori_Trie::delete_infrequent_two().

void Trie::show_content_preorder (   )  const

Shows the content in a preorder manner. Definition at line 117 of file Trie.cpp. References counter, edgevector, and maxpath. Referenced by MSApriori_Trie::show_content_preorder().

---

Friends And Related Function Documentation

friend class MSApriori_Trie [friend]

Definition at line 46 of file Trie.hpp.

---

Member Data Documentation

unsigned long Trie::counter [private]

counter stores the occurrence of the itemset represented by the Trie Definition at line 82 of file Trie.hpp. Referenced by MSApriori_Trie::assoc_rule_assist(), MSApriori_Trie::assoc_rule_find(), find_candidate(), show_content_preorder(), MSApriori_Trie::write_content_to_file(), and MSApriori_Trie::write_content_to_file_assist().

vector<Edge> Trie::edgevector [private]

edgevector stores the edges of the root the trie. edgevector is always sorted! Definition at line 88 of file Trie.hpp. Referenced by add_empty_state(), MSApriori_Trie::assoc_rule_assist(), MSApriori_Trie::candidate_generation_assist(), delete_infrequent(), MSApriori_Trie::delete_infrequent(), MSApriori_Trie::delete_infrequent_two(), find_candidate(), MSApriori_Trie::insert_frequent_items(), is_included(), max_path_set(), show_content_preorder(), MSApriori_Trie::write_content_to_file_assist(), and ~Trie().

itemtype Trie::maxpath [private]

maxpath stores the length of the longest path starting from the root node. Definition at line 91 of file Trie.hpp. Referenced by MSApriori_Trie::candidate_generation(), MSApriori_Trie::candidate_generation_assist(), MSApriori_Trie::candidate_generation_two(), delete_infrequent(), MSApriori_Trie::insert_frequent_items(), MSApriori_Trie::longest_path(), max_path_set(), show_content_preorder(), and MSApriori_Trie::write_content_to_file().

Trie* Trie::parent [private]

parent stores the address of the parent of the Trie. Definition at line 79 of file Trie.hpp. Referenced by delete_infrequent(), and max_path_set().

---

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

• Trie.hpp
• Trie.cpp

---