trie.cpp

来自「数据挖掘的算法」· C++ 代码 · 共 102 行

 
 
 #include "Trie.hpp"
 #include <cstdlib>
 #include <iostream>
 #include <algorithm>
 
 bool Edge_point_less(const Edge edge, const itemtype label)
 {
    return edge.label < label;
 };
 
 const Trie* Trie::is_included( const set<itemtype>& an_itemset, 
                                set<itemtype>::const_iterator item_it ) const
 {
    if( item_it == an_itemset.end() ) return this;
    else
    {
       vector<Edge>::const_iterator it_edgevector = 
          lower_bound(edgevector.begin(), edgevector.end(), 
                      *item_it, Edge_point_less);
       if( it_edgevector != edgevector.end() && 
           (*it_edgevector).label == *item_it )
          return (*it_edgevector).subtrie->is_included( an_itemset, ++item_it );
       else return NULL;
    }
 }
 
 void Trie::find_candidate( 
    vector<itemtype>::const_iterator it_basket_upper_bound,
    vector<itemtype>::const_iterator it_basket, 
    const countertype counter_incr )
 {
    if( edgevector.empty() ) 
       counter += counter_incr;
    else
    {
         
          vector<Edge>::iterator it_edge = edgevector.begin();
          while( it_edge != edgevector.end() && 
                 it_basket != it_basket_upper_bound )
          {
             if( (*it_edge).label < *it_basket) ++it_edge;
             else if( (*it_edge).label > *it_basket) ++it_basket;
             else
             {
                (*it_edge).subtrie->find_candidate( it_basket_upper_bound + 1, 
                                                    it_basket + 1, 
                                                    counter_incr);
                ++it_edge;
                ++it_basket;
             }
          }
    }
 }
 
 void Trie::delete_infrequent( const double min_occurrence )
 {
    vector<Edge>::iterator itEdge = edgevector.begin();
    while(itEdge != edgevector.end() )
    {
       if( (*itEdge).subtrie->edgevector.empty() )
       {
          if( (*itEdge).subtrie->counter < min_occurrence )
          {
             delete (*itEdge).subtrie;
             itEdge = edgevector.erase(itEdge);
          }
          else ++itEdge;
       }
       else
       {
          (*itEdge).subtrie->delete_infrequent( min_occurrence );
 
          if( (*itEdge).subtrie->edgevector.empty() )
          {
             delete (*itEdge).subtrie;
             itEdge = edgevector.erase(itEdge);
          }
          else ++itEdge;
       }
    }
 }
 
 
 Trie::~Trie()
 {
    for( vector<Edge>::iterator itEdge = edgevector.begin();
         itEdge != edgevector.end(); ++itEdge )
       delete (*itEdge).subtrie;
 }
 
 
 void Trie::add_empty_state( const itemtype item, const countertype counter )
 {
    Edge temp_edge;
    temp_edge.label = item;
    temp_edge.subtrie = new Trie( counter );
    edgevector.push_back(temp_edge);
 }