// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_CRDTP_FIND_BY_FIRST_H_
#define V8_CRDTP_FIND_BY_FIRST_H_

#include <algorithm>
#include <cstdint>
#include <memory>
#include <vector>

#include "export.h"
#include "span.h"

namespace v8_crdtp {
// =============================================================================
// FindByFirst - Retrieval from a sorted vector that's keyed by span<uint8_t>.
// =============================================================================

// Given a vector of pairs sorted by the first element of each pair, find
// the corresponding value given a key to be compared to the first element.
// Together with std::inplace_merge and pre-sorting or std::sort, this can
// be used to implement a minimalistic equivalent of Chromium's flat_map.

// In this variant, the template parameter |T| is a value type and a
// |default_value| is provided.
template <typename T>
T FindByFirst(const std::vector<std::pair<span<uint8_t>, T>>& sorted_by_first,
              span<uint8_t> key,
              T default_value) {
  auto it = std::lower_bound(
      sorted_by_first.begin(), sorted_by_first.end(), key,
      [](const std::pair<span<uint8_t>, T>& left, span<uint8_t> right) {
        return SpanLessThan(left.first, right);
      });
  return (it != sorted_by_first.end() && SpanEquals(it->first, key))
             ? it->second
             : default_value;
}

// In this variant, the template parameter |T| is a class or struct that's
// instantiated in std::unique_ptr, and we return either a T* or a nullptr.
template <typename T>
T* FindByFirst(const std::vector<std::pair<span<uint8_t>, std::unique_ptr<T>>>&
                   sorted_by_first,
               span<uint8_t> key) {
  auto it = std::lower_bound(
      sorted_by_first.begin(), sorted_by_first.end(), key,
      [](const std::pair<span<uint8_t>, std::unique_ptr<T>>& left,
         span<uint8_t> right) { return SpanLessThan(left.first, right); });
  return (it != sorted_by_first.end() && SpanEquals(it->first, key))
             ? it->second.get()
             : nullptr;
}
}  // namespace v8_crdtp

#endif  // V8_CRDTP_FIND_BY_FIRST_H_