/*
 * Copyright (c) 2022, Alliance for Open Media. All rights reserved
 *
 * This source code is subject to the terms of the BSD 2 Clause License and
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
 * was not distributed with this source code in the LICENSE file, you can
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
 * Media Patent License 1.0 was not distributed with this source code in the
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
 */

#include <algorithm>
#include <set>
#include <utility>
#include <tuple>
#include <vector>

#include "av1/reference_manager.h"
#include "av1/ratectrl_qmode.h"

namespace aom {

void RefFrameManager::Reset() {
  free_ref_idx_list_.clear();
  for (int i = 0; i < static_cast<int>(ref_frame_table_.size()); ++i) {
    free_ref_idx_list_.push_back(i);
    ref_frame_table_[i] = GopFrameInvalid();
  }
  forward_stack_.clear();
  backward_queue_.clear();
  last_queue_.clear();
}

int RefFrameManager::AllocateRefIdx() {
  if (free_ref_idx_list_.empty()) {
    size_t backward_size = backward_queue_.size();
    size_t last_size = last_queue_.size();
    if (last_size >= backward_size) {
      int ref_idx = last_queue_.front();
      last_queue_.pop_front();
      free_ref_idx_list_.push_back(ref_idx);
    } else {
      int ref_idx = backward_queue_.front();
      backward_queue_.pop_front();
      free_ref_idx_list_.push_back(ref_idx);
    }
  }

  int ref_idx = free_ref_idx_list_.front();
  free_ref_idx_list_.pop_front();
  return ref_idx;
}

int RefFrameManager::GetRefFrameCountByType(
    RefUpdateType ref_update_type) const {
  size_t cnt = 0;
  switch (ref_update_type) {
    case RefUpdateType::kForward: cnt = forward_stack_.size(); break;
    case RefUpdateType::kBackward: cnt = backward_queue_.size(); break;
    case RefUpdateType::kLast: cnt = last_queue_.size(); break;
    case RefUpdateType::kNone: cnt = 0; break;
  }
  return static_cast<int>(cnt);
}

int RefFrameManager::GetRefFrameCount() const {
  return GetRefFrameCountByType(RefUpdateType::kForward) +
         GetRefFrameCountByType(RefUpdateType::kBackward) +
         GetRefFrameCountByType(RefUpdateType::kLast);
}

// TODO(angiebird): Add unit test.
// Find the ref_idx corresponding to a ref_update_type.
// Return -1 if no ref frame is found.
// The priority_idx indicate closeness between the current frame and
// the ref frame in display order.
// For example, ref_update_type == kForward and priority_idx == 0 means
// find the closest ref frame in forward_stack_.
int RefFrameManager::GetRefFrameIdxByPriority(RefUpdateType ref_update_type,
                                              int priority_idx) const {
  if (ref_update_type == RefUpdateType::kForward) {
    int size = static_cast<int>(forward_stack_.size());
    // When two or more forward reference frames can be used, first get
    // the highest quality one as the ARF, then going from nearest to
    // the more distant ones in the forward reference frame list.
    if (priority_idx < size) {
      if (allow_two_fwd_frames_) {
        if (priority_idx == 0) return forward_stack_[0];
        return forward_stack_[size - priority_idx];
      }

      // Handle the special case where only one forward reference frame
      // can be used. In this setting, we prefer the nearest frame.
      return forward_stack_[size - 1 - priority_idx];
    }
  } else if (ref_update_type == RefUpdateType::kBackward) {
    int size = static_cast<int>(backward_queue_.size());
    if (priority_idx < size) {
      return backward_queue_[size - priority_idx - 1];
    }
  } else if (ref_update_type == RefUpdateType::kLast) {
    int size = static_cast<int>(last_queue_.size());
    if (priority_idx < size) {
      return last_queue_[size - priority_idx - 1];
    }
  }
  return -1;
}

// The priority_idx indicate closeness between the current frame and
// the ref frame in display order.
// For example, ref_update_type == kForward and priority_idx == 0 means
// find the closest ref frame in forward_stack_.
GopFrame RefFrameManager::GetRefFrameByPriority(RefUpdateType ref_update_type,
                                                int priority_idx) const {
  int ref_idx = GetRefFrameIdxByPriority(ref_update_type, priority_idx);
  if (ref_idx == -1) {
    return GopFrameInvalid();
  }
  assert(ref_frame_table_[ref_idx].update_ref_idx == ref_idx);
  return ref_frame_table_[ref_idx];
}

GopFrame RefFrameManager::GetRefFrameByIndex(int ref_idx) const {
  return ref_frame_table_[ref_idx];
}

ReferenceName get_ref_name(RefUpdateType ref_update_type, int priority_idx,
                           const std::set<ReferenceName> &used_name_set) {
  // TODO(angiebird): Find the better way to assign name lists.
  // Maybe sort the names based on how frequent each name is being used in the
  // past?
  const std::vector<ReferenceName> forward_name_list{
    ReferenceName::kAltrefFrame,  ReferenceName::kBwdrefFrame,
    ReferenceName::kAltref2Frame, ReferenceName::kGoldenFrame,
    ReferenceName::kLast3Frame,   ReferenceName::kLast2Frame,
    ReferenceName::kLastFrame
  };
  const std::vector<ReferenceName> backward_name_list{
    ReferenceName::kGoldenFrame, ReferenceName::kLastFrame,
    ReferenceName::kLast2Frame,  ReferenceName::kLast3Frame,
    ReferenceName::kBwdrefFrame, ReferenceName::kAltref2Frame,
    ReferenceName::kAltrefFrame
  };
  const std::vector<ReferenceName> last_name_list{
    ReferenceName::kLastFrame,   ReferenceName::kLast2Frame,
    ReferenceName::kLast3Frame,  ReferenceName::kGoldenFrame,
    ReferenceName::kBwdrefFrame, ReferenceName::kAltref2Frame,
    ReferenceName::kAltrefFrame
  };

  const std::vector<ReferenceName> *name_list = nullptr;
  switch (ref_update_type) {
    case RefUpdateType::kForward: name_list = &forward_name_list; break;
    case RefUpdateType::kBackward: name_list = &backward_name_list; break;
    case RefUpdateType::kLast: name_list = &last_name_list; break;
    case RefUpdateType::kNone: break;
  }

  if (name_list) {
    const int name_list_size = static_cast<int>(name_list->size());
    for (int idx = priority_idx; idx < name_list_size; ++idx) {
      ReferenceName ref_name = name_list->at(idx);
      bool not_used = used_name_set.find(ref_name) == used_name_set.end();
      if (not_used) return ref_name;
    }
  }
  return ReferenceName::kNoneFrame;
}

// Generate a list of available reference frames in priority order for the
// current to-be-coded frame. The list size should be less or equal to the size
// of ref_frame_table_. The reference frames with smaller indices are more
// likely to be a good reference frame. Therefore, they should be prioritized
// when the reference frame count is limited. For example, if we plan to use 3
// reference frames, we should choose ref_frame_list[0], ref_frame_list[1] and
// ref_frame_list[2].
std::vector<ReferenceFrame> RefFrameManager::GetRefFrameListByPriority() const {
  constexpr int round_robin_size = 3;
  const std::vector<RefUpdateType> round_robin_list{ RefUpdateType::kForward,
                                                     RefUpdateType::kBackward,
                                                     RefUpdateType::kLast };
  std::vector<int> priority_idx_list(round_robin_size, 0);
  int available_ref_frames = GetRefFrameCount();
  std::vector<ReferenceFrame> ref_frame_list;
  int ref_frame_count = 0;
  int round_robin_idx = 0;

  std::set<ReferenceName> used_name_set;
  while (ref_frame_count < available_ref_frames &&
         ref_frame_count < max_ref_frames_) {
    const RefUpdateType ref_update_type = round_robin_list[round_robin_idx];
    int priority_idx = priority_idx_list[round_robin_idx];
    int ref_idx = GetRefFrameIdxByPriority(ref_update_type, priority_idx);
    if (ref_idx != -1) {
      const ReferenceName name =
          get_ref_name(ref_update_type, priority_idx, used_name_set);
      assert(name != ReferenceName::kNoneFrame);
      used_name_set.insert(name);
      ReferenceFrame ref_frame = { ref_idx, name };
      ref_frame_list.push_back(ref_frame);
      ++ref_frame_count;
      ++priority_idx_list[round_robin_idx];
    }
    round_robin_idx = (round_robin_idx + 1) % round_robin_size;
  }
  return ref_frame_list;
}

void RefFrameManager::UpdateOrder(int global_order_idx) {
  cur_global_order_idx_ = global_order_idx;
  if (forward_stack_.empty()) {
    return;
  }
  int ref_idx = forward_stack_.back();
  const GopFrame &gf_frame = ref_frame_table_[ref_idx];

  // If the current processing frame is an overlay / show existing frame.
  if (gf_frame.global_order_idx == global_order_idx) {
    forward_stack_.pop_back();
    if (gf_frame.is_golden_frame) {
      // high quality frame
      backward_queue_.push_back(ref_idx);
    } else {
      last_queue_.push_back(ref_idx);
    }
  }
}

int RefFrameManager::ColocatedRefIdx(int global_order_idx) {
  if (forward_stack_.empty()) return -1;
  int ref_idx = forward_stack_.back();
  int arf_global_order_idx = ref_frame_table_[ref_idx].global_order_idx;
  if (arf_global_order_idx == global_order_idx) {
    return ref_idx;
  }
  return -1;
}

static RefUpdateType infer_ref_update_type(const GopFrame &gop_frame,
                                           int cur_global_order_idx) {
  if (gop_frame.global_order_idx > cur_global_order_idx) {
    return RefUpdateType::kForward;
  }
  if (gop_frame.is_golden_frame) {
    return RefUpdateType::kBackward;
  }
  if (gop_frame.encode_ref_mode == EncodeRefMode::kShowExisting ||
      gop_frame.encode_ref_mode == EncodeRefMode::kOverlay) {
    return RefUpdateType::kNone;
  }
  return RefUpdateType::kLast;
}

using PrimaryRefKey = std::tuple<int,   // abs layer_depth delta
                                 bool,  // is_key_frame differs
                                 bool,  // is_golden_frame differs
                                 bool,  // is_arf_frame differs
                                 bool,  // is_show_frame differs
                                 bool,  // encode_ref_mode differs
                                 int>;  // abs order_idx delta

// Generate PrimaryRefKey based on abs layer_depth delta,
// frame flags and abs order_idx delta. These are the fields that will
// be used to pick the primary reference frame for probability model
static PrimaryRefKey get_primary_ref_key(const GopFrame &cur_frame,
                                         const GopFrame &ref_frame) {
  return std::make_tuple(abs(cur_frame.layer_depth - ref_frame.layer_depth),
                         cur_frame.is_key_frame != ref_frame.is_key_frame,
                         cur_frame.is_golden_frame != ref_frame.is_golden_frame,
                         cur_frame.is_arf_frame != ref_frame.is_arf_frame,
                         cur_frame.is_show_frame != ref_frame.is_show_frame,
                         cur_frame.encode_ref_mode != ref_frame.encode_ref_mode,
                         abs(cur_frame.order_idx - ref_frame.order_idx));
}

// Pick primary_ref_idx for probability model.
ReferenceFrame RefFrameManager::GetPrimaryRefFrame(
    const GopFrame &gop_frame) const {
  assert(gop_frame.is_valid);
  std::vector<std::pair<PrimaryRefKey, int>> candidate_list;
  for (auto &ref_frame_in_gop_frame : gop_frame.ref_frame_list) {
    const GopFrame &ref_frame = ref_frame_table_[ref_frame_in_gop_frame.index];
    if (ref_frame.is_valid) {
      assert(ref_frame_in_gop_frame.index == ref_frame.update_ref_idx);
      PrimaryRefKey key = get_primary_ref_key(gop_frame, ref_frame);
      std::pair<PrimaryRefKey, int> candidate = {
        key, ref_frame_in_gop_frame.index
      };
      candidate_list.push_back(candidate);
    }
  }

  std::sort(candidate_list.begin(), candidate_list.end());

  ReferenceFrame ref_frame = { -1, ReferenceName::kNoneFrame };
  assert(candidate_list.size() == gop_frame.ref_frame_list.size());
  if (!candidate_list.empty()) {
    int ref_idx = candidate_list[0].second;
    for (const auto &frame : gop_frame.ref_frame_list) {
      if (frame.index == ref_idx) {
        ref_frame = frame;
      }
    }
  }
  return ref_frame;
}

void RefFrameManager::UpdateRefFrameTable(GopFrame *gop_frame) {
  allow_two_fwd_frames_ =
      (max_ref_frames_ - !!GetRefFrameCountByType(RefUpdateType::kBackward) -
       !!GetRefFrameCountByType(RefUpdateType::kLast)) >= 2;
  gop_frame->ref_frame_list = GetRefFrameListByPriority();
  gop_frame->primary_ref_frame = GetPrimaryRefFrame(*gop_frame);
  gop_frame->colocated_ref_idx = ColocatedRefIdx(gop_frame->global_order_idx);

  if (gop_frame->is_show_frame) {
    UpdateOrder(gop_frame->global_order_idx);
  }
  // Call infer_ref_update_type() after UpdateOrder() so that
  // cur_global_order_idx_ is up-to-date
  RefUpdateType ref_update_type =
      infer_ref_update_type(*gop_frame, cur_global_order_idx_);
  if (ref_update_type == RefUpdateType::kNone) {
    gop_frame->update_ref_idx = -1;
  } else {
    const int ref_idx = AllocateRefIdx();
    gop_frame->update_ref_idx = ref_idx;
    switch (ref_update_type) {
      case RefUpdateType::kForward: forward_stack_.push_back(ref_idx); break;
      case RefUpdateType::kBackward: backward_queue_.push_back(ref_idx); break;
      case RefUpdateType::kLast: last_queue_.push_back(ref_idx); break;
      case RefUpdateType::kNone: break;
    }
    ref_frame_table_[ref_idx] = *gop_frame;
  }
}

}  // namespace aom