Changeset 61

Show
Ignore:
Timestamp:
1999-09-17 15:47:14 (9 years ago)
Author:
olly
Message:

build up frequency balanced tree of MergedPostList?-s
get_termfreq now const to facilitate this

Location:
trunk/xapian-core
Files:
5 modified

Legend:

Unmodified
Added
Removed

  • trunk/xapian-core/backends/da/da_database.cc

    r60 r61  
    2626} 
    2727 
    28 doccount DAPostList::get_termfreq() { 
     28doccount DAPostList::get_termfreq() const { 
    2929    return termfreq; 
    3030} 

  • trunk/xapian-core/backends/da/da_database.h

    r60 r61  
    1919        ~DAPostList(); 
    2020 
    21         doccount get_termfreq();  
     21        doccount get_termfreq() const; 
    2222 
    2323        docid  get_docid();     // Gets current docid 

  • trunk/xapian-core/common/database.h

    r57 r61  
    3939    private: 
    4040    public: 
    41         virtual doccount get_termfreq() = 0;// Gets number of docs indexed by this term 
     41        virtual doccount get_termfreq() const = 0;// Gets number of docs indexed by this term 
    4242 
    4343        virtual docid  get_docid() = 0;     // Gets current docid 
    … …  
    4949 
    5050        virtual ~PostList() { return; } 
     51 
     52        virtual bool operator < (const PostList *x) const 
     53        { 
     54            return get_termfreq() > x->get_termfreq(); 
     55        } 
    5156}; 
    5257 

  • trunk/xapian-core/common/match.h

    r35 r61  
    11#include "database.h" 
    22#include "mergedpostlist.h" 
     3 
     4#include <queue> 
    35 
    46class Match { 
    57    private: 
    68        IRDatabase *DB; 
     9    
    710        PostList *merger; 
    811//        const int msize = 1000; 
     12 
     13        priority_queue<PostList *> pq; 
    914 
    1015    public: 

  • trunk/xapian-core/matcher/match.cc

    r59 r61  
    1515 
    1616    PostList *postlist = DB->open_post_list(id); 
    17     if (merger) { 
    18         // FIXME: want to build a tree balanced by the term frequencies 
    19         // (similar to a huffman encoding tree) 
    20         merger = new MergedPostList(merger, postlist); 
    21     } else { 
    22         merger = postlist; 
    23     } 
     17    
     18    pq.push(postlist); 
     19    
    2420    return true; 
    2521} 
    … …  
    3430void 
    3531Match::match(void) 
    36 { 
    37     if (!merger) return; 
     32{     
     33    if (!merger) { 
     34        if (pq.empty()) return; // No terms in query 
     35 
     36        PostList *tmp; 
     37        
     38        // build a tree balanced by the term frequencies 
     39        // (similar to a huffman encoding tree) 
     40        while (true) { 
     41            tmp = pq.top(); 
     42            pq.pop(); 
     43            if (pq.empty()) break; 
     44            tmp = new MergedPostList(pq.top(), tmp); 
     45            pq.pop(); 
     46            pq.push(tmp); 
     47        } 
     48        
     49        merger = tmp; 
     50    } 
    3851 
    3952    docid msize = 0, mtotal = 0;