00001 #ifndef SupportCounterMerge2_HPP
00002 #define SupportCounterMerge2_HPP
00003
00004 #include <algorithm>
00005 #include "common.hpp"
00006 #include <vector>
00007 #include "apriori/bodon/Leaf.hpp"
00008
00009
00010
00011
00012
00013
00014 namespace Bodon
00015 {
00016 namespace sequence
00017 {
00018 template <class TRIE>
00019 class SupportCounterMerge2
00020 {
00021 private:
00022 typedef std::pair<item_t, std::vector<item_t>::const_iterator> SeqFirstOcc;
00023
00024 public:
00025 SupportCounterMerge2( ){}
00026
00029 void findCandidates( TRIE* subtrie,
00030 std::vector<item_t>::const_iterator it_transaction_upper_bound,
00031 std::vector<item_t>::const_iterator it_transaction,
00032 item_t step_to_candidate,
00033 const counter_t counter_incr );
00034
00035
00036 };
00037
00038 template <class TRIE> void
00039 SupportCounterMerge2<TRIE>::findCandidates(
00040 TRIE* subtrie, std::vector<item_t>::const_iterator it_transaction_upper_bound,
00041 std::vector<item_t>::const_iterator it_transaction,
00042 item_t step_to_candidate, const counter_t counter_incr )
00043 {
00044 --step_to_candidate;
00045 vector<bool>::size_type largestEdgelabel =
00046 subtrie->edgelist.largestEdgelabel();
00047 vector<bool>::size_type smallestEdgelabel =
00048 subtrie->edgelist.smallestEdgelabel();
00049 vector<bool> pattern(largestEdgelabel + 1 - smallestEdgelabel, true);
00050 typename std::vector<SupportCounterMerge2<TRIE>::SeqFirstOcc>
00051 first_occ;
00052 first_occ.reserve(it_transaction_upper_bound - it_transaction);
00053 while(it_transaction != it_transaction_upper_bound)
00054 if(*it_transaction <= largestEdgelabel &&
00055 *it_transaction >= smallestEdgelabel &&
00056 pattern[*it_transaction - smallestEdgelabel])
00057 {
00058 pattern[*it_transaction - smallestEdgelabel] = false;
00059 first_occ.push_back(SupportCounterMerge2<TRIE>::SeqFirstOcc(
00060 *it_transaction, ++it_transaction));
00061 }
00062 else
00063 ++it_transaction;
00064 std::sort(first_occ.begin(), first_occ.end() );
00065
00066 typename TRIE::iterator it_edge(subtrie->edgelist.begin());
00067 typename std::vector<SupportCounterMerge2<TRIE>::SeqFirstOcc>::const_iterator
00068 it_transaction2(first_occ.begin());
00069 while( it_edge != subtrie->edgelist.end() &&
00070 it_transaction2 != first_occ.end() )
00071 {
00072 if( (*it_edge).first < (*it_transaction2).first ) ++it_edge;
00073 else if( (*it_edge).first > (*it_transaction2).first ) ++it_transaction2;
00074 else
00075 {
00076 if( step_to_candidate )
00077 findCandidates( static_cast<TRIE*>((*it_edge).second),
00078 it_transaction_upper_bound + 1, (*it_transaction2).second,
00079 step_to_candidate, counter_incr);
00080 else
00081 static_cast<Leaf*>((*it_edge).second)->increaseCounter( counter_incr);
00082 ++it_transaction2;
00083 ++it_edge;
00084 }
00085 }
00086 }
00087 }
00088 }
00089 #endif
