/*
  This file is part of CDO. CDO is a collection of Operators to
  manipulate and analyse Climate model Data.

  Copyright (C) 2003-2020 Uwe Schulzweida, <uwe.schulzweida AT mpimet.mpg.de>
  See COPYING file for copying and redistribution conditions.

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; version 2 of the License.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
*/
/*
  This is a C library of the Fortran SCRIP version 1.4

  ===>>> Please send bug reports to <https://mpimet.mpg.de/cdo> <<<===

  Spherical Coordinate Remapping and Interpolation Package (SCRIP)
  ================================================================

  SCRIP is a software package which computes addresses and weights for
  remapping and interpolating fields between grids in spherical coordinates.
  It was written originally for remapping fields to other grids in a coupled
  climate model, but is sufficiently general that it can be used in other
  applications as well. The package should work for any grid on the surface
  of a sphere. SCRIP currently supports four remapping options:

  Conservative remapping
  ----------------------
  First- and second-order conservative remapping as described in
  Jones (1999, Monthly Weather Review, 127, 2204-2210).

  Bilinear interpolation
  ----------------------
  Slightly generalized to use a local bilinear approximation
  (only logically-rectangular grids).

  Bicubic interpolation
  ----------------------
  Similarly generalized (only logically-rectangular grids).

  Distance-weighted averaging
  ---------------------------
  Distance-weighted average of a user-specified number of nearest neighbor
  values.

  Documentation
  =============

  http://climate.lanl.gov/Software/SCRIP/SCRIPusers.pdf

*/
/*
  2013-11-08 Uwe Schulzweida: split remapgrid class to src_grid and tgt_grid
  2012-01-16 Uwe Schulzweida: alloc grid2_bound_box only for conservative
  remapping 2011-01-07 Uwe Schulzweida: Changed remap weights from 2D to 1D
  array 2009-05-25 Uwe Schulzweida: Changed restrict data type from double to
  int 2009-01-11 Uwe Schulzweida: OpenMP parallelization
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <cdi.h>

#include "cdo_options.h"
#include "cimdOmp.h"
#include "dmemory.h"
#include "process_int.h"
#include "cdo_wtime.h"
#include <mpim_grid.h>
#include "gridreference.h"
#include "remap.h"

#define IS_REG2D_GRID(gridID) (gridInqType(gridID) == GRID_LONLAT || gridInqType(gridID) == GRID_GAUSSIAN)

static bool remap_gen_weights = true;
static bool remap_write_remap = false;
static int remap_num_srch_bins = 180;
#define DEFAULT_MAX_ITER 100
size_t remap_max_iter = DEFAULT_MAX_ITER;  // Max iteration count for i, j iteration

void
remap_set_int(int remapvar, int value)
{
  // clang-format off
  if      (remapvar == REMAP_WRITE_REMAP)   remap_write_remap = value > 0;
  else if (remapvar == REMAP_MAX_ITER)      remap_max_iter = value;
  else if (remapvar == REMAP_NUM_SRCH_BINS) remap_num_srch_bins = value;
  else if (remapvar == REMAP_GENWEIGHTS)    remap_gen_weights = value > 0;
  else    cdoAbort("Unsupported remap variable (%d)!", remapvar);
  // clang-format on
}

/*****************************************************************************/
static void
boundboxFromCorners(size_t size, size_t nc, const double *restrict corner_lon, const double *restrict corner_lat,
                    float *restrict bound_box)
{
#ifdef _OPENMP
#pragma omp parallel for default(none) shared(bound_box, corner_lat, corner_lon, nc, size)
#endif
  for (size_t i = 0; i < size; ++i)
    {
      size_t i4 = i << 2;  // *4
      size_t inc = i * nc;
      float clat = corner_lat[inc];
      float clon = corner_lon[inc];
      bound_box[i4 + 0] = clat;
      bound_box[i4 + 1] = clat;
      bound_box[i4 + 2] = clon;
      bound_box[i4 + 3] = clon;
      for (size_t j = 1; j < nc; ++j)
        {
          clat = corner_lat[inc + j];
          clon = corner_lon[inc + j];
          if (clat < bound_box[i4 + 0]) bound_box[i4 + 0] = clat;
          if (clat > bound_box[i4 + 1]) bound_box[i4 + 1] = clat;
          if (clon < bound_box[i4 + 2]) bound_box[i4 + 2] = clon;
          if (clon > bound_box[i4 + 3]) bound_box[i4 + 3] = clon;
        }
    }
}

static void
boundboxFromCenter(bool lonIsCyclic, size_t size, size_t nx, size_t ny, const double *restrict center_lon,
                   const double *restrict center_lat, float *restrict bound_box)
{
#ifdef _OPENMP
#pragma omp parallel for default(none)  shared(lonIsCyclic, size, nx, ny, center_lon, center_lat, bound_box)
#endif
  for (size_t n = 0; n < size; n++)
    {
      size_t idx[4];
      float tmp_lats[4], tmp_lons[4];

      size_t n4 = n << 2;

      // Find N,S and NE points to this grid point

      size_t j = n / nx;
      size_t i = n - j * nx;

      size_t ip1 = (i < (nx - 1)) ? i + 1 : lonIsCyclic ? 0 : i;
      size_t jp1 = (j < (ny - 1)) ? j + 1 : j;

      idx[0] = n;
      idx[1] = j * nx + ip1;    // east
      idx[2] = jp1 * nx + ip1;  // north-east
      idx[3] = jp1 * nx + i;    // north

      // Find N,S and NE lat/lon coords and check bounding box

      for (unsigned k = 0; k < 4; ++k) tmp_lons[k] = center_lon[idx[k]];
      for (unsigned k = 0; k < 4; ++k) tmp_lats[k] = center_lat[idx[k]];

      bound_box[n4 + 0] = tmp_lats[0];
      bound_box[n4 + 1] = tmp_lats[0];
      bound_box[n4 + 2] = tmp_lons[0];
      bound_box[n4 + 3] = tmp_lons[0];

      for (unsigned k = 1; k < 4; k++)
        {
          if (tmp_lats[k] < bound_box[n4 + 0]) bound_box[n4 + 0] = tmp_lats[k];
          if (tmp_lats[k] > bound_box[n4 + 1]) bound_box[n4 + 1] = tmp_lats[k];
          if (tmp_lons[k] < bound_box[n4 + 2]) bound_box[n4 + 2] = tmp_lons[k];
          if (tmp_lons[k] > bound_box[n4 + 3]) bound_box[n4 + 3] = tmp_lons[k];
        }
    }
}

void
remapgrid_get_lonlat(RemapGrid *grid, size_t cell_add, double *plon, double *plat)
{
  if (grid->type == RemapGridType::Reg2D)
    {
      size_t nx = grid->dims[0];
      size_t iy = cell_add / nx;
      size_t ix = cell_add - iy * nx;
      *plat = grid->reg2d_center_lat[iy];
      *plon = grid->reg2d_center_lon[ix];
      if (*plon < 0) *plon += PI2;
    }
  else
    {
      *plat = grid->cell_center_lat[cell_add];
      *plon = grid->cell_center_lon[cell_add];
    }
}

void
check_lon_range(size_t nlons, double *lons)
{
  assert(lons != nullptr);

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(nlons, lons)
#endif
  for (size_t n = 0; n < nlons; ++n)
    {
      // remove missing values
      if (lons[n] < -PI2) lons[n] = 0;
      if (lons[n] > 2 * PI2) lons[n] = PI2;

      if (lons[n] > PI2) lons[n] -= PI2;
      if (lons[n] < 0.0) lons[n] += PI2;
    }
}

void
check_lat_range(size_t nlats, double *lats)
{
  assert(lats != nullptr);

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(nlats, lats)
#endif
  for (size_t n = 0; n < nlats; ++n)
    {
      if (lats[n] > PIH) lats[n] = PIH;
      if (lats[n] < -PIH) lats[n] = -PIH;
    }
}

static void
check_lon_boundbox_range(size_t nlons, float *bound_box)
{
  assert(bound_box != nullptr);

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(nlons, bound_box)
#endif
  for (size_t n = 0; n < nlons; ++n)
    {
      size_t n4 = n << 2;
      if (fabsf(bound_box[n4 + 3] - bound_box[n4 + 2]) > PI_f)
        {
          bound_box[n4 + 2] = 0.0f;
          bound_box[n4 + 3] = PI2_f;
        }
    }
}

static void
check_lat_boundbox_range(size_t nlats, float *restrict bound_box, double *restrict lats)
{
  assert(bound_box != nullptr);

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(nlats, bound_box, lats)
#endif
  for (size_t n = 0; n < nlats; ++n)
    {
      size_t n4 = n << 2;
      if ((float) lats[n] < bound_box[n4]) bound_box[n4] = -PIH_f;
      if ((float) lats[n] > bound_box[n4 + 1]) bound_box[n4 + 1] = PIH_f;
    }
}

/*****************************************************************************/

static void
grid_check_lat_borders_rad(size_t n, double *ybounds)
{
  constexpr double YLIM = 88 * DEG2RAD;
  if (ybounds[0] > ybounds[n - 1])
    {
      if (ybounds[0] > YLIM) ybounds[0] = PIH;
      if (ybounds[n - 1] < -YLIM) ybounds[n - 1] = -PIH;
    }
  else
    {
      if (ybounds[0] < -YLIM) ybounds[0] = -PIH;
      if (ybounds[n - 1] > YLIM) ybounds[n - 1] = PIH;
    }
}

static void
remap_define_reg2d(int gridID, RemapGrid &grid)
{
  size_t nx = grid.dims[0];
  size_t ny = grid.dims[1];
  size_t nxp1 = nx + 1;
  size_t nyp1 = ny + 1;

  size_t nxm = nx;
  if (grid.is_cyclic) nxm++;

  if (grid.size != nx * ny) cdoAbort("Internal error, wrong dimensions!");

  grid.reg2d_center_lon = (double *) Malloc(nxm * sizeof(double));
  grid.reg2d_center_lat = (double *) Malloc(ny * sizeof(double));

  grid.reg2d_center_lon[0] = 0;
  grid.reg2d_center_lat[0] = 0;
  gridInqXvals(gridID, grid.reg2d_center_lon);
  gridInqYvals(gridID, grid.reg2d_center_lat);

  // Convert lat/lon units if required
  cdo_grid_to_radian(gridID, CDI_XAXIS, nx, grid.reg2d_center_lon, "grid reg2d center lon");
  cdo_grid_to_radian(gridID, CDI_YAXIS, ny, grid.reg2d_center_lat, "grid reg2d center lat");

  if (grid.reg2d_center_lon[nx - 1] < grid.reg2d_center_lon[0])
    for (size_t i = 1; i < nx; ++i)
      if (grid.reg2d_center_lon[i] < grid.reg2d_center_lon[i - 1]) grid.reg2d_center_lon[i] += PI2;

  if (grid.is_cyclic) grid.reg2d_center_lon[nx] = grid.reg2d_center_lon[0] + PI2;

  grid.reg2d_corner_lon = (double *) Malloc(nxp1 * sizeof(double));
  grid.reg2d_corner_lat = (double *) Malloc(nyp1 * sizeof(double));

  if (gridInqXbounds(gridID, nullptr))
    {
      std::vector<double> xbounds(2 * nx);
      gridInqXbounds(gridID, xbounds.data());
      grid.reg2d_corner_lon[0] = xbounds[1];
      for (size_t i = 0; i < nx; ++i) grid.reg2d_corner_lon[i + 1] = xbounds[2 * i];
      cdo_grid_to_radian(gridID, CDI_XAXIS, nx + 1, grid.reg2d_corner_lon, "grid reg2d corner lon");
    }
  else
    {
      grid_gen_corners(nx, grid.reg2d_center_lon, grid.reg2d_corner_lon);
    }

  if (gridInqYbounds(gridID, nullptr))
    {
      std::vector<double> ybounds(2 * ny);
      gridInqYbounds(gridID, ybounds.data());
      grid.reg2d_corner_lat[0] = ybounds[1];
      for (size_t j = 0; j < ny; ++j) grid.reg2d_corner_lat[j + 1] = ybounds[2 * j];
      cdo_grid_to_radian(gridID, CDI_YAXIS, ny + 1, grid.reg2d_corner_lat, "grid reg2d corner lat");
    }
  else
    {
      grid_gen_corners(ny, grid.reg2d_center_lat, grid.reg2d_corner_lat);
      grid_check_lat_borders_rad(ny + 1, grid.reg2d_corner_lat);
    }
}

static void
remapDefineGrid(RemapMethod mapType, int gridID, RemapGrid &grid, const char *txt)
{
  bool lgrid_destroy = false;
  int gridID_gme = -1;

  auto gridtype = gridInqType(grid.gridID);
  if (gridtype != GRID_UNSTRUCTURED && gridtype != GRID_CURVILINEAR)
    {
      if (gridtype == GRID_GME)
        {
          gridID_gme = gridToUnstructured(grid.gridID, 1);
          grid.nvgp = gridInqSize(gridID_gme);
          gridID = gridDuplicate(gridID_gme);
          gridCompress(gridID);
          grid.luse_cell_corners = true;
        }
      else if (gridtype == GRID_GAUSSIAN_REDUCED)
        {
          lgrid_destroy = true;
          gridID = gridToUnstructured(grid.gridID, 1);
        }
      else if (remap_write_remap || grid.type != RemapGridType::Reg2D)
        {
          lgrid_destroy = true;
          gridID = gridToCurvilinear(grid.gridID, 1);
        }
    }

  auto gridsize = grid.size = gridInqSize(gridID);

  grid.dims[0] = gridInqXsize(gridID);
  grid.dims[1] = gridInqYsize(gridID);
  if (gridInqType(grid.gridID) != GRID_UNSTRUCTURED)
    {
      if (grid.dims[0] == 0) cdoAbort("%s grid without longitude coordinates!", gridNamePtr(gridInqType(grid.gridID)));
      if (grid.dims[1] == 0) cdoAbort("%s grid without latitude coordinates!", gridNamePtr(gridInqType(grid.gridID)));
    }

  grid.is_cyclic = (gridIsCircular(gridID) > 0);

  grid.rank = (gridInqType(gridID) == GRID_UNSTRUCTURED) ? 1 : 2;

  grid.num_cell_corners = (gridInqType(gridID) == GRID_UNSTRUCTURED) ? gridInqNvertex(gridID) : 4;

  remapGridAlloc(mapType, grid);

  // Initialize logical mask

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(gridsize, grid)
#endif
  for (size_t i = 0; i < gridsize; ++i) grid.mask[i] = true;

  if (gridInqMask(gridID, nullptr))
    {
      std::vector<int> mask(gridsize);
      gridInqMask(gridID, &mask[0]);
      for (size_t i = 0; i < gridsize; ++i)
        if (mask[i] == 0) grid.mask[i] = false;
    }

  if (!remap_write_remap && grid.type == RemapGridType::Reg2D) return;

  if (!(gridInqXvals(gridID, nullptr) && gridInqYvals(gridID, nullptr))) cdoAbort("%s grid cell center coordinates missing!", txt);

  gridInqXvals(gridID, grid.cell_center_lon);
  gridInqYvals(gridID, grid.cell_center_lat);

  if (grid.lneed_cell_corners)
    {
      if (gridInqXbounds(gridID, nullptr) && gridInqYbounds(gridID, nullptr))
        {
          gridInqXbounds(gridID, grid.cell_corner_lon);
          gridInqYbounds(gridID, grid.cell_corner_lat);
        }
      else
        {
          cdoAbort("%s grid cell corner coordinates missing!", txt);
        }
    }

  if (gridInqType(grid.gridID) == GRID_GME) gridInqMaskGME(gridID_gme, &grid.vgpm[0]);

  // Convert lat/lon units if required
  cdo_grid_to_radian(gridID, CDI_XAXIS, grid.size, grid.cell_center_lon, "grid center lon");
  cdo_grid_to_radian(gridID, CDI_YAXIS, grid.size, grid.cell_center_lat, "grid center lat");
  if (grid.num_cell_corners && grid.lneed_cell_corners)
    {
      cdo_grid_to_radian(gridID, CDI_XAXIS, grid.num_cell_corners * grid.size, grid.cell_corner_lon, "grid corner lon");
      cdo_grid_to_radian(gridID, CDI_YAXIS, grid.num_cell_corners * grid.size, grid.cell_corner_lat, "grid corner lat");
    }

  if (lgrid_destroy) gridDestroy(gridID);

  // Convert longitudes to 0,2pi interval
  check_lon_range(grid.size, grid.cell_center_lon);
  if (grid.num_cell_corners && grid.lneed_cell_corners) check_lon_range(grid.num_cell_corners * grid.size, grid.cell_corner_lon);

  //  Make sure input latitude range is within the machine values for +/- pi/2
  check_lat_range(grid.size, grid.cell_center_lat);

  if (grid.num_cell_corners && grid.lneed_cell_corners) check_lat_range(grid.num_cell_corners * grid.size, grid.cell_corner_lat);
}

/*  Compute bounding boxes for restricting future grid searches */
static void
cell_bounding_boxes(RemapGrid &grid, float *cell_bound_box, int remap_grid_basis)
{
  if (grid.luse_cell_corners)
    {
      if (grid.lneed_cell_corners)
        {
          if (Options::cdoVerbose) cdoPrint("Grid: boundboxFromCorners");
          boundboxFromCorners(grid.size, grid.num_cell_corners, grid.cell_corner_lon, grid.cell_corner_lat, cell_bound_box);
        }
      else  // full grid search
        {
          if (Options::cdoVerbose) cdoPrint("Grid: bounds missing -> full grid search!");

          size_t gridsize = grid.size;
          for (size_t i = 0; i < gridsize; ++i)
            {
              cell_bound_box[i * 4] = -PIH_f;
              cell_bound_box[i * 4 + 1] = PIH_f;
              cell_bound_box[i * 4 + 2] = 0.0f;
              cell_bound_box[i * 4 + 3] = PI2_f;
            }
        }
    }
  else if (remap_grid_basis == REMAP_GRID_BASIS_SRC)
    {
      if (Options::cdoVerbose) cdoPrint("Grid: boundboxFromCenter");
      if (grid.rank != 2) cdoAbort("Internal problem, grid rank = %d!", grid.rank);

      size_t nx = grid.dims[0];
      size_t ny = grid.dims[1];
      boundboxFromCenter(grid.is_cyclic, grid.size, nx, ny, grid.cell_center_lon, grid.cell_center_lat, cell_bound_box);
    }

  if (remap_grid_basis == REMAP_GRID_BASIS_SRC || grid.lneed_cell_corners) check_lon_boundbox_range(grid.size, cell_bound_box);

  // Try to check for cells that overlap poles
  if (remap_grid_basis == REMAP_GRID_BASIS_SRC || grid.lneed_cell_corners)
    check_lat_boundbox_range(grid.size, cell_bound_box, grid.cell_center_lat);
}

void
remapGridAlloc(RemapMethod mapType, RemapGrid &grid)
{
  if (grid.nvgp) grid.vgpm.resize(grid.nvgp);

  grid.mask.resize(grid.size);

  if (remap_write_remap || grid.type != RemapGridType::Reg2D)
    {
      grid.cell_center_lon = (double *) Malloc(grid.size * sizeof(double));
      grid.cell_center_lat = (double *) Malloc(grid.size * sizeof(double));
    }

  if (mapType == RemapMethod::CONSERV_SCRIP || mapType == RemapMethod::CONSERV)
    {
      grid.cell_area.resize(grid.size, 0.0);
    }

  grid.cell_frac.resize(grid.size, 0.0);

  if (grid.lneed_cell_corners)
    {
      if (grid.num_cell_corners > 0)
        {
          size_t nalloc = grid.num_cell_corners * grid.size;
          grid.cell_corner_lon = (double *) Calloc(nalloc, sizeof(double));
          grid.cell_corner_lat = (double *) Calloc(nalloc, sizeof(double));
        }
    }
}

void
remapGridInit(RemapGrid &grid)
{
  grid.tmpgridID = -1;
  grid.type = RemapGridType::Undefined;

  grid.num_cell_corners = 0;
  grid.luse_cell_corners = false;
  grid.lneed_cell_corners = false;

  grid.nvgp = 0;

  grid.reg2d_center_lon = nullptr;
  grid.reg2d_center_lat = nullptr;
  grid.reg2d_corner_lon = nullptr;
  grid.reg2d_corner_lat = nullptr;

  grid.cell_center_lon = nullptr;
  grid.cell_center_lat = nullptr;
  grid.cell_corner_lon = nullptr;
  grid.cell_corner_lat = nullptr;
}

void
remapGridFree(RemapGrid &grid)
{
  varrayFree(grid.vgpm);
  varrayFree(grid.mask);

  if (grid.reg2d_center_lat) Free(grid.reg2d_center_lat);
  if (grid.reg2d_center_lon) Free(grid.reg2d_center_lon);
  if (grid.reg2d_corner_lat) Free(grid.reg2d_corner_lat);
  if (grid.reg2d_corner_lon) Free(grid.reg2d_corner_lon);

  if (grid.cell_center_lat) Free(grid.cell_center_lat);
  if (grid.cell_center_lon) Free(grid.cell_center_lon);
  if (grid.cell_corner_lat) Free(grid.cell_corner_lat);
  if (grid.cell_corner_lon) Free(grid.cell_corner_lon);

  varrayFree(grid.cell_area);
  varrayFree(grid.cell_frac);

  if (grid.tmpgridID != -1) gridDestroy(grid.tmpgridID);
}

void
remapSearchInit(RemapMethod mapType, RemapSearch &search, RemapGrid &src_grid, RemapGrid &tgt_grid)
{
  extern PointSearchMethod pointSearchMethod;
  extern CellSearchMethod cellSearchMethod;

  search.srcGrid = &src_grid;
  search.tgtGrid = &tgt_grid;

  search.srcBins.ncells = src_grid.size;
  search.tgtBins.ncells = tgt_grid.size;

  search.srcBins.nbins = remap_num_srch_bins;
  search.tgtBins.nbins = remap_num_srch_bins;

  bool usePointsearch = mapType == RemapMethod::DISTWGT;
  if (src_grid.type != RemapGridType::Reg2D && pointSearchMethod != PointSearchMethod::latbins)
    {
      usePointsearch |= mapType == RemapMethod::BILINEAR;
      usePointsearch |= mapType == RemapMethod::BICUBIC;
    }

  bool useCellsearch = (mapType == RemapMethod::CONSERV)
                       && (cellSearchMethod == CellSearchMethod::spherepart || src_grid.type == RemapGridType::Reg2D);

  double start = Options::cdoVerbose ? cdo_get_wtime() : 0;

  if (usePointsearch)
    {
      bool xIsCyclic = src_grid.is_cyclic;
      if (src_grid.type == RemapGridType::Reg2D)
        gridPointSearchCreateReg2d(search.gps, xIsCyclic, src_grid.dims, src_grid.reg2d_center_lon, src_grid.reg2d_center_lat);
      else
        gridPointSearchCreate(search.gps, xIsCyclic, src_grid.dims, src_grid.size, src_grid.cell_center_lon, src_grid.cell_center_lat);

      if (src_grid.lextrapolate) gridPointSearchExtrapolate(search.gps);

      if (Options::cdoVerbose) cdoPrint("Point search created: %.2f seconds", cdo_get_wtime() - start);
    }
  else if (useCellsearch)
    {
      if (src_grid.type == RemapGridType::Reg2D)
        gridCellSearchCreateReg2d(search.gcs, src_grid.dims, src_grid.reg2d_corner_lon, src_grid.reg2d_corner_lat);
      else
        gridCellSearchCreate(search.gcs, src_grid.size, src_grid.num_cell_corners, src_grid.cell_corner_lon, src_grid.cell_corner_lat);

      if (Options::cdoVerbose) cdoPrint("Cell search created: %.2f seconds", cdo_get_wtime() - start);
    }
  else if (!(src_grid.type == RemapGridType::Reg2D || tgt_grid.type == RemapGridType::Reg2D))
    {
      search.srcBins.cell_bound_box.resize(4 * src_grid.size);
      if (tgt_grid.luse_cell_corners) search.tgtBins.cell_bound_box.resize(4 * tgt_grid.size);

      cell_bounding_boxes(src_grid, &search.srcBins.cell_bound_box[0], REMAP_GRID_BASIS_SRC);
      cell_bounding_boxes(tgt_grid, &search.tgtBins.cell_bound_box[0], REMAP_GRID_BASIS_TGT);
      // Set up and assign address ranges to search bins in order to further restrict later searches
      calcLatBins(search.srcBins);
      if (mapType == RemapMethod::CONSERV_SCRIP || mapType == RemapMethod::CONSERV)
        {
          calcLatBins(search.tgtBins);
          varrayFree(search.tgtBins.bin_lats);
          varrayFree(search.srcBins.bin_lats);
          if (mapType == RemapMethod::CONSERV) varrayFree(search.tgtBins.cell_bound_box);
        }

      if (Options::cdoVerbose) cdoPrint("Latitude bins created: %.2f seconds", cdo_get_wtime() - start);
    }
}

void
remapSearchFree(RemapSearch &search)
{
  varrayFree(search.srcBins.bin_addr);
  varrayFree(search.srcBins.bin_lats);
  varrayFree(search.srcBins.cell_bound_box);

  varrayFree(search.tgtBins.bin_addr);
  varrayFree(search.tgtBins.bin_lats);
  varrayFree(search.tgtBins.cell_bound_box);

  gridPointSearchDelete(search.gps);
  gridCellSearchDelete(search.gcs);
}

void
remapInitGrids(RemapMethod mapType, bool lextrapolate, int gridID1, RemapGrid &src_grid, int gridID2, RemapGrid &tgt_grid)
{
  int reg2d_src_gridID = gridID1;
  int reg2d_tgt_gridID = gridID2;

  remapGridInit(src_grid);
  remapGridInit(tgt_grid);

  if (mapType == RemapMethod::BILINEAR || mapType == RemapMethod::BICUBIC || mapType == RemapMethod::DISTWGT
      || mapType == RemapMethod::CONSERV)
    {
      if (IS_REG2D_GRID(gridID1)) src_grid.type = RemapGridType::Reg2D;
      // src_grid.type = 0;
    }

  //#ifdef YAC_CELL_SEARCH
  // if (IS_REG2D_GRID(gridID2) && mapType == RemapMethod::CONSERV) tgt_grid.type = RemapGridType::Reg2D;
  //#else
  if (src_grid.type == RemapGridType::Reg2D)
    {
      if (IS_REG2D_GRID(gridID2) && mapType == RemapMethod::CONSERV) tgt_grid.type = RemapGridType::Reg2D;
      // else src_grid.type = -1;
    }
  //#endif

  if (!remap_gen_weights && IS_REG2D_GRID(gridID2) && tgt_grid.type != RemapGridType::Reg2D)
    {
      if (mapType == RemapMethod::DISTWGT) tgt_grid.type = RemapGridType::Reg2D;
      if (mapType == RemapMethod::BILINEAR && src_grid.type == RemapGridType::Reg2D) tgt_grid.type = RemapGridType::Reg2D;
    }

  src_grid.lextrapolate = lextrapolate;

  if (mapType == RemapMethod::CONSERV_SCRIP || mapType == RemapMethod::CONSERV)
    {
      if (src_grid.type != RemapGridType::Reg2D)
        {
          src_grid.luse_cell_corners = true;
          src_grid.lneed_cell_corners = true;
        }

      if (tgt_grid.type != RemapGridType::Reg2D)
        {
          tgt_grid.luse_cell_corners = true;
          tgt_grid.lneed_cell_corners = true;
        }
    }

  src_grid.gridID = gridID1;
  tgt_grid.gridID = gridID2;

  if (gridInqType(gridID1) == GRID_UNSTRUCTURED)
    {
      if (gridInqYvals(gridID1, nullptr) == 0 || gridInqXvals(gridID1, nullptr) == 0)
        {
          int number = 0;
          cdiInqKeyInt(gridID1, CDI_GLOBAL, CDI_KEY_NUMBEROFGRIDUSED, &number);
          if (number > 0)
            {
              src_grid.gridID = gridID1 = referenceToGrid(gridID1);
              if (gridID1 == -1) cdoAbort("Reference to source grid not found!");
            }
        }
    }

  if (gridInqType(gridID2) == GRID_UNSTRUCTURED)
    {
      if (gridInqYvals(gridID2, nullptr) == 0 || gridInqXvals(gridID2, nullptr) == 0)
        {
          int number = 0;
          cdiInqKeyInt(gridID2, CDI_GLOBAL, CDI_KEY_NUMBEROFGRIDUSED, &number);
          if (number > 0)
            {
              tgt_grid.gridID = gridID2 = referenceToGrid(gridID2);
              if (gridID2 == -1) cdoAbort("Reference to target grid not found!");
            }
        }
    }

  int sgridID = src_grid.gridID;
  if (gridInqSize(sgridID) > 1
      && ((gridInqType(sgridID) == GRID_PROJECTION && gridInqProjType(sgridID) == CDI_PROJ_LCC)
          || (gridInqType(sgridID) == GRID_PROJECTION && gridInqProjType(sgridID) == CDI_PROJ_STERE)
          || (gridInqType(sgridID) == GRID_PROJECTION && gridInqProjType(sgridID) == CDI_PROJ_RLL)
          || (gridInqType(sgridID) == GRID_PROJECTION && gridInqProjType(sgridID) == CDI_PROJ_LAEA)
          || (gridInqType(sgridID) == GRID_PROJECTION && gridInqProjType(sgridID) == CDI_PROJ_SINU)))
    {
      bool lbounds = true;
      src_grid.gridID = gridID1 = gridToCurvilinear(src_grid.gridID, lbounds);
      src_grid.tmpgridID = src_grid.gridID;
    }

  // if ( src_grid.type != RemapGridType::Reg2D )
  remapDefineGrid(mapType, gridID1, src_grid, "Source");
  remapDefineGrid(mapType, gridID2, tgt_grid, "Target");

  if (src_grid.type == RemapGridType::Reg2D || tgt_grid.type == RemapGridType::Reg2D)
    {
      if (src_grid.type == RemapGridType::Reg2D) remap_define_reg2d(reg2d_src_gridID, src_grid);
      if (tgt_grid.type == RemapGridType::Reg2D) remap_define_reg2d(reg2d_tgt_gridID, tgt_grid);
    }
}

/*****************************************************************************/

void
remapStat(int remapOrder, RemapGrid &src_grid, RemapGrid &tgt_grid, RemapVars &rv, const Varray<double> &array1,
          const Varray<double> &array2, double missval)
{
  if (remapOrder == 2)
    cdoPrint("Second order mapping from grid1 to grid2:");
  else
    cdoPrint("First order mapping from grid1 to grid2:");
  cdoPrint("----------------------------------------------");

  auto mmm = varrayMinMaxMeanMV(src_grid.size, array1, missval);
  cdoPrint("  Grid1 min,mean,max: %g %g %g", mmm.min, mmm.mean, mmm.max);

  mmm = varrayMinMaxMeanMV(tgt_grid.size, array2, missval);
  cdoPrint("  Grid2 min,mean,max: %g %g %g", mmm.min, mmm.mean, mmm.max);

  // Conservation Test

  if (src_grid.cell_area.size())
    {
      cdoPrint("  Conservation:");
      double sum = 0;
      for (size_t n = 0; n < src_grid.size; ++n)
        if (!DBL_IS_EQUAL(array1[n], missval)) sum += array1[n] * src_grid.cell_area[n] * src_grid.cell_frac[n];
      cdoPrint("  Grid1 Integral = %g", sum);

      sum = 0;
      for (size_t n = 0; n < tgt_grid.size; ++n)
        if (!DBL_IS_EQUAL(array2[n], missval)) sum += array2[n] * tgt_grid.cell_area[n] * tgt_grid.cell_frac[n];
      cdoPrint("  Grid2 Integral = %g", sum);
      /*
      for ( n = 0; n < src_grid.size; n++ )
       fprintf(stderr, "1 %d %g %g %g\n", n, array1[n], src_grid.cell_area[n],
      src_grid.cell_frac[n]); for ( n = 0; n < tgt_grid.size; n++ )
        fprintf(stderr, "2 %d %g %g %g\n", n, array2[n], tgt_grid.cell_area[n],
      tgt_grid.cell_frac[n]);
      */
    }

  cdoPrint("  Number of weights %zu", rv.num_wts);
  cdoPrint("  Number of sparse matrix entries %zu", rv.num_links);
  cdoPrint("  Total number of dest cells %zu", tgt_grid.size);

  std::vector<size_t> tgt_count(tgt_grid.size, 0);

#ifdef HAVE_OPENMP4
#pragma omp simd
#endif
  for (size_t n = 0; n < rv.num_links; ++n) tgt_count[rv.tgt_cell_add[n]]++;

  size_t imin = SIZE_MAX;
  size_t imax = 0;
  for (size_t n = 0; n < tgt_grid.size; ++n)
    {
      if (tgt_count[n] > 0)
        {
          if (tgt_count[n] < imin) imin = tgt_count[n];
          if (tgt_count[n] > imax) imax = tgt_count[n];
        }
    }

  size_t idiff = (imax - imin) / 10 + 1;
  size_t icount = 0;
  for (size_t i = 0; i < tgt_grid.size; ++i)
    if (tgt_count[i] > 0) icount++;

  cdoPrint("  Number of cells participating in remap %zu", icount);

  if (icount)
    {
      cdoPrint("  Min no of entries/row = %zu", imin);
      cdoPrint("  Max no of entries/row = %zu", imax);

      imax = imin + idiff;
      for (size_t n = 0; n < 10; ++n)
        {
          icount = 0;
          for (size_t i = 0; i < tgt_grid.size; ++i)
            if (tgt_count[i] >= imin && tgt_count[i] < imax) icount++;

          if (icount) cdoPrint("  Num of rows with entries between %zu - %zu  %zu", imin, imax - 1, icount);

          imin = imin + idiff;
          imax = imax + idiff;
        }
    }

  if (rv.sort_add) cdoPrint("  Sparse matrix entries are explicitly sorted.");
}

/*****************************************************************************/

void
remapGradients(RemapGrid &grid, const std::vector<bool> &mask, const double *restrict array, RemapGradients &gradients)
{
  if (grid.rank != 2) cdoAbort("Internal problem (remapGradients), grid rank = %d!", grid.rank);

  size_t grid_size = grid.size;
  size_t nx = grid.dims[0];
  size_t ny = grid.dims[1];

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(grid_size, gradients, grid, nx, ny, array, mask)
#endif
  for (size_t n = 0; n < grid_size; ++n)
    {
      gradients.grad_lat[n] = 0.0;
      gradients.grad_lon[n] = 0.0;
      gradients.grad_latlon[n] = 0.0;

      if (mask[n])
        {
          // clang-format off
          double delew = 0.5;
          double delns = 0.5;

          const size_t j = n / nx + 1;
          const size_t i = n - (j - 1) * nx + 1;

          size_t ip1 = i + 1;
          size_t im1 = i - 1;
          size_t jp1 = j + 1;
          size_t jm1 = j - 1;

          if (ip1 > nx) ip1 = ip1 - nx;
          if (im1 < 1)  im1 = nx;
          if (jp1 > ny) { jp1 = j; delns = 1.0; }
          if (jm1 < 1)  { jm1 = j; delns = 1.0; }

          size_t in = (jp1 - 1) * nx + i - 1;
          size_t is = (jm1 - 1) * nx + i - 1;
          size_t ie = (j - 1) * nx + ip1 - 1;
          size_t iw = (j - 1) * nx + im1 - 1;

          size_t ine = (jp1 - 1) * nx + ip1 - 1;
          size_t inw = (jp1 - 1) * nx + im1 - 1;
          size_t ise = (jm1 - 1) * nx + ip1 - 1;
          size_t isw = (jm1 - 1) * nx + im1 - 1;

          // Compute i-gradient
          if (!mask[ie]) { ie = n; delew = 1.0; }
          if (!mask[iw]) { iw = n; delew = 1.0; }

          gradients.grad_lat[n] = delew * (array[ie] - array[iw]);

          // Compute j-gradient
          if (!mask[in]) { in = n; delns = 1.0; }
          if (!mask[is]) { is = n; delns = 1.0; }

          gradients.grad_lon[n] = delns * (array[in] - array[is]);
          // clang-format on

          // Compute ij-gradient
          delew = 0.5;
          delns = (jp1 == j || jm1 == j) ? 1.0 : 0.5;

          if (!mask[ine])
            {
              if (in != n)
                {
                  ine = in;
                  delew = 1.0;
                }
              else if (ie != n)
                {
                  ine = ie;
                  inw = iw;
                  if (inw == n) delew = 1.0;
                  delns = 1.0;
                }
              else
                {
                  ine = n;
                  inw = iw;
                  delew = 1.0;
                  delns = 1.0;
                }
            }

          if (!mask[inw])
            {
              if (in != n)
                {
                  inw = in;
                  delew = 1.0;
                }
              else if (iw != n)
                {
                  inw = iw;
                  ine = ie;
                  if (ie == n) delew = 1.0;
                  delns = 1.0;
                }
              else
                {
                  inw = n;
                  ine = ie;
                  delew = 1.0;
                  delns = 1.0;
                }
            }

          const double grad_lat_zero = delew * (array[ine] - array[inw]);

          if (!mask[ise])
            {
              if (is != n)
                {
                  ise = is;
                  delew = 1.0;
                }
              else if (ie != n)
                {
                  ise = ie;
                  isw = iw;
                  if (isw == n) delew = 1.0;
                  delns = 1.0;
                }
              else
                {
                  ise = n;
                  isw = iw;
                  delew = 1.0;
                  delns = 1.0;
                }
            }

          if (!mask[isw])
            {
              if (is != n)
                {
                  isw = is;
                  delew = 1.0;
                }
              else if (iw != n)
                {
                  isw = iw;
                  ise = ie;
                  if (ie == n) delew = 1.0;
                  delns = 1.0;
                }
              else
                {
                  isw = n;
                  ise = ie;
                  delew = 1.0;
                  delns = 1.0;
                }
            }

          const double grad_lon_zero = delew * (array[ise] - array[isw]);

          gradients.grad_latlon[n] = delns * (grad_lat_zero - grad_lon_zero);
        }
    }
} /* remapGradients */

void
remapGradients(RemapGrid &grid, const double *restrict array, RemapGradients &gradients)
{
  size_t grid_size = grid.size;
  std::vector<bool> mask(grid_size);
  /* doesn't work with bool vector!!!
#ifdef _OPENMP
#pragma omp parallel for default(none) schedule(static) shared(grid_size, grid, mask)
#endif
  */
  for (size_t i = 0; i < grid_size; ++i) mask[i] = grid.mask[i] > 0;

  remapGradients(grid, mask, array, gradients);
}

/*****************************************************************************/

void
remapCheckArea(size_t grid_size, double *restrict cell_area, const char *name)
{
  for (size_t n = 0; n < grid_size; ++n)
    {
      if (cell_area[n] < -.01) cdoPrint("%s grid area error: %zu %g", name, n, cell_area[n]);
    }
}