📄 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.9.1 --><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 class="fragment">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@cs.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_8cpp.html#a0">00015</a> <span class="keywordtype">bool</span> <a class="code" href="Trie_8cpp.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> itemtype label)00016 {00017 <span class="keywordflow">return</span> edge.<a class="code" href="structEdge.html#o0">label</a> < label;00018 };00019 <a name="l00028"></a><a class="code" href="classTrie.html#a1">00028</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, 00029 set<itemtype>::const_iterator item_it )<span class="keyword"> const</span>00030 <span class="keyword"></span>{00031 <span class="keywordflow">if</span>( item_it == an_itemset.end() ) <span class="keywordflow">return</span> <span class="keyword">this</span>;00032 <span class="keywordflow">else</span>00033 {00034 vector<Edge>::const_iterator it_edgevector = 00035 lower_bound(<a class="code" href="classTrie.html#r1">edgevector</a>.begin(), <a class="code" href="classTrie.html#r1">edgevector</a>.end(), 00036 *item_it, Edge_point_less);00037 <span class="keywordflow">if</span>( it_edgevector != <a class="code" href="classTrie.html#r1">edgevector</a>.end() && 00038 (*it_edgevector).label == *item_it )00039 <span class="keywordflow">return</span> (*it_edgevector).subtrie-><a class="code" href="classTrie.html#a1">is_included</a>( an_itemset, ++item_it );00040 <span class="keywordflow">else</span> <span class="keywordflow">return</span> NULL;00041 }00042 }00043 <a name="l00051"></a><a class="code" href="classTrie.html#a2">00051</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#a2">Trie::find_candidate</a>( 00052 vector<itemtype>::const_iterator it_basket_upper_bound,00053 vector<itemtype>::const_iterator it_basket, 00054 <span class="keyword">const</span> countertype counter_incr )00055 {00056 <span class="keywordflow">if</span>( <a class="code" href="classTrie.html#r1">edgevector</a>.empty() ) 00057 <a class="code" href="classTrie.html#r0">counter</a> += counter_incr;00058 <span class="keywordflow">else</span>00059 {00060 00061 vector<Edge>::iterator it_edge = <a class="code" href="classTrie.html#r1">edgevector</a>.begin();00062 <span class="keywordflow">while</span>( it_edge != <a class="code" href="classTrie.html#r1">edgevector</a>.end() && 00063 it_basket != it_basket_upper_bound )00064 {00065 <span class="keywordflow">if</span>( (*it_edge).label < *it_basket) ++it_edge;00066 <span class="keywordflow">else</span> <span class="keywordflow">if</span>( (*it_edge).label > *it_basket) ++it_basket;00067 <span class="keywordflow">else</span>00068 {00069 (*it_edge).subtrie-><a class="code" href="classTrie.html#a2">find_candidate</a>( it_basket_upper_bound + 1, 00070 it_basket + 1, 00071 counter_incr);00072 ++it_edge;00073 ++it_basket;00074 }00075 }00076 }00077 }00078 <a name="l00082"></a><a class="code" href="classTrie.html#a3">00082</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 )00083 {00084 vector<Edge>::iterator itEdge = <a class="code" href="classTrie.html#r1">edgevector</a>.begin();00085 <span class="keywordflow">while</span>(itEdge != <a class="code" href="classTrie.html#r1">edgevector</a>.end() )00086 {00087 <span class="keywordflow">if</span>( (*itEdge).subtrie->edgevector.empty() )00088 {00089 <span class="keywordflow">if</span>( (*itEdge).subtrie->counter < min_occurrence )00090 {00091 <span class="keyword">delete</span> (*itEdge).subtrie;00092 itEdge = <a class="code" href="classTrie.html#r1">edgevector</a>.erase(itEdge);00093 }00094 <span class="keywordflow">else</span> ++itEdge;00095 }00096 <span class="keywordflow">else</span>00097 {00098 (*itEdge).subtrie-><a class="code" href="classTrie.html#a3">delete_infrequent</a>( min_occurrence );00099 00100 <span class="keywordflow">if</span>( (*itEdge).subtrie->edgevector.empty() )00101 {00102 <span class="keyword">delete</span> (*itEdge).subtrie;00103 itEdge = <a class="code" href="classTrie.html#r1">edgevector</a>.erase(itEdge);00104 }00105 <span class="keywordflow">else</span> ++itEdge;00106 }00107 }00108 }00109 00110 <a name="l00111"></a><a class="code" href="classTrie.html#a4">00111</a> <a class="code" href="classTrie.html#a4">Trie::~Trie</a>()00112 {00113 <span class="keywordflow">for</span>( vector<Edge>::iterator itEdge = <a class="code" href="classTrie.html#r1">edgevector</a>.begin();00114 itEdge != <a class="code" href="classTrie.html#r1">edgevector</a>.end(); ++itEdge )00115 <span class="keyword">delete</span> (*itEdge).subtrie;00116 }00117 00118 <a name="l00123"></a><a class="code" href="classTrie.html#d0">00123</a> <span class="keywordtype">void</span> <a class="code" href="classTrie.html#d0">Trie::add_empty_state</a>( <span class="keyword">const</span> itemtype item, <span class="keyword">const</span> countertype counter )00124 {00125 <a class="code" href="structEdge.html">Edge</a> temp_edge;00126 temp_edge.<a class="code" href="structEdge.html#o0">label</a> = item;00127 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>( counter );00128 <a class="code" href="classTrie.html#r1">edgevector</a>.push_back(temp_edge);00129 }</pre></div><hr size="1"><address style="align: right;"><small>Generated on Fri Mar 11 14:48:06 2005 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.9.1 </small></address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -