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
|
/***************************************************************************
* Copyright (C) 2006 by BUI Quang Minh, Steffen Klaere, Arndt von Haeseler *
* minh.bui@univie.ac.at *
* *
* 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 HASHSPLITSET_H
#define HASHSPLITSET_H
#include "utils/tools.h"
#include "split.h"
using namespace std;
class SplitGraph;
#ifdef USE_HASH_MAP
/*
Define the hash function of Split
*/
struct hashfunc_Split {
size_t operator()(const Split* sp) const {
size_t sum = 0;
for (Split::const_iterator it = sp->begin(); it != sp->end(); it++)
sum = (*it) + (sum << 6) + (sum << 16) - sum;
return sum;
}
};
#endif // USE_HASH_MAP
namespace std {
/**
Define equal_to of two splits, used for hash_set (or hash_map) template
*/
template<>
struct equal_to<Split*> {
/**
@return true if *s1 == *s2
@param s1 first split
@param s2 second split
*/
bool operator()(const Split* s1, const Split* s2) const{
return *s1 == *s2;
}
};
/**
Define less than relationship of two splits, used for set (or map) template
*/
template<>
struct less<Split*> {
/**
@return true if *s1 < *s2 alphabetically
@param s1 first split
@param s2 second split
*/
bool operator()(const Split *s1, const Split *s2) const {
ASSERT(s1->size() == s2->size());
for (int i = 0; i < s1->size(); i++)
if ((*s1)[i] < (*s2)[i])
return true;
else if ((*s1)[i] > (*s2)[i]) return false;
return false;
}
};
} // namespace std
/**
SplitSet for quick search purpose
@author BUI Quang Minh, Steffen Klaere, Arndt von Haeseler
*/
#ifdef USE_HASH_MAP
class SplitIntMap : public unordered_map<Split*, int, hashfunc_Split>
#else
class SplitIntMap : map<Split*, int, std::less<Split*> >
#endif
{
public:
/**
find a split
@param sp target split
@return the split containing the same set of taxa with sp, NULL if not found
*/
Split *findSplit(Split *sp);
/**
find a split
@param sp target split
@param value (OUT) associated value
@return the split containing the same set of taxa with sp, NULL if not found
*/
Split *findSplit(Split *sp, int &value);
int getValue(Split *sp);
void setValue(Split *sp, int value);
void eraseSplit(Split *sp);
void insertSplit(Split *sp, int value);
/**
* build a map from the input split graph
* @param sg input split graph
* @param use_index TRUE to map to index of splits in sg, FALSE to map to split weights
*/
void buildMap(SplitGraph &sg, bool use_index = true);
int getNumTree() {
return numTree;
}
void setNumTree(int maxValue) {
this->numTree = maxValue;
}
private:
/**
* The maximum weight value. If the splits are generated from n trees and splits of every tree
* all have weight = 1, then maxValue = n
* This variable is used to determine whether a split appear on all input trees.
*/
int numTree;
};
#endif
|
