remove winner_tree.*

2 files changed, 0 insertions, 291 deletions

diff --git a/src/lookup/winner_tree.cpp b/src/lookup/winner_tree.cpp
deleted file mode 100644
index 35e92ae..0000000
--- a/src/lookup/winner_tree.cpp
+++ /dev/null
@@ -1,142 +0,0 @@
-/* 
- *  libpinyin
- *  Library to deal with pinyin.
- *  
- *  Copyright (C) 2006-2007 Peng Wu
- *  
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- * 
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- *  GNU General Public License for more details.
- *  
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
- */
-
-#include <float.h>
-#include <limits.h>
-#include <stdio.h>
-#include "memory_chunk.h"
-#include "phrase_index.h"
-#include "pinyin_lookup.h"
-#include "winner_tree.h"
-
-using namespace pinyin;
-
-WinnerTreeBranchIterator::WinnerTreeBranchIterator(WinnerTree & tree)
-    :m_tree(tree), m_counter(0){
-    m_max_value = m_tree.m_items[m_tree.get_winner()];
-    m_counter = 0;
-}
-
-bool WinnerTreeBranchIterator::has_next(){
-    if ( m_counter >= m_tree.m_tree_size)
-	return false;
-    return m_counter < nbranch;
-}
-
-lookup_value_t WinnerTreeBranchIterator::next(){
-    int winner = m_tree.get_winner();
-    lookup_value_t tmp = m_tree.m_items[winner];
-    m_tree.m_items[winner].m_poss = 
-	- FLT_MAX;
-    m_tree.replay(winner);
-    ++m_counter;
-    return tmp;
-}
-
-void WinnerTree::play(int p, int lc, int rc){
-    m_tree[p] = winner(lc, rc);
-    //continue competition
-    while( p > 1 && p % 2) {
-	m_tree[p/2] = winner( m_tree[p - 1], m_tree[p]);
-	p/=2;
-  }
-}
-
-
-bool WinnerTree::initialize(LookupStepContent cur_step){
-    size_t size = cur_step->len;
-    if ( size > m_max_tree_size ){
-	init(size);
-    }
-    assert(size > nbranch);
-    m_tree_size = size;
-    
-    //initialize array tree
-    int nindex = 1;
-    
-    for( size_t i = 0; i < cur_step->len ; ++i){
-	lookup_value_t * cur_value = &g_array_index(cur_step, lookup_value_t, i);
-	m_items[nindex++] = *cur_value;
-    }
-    
-    //compute s = 2 ^ log(n -1)
-    int i, s;
-    for( s = 1; 2 * s <= m_tree_size - 1; s += s);
-  
-    m_low_ext = 2 * (m_tree_size - s);
-    m_offset = 2 * s - 1;
-  
-    //compute outside nodes
-    for( i = 2; i <= m_low_ext; i += 2)
-	play((m_offset + i)/2, i - 1, i);
-    //compute other nodes
-    if ( m_tree_size % 2){
-	play( m_tree_size / 2, m_tree[m_tree_size - 1], m_low_ext +1);
-	i = m_low_ext + 3;
-    }else i = m_low_ext + 2;
-  
-    //compute others 
-    for( ; i <= m_tree_size; i += 2)
-    play( (i - m_low_ext + m_tree_size - 1) / 2, i - 1, i);
-    return true;
-}
-
-void WinnerTree::replay(int i){
-    assert( 1 <= i && i <= m_tree_size);
-    
-    int p; //compete node
-    int lc; //p's left child
-    int rc; //p's right child
-    
-    //first compete
-    if ( i <= m_low_ext){
-	p = (m_offset + i) / 2;
-	lc = 2 * p - m_offset;
-	rc = lc + 1;
-    }else{
-	p = (i - m_low_ext + m_tree_size -1) / 2;
-	if ( 2 * p == m_tree_size - 1 ){
-	    lc = m_tree[2*p];
-	    rc = i;
-	}else{
-	    lc = 2 * p - m_tree_size + 1 + m_low_ext;
-	    rc = lc + 1;
-	}
-    }
-    
-    m_tree[p] = winner(lc, rc);
-    
-    //added by wupeng
-    if ( ( p | 0x01 )  == m_tree_size ){
-        p /= 2;
-	m_tree[p] = winner( m_tree[2 * p], m_low_ext + 1 );
-    }
-    
-    //compute others
-    p /= 2;
-    for( ; p >= 1 ; p /= 2)
-	m_tree[p] = winner( m_tree[2 * p], m_tree[2 * p + 1]);
-}
-
-int WinnerTree::winner(int lc, int rc){
-    return m_items[lc].m_poss > m_items[rc].m_poss ? 
-    lc : rc;
-}
diff --git a/src/lookup/winner_tree.h b/src/lookup/winner_tree.h
deleted file mode 100644
index b83b7fe..0000000
--- a/src/lookup/winner_tree.h
+++ /dev/null
@@ -1,149 +0,0 @@
-/* 
- *  libpinyin
- *  Library to deal with pinyin.
- *  
- *  Copyright (C) 2006-2007 Peng Wu
- *  
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- * 
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- *  GNU General Public License for more details.
- *  
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
- */
-
-#ifndef LOOKUP_WINNER_TREE_H
-#define LOOKUP_WINNER_TREE_H
-
-#include <assert.h>
-
-namespace pinyin{
-
-const int nbranch = 32;
-
-class DirectBranchIterator: public IBranchIterator{//for nitem <= nbranch
-    LookupStepContent m_step_content;
-    size_t m_iter_pos;
-public:
-    //Constructor
-    DirectBranchIterator(LookupStepContent step_content)
-	:m_step_content(step_content)
-    { m_iter_pos = 0; }
-    
-    //Destructor
-    virtual ~DirectBranchIterator(){}
-    
-    //Member Function
-    bool has_next(){
-	return m_iter_pos != m_step_content->len;
-    }
-    
-    lookup_value_t next(){
-	lookup_value_t * tmp = &g_array_index(m_step_content, 
-					      lookup_value_t, m_iter_pos);
-	++m_iter_pos;
-	return *tmp;
-    }
-    
-    lookup_value_t max(){
-	lookup_value_t * max_value = &g_array_index(m_step_content, lookup_value_t, 0);
-	for ( size_t i = 1 ; i < m_step_content->len; ++i){
-	    lookup_value_t * cur_value = &g_array_index(m_step_content, lookup_value_t, i);
-	    if ( cur_value->m_poss > max_value->m_poss )
-		max_value = cur_value;
-	}
-	return *max_value;
-    }
-};
-
-class WinnerTree;
-
-class WinnerTreeBranchIterator: public IBranchIterator{//for nitem <= nbranch
-    WinnerTree& m_tree;
-    int m_counter;
-    lookup_value_t m_max_value;
-public:
-    //Constructor
-    WinnerTreeBranchIterator(WinnerTree & tree);
-    
-    //Destructor
-    virtual ~WinnerTreeBranchIterator(){}
-  
-    //Member Function
-    bool has_next();
-    
-    lookup_value_t next();
-    
-    lookup_value_t max(){
-	return m_max_value;
-    }
-    
-};
-
-class WinnerTree{
-    friend class WinnerTreeBranchIterator;
-private:
-    size_t m_max_tree_size; // maxsize
-    int m_tree_size; // n
-    int m_low_ext;
-    int m_offset;
-    int * m_tree; 
-    MemoryChunk m_buffer;
-    MemoryChunk m_tree_buffer;
-    lookup_value_t * m_items;
-
-    int winner(int lc, int rc);
-    
-    void play(int p, int lc, int rc);
-    
-    void init(int tree_size){
-	m_max_tree_size = tree_size;
-	//data buffer
-	m_buffer.set_size( sizeof(lookup_value_t) * (tree_size + 1) );
-	m_items = (lookup_value_t *) m_buffer.begin();
-	
-	//tree item buffer
-	m_tree_buffer.set_size( sizeof(int) * m_max_tree_size);
-	m_tree = (int * ) m_tree_buffer.begin();
-	m_tree_size = 0;
-    }
-    
-public:
-    
-    //Constructor
-    WinnerTree(int tree_size = 10){
-	init(tree_size);
-    }
-    
-    //Destructor
-    ~WinnerTree() { }
-
-    //need delete this
-    IBranchIterator* get_iterator(LookupStepContent step){
-	if ( step->len <= nbranch )
-	    return new DirectBranchIterator(step);
-	//TODO:another situation > nbranch
-	assert(initialize(step));
-	return new WinnerTreeBranchIterator(*this);
-    }
-    
-protected:
-    
-    int get_winner() const {
-	return (m_tree_size)? m_tree[1] : 0;
-    }
-    
-    //Member Function
-    bool initialize(LookupStepContent cur_step);
-    void replay(int i);
-};
-
-};
-#endif