wavelength 1.0.0
Loading...
Searching...
No Matches
tickobjvector.h
Go to the documentation of this file.
1#pragma once
2
3#include <algorithm>
4#include <functional>
5#include <vector>
6
7#include "mid/tickobj.h"
8
9// Searches and sorted insertion over a vector of TickObj ordered by song position.
10//
11// Each template below was emitted once per element type and per translation unit that used it, and
12// one declaration stands for several addresses. The instantiations share their instruction shapes
13// exactly and differ only in the comparator and helper addresses they call. The element type of
14// each instantiation is not recorded where the call sites have not settled it.
15//
16// The comparators are called through a function pointer rather than inlined, as std::upper_bound
17// and std::lower_bound do with a comparator passed as a plain function. Each search inlines the
18// standard algorithm and calls the comparator out of line.
19
30template <typename T>
31bool TickObjLess(TickObj<T> first, TickObj<T> second) {
32 return first.mPosition < second.mPosition;
33}
34
42template <typename T>
43bool TickObjBefore(int nTick, TickObj<T> entry) {
44 return nTick < entry.mPosition;
45}
46
54template <typename T>
55bool TickObjAfter(TickObj<T> entry, int nTick) {
56 return entry.mPosition < nTick;
57}
58
66template <typename T>
67typename std::vector<TickObj<T> >::iterator UpperBoundByEntry(std::vector<TickObj<T> > &values,
68 const TickObj<T> &value) {
69 return std::upper_bound(values.begin(), values.end(), value, TickObjLess<T>);
70}
71
79template <typename T>
80typename std::vector<TickObj<T> >::iterator LowerBoundByEntry(std::vector<TickObj<T> > &values,
81 const TickObj<T> &value) {
82 return std::lower_bound(values.begin(), values.end(), value, TickObjLess<T>);
83}
84
92template <typename T>
93typename std::vector<TickObj<T> >::const_iterator
94UpperBoundByTick(const std::vector<TickObj<T> > &values, int nTick) {
95 return std::upper_bound(values.begin(), values.end(), nTick, TickObjBefore<T>);
96}
97
105template <typename T>
106typename std::vector<TickObj<T> >::const_iterator
107LowerBoundByTick(const std::vector<TickObj<T> > &values, int nTick) {
108 return std::lower_bound(values.begin(), values.end(), nTick, TickObjAfter<T>);
109}
110
118template <typename T>
119typename std::vector<TickObj<T> >::const_iterator
120FindAtOrBefore(const std::vector<TickObj<T> > &values, int nTick) {
121 if (values.begin() == values.end()) {
122 return values.end();
123 }
124 const auto upper = UpperBoundByTick(values, nTick);
125 if (upper == values.begin()) {
126 return values.end();
127 }
128 return upper - 1;
129}
130
138template <typename T>
139typename std::vector<TickObj<T> >::const_iterator
140FindAtOrAfter(const std::vector<TickObj<T> > &values, int nTick) {
141 if (values.begin() == values.end()) {
142 return values.end();
143 }
144 return LowerBoundByTick(values, nTick);
145}
146
155template <typename T>
156void InsertSorted(std::vector<TickObj<T> > &values, const TickObj<T> &value) {
157 if (values.size() != 0 && !(value.mPosition < values.back().mPosition)) {
158 values.push_back(value);
159 return;
160 }
161 values.insert(UpperBoundByEntry(values, value), value);
162}
163
182template <typename T, typename Compare>
183void InsertOrdered(const T &value, std::vector<T> &values, Compare compare) {
184 values.insert(std::lower_bound(values.begin(), values.end(), value, compare), value);
185}
186
204template <typename T>
205void InsertOrdered(const T &value, std::vector<T> &values) {
206 InsertOrdered(value, values, std::less<T>());
207}
208
227template <typename T, typename Compare>
228void AddOrdered(const T &value, std::vector<T> &values, Compare compare) {
229 if (!values.empty() && compare(value, values.back())) {
230 InsertOrdered(value, values);
231 return;
232 }
233 values.push_back(value);
234}
235
252template <typename T>
253void AddOrdered(const T &value, std::vector<T> &values) {
254 AddOrdered(value, values, std::less<T>());
255}
256
274template <typename T, typename Compare>
275typename std::vector<T>::const_iterator
276FindOrdered(const T &key, const std::vector<T> &values, Compare compare) {
277 const auto upper = std::upper_bound(values.begin(), values.end(), key, compare);
278 if (upper == values.begin()) {
279 return values.end();
280 }
281 return upper - 1;
282}
283
300template <typename T>
301typename std::vector<T>::const_iterator FindOrdered(const T &key, const std::vector<T> &values) {
302 return FindOrdered(key, values, std::less<T>());
303}
304
312template <typename T>
313void SetAtTick(std::vector<TickObj<T> > &values, const T &value, int nTick) {
314 TickObj<T> entry;
315 entry.mPosition = nTick;
316 entry.mValue = value;
317 typename std::vector<TickObj<T> >::iterator it = LowerBoundByEntry(values, entry);
318 if (it != values.end() && it->mPosition == nTick) {
319 *it = entry;
320 return;
321 }
322 values.insert(it, entry);
323}
324
333template <typename T>
334void InsertAtLowerBound(std::vector<TickObj<T> > &values, const TickObj<T> &value) {
335 values.insert(LowerBoundByEntry(values, value), value);
336}
337
345template <typename T>
346void InsertAtTick(std::vector<TickObj<T> > &values, const T &value, int nTick) {
347 TickObj<T> entry;
348 entry.mPosition = nTick;
349 entry.mValue = value;
350 InsertSorted(values, entry);
351}
One value at one song position.
Definition tickobj.h:18
T mValue
Definition tickobj.h:20
int mPosition
Definition tickobj.h:19
std::vector< TickObj< T > >::const_iterator UpperBoundByTick(const std::vector< TickObj< T > > &values, int nTick)
Find the first entry a song position strictly precedes.
Definition tickobjvector.h:94
bool TickObjAfter(TickObj< T > entry, int nTick)
Report whether an entry comes strictly before a song position.
Definition tickobjvector.h:55
std::vector< TickObj< T > >::const_iterator LowerBoundByTick(const std::vector< TickObj< T > > &values, int nTick)
Find the first entry at or after a song position.
Definition tickobjvector.h:107
void InsertSorted(std::vector< TickObj< T > > &values, const TickObj< T > &value)
Insert an entry at its sorted place, after every entry at the same position.
Definition tickobjvector.h:156
std::vector< TickObj< T > >::iterator LowerBoundByEntry(std::vector< TickObj< T > > &values, const TickObj< T > &value)
Find the first entry a value does not follow.
Definition tickobjvector.h:80
std::vector< TickObj< T > >::const_iterator FindAtOrAfter(const std::vector< TickObj< T > > &values, int nTick)
Find the first entry at or after a song position.
Definition tickobjvector.h:140
void InsertAtLowerBound(std::vector< TickObj< T > > &values, const TickObj< T > &value)
Insert an entry before every entry at the same position, always searching first.
Definition tickobjvector.h:334
std::vector< TickObj< T > >::iterator UpperBoundByEntry(std::vector< TickObj< T > > &values, const TickObj< T > &value)
Find the first entry a value strictly precedes.
Definition tickobjvector.h:67
void AddOrdered(const T &value, std::vector< T > &values, Compare compare)
Append a value that does not sort before the last one, and otherwise insert it at its lower bound.
Definition tickobjvector.h:228
bool TickObjLess(TickObj< T > first, TickObj< T > second)
Order two entries by song position.
Definition tickobjvector.h:31
void InsertAtTick(std::vector< TickObj< T > > &values, const T &value, int nTick)
Insert a value at a song position, after every entry at the same position.
Definition tickobjvector.h:346
std::vector< T >::const_iterator FindOrdered(const T &key, const std::vector< T > &values, Compare compare)
Find the last value that does not sort after a key.
Definition tickobjvector.h:276
void SetAtTick(std::vector< TickObj< T > > &values, const T &value, int nTick)
Store a value at a song position, overwriting the first entry already at that position.
Definition tickobjvector.h:313
bool TickObjBefore(int nTick, TickObj< T > entry)
Report whether a song position comes strictly before an entry.
Definition tickobjvector.h:43
void InsertOrdered(const T &value, std::vector< T > &values, Compare compare)
Insert a value at its lower bound under a comparator, before every equal value.
Definition tickobjvector.h:183
std::vector< TickObj< T > >::const_iterator FindAtOrBefore(const std::vector< TickObj< T > > &values, int nTick)
Find the last entry at or before a song position.
Definition tickobjvector.h:120