summaryrefslogtreecommitdiffstats
path: root/src/lookup/winner_tree.h
diff options
context:
space:
mode:
authorPeng Wu <alexepico@gmail.com>2010-08-03 10:42:47 +0800
committerPeng Wu <alexepico@gmail.com>2010-08-03 10:42:47 +0800
commitf41d1fdf83408e042ab07925710a8913bad0c27c (patch)
tree1757833ac4cdd0830834d2f9ef92be07c0bc1a5b /src/lookup/winner_tree.h
parent34acf9be9033e0dc0a5905999133482c20b6cbf3 (diff)
downloadlibpinyin-f41d1fdf83408e042ab07925710a8913bad0c27c.tar.gz
libpinyin-f41d1fdf83408e042ab07925710a8913bad0c27c.tar.xz
libpinyin-f41d1fdf83408e042ab07925710a8913bad0c27c.zip
import from pinyin.
Diffstat (limited to 'src/lookup/winner_tree.h')
-rw-r--r--src/lookup/winner_tree.h148
1 files changed, 148 insertions, 0 deletions
diff --git a/src/lookup/winner_tree.h b/src/lookup/winner_tree.h
new file mode 100644
index 0000000..262f196
--- /dev/null
+++ b/src/lookup/winner_tree.h
@@ -0,0 +1,148 @@
+/*
+ * 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
+ */
+
+#ifndef LOOKUP_WINNER_TREE_H
+#define LOOKUP_WINNER_TREE_H
+
+#include <assert.h>
+#include "lookup.h"
+
+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