1 /****
2 DIAMOND protein aligner
3 Copyright (C) 2021 Max Planck Society for the Advancement of Science e.V.
4
5 Code developed by Benjamin Buchfink <benjamin.buchfink@tue.mpg.de>
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 ****/
20
21 #pragma once
22 #include <set>
23
24 template<typename It1, typename It2, typename Cmp, typename Value>
25 struct SortedListJoiner {
26
SortedListJoinerSortedListJoiner27 SortedListJoiner(It1& it1, It2& it2, Cmp cmp, Value value) :
28 it1_(&it1),
29 it2_(&it2),
30 cmp_(cmp),
31 value_(value)
32 {
33 }
34
goodSortedListJoiner35 bool good() {
36 return it1_->good() && it2_->good();
37 }
38
39 typename std::result_of<Value(const typename It1::Value&, const typename It2::Value&)>::type operator*() const {
40 return value_(**it1_, **it2_);
41 }
42
43 void operator++() {
44 const auto v1 = **it1_;
45 const auto v2 = **it2_;
46 ++(*it1_);
47 if (!it1_->good())
48 return;
49
50 if (!cmp_(v2, **it1_) && !cmp_(**it1_, v2))
51 return;
52
53 ++(*it2_);
54 if (!it2_->good())
55 return;
56
57 if (!cmp_(v1, **it2_) && !cmp_(**it2_, v1))
58 throw std::runtime_error("Duplicate keys: " + v1.first);
59
60 do {
61 if (cmp_(**it1_, **it2_))
62 ++(*it1_);
63 else if (cmp_(**it2_, **it1_))
64 ++(*it2_);
65 else
66 return;
67 } while (good());
68 }
69
70 private:
71
72 It1* it1_;
73 It2* it2_;
74 const Cmp cmp_;
75 const Value value_;
76
77 };
78
79 template<typename It1, typename It2, typename Cmp, typename Value>
join_sorted_lists(It1 & it1,It2 & it2,Cmp cmp,Value value)80 SortedListJoiner<It1, It2, Cmp, Value> join_sorted_lists(It1& it1, It2& it2, Cmp cmp, Value value) {
81 return SortedListJoiner<It1, It2, Cmp, Value>(it1, it2, cmp, value);
82 }
83
84 template<typename It, typename Key, typename Value>
85 struct KeyMerger
86 {
87
88 typedef typename std::result_of<Key(const typename It::Value&)>::type KeyType;
89 typedef typename std::result_of<Value(const typename It::Value&)>::type ValueType;
90
KeyMergerKeyMerger91 KeyMerger(It& it, KeyType begin):
92 it_(&it),
93 key_(begin)
94 {}
95
96 KeyMerger& operator++() {
97 ++key_;
98 return *this;
99 }
100
101 std::set<ValueType> operator*() {
102 std::set<ValueType> v;
103 while (it_->good() && Key()(**it_) == key_) {
104 v.insert(Value()(**it_));
105 ++(*it_);
106 }
107 return v;
108 }
109
keyKeyMerger110 KeyType key() const {
111 return key_;
112 }
113
114 private:
115
116 It* it_;
117 KeyType key_;
118
119 };
120
121 template<typename It, typename Key, typename Value>
merge_keys(It & it,Key key,Value value,typename std::result_of<Key (const typename It::Value &)>::type begin)122 KeyMerger<It, Key, Value> merge_keys(It& it, Key key, Value value, typename std::result_of<Key(const typename It::Value&)>::type begin) {
123 return KeyMerger<It, Key, Value>(it, begin);
124 }
125
126 template<typename Type1, typename Type2>
127 struct First {
operatorFirst128 Type1 operator()(const std::pair<Type1, Type2>& p) const {
129 return p.first;
130 }
131 };
132
133 template<typename Type1, typename Type2>
134 struct Second {
operatorSecond135 Type2 operator()(const std::pair<Type1, Type2>& p) const {
136 return p.second;
137 }
138 };