📄 trie_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>APRIORI algorithm: Trie.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>Trie.cpp</h1><a href="Trie_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 <span class="comment">/***************************************************************************</span>00002 <span class="comment"> Trie.cpp - description</span>00003 <span class="comment"> -------------------</span>00004 <span class="comment"> begin : cs dec 26 2002</span>00005 <span class="comment"> copyright : (C) 2002 by Ferenc Bodon</span>00006 <span class="comment"> email : bodon@mit.bme.hu</span>00007 <span class="comment"> ***************************************************************************/</span>00008 00009 00010 <span class="preprocessor">#include "<a class="code" href="Trie_8hpp.html">Trie.hpp</a>"</span>00011 <span class="preprocessor">#include <cstdlib></span>00012 <span class="preprocessor">#include <iostream></span>00013 <span class="preprocessor">#include <algorithm></span>00014 <a name="l00015"></a><a class="code" href="Trie_8hpp.html#a0">00015</a> <span class="keywordtype">bool</span> <a class="code" href="Trie_8hpp.html#a0">Edge_point_less</a>(<span class="keyword">const</span> <a class="code" href="structEdge.html">Edge</a> edge, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> label)00016 {00017 <span class="keywordflow">return</span> edge.<a class="code" href="structEdge.html#o0">label</a> < label;00018 };00019 <a name="l00024"></a><a class="code" href="classTrie.html#a0">00024</a> <a class="code" href="classTrie.html#a0">Trie::Trie</a>(<a class="code" href="classTrie.html">Trie</a>* parent_trie, 00025 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> init_counter):00026 parent(parent_trie),00027 counter(init_counter),00028 maxpath(0)00029 {00030 }00031 <a name="l00038"></a><a class="code" href="classTrie.html#a1">00038</a> <span class="keyword">const</span> <a class="code" href="classTrie.html">Trie</a>* <a class="code" href="classTrie.html#a1">Trie::is_included</a>( <span class="keyword">const</span> set<itemtype>& an_itemset, 00039 set<itemtype>::const_iterator item_it )<span class="keyword"> const</span>00040 <span class="keyword"></span>{00041 <span class="keywordflow">if</span>( item_it == an_itemset.end() ) <span class="keywordflow">return</span> <span class="keyword">this</span>;00042 <span class="keywordflow">else</span>00043 {00044 vector<Edge>::const_iterator it_edgevector = 00045 lower_bound(<a class="code" href="classTrie.html#r2">edgevector</a>.begin(), <a class="code" href="classTrie.html#r2">edgevector</a>.end(), *item_it, <a class="code" href="Trie_8cpp.html#a0">Edge_point_less</a>);00046 <span class="keywordflow">if</span>( it_edgevector != <a class="code" href="classTrie.html#r2">edgevector</a>.end() && (*it_edgevector).label == *item_it)00047 <span class="keywordflow">return</span> (*it_edgevector).subtrie-><a class="code" href="classTrie.html#a1">is_included</a>( an_itemset, ++item_it );00048 <span class="keywordflow">else</span> <span class="keywordflow">return</span> NULL;00049 }00050 }00051 <a name="l00058"></a><a class="code" href="classTrie.html#a2">00058</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#a2">Trie::find_candidate</a>( <span class="keyword">const</span> vector<itemtype>& basket, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> distance_from_candidate,00059 vector<itemtype>::const_iterator it_basket, <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> counter_incr)00060 {00061 <span class="keywordflow">if</span>( distance_from_candidate )00062 {00063 <span class="keywordflow">if</span> (distance_from_candidate < (<a class="code" href="common_8hpp.html#a0">itemtype</a>)(basket.end() - it_basket) + 1)00064 {00065 vector<itemtype>::const_iterator it_basket_upper_bound = basket.end() - distance_from_candidate + 1;00066 vector<Edge>::iterator it_edge = <a class="code" href="classTrie.html#r2">edgevector</a>.begin();00067 00068 <span class="keywordflow">while</span>( it_edge != <a class="code" href="classTrie.html#r2">edgevector</a>.end() && it_basket != it_basket_upper_bound )00069 {00070 <span class="keywordflow">if</span>( (*it_edge).label < *it_basket) it_edge++;00071 <span class="keywordflow">else</span> <span class="keywordflow">if</span>( (*it_edge).label > *it_basket) it_basket++;00072 <span class="keywordflow">else</span>00073 {00074 <span class="keywordflow">if</span>( (*it_edge).subtrie->maxpath + 1 == distance_from_candidate )00075 (*it_edge).subtrie->find_candidate( basket, distance_from_candidate - 1, it_basket + 1, counter_incr);00076 it_edge++;00077 it_basket++;00078 }00079 }00080 }00081 }00082 <span class="keywordflow">else</span> <a class="code" href="classTrie.html#r1">counter</a> += counter_incr;00083 }00084 <a name="l00089"></a><a class="code" href="classTrie.html#a3">00089</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#a3">Trie::delete_infrequent</a>( <span class="keyword">const</span> <span class="keywordtype">double</span> min_occurrence, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> distance_from_candidate_parent )00090 {00091 vector<Edge>::iterator itEdge = <a class="code" href="classTrie.html#r2">edgevector</a>.begin();00092 <span class="keywordflow">if</span>( distance_from_candidate_parent )00093 {00094 <span class="keywordflow">for</span>( ;itEdge != <a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )00095 <span class="keywordflow">if</span>( (*itEdge).subtrie->maxpath == distance_from_candidate_parent )00096 (*itEdge).subtrie->delete_infrequent( min_occurrence, distance_from_candidate_parent - 1 );00097 }00098 <span class="keywordflow">else</span>00099 {00100 <span class="keywordflow">while</span> ( itEdge != <a class="code" href="classTrie.html#r2">edgevector</a>.end() )00101 {00102 <span class="keywordflow">if</span>( (*itEdge).subtrie->counter < min_occurrence )00103 {00104 <span class="keyword">delete</span> (*itEdge).subtrie;00105 itEdge = <a class="code" href="classTrie.html#r2">edgevector</a>.erase(itEdge);00106 }00107 <span class="keywordflow">else</span> itEdge++;00108 }00109 <span class="keywordflow">if</span>( <a class="code" href="classTrie.html#r2">edgevector</a>.empty() )00110 {00111 <a class="code" href="classTrie.html#r3">maxpath</a> = 0;00112 <a class="code" href="classTrie.html#r0">parent</a>-><a class="code" href="classTrie.html#d0">max_path_set</a>();00113 }00114 }00115 }00116 <a name="l00117"></a><a class="code" href="classTrie.html#a4">00117</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#a4">Trie::show_content_preorder</a>( )<span class="keyword"> const</span>00118 <span class="keyword"></span>{00119 cout<<<span class="stringliteral">"\ncounter: "</span><<<a class="code" href="classTrie.html#r1">counter</a><<<span class="stringliteral">" maxpath: "</span><<<a class="code" href="classTrie.html#r3">maxpath</a>;00120 <span class="keywordflow">for</span>( vector<Edge>::const_iterator itEdge = <a class="code" href="classTrie.html#r2">edgevector</a>.begin(); itEdge != <a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )00121 {00122 cout<<<span class="stringliteral">"\nitem"</span><<(*itEdge).label<<<span class="stringliteral">" leads to the Trie, where"</span>;00123 (*itEdge).subtrie->show_content_preorder();00124 }00125 cout<<<span class="stringliteral">"\nNo more edges. Let's go back to the parent!"</span>;00126 }00127 <a name="l00128"></a><a class="code" href="classTrie.html#a5">00128</a> <a class="code" href="classTrie.html#a5">Trie::~Trie</a>()00129 {00130 <span class="keywordflow">for</span>( vector<Edge>::iterator itEdge = <a class="code" href="classTrie.html#r2">edgevector</a>.begin(); itEdge != <a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )00131 <span class="keyword">delete</span> (*itEdge).subtrie;00132 }00133 <a name="l00134"></a><a class="code" href="classTrie.html#d0">00134</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#d0">Trie::max_path_set</a>( )00135 {00136 <a class="code" href="common_8hpp.html#a0">itemtype</a> temp_max_path = 0;00137 <span class="keywordflow">for</span>( vector<Edge>::iterator itEdge = <a class="code" href="classTrie.html#r2">edgevector</a>.begin(); itEdge != <a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )00138 <span class="keywordflow">if</span>( temp_max_path < (*itEdge).subtrie->maxpath ) temp_max_path=(*itEdge).subtrie->maxpath;00139 <span class="keywordflow">if</span>( <a class="code" href="classTrie.html#r3">maxpath</a> != temp_max_path + 1)00140 {00141 <a class="code" href="classTrie.html#r3">maxpath</a> = temp_max_path + 1;00142 <span class="keywordflow">if</span>( <a class="code" href="classTrie.html#r0">parent</a>!=NULL ) <a class="code" href="classTrie.html#r0">parent</a>-><a class="code" href="classTrie.html#d0">max_path_set</a>( );00143 }00144 }00145 <a name="l00150"></a><a class="code" href="classTrie.html#d1">00150</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#d1">Trie::add_empty_state</a>( <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> item, <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> counter )00151 {00152 <a class="code" href="structEdge.html">Edge</a> temp_edge;00153 temp_edge.<a class="code" href="structEdge.html#o0">label</a> = item;00154 temp_edge.<a class="code" href="structEdge.html#o1">subtrie</a> = <span class="keyword">new</span> <a class="code" href="classTrie.html#a0">Trie</a>( <span class="keyword">this</span>, counter );00155 <a class="code" href="classTrie.html#r2">edgevector</a>.push_back(temp_edge);00156 }</pre></div><hr size="1"><address style="align: right;"><small>Generated on Sun Jun 20 23:41:08 2004 for APRIORI algorithm by<a href="http://www.doxygen.org/index.html"><img src="doxygen.png" alt="doxygen" align="middle" border=0 > </a>1.3.5 </small></address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -