void
Trace::GetPoints(TracePointVector &v, unsigned min_time,
                 const GeoPoint &location, fixed min_distance) const
{
  /* skip the trace points that are before min_time */
  Trace::const_iterator i = begin(), end = this->end();
  unsigned skipped = 0;
  while (true) {
    if (i == end)
      /* nothing left */
      return;

    if (i->GetTime() >= min_time)
      /* found the first point that is within range */
      break;

    ++i;
    ++skipped;
  }

  assert(skipped < size());

  v.reserve(size() - skipped);
  const unsigned range = ProjectRange(location, min_distance);
  const unsigned sq_range = range * range;
  do {
    v.push_back(*i);
    i.NextSquareRange(sq_range, end);
  } while (i != end);
}

static std::pair<double, double>
GetMinMax(TrailSettings::Type type, const TracePointVector &trace)
{
  double value_min, value_max;

  if (type == TrailSettings::Type::ALTITUDE) {
    value_max = 1000;
    value_min = 500;

    for (auto it = trace.begin(); it != trace.end(); ++it) {
      value_max = std::max(it->GetAltitude(), value_max);
      value_min = std::min(it->GetAltitude(), value_min);
    }
  } else {
    value_max = 0.75;
    value_min = -2.0;

    for (auto it = trace.begin(); it != trace.end(); ++it) {
      value_max = std::max(it->GetVario(), value_max);
      value_min = std::min(it->GetVario(), value_min);
    }

    value_max = std::min(7.5, value_max);
    value_min = std::max(-5.0, value_min);
  }

  return std::make_pair(value_min, value_max);
}

void
Trace::GetPoints(TracePointVector& iov) const
{
  iov.clear();
  iov.reserve(size());
  std::copy(begin(), end(), std::back_inserter(iov));
}

static std::pair<fixed, fixed>
GetMinMax(TrailSettings::Type type, const TracePointVector &trace)
{
  fixed value_min, value_max;

  if (type == TrailSettings::Type::ALTITUDE) {
    value_max = fixed(1000);
    value_min = fixed(500);

    for (auto it = trace.begin(); it != trace.end(); ++it) {
      value_max = std::max(it->GetAltitude(), value_max);
      value_min = std::min(it->GetAltitude(), value_min);
    }
  } else {
    value_max = fixed(0.75);
    value_min = fixed(-2.0);

    for (auto it = trace.begin(); it != trace.end(); ++it) {
      value_max = std::max(it->GetVario(), value_max);
      value_min = std::min(it->GetVario(), value_min);
    }

    value_max = std::min(fixed(7.5), value_max);
    value_min = std::max(fixed(-5.0), value_min);
  }

  return std::make_pair(value_min, value_max);
}

void 
OLCLeague::copy_solution(TracePointVector &vec) const
{
  vec.clear();
  vec.reserve(5);
  if (solution_found) {
    for (unsigned i = 0; i < 5; ++i)
      vec.push_back(best_solution[i]);
  }
}

void
OLCDijkstra::copy_solution(TracePointVector &vec)
{
  vec.clear();
  if (solution_found) {
    vec.reserve(num_stages);
    for (unsigned i = 0; i < num_stages; ++i)
      vec.push_back(best_solution[i]);
  }
}

void
PrintHelper::contestmanager_print(const ContestManager &man,
                                  const Trace &trace_full,
                                  const Trace &trace_triangle,
                                  const Trace &trace_sprint)
{
  Directory::Create(_T("output/results"));

  {
    std::ofstream fs("output/results/res-olc-trace.txt");
    TracePointVector v;
    trace_full.GetPoints(v);

    for (auto it = v.begin(); it != v.end(); ++it)
      fs << it->GetLocation().longitude << " " << it->GetLocation().latitude
         << " " << it->GetAltitude() << " " << it->GetTime()
         << "\n";
  }

  {
    std::ofstream fs("output/results/res-olc-trace_triangle.txt");

    TracePointVector v;
    trace_triangle.GetPoints(v);

    for (auto it = v.begin(); it != v.end(); ++it)
      fs << it->GetLocation().longitude << " " << it->GetLocation().latitude
         << " " << it->GetAltitude() << " " << it->GetTime()
         << "\n";
  }

  {
    std::ofstream fs("output/results/res-olc-trace_sprint.txt");

    TracePointVector v;
    trace_sprint.GetPoints(v);

    for (auto it = v.begin(); it != v.end(); ++it)
      fs << it->GetLocation().longitude << " " << it->GetLocation().latitude
         << " " << it->GetAltitude() << " " << it->GetTime()
         << "\n";
  }

  std::ofstream fs("output/results/res-olc-solution.txt");

  if (man.stats.solution[0].empty()) {
    fs << "# no solution\n";
    return;
  }

  if (positive(man.stats.result[0].time)) {

    for (auto it = man.stats.solution[0].begin();
         it != man.stats.solution[0].end(); ++it) {
      fs << it->GetLocation().longitude << " " << it->GetLocation().latitude
         << " " << it->GetTime()
         << "\n";
    }
  }
}

bool 
OnlineContest::update_trace_sample(const AIRCRAFT_STATE &state,
                                   TracePointVector& vec)
{
  if (vec.empty())
    return false;
    
  if (state.NavAltitude < vec.back().NavAltitude) {
    // replace if lower even if not significant distance away
    vec.back().NavAltitude = state.NavAltitude;
    return true;
  }

  return false;
}

bool
OLCLeague::solve(bool exhaustive)
{
  TracePointVector trace;
  trace_master.get_trace_edges(trace);

  if (trace.size()!=2) {
    return false;
  }

  if (!finish_altitude_valid(trace[0], trace[1])) {
    return false;
  }

  // solution found, so set start/finish points
  solution[0] = trace[0];
  solution[4] = trace[1];

  // scan through classic solution to find points there to add

  unsigned index_fill = 1;

  for (unsigned index_classic = 1; index_classic+1 < solution_classic.size(); ++index_classic) {
    if ((solution_classic[index_classic].time > solution[index_fill-1].time)
        &&(solution_classic[index_classic].time < trace[1].time)) {

      solution[index_fill] = solution_classic[index_classic];
      index_fill++;
      if (index_fill==4) {
        break;
      }
    }
  }

  // if insufficient points found, add repeats of previous points

  for (; index_fill<4; ++index_fill) {
    solution[index_fill] = solution[index_fill-1];
  }

  solution_found = true;

  return true;
}

void
TrailRenderer::DrawTraceVector(Canvas &canvas, const Projection &projection,
                               const TracePointVector &trace)
{
  const unsigned n = trace.size();
  RasterPoint *p = Prepare(n);

  for (const auto &i : trace)
    *p++ = projection.GeoToScreen(i.GetLocation());

  DrawPreparedPolyline(canvas, n);
}

TracePointVector
Trace::get_trace_points(const unsigned max_points) const
{
  if (max_points == 2) {
    if (trace_tree.size()<2) {
      return TracePointVector();
    }
    // special case - just look for points within time range
    TracePoint p;
    unsigned tmin = (unsigned)-1;
    for (TraceTree::const_iterator tr = trace_tree.begin();
         tr != trace_tree.end(); ++tr) {
      if (inside_time_window(tr->time) && (tr->time< tmin)) {
        p = *tr;
        tmin = tr->time;
      }
    }
    TracePointVector v;
    v.push_back(p);
    v.push_back(m_last_point);
    return v;
  }

  TracePointSet tset(begin(), end());

  if (tset.empty())
    return TracePointVector();

  TracePointList tlist(tset.begin(), tset.end());

  unsigned mrange = 3;

  while (tlist.size() > max_points) {
    thin_trace(tlist, mrange);
    mrange = (mrange * 4) / 3;
  }

  return TracePointVector(tlist.begin(), tlist.end());
}

 void ScanBounds(GeoBounds &bounds) const {
   trace.ScanBounds(bounds);
 }