1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef LOOKUP_WINNER_TREE_H
#define LOOKUP_WINNER_TREE_H
#include <assert.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
|
