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
|
/*
* Debian menu system -- install-menu
* install-menu/hints.h
*
* Copyright (C) 1996-2003 Joost Witteveen,
* Copyright (C) 2002-2004 Bill Allombert and Morten Brix Pedersen.
*
* 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 with
* the Debian GNU/Linux distribution in file /usr/share/common-licenses/GPL;
* if not, write to the Free Software Foundation, Inc., 59 Temple Place,
* Suite 330, Boston, MA 02111-1307 USA
*
*
* Written by Joost Witteveen.
*/
#ifndef HINTS_H
#define HINTS_H
#include <vector>
#include <map>
#include <set>
#include <string>
bool operator<(const std::set<std::string> &left, const std::set<std::string> &right);
std::ostream& operator<<(std::ostream &, const std::vector<std::string> &);
class hint_tree;
class correlation;
typedef std::multimap<double, std::vector<hint_tree> > possible_divisions;
typedef std::multimap<double, possible_divisions::iterator> possible_divisions_it;
class hint_tree {
public:
hint_tree(std::string k, std::vector<hint_tree> &c) : key(k), children(c) { }
hint_tree(std::string k) : key(k) { }
std::string key;
std::vector<std::vector<std::string> > entries;
double penalty; //of the whole tree (including children, grandchildren, etc).
std::vector<hint_tree> children;
};
class hints {
bool debug_enabled;
double max_local_penalty;
hint_tree root_tree;
double mixed_penalty;
double min_hint_freq;
double hint_nentry, hint_topnentry;
unsigned int max_ntry;
int max_iter_hint;
std::vector<std::vector<std::string> > hint_list;
std::vector<int> raw_count;
public:
hints()
: debug_enabled(false), root_tree("-"), min_hint_freq(0.3 /
hint_nentry), hint_nentry(6), hint_topnentry(6), max_ntry(5),
max_iter_hint(5) { }
void set_nentry(double n) { hint_nentry = n; }
void set_topnentry(double n) { hint_topnentry = n; }
void set_mixedpenalty(double p) { mixed_penalty = p; }
void set_minhintfreq(double m) { min_hint_freq = m / hint_nentry; }
void set_max_local_penalty(double p) { max_local_penalty = p; }
void set_max_ntry(int n) { max_ntry = n; }
void set_max_iter_hint(int n) { max_iter_hint = n;}
void set_debug(bool opt) { debug_enabled = opt; }
void calc_tree(const std::vector<std::vector<std::string> > &hint_input,
std::vector<std::vector<std::string> > &hint_output);
private:
void sort_hints();
double calc_penalty(int level, int n, int unused);
double nopt(int level) const {
if (level != 0)
return hint_nentry;
else
return hint_topnentry;
}
void add_division(int level, possible_divisions &division_list,
const std::vector<unsigned int> &division,
correlation &h,
int unused,
double &worst_penalty,
unsigned int itteration);
bool try_shortcut(int level,
const std::vector<std::vector<std::string> > &hint_input,
const std::vector<int> &raw_input_count,
hint_tree &t,
int already_used);
void find_possible_divisions(int level, possible_divisions &division_list,
const std::vector<std::vector<std::string> > &hint_input,
const std::vector<int> &raw_input_count,
int already_used);
void postprocess(int level,
const std::vector<std::vector<std::string> > &hint_input,
const std::vector<int> &raw_input_count,
hint_tree &t,
int already_used);
void search_hint(hint_tree &t, const std::vector<std::string> &hint_in,
std::vector<std::string> &hint_out);
void debug_hint_tree(const hint_tree &t, int level);
void debug();
};
#endif /* HINTS_H */
|
