1 files changed, 141 insertions, 0 deletions
diff --git a/src/lookup/winner_tree.cpp b/src/lookup/winner_tree.cpp
new file mode 100644
index 0000000..248a749
--- /dev/null
+++ b/src/lookup/winner_tree.cpp
@@ -0,0 +1,141 @@
+/* 
+ *  novel-pinyin,
+ *  A Simplified Chinese Sentence-Based Pinyin Input Method Engine
+ *  Based On Markov Model.
+ *  
+ *  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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <float.h>
+#include <limits.h>
+#include <stdio.h>
+#include "memory_chunk.h"
+#include "phrase_index.h"
+#include "lookup.h"
+#include "winner_tree.h"
+
+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;
+}