86 Position_ query_start,
90 std::vector<Index_>& matches)
93 if (subject.root_children == 0) {
148 if (query_end - query_start < params.
min_overlap) {
153 Position_ effective_query_end = query_end;
155 effective_query_end = safe_subtract_gap(query_end, params.
max_gap);
158 auto find_first_child = [&](Index_ children_start, Index_ children_end) -> Index_ {
159 auto ebegin = subject.ends.begin();
160 auto estart = ebegin + children_start;
161 auto eend = ebegin + children_end;
162 return std::lower_bound(estart, eend, effective_query_end) - ebegin;
165 auto is_finished = [&](Position_ subject_start) ->
bool {
166 if (subject_start > query_start) {
168 if (subject_start - query_start > params.
max_gap) {
176 if (subject_start >= query_end || query_end - subject_start < params.
min_overlap) {
184 if (query_end - subject_start < params.
min_overlap) {
193 Index_ root_child_at = find_first_child(0, subject.root_children);
195 workspace.history.clear();
197 Index_ current_subject;
198 if (workspace.history.empty()) {
199 if (root_child_at == subject.root_children || is_finished(subject.starts[root_child_at])) {
202 current_subject = root_child_at;
205 auto& current_state = workspace.history.back();
206 if (current_state.child_at == current_state.child_end || is_finished(subject.starts[current_state.child_at])) {
207 workspace.history.pop_back();
210 current_subject = current_state.child_at;
211 ++(current_state.child_at);
214 const auto& current_node = subject.nodes[current_subject];
215 auto subject_start = subject.starts[current_subject];
216 auto subject_end = subject.ends[current_subject];
219 auto common_end = std::min(subject_end, query_end);
220 auto common_start = std::max(subject_start, query_start);
221 if (common_end <= common_start || common_end - common_start < params.
min_overlap) {
230 okay = !diff_above_gap(query_start, subject_start, params.
max_gap) && !diff_above_gap(query_end, subject_end, params.
max_gap);
232 okay = (subject_start == query_start && subject_end == query_end);
236 matches.push_back(current_node.id);
240 if (current_node.duplicates_start != current_node.duplicates_end) {
241 matches.insert(matches.end(), subject.duplicates.begin() + current_node.duplicates_start, subject.duplicates.begin() + current_node.duplicates_end);
248 if (current_node.children_start != current_node.children_end) {
249 Index_ start_pos = find_first_child(current_node.children_start, current_node.children_end);
250 if (start_pos != current_node.children_end) {
251 workspace.history.emplace_back(start_pos, current_node.children_end);
void overlaps_equal(const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsEqualParameters< Position_ > ¶ms, OverlapsEqualWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)
Definition overlaps_equal.hpp:84