diff options
| -rw-r--r-- | drape/shaders/shader_index.txt | 1 | ||||
| -rw-r--r-- | drape/shaders/trackpoint_fragment_shader.fsh | 22 | ||||
| -rw-r--r-- | drape/shaders/trackpoint_vertex_shader.vsh | 21 | ||||
| -rw-r--r-- | drape_frontend/backend_renderer.cpp | 12 | ||||
| -rw-r--r-- | drape_frontend/drape_engine.cpp | 14 | ||||
| -rw-r--r-- | drape_frontend/drape_engine.hpp | 3 | ||||
| -rwxr-xr-x | drape_frontend/drape_frontend.pro | 5 | ||||
| -rwxr-xr-x | drape_frontend/frontend_renderer.cpp | 34 | ||||
| -rwxr-xr-x | drape_frontend/frontend_renderer.hpp | 4 | ||||
| -rw-r--r-- | drape_frontend/gps_track_point.hpp | 23 | ||||
| -rw-r--r-- | drape_frontend/gps_track_renderer.cpp | 329 | ||||
| -rw-r--r-- | drape_frontend/gps_track_renderer.hpp | 64 | ||||
| -rw-r--r-- | drape_frontend/gps_track_shape.cpp | 173 | ||||
| -rw-r--r-- | drape_frontend/gps_track_shape.hpp | 69 | ||||
| -rw-r--r-- | drape_frontend/message.hpp | 6 | ||||
| -rw-r--r-- | drape_frontend/message_subclasses.hpp | 51 | ||||
| -rw-r--r-- | map/framework.cpp | 6 | ||||
| -rw-r--r-- | map/framework.hpp | 3 | ||||
| -rw-r--r-- | map/gps_track_container.cpp | 23 | ||||
| -rw-r--r-- | map/gps_track_container.hpp | 26 | ||||
| -rw-r--r-- | map/map_tests/gps_track_container_test.cpp | 6 | ||||
| -rw-r--r-- | std/algorithm.hpp | 1 |
22 files changed, 861 insertions, 35 deletions
diff --git a/drape/shaders/shader_index.txt b/drape/shaders/shader_index.txt index 9186a52ea3..3e6d412bbc 100644 --- a/drape/shaders/shader_index.txt +++ b/drape/shaders/shader_index.txt @@ -16,6 +16,7 @@ BUTTON_PROGRAM button_vertex_shader.vsh button_fragment_shader.fsh BOOKMARK_PROGRAM user_mark.vsh texturing_fragment_shader.fsh ROUTE_PROGRAM route_vertex_shader.vsh route_fragment_shader.fsh ROUTE_ARROW_PROGRAM route_vertex_shader.vsh route_arrow_fragment_shader.fsh +TRACK_POINT_PROGRAM trackpoint_vertex_shader.vsh trackpoint_fragment_shader.fsh DEBUG_RECT_PROGRAM debug_rect_vertex_shader.vsh debug_rect_fragment_shader.fsh TRANSPARENT_LAYER_PROGRAM transparent_layer_vertex_shader.vsh transparent_layer_fragment_shader.fsh ARROW_3D_PROGRAM arrow3d_vertex_shader.vsh arrow3d_fragment_shader.fsh diff --git a/drape/shaders/trackpoint_fragment_shader.fsh b/drape/shaders/trackpoint_fragment_shader.fsh new file mode 100644 index 0000000000..1799c4ec93 --- /dev/null +++ b/drape/shaders/trackpoint_fragment_shader.fsh @@ -0,0 +1,22 @@ +uniform float u_opacity; +uniform float u_radiusShift; + +varying vec3 v_radius; +varying vec4 v_color; + +const float kAntialiasingScalar = 0.9; +const vec4 kOutlineColor = vec4(1.0, 1.0, 1.0, 1.0); + +void main(void) +{ + float d = dot(v_radius.xy, v_radius.xy); + + float shiftedRadius = v_radius.z - u_radiusShift; + float aaRadius = shiftedRadius * kAntialiasingScalar; + vec4 finalColor = mix(v_color, kOutlineColor, smoothstep(aaRadius * aaRadius, shiftedRadius * shiftedRadius, d)); + + aaRadius = v_radius.z * kAntialiasingScalar; + float stepValue = smoothstep(aaRadius * aaRadius, v_radius.z * v_radius.z, d); + finalColor.a = finalColor.a * u_opacity * (1.0 - stepValue); + gl_FragColor = finalColor; +} diff --git a/drape/shaders/trackpoint_vertex_shader.vsh b/drape/shaders/trackpoint_vertex_shader.vsh new file mode 100644 index 0000000000..21cbe2062b --- /dev/null +++ b/drape/shaders/trackpoint_vertex_shader.vsh @@ -0,0 +1,21 @@ +attribute vec3 a_normal; +attribute vec3 a_position; +attribute vec4 a_color; + +uniform mat4 modelView; +uniform mat4 projection; + +varying vec3 v_radius; +varying vec4 v_color; + +void main(void) +{ + vec3 radius = a_normal * a_position.z; + // Here we intentionally decrease precision of 'pos' calculation + // to eliminate jittering effect in process of billboard reconstruction. + lowp vec4 pos = vec4(a_position.xy, 0, 1) * modelView; + highp vec4 shiftedPos = vec4(radius.xy, 0, 0) + pos; + gl_Position = shiftedPos * projection; + v_radius = radius; + v_color = a_color; +} diff --git a/drape_frontend/backend_renderer.cpp b/drape_frontend/backend_renderer.cpp index 8be34cb08c..225ad229da 100644 --- a/drape_frontend/backend_renderer.cpp +++ b/drape_frontend/backend_renderer.cpp @@ -2,6 +2,7 @@ #include "drape_frontend/backend_renderer.hpp" #include "drape_frontend/batchers_pool.hpp" +#include "drape_frontend/gps_track_shape.hpp" #include "drape_frontend/map_shape.hpp" #include "drape_frontend/message_subclasses.hpp" #include "drape_frontend/read_manager.hpp" @@ -233,6 +234,17 @@ void BackendRenderer::AcceptMessage(ref_ptr<Message> message) RecacheMyPosition(); break; } + case Message::CacheGpsTrackPoints: + { + ref_ptr<CacheGpsTrackPointsMessage> msg = message; + drape_ptr<GpsTrackRenderData> data = make_unique_dp<GpsTrackRenderData>(); + data->m_pointsCount = msg->GetPointsCount(); + GpsTrackShape::Draw(*data.get()); + m_commutator->PostMessage(ThreadsCommutator::RenderThread, + make_unique_dp<FlushGpsTrackPointsMessage>(move(data)), + MessagePriority::Normal); + break; + } case Message::StopRendering: { ProcessStopRenderingMessage(); diff --git a/drape_frontend/drape_engine.cpp b/drape_frontend/drape_engine.cpp index 0fb3ee6bc6..eab573c9a3 100644 --- a/drape_frontend/drape_engine.cpp +++ b/drape_frontend/drape_engine.cpp @@ -449,4 +449,18 @@ void DrapeEngine::EnablePerspective(double rotationAngle, double angleFOV) MessagePriority::Normal); } +void DrapeEngine::UpdateGpsTrackPoints(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove) +{ + m_threadCommutator->PostMessage(ThreadsCommutator::RenderThread, + make_unique_dp<UpdateGpsTrackPointsMessage>(move(toAdd), move(toRemove)), + MessagePriority::Normal); +} + +void DrapeEngine::ClearGpsTrackPoints() +{ + m_threadCommutator->PostMessage(ThreadsCommutator::RenderThread, + make_unique_dp<ClearGpsTrackPointsMessage>(), + MessagePriority::Normal); +} + } // namespace df diff --git a/drape_frontend/drape_engine.hpp b/drape_frontend/drape_engine.hpp index b8ce24fa66..38b364e760 100644 --- a/drape_frontend/drape_engine.hpp +++ b/drape_frontend/drape_engine.hpp @@ -120,6 +120,9 @@ public: void Allow3dMode(bool allowPerspectiveInNavigation, bool allow3dBuildings, double rotationAngle, double angleFOV); void EnablePerspective(double rotationAngle, double angleFOV); + void UpdateGpsTrackPoints(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove); + void ClearGpsTrackPoints(); + private: void AddUserEvent(UserEvent const & e); void ModelViewChanged(ScreenBase const & screen); diff --git a/drape_frontend/drape_frontend.pro b/drape_frontend/drape_frontend.pro index f99488f630..5c9dae59bb 100755 --- a/drape_frontend/drape_frontend.pro +++ b/drape_frontend/drape_frontend.pro @@ -42,6 +42,8 @@ SOURCES += \ engine_context.cpp \ framebuffer.cpp \ frontend_renderer.cpp \ + gps_track_renderer.cpp \ + gps_track_shape.cpp \ line_shape.cpp \ line_shape_helper.cpp \ map_data_provider.cpp \ @@ -126,6 +128,9 @@ HEADERS += \ engine_context.hpp \ framebuffer.hpp \ frontend_renderer.hpp \ + gps_track_point.hpp \ + gps_track_renderer.hpp \ + gps_track_shape.hpp \ intrusive_vector.hpp \ line_shape.hpp \ line_shape_helper.hpp \ diff --git a/drape_frontend/frontend_renderer.cpp b/drape_frontend/frontend_renderer.cpp index 3bd7901ddf..6fce1d5c54 100755 --- a/drape_frontend/frontend_renderer.cpp +++ b/drape_frontend/frontend_renderer.cpp @@ -47,6 +47,7 @@ FrontendRenderer::FrontendRenderer(Params const & params) , m_routeRenderer(new RouteRenderer()) , m_framebuffer(new Framebuffer()) , m_transparentLayer(new TransparentLayer()) + , m_gpsTrackRenderer(new GpsTrackRenderer(bind(&FrontendRenderer::PrepareGpsTrackPoints, this, _1))) , m_overlayTree(new dp::OverlayTree()) , m_enablePerspectiveInNavigation(false) , m_enable3dBuildings(params.m_allow3dBuildings) @@ -523,6 +524,26 @@ void FrontendRenderer::AcceptMessage(ref_ptr<Message> message) break; } + case Message::FlushGpsTrackPoints: + { + ref_ptr<FlushGpsTrackPointsMessage> msg = message; + m_gpsTrackRenderer->AddRenderData(make_ref(m_gpuProgramManager), msg->AcceptRenderData()); + break; + } + + case Message::UpdateGpsTrackPoints: + { + ref_ptr<UpdateGpsTrackPointsMessage> msg = message; + m_gpsTrackRenderer->UpdatePoints(msg->GetPointsToAdd(), msg->GetPointsToRemove()); + break; + } + + case Message::ClearGpsTrackPoints: + { + m_gpsTrackRenderer->Clear(); + break; + } + case Message::Invalidate: { // Do nothing here, new frame will be rendered because of this message processing. @@ -718,6 +739,13 @@ FeatureID FrontendRenderer::GetVisiblePOI(m2::RectD const & pixelRect) const return featureID; } +void FrontendRenderer::PrepareGpsTrackPoints(size_t pointsCount) +{ + m_commutator->PostMessage(ThreadsCommutator::ResourceUploadThread, + make_unique_dp<CacheGpsTrackPointsMessage>(pointsCount), + MessagePriority::Normal); +} + void FrontendRenderer::BeginUpdateOverlayTree(ScreenBase const & modelView) { if (m_overlayTree->Frame(modelView.isPerspective())) @@ -881,6 +909,9 @@ void FrontendRenderer::RenderScene(ScreenBase const & modelView) RenderSingleGroup(modelView, make_ref(group)); } + m_gpsTrackRenderer->RenderTrack(modelView, GetCurrentZoomLevel(), + make_ref(m_gpuProgramManager), m_generalUniforms); + GLFunctions::glDisable(gl_const::GLDepthTest); if (m_selectionShape != nullptr && m_selectionShape->GetSelectedObject() == SelectionShape::OBJECT_USER_MARK) m_selectionShape->Render(modelView, make_ref(m_gpuProgramManager), m_generalUniforms); @@ -1420,7 +1451,8 @@ void FrontendRenderer::UpdateScene(ScreenBase const & modelView) TTilesCollection tiles; ResolveTileKeys(modelView, tiles); - m_overlayTree->ForceUpdate(); + m_gpsTrackRenderer->Update(); + auto removePredicate = [this](drape_ptr<RenderGroup> const & group) { return group->IsOverlay() && group->GetTileKey().m_styleZoomLevel > GetCurrentZoomLevel(); diff --git a/drape_frontend/frontend_renderer.hpp b/drape_frontend/frontend_renderer.hpp index bdbac1100b..7daa76588a 100755 --- a/drape_frontend/frontend_renderer.hpp +++ b/drape_frontend/frontend_renderer.hpp @@ -12,6 +12,7 @@ #include "drape_frontend/backend_renderer.hpp" #include "drape_frontend/base_renderer.hpp" +#include "drape_frontend/gps_track_renderer.hpp" #include "drape_frontend/my_position_controller.hpp" #include "drape_frontend/navigator.hpp" #include "drape_frontend/render_group.hpp" @@ -222,6 +223,8 @@ private: bool IsPerspective() const; + void PrepareGpsTrackPoints(size_t pointsCount); + private: drape_ptr<dp::GpuProgramManager> m_gpuProgramManager; @@ -236,6 +239,7 @@ private: drape_ptr<RouteRenderer> m_routeRenderer; drape_ptr<Framebuffer> m_framebuffer; drape_ptr<TransparentLayer> m_transparentLayer; + drape_ptr<GpsTrackRenderer> m_gpsTrackRenderer; drape_ptr<dp::OverlayTree> m_overlayTree; diff --git a/drape_frontend/gps_track_point.hpp b/drape_frontend/gps_track_point.hpp new file mode 100644 index 0000000000..4de53e85e5 --- /dev/null +++ b/drape_frontend/gps_track_point.hpp @@ -0,0 +1,23 @@ +#pragma once + +#include "geometry/point2d.hpp" + +namespace df +{ + +struct GpsTrackPoint +{ + // Timestamp of the point, seconds from 1st Jan 1970 + double m_timestamp; + + // Point in the Mercator projection + m2::PointD m_point; + + // Speed in the point, M/S + double m_speedMPS; + + // Unique identifier of the point + uint32_t m_id; +}; + +} // namespace df diff --git a/drape_frontend/gps_track_renderer.cpp b/drape_frontend/gps_track_renderer.cpp new file mode 100644 index 0000000000..48dea882dc --- /dev/null +++ b/drape_frontend/gps_track_renderer.cpp @@ -0,0 +1,329 @@ +#include "drape_frontend/gps_track_renderer.hpp" +#include "drape_frontend/visual_params.hpp" + +#include "drape/glsl_func.hpp" +#include "drape/shader_def.hpp" +#include "drape/vertex_array_buffer.hpp" + +#include "indexer/scales.hpp" + +#include "base/logging.hpp" + +#include "std/algorithm.hpp" + +namespace df +{ + +namespace +{ + +int const kMinVisibleZoomLevel = 15; + +size_t const kAveragePointsCount = 512; + +// Radius of circles depending on zoom levels. +float const kRadiusInPixel[] = +{ + // 1 2 3 4 5 6 7 8 9 10 + 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, + //11 12 13 14 15 16 17 18 19 20 + 1.0f, 1.0f, 1.0f, 1.5f, 3.0f, 4.0f, 5.0f, 5.0f, 5.0f, 6.0f +}; + +double const kMinSpeed = 1.0; // meters per second +double const kAvgSpeed = 2.0; // meters per second +double const kMaxSpeed = 5.0; // meters per second +dp::Color const kMinSpeedColor = dp::Color(255, 0, 0, 255); +dp::Color const kAvgSpeedColor = dp::Color(251, 192, 45, 255); +dp::Color const kMaxSpeedColor = dp::Color(44, 120, 47, 255); +uint8_t const kMinAlpha = 50; +uint8_t const kMaxAlpha = 255; + +float const kOutlineRadiusScalar = 0.3f; + +bool GpsPointsSortPredicate(GpsTrackPoint const & pt1, GpsTrackPoint const & pt2) +{ + return pt1.m_id < pt2.m_id; +} + +dp::Color InterpolateColors(dp::Color const & color1, dp::Color const & color2, double t) +{ + double const r = color1.GetRed() * (1.0 - t) + color2.GetRed() * t; + double const g = color1.GetGreen() * (1.0 - t) + color2.GetGreen() * t; + double const b = color1.GetBlue() * (1.0 - t) + color2.GetBlue() * t; + double const a = color1.GetAlfa() * (1.0 - t) + color2.GetAlfa() * t; + return dp::Color(r, g, b, a); +} + +} // namespace + +GpsTrackRenderer::GpsTrackRenderer(TRenderDataRequestFn const & dataRequestFn) + : m_dataRequestFn(dataRequestFn) + , m_needUpdate(false) + , m_waitForRenderData(false) + , m_startSpeed(0.0) + , m_endSpeed(0.0) + , m_startColor(kMaxSpeedColor) + , m_radius(0.0f) +{ + ASSERT(m_dataRequestFn != nullptr, ()); + m_points.reserve(kAveragePointsCount); + m_handlesCache.reserve(8); +} + +float GpsTrackRenderer::CalculateRadius(ScreenBase const & screen) const +{ + double const kLog2 = log(2.0); + double const zoomLevel = my::clamp(fabs(log(screen.GetScale()) / kLog2), 1.0, scales::UPPER_STYLE_SCALE + 1.0); + double zoom = trunc(zoomLevel); + int const index = zoom - 1.0; + float const lerpCoef = zoomLevel - zoom; + + float radius = 0.0f; + if (index < scales::UPPER_STYLE_SCALE) + radius = kRadiusInPixel[index] + lerpCoef * (kRadiusInPixel[index + 1] - kRadiusInPixel[index]); + else + radius = kRadiusInPixel[scales::UPPER_STYLE_SCALE]; + + return radius * VisualParams::Instance().GetVisualScale(); +} + +void GpsTrackRenderer::AddRenderData(ref_ptr<dp::GpuProgramManager> mng, + drape_ptr<GpsTrackRenderData> && renderData) +{ + drape_ptr<GpsTrackRenderData> data = move(renderData); + ref_ptr<dp::GpuProgram> program = mng->GetProgram(gpu::TRACK_POINT_PROGRAM); + program->Bind(); + data->m_bucket->GetBuffer()->Build(program); + m_renderData.push_back(move(data)); +} + +void GpsTrackRenderer::UpdatePoints(vector<GpsTrackPoint> const & toAdd, vector<uint32_t> const & toRemove) +{ + if (!toRemove.empty()) + { + auto removePredicate = [&toRemove](GpsTrackPoint const & pt) + { + return find(toRemove.begin(), toRemove.end(), pt.m_id) != toRemove.end(); + }; + m_points.erase(remove_if(m_points.begin(), m_points.end(), removePredicate), m_points.end()); + } + + if (!toAdd.empty()) + { + ASSERT(is_sorted(toAdd.begin(), toAdd.end(), GpsPointsSortPredicate), ()); + if (!m_points.empty()) + ASSERT(GpsPointsSortPredicate(m_points.back(), toAdd.front()), ()); + m_points.insert(m_points.end(), toAdd.begin(), toAdd.end()); + } + + m_needUpdate = true; +} + +double GpsTrackRenderer::CalculateTrackLength() const +{ + double len = 0.0; + for (size_t i = 0; i + 1 < m_points.size(); i++) + len += (m_points[i + 1].m_point - m_points[i].m_point).Length(); + + return len; +} + +void GpsTrackRenderer::UpdateSpeedsAndColors() +{ + m_startSpeed = 0.0; + m_endSpeed = 0.0; + for (size_t i = 0; i < m_points.size(); i++) + { + if (m_points[i].m_speedMPS < m_startSpeed) + m_startSpeed = m_points[i].m_speedMPS; + + if (m_points[i].m_speedMPS > m_endSpeed) + m_endSpeed = m_points[i].m_speedMPS; + } + + double const delta = m_endSpeed - m_startSpeed; + if (delta <= kMinSpeed) + m_startColor = kMaxSpeedColor; + else if (delta <= kAvgSpeed) + m_startColor = kAvgSpeedColor; + else + m_startColor = kMinSpeedColor; + + m_startSpeed = max(m_startSpeed, kMinSpeed); + m_endSpeed = min(m_endSpeed, kMaxSpeed); + + double const kBias = 0.01; + if (fabs(m_endSpeed - m_startSpeed) < 1e-5) + m_endSpeed += kBias; +} + +size_t GpsTrackRenderer::GetAvailablePointsCount() const +{ + size_t pointsCount = 0; + for (size_t i = 0; i < m_renderData.size(); i++) + pointsCount += m_renderData[i]->m_pointsCount; + + return pointsCount; +} + +double GpsTrackRenderer::PlacePoints(size_t & cacheIndex, + GpsTrackPoint const & start, GpsTrackPoint const & end, + float radius, double diameterMercator, + double offset, double trackLengthMercator, + bool & gap, double & lengthFromStart) +{ + if (start.m_point.EqualDxDy(end.m_point, 1e-5)) + return offset; + + double const kDistanceScalar = 0.65; + + m2::PointD const delta = end.m_point - start.m_point; + double const length = delta.Length(); + m2::PointD const dir = delta.Normalize(); + double pos = offset; + while (pos < length) + { + if (gap) + { + double const dist = pos + diameterMercator * 0.5; + double const td = my::clamp(dist / length, 0.0, 1.0); + double const speed = start.m_speedMPS * (1.0 - td) + end.m_speedMPS * td; + double const ts = my::clamp((speed - m_startSpeed) / (m_endSpeed - m_startSpeed), 0.0, 1.0); + dp::Color color = InterpolateColors(m_startColor, kMaxSpeedColor, ts); + double const ta = my::clamp((lengthFromStart + dist) / trackLengthMercator, 0.0, 1.0); + double const alpha = kMinAlpha * (1.0 - ta) + kMaxAlpha * ta; + color = dp::Color(color.GetRed(), color.GetGreen(), color.GetBlue(), alpha); + + m2::PointD const p = start.m_point + dir * dist; + m_handlesCache[cacheIndex].first->SetPoint(m_handlesCache[cacheIndex].second, p, radius, color); + m_handlesCache[cacheIndex].second++; + if (m_handlesCache[cacheIndex].second >= m_handlesCache[cacheIndex].first->GetPointsCount()) + cacheIndex++; + ASSERT_LESS(cacheIndex, m_handlesCache.size(), ()); + } + gap = !gap; + pos += (diameterMercator * kDistanceScalar); + } + + lengthFromStart += length; + return pos - length; +} + +void GpsTrackRenderer::RenderTrack(ScreenBase const & screen, int zoomLevel, + ref_ptr<dp::GpuProgramManager> mng, + dp::UniformValuesStorage const & commonUniforms) +{ + if (zoomLevel < kMinVisibleZoomLevel) + return; + + if (m_needUpdate) + { + // Skip rendering if there is no any point. + if (m_points.empty()) + { + m_needUpdate = false; + return; + } + + m_radius = CalculateRadius(screen); + float const diameter = 2.0f * m_radius; + float const currentScaleGtoP = 1.0f / screen.GetScale(); + double const trackLengthMercator = CalculateTrackLength(); + double const trackLengthPixels = trackLengthMercator * currentScaleGtoP; + size_t const pointsCount = static_cast<size_t>(trackLengthPixels / (2 * diameter)); + if (pointsCount == 0) + { + m_needUpdate = false; + return; + } + + // Check if we have enough points. + size_t const availablePointsCount = GetAvailablePointsCount(); + if (pointsCount > availablePointsCount) + { + if (!m_waitForRenderData) + { + size_t const bucketSize = (pointsCount / kAveragePointsCount + 1) * kAveragePointsCount - availablePointsCount; + m_dataRequestFn(bucketSize); + } + m_waitForRenderData = true; + return; + } + else + { + m_waitForRenderData = false; + } + + // Update points' positions and colors. + if (!m_waitForRenderData) + { + ASSERT(!m_renderData.empty(), ()); + m_handlesCache.clear(); + for (size_t i = 0; i < m_renderData.size(); i++) + { + ASSERT_EQUAL(m_renderData[i]->m_bucket->GetOverlayHandlesCount(), 1, ()); + GpsTrackHandle * handle = static_cast<GpsTrackHandle*>(m_renderData[i]->m_bucket->GetOverlayHandle(0).get()); + handle->Clear(); + m_handlesCache.push_back(make_pair(handle, 0)); + } + + UpdateSpeedsAndColors(); + + size_t cacheIndex = 0; + double lengthFromStart = 0.0; + if (m_points.size() == 1) + { + m_handlesCache[cacheIndex].first->SetPoint(0, m_points.front().m_point, m_radius, kMaxSpeedColor); + m_handlesCache[cacheIndex].second++; + } + else + { + bool gap = true; + double const diameterMercator = diameter / currentScaleGtoP; + double offset = 0.0; + for (size_t i = 0; i + 1 < m_points.size(); i++) + offset = PlacePoints(cacheIndex, m_points[i], m_points[i + 1], m_radius, + diameterMercator, offset, trackLengthMercator, + gap, lengthFromStart); + } + m_needUpdate = false; + } + } + + if (m_handlesCache.empty() || m_handlesCache.front().second == 0) + return; + + GLFunctions::glClearDepth(); + + ASSERT_EQUAL(m_renderData.size(), m_handlesCache.size(), ()); + + // Render points. + dp::UniformValuesStorage uniforms = commonUniforms; + uniforms.SetFloatValue("u_opacity", 1.0f); + uniforms.SetFloatValue("u_radiusShift", m_radius * kOutlineRadiusScalar); + ref_ptr<dp::GpuProgram> program = mng->GetProgram(gpu::TRACK_POINT_PROGRAM); + program->Bind(); + + ASSERT_GREATER(m_renderData.size(), 0, ()); + dp::ApplyState(m_renderData.front()->m_state, program); + dp::ApplyUniforms(uniforms, program); + + for (size_t i = 0; i < m_renderData.size(); i++) + if (m_handlesCache[i].second != 0) + m_renderData[i]->m_bucket->Render(screen); +} + +void GpsTrackRenderer::Update() +{ + m_needUpdate = true; +} + +void GpsTrackRenderer::Clear() +{ + m_points.clear(); + m_needUpdate = true; +} + +} // namespace df + diff --git a/drape_frontend/gps_track_renderer.hpp b/drape_frontend/gps_track_renderer.hpp new file mode 100644 index 0000000000..3cdc81b151 --- /dev/null +++ b/drape_frontend/gps_track_renderer.hpp @@ -0,0 +1,64 @@ +#pragma once + +#include "drape_frontend/gps_track_point.hpp" +#include "drape_frontend/gps_track_shape.hpp" + +#include "drape/gpu_program_manager.hpp" +#include "drape/pointers.hpp" +#include "drape/uniform_values_storage.hpp" + +#include "map/gps_track_container.hpp" + +#include "geometry/screenbase.hpp" +#include "geometry/spline.hpp" + +#include "std/map.hpp" +#include "std/vector.hpp" + +namespace df +{ + +class GpsTrackRenderer final +{ +public: + using TRenderDataRequestFn = function<void(size_t)>; + explicit GpsTrackRenderer(TRenderDataRequestFn const & dataRequestFn); + + void AddRenderData(ref_ptr<dp::GpuProgramManager> mng, + drape_ptr<GpsTrackRenderData> && renderData); + + void UpdatePoints(vector<GpsTrackPoint> const & toAdd, + vector<uint32_t> const & toRemove); + + void RenderTrack(ScreenBase const & screen, int zoomLevel, + ref_ptr<dp::GpuProgramManager> mng, + dp::UniformValuesStorage const & commonUniforms); + + void Update(); + void Clear(); + +private: + float CalculateRadius(ScreenBase const & screen) const; + double CalculateTrackLength() const; + void UpdateSpeedsAndColors(); + size_t GetAvailablePointsCount() const; + double PlacePoints(size_t & cacheIndex, + GpsTrackPoint const & start, GpsTrackPoint const & end, + float radius, double diameterMercator, + double offset, double trackLengthMercator, + bool & gap, double & lengthFromStart); + + TRenderDataRequestFn m_dataRequestFn; + vector<drape_ptr<GpsTrackRenderData>> m_renderData; + vector<GpsTrackPoint> m_points; + bool m_needUpdate; + bool m_waitForRenderData; + vector<pair<GpsTrackHandle*, size_t>> m_handlesCache; + + double m_startSpeed; + double m_endSpeed; + dp::Color m_startColor; + float m_radius; +}; + +} // namespace df diff --git a/drape_frontend/gps_track_shape.cpp b/drape_frontend/gps_track_shape.cpp new file mode 100644 index 0000000000..f25dc08852 --- /dev/null +++ b/drape_frontend/gps_track_shape.cpp @@ -0,0 +1,173 @@ +#include "drape_frontend/gps_track_shape.hpp" + +#include "drape/attribute_provider.hpp" +#include "drape/batcher.hpp" +#include "drape/glsl_func.hpp" +#include "drape/glsl_types.hpp" +#include "drape/shader_def.hpp" + +#include "base/logging.hpp" + +namespace df +{ + +namespace +{ + +uint32_t const kDynamicStreamID = 0x7F; + +struct GpsTrackStaticVertex +{ + using TNormal = glsl::vec3; + + GpsTrackStaticVertex() = default; + GpsTrackStaticVertex(TNormal const & normal) : m_normal(normal) {} + + TNormal m_normal; +}; + +dp::GLState GetGpsTrackState() +{ + dp::GLState state(gpu::TRACK_POINT_PROGRAM, dp::GLState::OverlayLayer); + return state; +} + +dp::BindingInfo const & GetGpsTrackStaticBindingInfo() +{ + static unique_ptr<dp::BindingInfo> s_info; + if (s_info == nullptr) + { + dp::BindingFiller<GpsTrackStaticVertex> filler(1); + filler.FillDecl<GpsTrackStaticVertex::TNormal>("a_normal"); + s_info.reset(new dp::BindingInfo(filler.m_info)); + } + return *s_info; +} + +dp::BindingInfo const & GetGpsTrackDynamicBindingInfo() +{ + static unique_ptr<dp::BindingInfo> s_info; + if (s_info == nullptr) + { + dp::BindingFiller<GpsTrackDynamicVertex> filler(2, kDynamicStreamID); + filler.FillDecl<GpsTrackDynamicVertex::TPosition>("a_position"); + filler.FillDecl<GpsTrackDynamicVertex::TColor>("a_color"); + s_info.reset(new dp::BindingInfo(filler.m_info)); + } + return *s_info; +} + +} // namespace + +GpsTrackHandle::GpsTrackHandle(size_t pointsCount) + : OverlayHandle(FeatureID(), dp::Anchor::Center, 0) + , m_needUpdate(false) +{ + m_buffer.resize(pointsCount * dp::Batcher::VertexPerQuad); +} + +void GpsTrackHandle::GetAttributeMutation(ref_ptr<dp::AttributeBufferMutator> mutator, + ScreenBase const & screen) const +{ + UNUSED_VALUE(screen); + + if (!m_needUpdate) + return; + + TOffsetNode const & node = GetOffsetNode(kDynamicStreamID); + ASSERT(node.first.GetElementSize() == sizeof(GpsTrackDynamicVertex), ()); + ASSERT(node.second.m_count == m_buffer.size(), ()); + + uint32_t const byteCount = m_buffer.size() * sizeof(GpsTrackDynamicVertex); + void * buffer = mutator->AllocateMutationBuffer(byteCount); + memcpy(buffer, m_buffer.data(), byteCount); + + dp::MutateNode mutateNode; + mutateNode.m_region = node.second; + mutateNode.m_data = make_ref(buffer); + mutator->AddMutation(node.first, mutateNode); +} + +bool GpsTrackHandle::Update(ScreenBase const & screen) +{ + UNUSED_VALUE(screen); + return true; +} + +bool GpsTrackHandle::IndexesRequired() const +{ + return false; +} + +m2::RectD GpsTrackHandle::GetPixelRect(ScreenBase const & screen) const +{ + UNUSED_VALUE(screen); + return m2::RectD(); +} + +void GpsTrackHandle::GetPixelShape(ScreenBase const & screen, Rects & rects) const +{ + UNUSED_VALUE(screen); +} + +void GpsTrackHandle::SetPoint(size_t index, m2::PointD const & position, + float radius, dp::Color const & color) +{ + size_t bufferIndex = index * dp::Batcher::VertexPerQuad; + ASSERT_GREATER_OR_EQUAL(bufferIndex, 0, ()); + ASSERT_LESS(bufferIndex, m_buffer.size(), ()); + + for (size_t i = 0; i < dp::Batcher::VertexPerQuad; i++) + { + m_buffer[bufferIndex + i].m_position = glsl::vec3(position.x, position.y, radius); + m_buffer[bufferIndex + i].m_color = glsl::ToVec4(color); + } + m_needUpdate = true; +} + +void GpsTrackHandle::Clear() +{ + memset(m_buffer.data(), 0, m_buffer.size() * sizeof(GpsTrackDynamicVertex)); + m_needUpdate = true; +} + +size_t GpsTrackHandle::GetPointsCount() const +{ + return m_buffer.size() / dp::Batcher::VertexPerQuad; +} + +void GpsTrackShape::Draw(GpsTrackRenderData & data) +{ + ASSERT_NOT_EQUAL(data.m_pointsCount, 0, ()); + + size_t const kVerticesInPoint = dp::Batcher::VertexPerQuad; + size_t const kIndicesInPoint = dp::Batcher::IndexPerQuad; + vector<GpsTrackStaticVertex> staticVertexData; + staticVertexData.reserve(data.m_pointsCount * kVerticesInPoint); + for (size_t i = 0; i < data.m_pointsCount; i++) + { + staticVertexData.push_back(GpsTrackStaticVertex(GpsTrackStaticVertex::TNormal(-1.0f, 1.0f, 1.0f))); + staticVertexData.push_back(GpsTrackStaticVertex(GpsTrackStaticVertex::TNormal(-1.0f, -1.0f, 1.0f))); + staticVertexData.push_back(GpsTrackStaticVertex(GpsTrackStaticVertex::TNormal(1.0f, 1.0f, 1.0f))); + staticVertexData.push_back(GpsTrackStaticVertex(GpsTrackStaticVertex::TNormal(1.0f, -1.0f, 1.0f))); + } + + vector<GpsTrackDynamicVertex> dynamicVertexData; + dynamicVertexData.resize(data.m_pointsCount * kVerticesInPoint); + + dp::Batcher batcher(data.m_pointsCount * kIndicesInPoint, data.m_pointsCount * kVerticesInPoint); + dp::SessionGuard guard(batcher, [&data](dp::GLState const & state, drape_ptr<dp::RenderBucket> && b) + { + data.m_bucket = move(b); + data.m_state = state; + }); + + drape_ptr<dp::OverlayHandle> handle = make_unique_dp<GpsTrackHandle>(data.m_pointsCount); + + dp::AttributeProvider provider(2 /* stream count */, staticVertexData.size()); + provider.InitStream(0 /* stream index */, GetGpsTrackStaticBindingInfo(), make_ref(staticVertexData.data())); + provider.InitStream(1 /* stream index */, GetGpsTrackDynamicBindingInfo(), make_ref(dynamicVertexData.data())); + batcher.InsertListOfStrip(GetGpsTrackState(), make_ref(&provider), move(handle), kVerticesInPoint); +} + +} // namespace df diff --git a/drape_frontend/gps_track_shape.hpp b/drape_frontend/gps_track_shape.hpp new file mode 100644 index 0000000000..b8d57ccf1a --- /dev/null +++ b/drape_frontend/gps_track_shape.hpp @@ -0,0 +1,69 @@ +#pragma once + +#include "drape_frontend/map_shape.hpp" +#include "drape_frontend/shape_view_params.hpp" + +#include "drape/glstate.hpp" +#include "drape/render_bucket.hpp" +#include "drape/utils/vertex_decl.hpp" +#include "drape/overlay_handle.hpp" +#include "drape/pointers.hpp" + +#include "std/vector.hpp" + +namespace df +{ + +struct GpsTrackRenderData +{ + size_t m_pointsCount; + + dp::GLState m_state; + drape_ptr<dp::RenderBucket> m_bucket; + GpsTrackRenderData() : m_pointsCount(0), m_state(0, dp::GLState::OverlayLayer) {} +}; + +struct GpsTrackDynamicVertex +{ + using TPosition = glsl::vec3; + using TColor = glsl::vec4; + + GpsTrackDynamicVertex() = default; + GpsTrackDynamicVertex(TPosition const & pos, TColor const & color) + : m_position(pos) + , m_color(color) + {} + + TPosition m_position; + TColor m_color; +}; + +class GpsTrackHandle : public dp::OverlayHandle +{ + using TBase = dp::OverlayHandle; + +public: + GpsTrackHandle(size_t pointsCount); + void GetAttributeMutation(ref_ptr<dp::AttributeBufferMutator> mutator, + ScreenBase const & screen) const override; + bool Update(ScreenBase const & screen) override; + m2::RectD GetPixelRect(ScreenBase const & screen) const override; + void GetPixelShape(ScreenBase const & screen, Rects & rects) const override; + bool IndexesRequired() const override; + + void Clear(); + void SetPoint(size_t index, m2::PointD const & position, float radius, dp::Color const & color); + size_t GetPointsCount() const; + +private: + vector<GpsTrackDynamicVertex> m_buffer; + bool m_needUpdate; +}; + +class GpsTrackShape +{ +public: + static void Draw(GpsTrackRenderData & data); +}; + +} // namespace df diff --git a/drape_frontend/message.hpp b/drape_frontend/message.hpp index 0c5fafe824..621b9ca1f6 100644 --- a/drape_frontend/message.hpp +++ b/drape_frontend/message.hpp @@ -46,7 +46,11 @@ public: Invalidate, Allow3dMode, Allow3dBuildings, - EnablePerspective + EnablePerspective, + CacheGpsTrackPoints, + FlushGpsTrackPoints, + UpdateGpsTrackPoints, + ClearGpsTrackPoints }; virtual ~Message() {} diff --git a/drape_frontend/message_subclasses.hpp b/drape_frontend/message_subclasses.hpp index 3f1a1dd814..16351d0540 100644 --- a/drape_frontend/message_subclasses.hpp +++ b/drape_frontend/message_subclasses.hpp @@ -4,6 +4,8 @@ #include "drape_frontend/gui/layer_render.hpp" #include "drape_frontend/gui/skin.hpp" +#include "drape_frontend/gps_track_point.hpp" +#include "drape_frontend/gps_track_shape.hpp" #include "drape_frontend/route_builder.hpp" #include "drape_frontend/my_position.hpp" #include "drape_frontend/selection_shape.hpp" @@ -708,4 +710,53 @@ private: double const m_angleFOV; }; +class CacheGpsTrackPointsMessage : public Message +{ +public: + CacheGpsTrackPointsMessage(size_t pointsCount) : m_pointsCount(pointsCount) {} + Type GetType() const override { return Message::CacheGpsTrackPoints; } + size_t GetPointsCount() const { return m_pointsCount; } + +private: + size_t m_pointsCount; +}; + +class FlushGpsTrackPointsMessage : public Message +{ +public: + FlushGpsTrackPointsMessage(drape_ptr<GpsTrackRenderData> && renderData) + : m_renderData(move(renderData)) + {} + + Type GetType() const override { return Message::FlushGpsTrackPoints; } + drape_ptr<GpsTrackRenderData> && AcceptRenderData() { return move(m_renderData); } + +private: + drape_ptr<GpsTrackRenderData> m_renderData; +}; + +class UpdateGpsTrackPointsMessage : public Message +{ +public: + UpdateGpsTrackPointsMessage(vector<GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove) + : m_pointsToAdd(move(toAdd)) + , m_pointsToRemove(move(toRemove)) + {} + + Type GetType() const override { return Message::UpdateGpsTrackPoints; } + vector<GpsTrackPoint> const & GetPointsToAdd() { return m_pointsToAdd; } + vector<uint32_t> const & GetPointsToRemove() { return m_pointsToRemove; } + +private: + vector<GpsTrackPoint> m_pointsToAdd; + vector<uint32_t> m_pointsToRemove; +}; + +class ClearGpsTrackPointsMessage : public Message +{ +public: + ClearGpsTrackPointsMessage(){} + Type GetType() const override { return Message::ClearGpsTrackPoints; } +}; + } // namespace df diff --git a/map/framework.cpp b/map/framework.cpp index f4732ae79f..98f6da6f6a 100644 --- a/map/framework.cpp +++ b/map/framework.cpp @@ -878,6 +878,12 @@ void Framework::UpdateCountryInfo(storage::TIndex const & countryIndex, bool isC m_drapeEngine->SetCountryInfo(countryInfo, isCurrentCountry); } +void Framework::OnUpdateGpsTrackPoints(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove) +{ + if (m_drapeEngine != nullptr) + m_drapeEngine->UpdateGpsTrackPoints(move(toAdd), move(toRemove)); +} + void Framework::MemoryWarning() { LOG(LINFO, ("MemoryWarning")); diff --git a/map/framework.hpp b/map/framework.hpp index b91be003d7..f796da6e8c 100644 --- a/map/framework.hpp +++ b/map/framework.hpp @@ -11,6 +11,7 @@ #include "drape_frontend/gui/skin.hpp" #include "drape_frontend/drape_engine.hpp" +#include "drape_frontend/gps_track_point.hpp" #include "drape_frontend/user_event_stream.hpp" #include "drape_frontend/watch/frame_image.hpp" @@ -340,6 +341,8 @@ private: void OnUpdateCountryIndex(storage::TIndex const & currentIndex, m2::PointF const & pt); void UpdateCountryInfo(storage::TIndex const & countryIndex, bool isCurrentCountry); + void OnUpdateGpsTrackPoints(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove); + public: using TSearchRequest = search::QuerySaver::TSearchRequest; diff --git a/map/gps_track_container.cpp b/map/gps_track_container.cpp index 7965c0ee7c..b9ecc59193 100644 --- a/map/gps_track_container.cpp +++ b/map/gps_track_container.cpp @@ -29,7 +29,7 @@ void GpsTrackContainer::SetDuration(hours duration) RemoveOldPoints(removed); if (m_callback && !removed.empty()) - m_callback(vector<GpsTrackPoint>(), move(removed)); + m_callback(vector<df::GpsTrackPoint>(), move(removed)); } void GpsTrackContainer::SetMaxSize(size_t maxSize) @@ -42,7 +42,7 @@ void GpsTrackContainer::SetMaxSize(size_t maxSize) RemoveOldPoints(removed); if (m_callback && !removed.empty()) - m_callback(vector<GpsTrackPoint>(), move(removed)); + m_callback(vector<df::GpsTrackPoint>(), move(removed)); } void GpsTrackContainer::SetCallback(TGpsTrackDiffCallback callback, bool sendAll) @@ -54,7 +54,7 @@ void GpsTrackContainer::SetCallback(TGpsTrackDiffCallback callback, bool sendAll if (!m_callback || !sendAll || m_points.empty()) return; - vector<GpsTrackPoint> added; + vector<df::GpsTrackPoint> added; CopyPoints(added); m_callback(move(added), vector<uint32_t>()); @@ -72,7 +72,7 @@ uint32_t GpsTrackContainer::AddPoint(m2::PointD const & point, double speedMPS, return kInvalidId; } - GpsTrackPoint gtp; + df::GpsTrackPoint gtp; gtp.m_timestamp = timestamp; gtp.m_point = point; gtp.m_speedMPS = speedMPS; @@ -80,7 +80,7 @@ uint32_t GpsTrackContainer::AddPoint(m2::PointD const & point, double speedMPS, m_points.push_back(gtp); - vector<GpsTrackPoint> added; + vector<df::GpsTrackPoint> added; added.emplace_back(gtp); vector<uint32_t> removed; @@ -92,7 +92,7 @@ uint32_t GpsTrackContainer::AddPoint(m2::PointD const & point, double speedMPS, return gtp.m_id; } -void GpsTrackContainer::GetPoints(vector<GpsTrackPoint> & points) const +void GpsTrackContainer::GetPoints(vector<df::GpsTrackPoint> & points) const { lock_guard<mutex> lg(m_guard); @@ -110,11 +110,14 @@ void GpsTrackContainer::RemoveOldPoints(vector<uint32_t> & removedIds) if (m_points.front().m_timestamp < lowerBorder) { - GpsTrackPoint pt; + df::GpsTrackPoint pt; pt.m_timestamp = lowerBorder; auto const itr = lower_bound(m_points.begin(), m_points.end(), pt, - [](GpsTrackPoint const & a, GpsTrackPoint const & b)->bool{ return a.m_timestamp < b.m_timestamp; }); + [](df::GpsTrackPoint const & a, df::GpsTrackPoint const & b) -> bool + { + return a.m_timestamp < b.m_timestamp; + }); if (itr != m_points.begin()) { @@ -138,11 +141,11 @@ void GpsTrackContainer::RemoveOldPoints(vector<uint32_t> & removedIds) } } -void GpsTrackContainer::CopyPoints(vector<GpsTrackPoint> & points) const +void GpsTrackContainer::CopyPoints(vector<df::GpsTrackPoint> & points) const { // Must be called under m_guard lock - vector<GpsTrackPoint> tmp; + vector<df::GpsTrackPoint> tmp; tmp.reserve(m_points.size()); copy(m_points.begin(), m_points.end(), back_inserter(tmp)); points.swap(tmp); diff --git a/map/gps_track_container.hpp b/map/gps_track_container.hpp index ec3027e423..804d90c074 100644 --- a/map/gps_track_container.hpp +++ b/map/gps_track_container.hpp @@ -1,29 +1,15 @@ #pragma once +#include "drape_frontend/gps_track_point.hpp" + #include "std/chrono.hpp" #include "std/deque.hpp" #include "std/function.hpp" #include "std/mutex.hpp" -#include "geometry/point2d.hpp" - class GpsTrackContainer { public: - struct GpsTrackPoint - { - // Timestamp of the point, seconds from 1st Jan 1970 - double m_timestamp; - - // Point in the Mercator projection - m2::PointD m_point; - - // Speed in the point, M/S - double m_speedMPS; - - // Unique identifier of the point - uint32_t m_id; - }; static uint32_t constexpr kInvalidId = numeric_limits<uint32_t>::max(); @@ -31,7 +17,7 @@ public: /// @param toAdd - collection of points to add. /// @param toRemove - collection of point indices to remove. /// @note Calling of a GpsTrackContainer's function from the callback causes deadlock. - using TGpsTrackDiffCallback = std::function<void(vector<GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove)>; + using TGpsTrackDiffCallback = std::function<void(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove)>; GpsTrackContainer(); @@ -64,11 +50,11 @@ public: /// Returns points snapshot from the container. /// @param points - output for collection of points. - void GetPoints(vector<GpsTrackPoint> & points) const; + void GetPoints(vector<df::GpsTrackPoint> & points) const; private: void RemoveOldPoints(vector<uint32_t> & removedIds); - void CopyPoints(vector<GpsTrackPoint> & points) const; + void CopyPoints(vector<df::GpsTrackPoint> & points) const; mutable mutex m_guard; @@ -82,7 +68,7 @@ private: // Collection of points, by nature is asc. sorted by m_timestamp. // Max size of m_points is adjusted by m_trackDuration and m_maxSize. - deque<GpsTrackPoint> m_points; + deque<df::GpsTrackPoint> m_points; // Simple counter which is used to generate point unique ids. uint32_t m_counter; diff --git a/map/map_tests/gps_track_container_test.cpp b/map/map_tests/gps_track_container_test.cpp index 4d3baa219d..20c7a1279e 100644 --- a/map/map_tests/gps_track_container_test.cpp +++ b/map/map_tests/gps_track_container_test.cpp @@ -12,12 +12,12 @@ uint32_t constexpr kSecondsPerHour = 60 * 60; struct GpsTrackContainerCallback { public: - void OnChange(vector<GpsTrackContainer::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove) + void OnChange(vector<df::GpsTrackPoint> && toAdd, vector<uint32_t> && toRemove) { m_toAdd.insert(m_toAdd.end(), toAdd.begin(), toAdd.end()); m_toRemove.insert(m_toRemove.end(), toRemove.begin(), toRemove.end()); } - vector<GpsTrackContainer::GpsTrackPoint> m_toAdd; + vector<df::GpsTrackPoint> m_toAdd; vector<uint32_t> m_toRemove; }; @@ -76,7 +76,7 @@ UNIT_TEST(GpsTrackContainer_Test) // and test there is only id25 point in the track - vector<GpsTrackContainer::GpsTrackPoint> points; + vector<df::GpsTrackPoint> points; gpstrack.GetPoints(points); TEST_EQUAL(1, points.size(), ()); diff --git a/std/algorithm.hpp b/std/algorithm.hpp index b77cd4ff4c..27a647d675 100644 --- a/std/algorithm.hpp +++ b/std/algorithm.hpp @@ -13,6 +13,7 @@ using std::fill; using std::find; using std::find_if; using std::find_first_of; +using std::is_sorted; using std::lexicographical_compare; using std::lower_bound; using std::max; |