From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Wed, 12 Dec 2018 23:36:03 +0000 (+0100)
Subject: Add some binary search helpers.
X-Git-Tag: 1.8.0~30
X-Git-Url: https://git.sesse.net/?p=nageru;a=commitdiff_plain;h=5a1069f76339d67e0549091724b901468356fa2c

Add some binary search helpers.
---

diff --git a/futatabi/frame_on_disk.h b/futatabi/frame_on_disk.h
index 1843857..47fcb32 100644
--- a/futatabi/frame_on_disk.h
+++ b/futatabi/frame_on_disk.h
@@ -1,6 +1,7 @@
 #ifndef _FRAME_ON_DISK_H
 #define _FRAME_ON_DISK_H 1
 
+#include <algorithm>
 #include <mutex>
 #include <string>
 #include <vector>
@@ -34,4 +35,19 @@ private:
 	int last_filename_idx = -1;
 };
 
+// Utility functions for dealing with binary search.
+inline std::vector<FrameOnDisk>::iterator
+find_last_frame_before(std::vector<FrameOnDisk> &frames, int64_t pts_origin)
+{
+	return std::lower_bound(frames.begin(), frames.end(), pts_origin,
+		[](const FrameOnDisk &frame, int64_t pts) { return frame.pts < pts; });
+}
+
+inline std::vector<FrameOnDisk>::iterator
+find_first_frame_at_or_after(std::vector<FrameOnDisk> &frames, int64_t pts_origin)
+{
+	return std::upper_bound(frames.begin(), frames.end(), pts_origin - 1,
+		[](int64_t pts, const FrameOnDisk &frame) { return pts < frame.pts; });
+}
+
 #endif  // !defined(_FRAME_ON_DISK_H)
diff --git a/futatabi/mainwindow.cpp b/futatabi/mainwindow.cpp
index 24a9d5b..57693ef 100644
--- a/futatabi/mainwindow.cpp
+++ b/futatabi/mainwindow.cpp
@@ -661,8 +661,7 @@ void MainWindow::preview_single_frame(int64_t pts, unsigned stream_idx, MainWind
 		lock_guard<mutex> lock(frame_mu);
 		if (frames[stream_idx].empty())
 			return;
-		auto it = lower_bound(frames[stream_idx].begin(), frames[stream_idx].end(), pts,
-			[](const FrameOnDisk &frame, int64_t pts) { return frame.pts < pts; });
+		auto it = find_last_frame_before(frames[stream_idx], pts);
 		if (it != frames[stream_idx].end()) {
 			pts = it->pts;
 		}
@@ -671,8 +670,7 @@ void MainWindow::preview_single_frame(int64_t pts, unsigned stream_idx, MainWind
 		lock_guard<mutex> lock(frame_mu);
 		if (frames[stream_idx].empty())
 			return;
-		auto it = upper_bound(frames[stream_idx].begin(), frames[stream_idx].end(), pts - 1,
-			[](int64_t pts, const FrameOnDisk &frame) { return pts < frame.pts; });
+		auto it = find_first_frame_at_or_after(frames[stream_idx], pts);
 		if (it != frames[stream_idx].end()) {
 			pts = it->pts;
 		}
diff --git a/futatabi/player.cpp b/futatabi/player.cpp
index e20a43c..a5d093a 100644
--- a/futatabi/player.cpp
+++ b/futatabi/player.cpp
@@ -103,10 +103,7 @@ got_clip:
 			lock_guard<mutex> lock(frame_mu);
 
 			// Find the first frame such that frame.pts <= in_pts.
-			auto it = lower_bound(frames[stream_idx].begin(),
-				frames[stream_idx].end(),
-				in_pts_origin,
-				[](const FrameOnDisk &frame, int64_t pts) { return frame.pts < pts; });
+			auto it = find_last_frame_before(frames[stream_idx], in_pts_origin);
 			if (it != frames[stream_idx].end()) {
 				in_pts_origin = it->pts;
 			}
@@ -363,10 +360,7 @@ bool Player::find_surrounding_frames(int64_t pts, int stream_idx, FrameOnDisk *f
 	lock_guard<mutex> lock(frame_mu);
 
 	// Find the first frame such that frame.pts >= pts.
-	auto it = lower_bound(frames[stream_idx].begin(),
-		frames[stream_idx].end(),
-		pts,
-		[](const FrameOnDisk &frame, int64_t pts) { return frame.pts < pts; });
+	auto it = find_last_frame_before(frames[stream_idx], pts);
 	if (it == frames[stream_idx].end()) {
 		return false;
 	}
@@ -451,8 +445,7 @@ void Player::override_angle(unsigned stream_idx)
 	}
 
 	lock_guard<mutex> lock(frame_mu);
-	auto it = upper_bound(frames[stream_idx].begin(), frames[stream_idx].end(), pts_out,
-		[](int64_t pts, const FrameOnDisk &frame) { return pts < frame.pts; });
+	auto it = find_first_frame_at_or_after(frames[stream_idx], pts_out);
 	if (it == frames[stream_idx].end()) {
 		return;
 	}