#ifndef CAFFE2_OPERATORS_FIND_OP_H_
#define CAFFE2_OPERATORS_FIND_OP_H_

#include "caffe2/core/context.h"
#include "caffe2/core/logging.h"
#include "caffe2/core/operator.h"

#include <unordered_map>

namespace caffe2 {

template <class Context>
class FindOp final : public Operator<Context> {
 public:
  template <class... Args>
  explicit FindOp(Args&&... args)
      : Operator<Context>(std::forward<Args>(args)...),
        missing_value_(
            this->template GetSingleArgument<int>("missing_value", -1)) {}
  USE_OPERATOR_CONTEXT_FUNCTIONS;
  USE_DISPATCH_HELPER;

  bool RunOnDevice() {
    return DispatchHelper<TensorTypes<int, long>>::call(this, Input(0));
  }

 protected:
  template <typename T>
  bool DoRunWithType() {
    auto& idx = Input(0);
    auto& needles = Input(1);

    auto* res_indices = Output(0, needles.sizes(), at::dtype<T>());

    const T* idx_data = idx.template data<T>();
    const T* needles_data = needles.template data<T>();
    T* res_data = res_indices->template mutable_data<T>();
    auto idx_size = idx.numel();

    // Use an arbitrary cut-off for when to use brute-force
    // search. For larger needle sizes we first put the
    // index into a map
    if (needles.numel() < 16) {
      // Brute force O(nm)
      for (int i = 0; i < needles.numel(); i++) {
        T x = needles_data[i];
        T res = static_cast<T>(missing_value_);
        for (int j = idx_size - 1; j >= 0; j--) {
          if (idx_data[j] == x) {
            res = j;
            break;
          }
        }
        res_data[i] = res;
      }
    } else {
      // O(n + m)
      std::unordered_map<T, int> idx_map;
      for (int j = 0; j < idx_size; j++) {
        idx_map[idx_data[j]] = j;
      }
      for (int i = 0; i < needles.numel(); i++) {
        T x = needles_data[i];
        auto it = idx_map.find(x);
        res_data[i] = (it == idx_map.end() ? missing_value_ : it->second);
      }
    }

    return true;
  }

 protected:
  int missing_value_;
};

} // namespace caffe2

#endif // CAFFE2_OPERATORS_FIND_OP_H_