Sort all includes in src/gromacs
[alexxy/gromacs.git] / src / gromacs / selection / nbsearch.cpp
index d050c89e1c1d453158b325e504e73cf29b53c500..7e32fa6536b1ad066a2d7cdb1bb9df420a9fc742 100644 (file)
@@ -1,10 +1,10 @@
 /*
  * This file is part of the GROMACS molecular simulation package.
  *
- * Copyright (c) 2009,2010,2011,2012,2013, by the GROMACS development team, led by
- * David van der Spoel, Berk Hess, Erik Lindahl, and including many
- * others, as listed in the AUTHORS file in the top-level source
- * directory and at http://www.gromacs.org.
+ * Copyright (c) 2009,2010,2011,2012,2013,2014, by the GROMACS development team, led by
+ * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
+ * and including many others, as listed in the AUTHORS file in the
+ * top-level source directory and at http://www.gromacs.org.
  *
  * GROMACS is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License
@@ -40,9 +40,6 @@
  * The grid implementation could still be optimized in several different ways:
  *   - Triclinic grid cells are not the most efficient shape, but make PBC
  *     handling easier.
- *   - Precalculating the required PBC shift for a pair of cells outside the
- *     inner loop. After this is done, it should be quite straightforward to
- *     move to rectangular cells.
  *   - Pruning grid cells from the search list if they are completely outside
  *     the sphere that is being considered.
  *   - A better heuristic could be added for falling back to simple loops for a
  * \author Teemu Murtola <teemu.murtola@gmail.com>
  * \ingroup module_selection
  */
-#include "gromacs/selection/nbsearch.h"
+#include "gmxpre.h"
 
-#include <math.h>
+#include "nbsearch.h"
+
+#include <cmath>
+#include <cstring>
 
 #include <algorithm>
 #include <vector>
 
-#include "gromacs/legacyheaders/smalloc.h"
-#include "gromacs/legacyheaders/typedefs.h"
-#include "gromacs/legacyheaders/pbc.h"
-#include "gromacs/legacyheaders/vec.h"
-#include "gromacs/legacyheaders/thread_mpi/mutex.h"
+#include "thread_mpi/mutex.h"
 
+#include "gromacs/legacyheaders/names.h"
+#include "gromacs/math/vec.h"
+#include "gromacs/pbcutil/pbc.h"
 #include "gromacs/selection/position.h"
+#include "gromacs/topology/block.h"
+#include "gromacs/utility/arrayref.h"
+#include "gromacs/utility/exceptions.h"
 #include "gromacs/utility/gmxassert.h"
+#include "gromacs/utility/smalloc.h"
+#include "gromacs/utility/stringutil.h"
 
 namespace gmx
 {
@@ -92,8 +96,20 @@ class AnalysisNeighborhoodSearchImpl
         explicit AnalysisNeighborhoodSearchImpl(real cutoff);
         ~AnalysisNeighborhoodSearchImpl();
 
-        void init(AnalysisNeighborhood::SearchMode mode,
-                  const t_pbc *pbc, int n, const rvec x[], const int *refid);
+        /*! \brief
+         * Initializes the search with a given box and reference positions.
+         *
+         * \param[in]     mode      Search mode to use.
+         * \param[in]     bXY       Whether to use 2D searching.
+         * \param[in]     excls     Exclusions.
+         * \param[in]     pbc       PBC information.
+         * \param[in]     positions Set of reference positions.
+         */
+        void init(AnalysisNeighborhood::SearchMode     mode,
+                  bool                                 bXY,
+                  const t_blocka                      *excls,
+                  const t_pbc                         *pbc,
+                  const AnalysisNeighborhoodPositions &positions);
         PairSearchImplPointer getPairSearch();
 
         real cutoffSquared() const { return cutoff2_; }
@@ -108,23 +124,23 @@ class AnalysisNeighborhoodSearchImpl
          * \param[in]     pbc  Information about the box.
          * \returns  false if grid search is not suitable.
          */
-        bool initGridCells(const t_pbc *pbc);
+        bool initGridCells(const t_pbc &pbc);
         /*! \brief
          * Sets ua a search grid for a given box.
          *
          * \param[in]     pbc  Information about the box.
          * \returns  false if grid search is not suitable.
          */
-        bool initGrid(const t_pbc *pbc);
+        bool initGrid(const t_pbc &pbc);
         /*! \brief
          * Maps a point into a grid cell.
          *
          * \param[in]  x    Point to map.
          * \param[out] cell Indices of the grid cell in which \p x lies.
-         *
-         * \p x should be within the triclinic unit cell.
+         * \param[out] xout Coordinates to use
+         *     (will be within the triclinic unit cell).
          */
-        void mapPointToGridCell(const rvec x, ivec cell) const;
+        void mapPointToGridCell(const rvec x, ivec cell, rvec xout) const;
         /*! \brief
          * Calculates linear index of a grid cell.
          *
@@ -139,6 +155,16 @@ class AnalysisNeighborhoodSearchImpl
          * \param[in]     i    Index to add.
          */
         void addToGridCell(const ivec cell, int i);
+        /*! \brief
+         * Calculates the index of a neighboring grid cell.
+         *
+         * \param[in]  sourceCell Location of the source cell.
+         * \param[in]  index      Index of the neighbor to calculate.
+         * \param[out] shift      Shift to apply to get the periodic distance
+         *     for distances between the cells.
+         * \returns    Grid cell index of the neighboring cell.
+         */
+        int getNeighboringCell(const ivec sourceCell, int index, rvec shift) const;
 
         //! Whether to try grid searching.
         bool                    bTryGrid_;
@@ -146,20 +172,19 @@ class AnalysisNeighborhoodSearchImpl
         real                    cutoff_;
         //! The cutoff squared.
         real                    cutoff2_;
+        //! Whether to do searching in XY plane only.
+        bool                    bXY_;
 
         //! Number of reference points for the current frame.
         int                     nref_;
         //! Reference point positions.
         const rvec             *xref_;
-        //! Reference position ids (NULL if not available).
-        const int              *refid_;
+        //! Reference position exclusion IDs.
+        const int              *refExclusionIds_;
+        //! Exclusions.
+        const t_blocka         *excls_;
         //! PBC data.
-        t_pbc                  *pbc_;
-
-        //! Number of excluded reference positions for current test particle.
-        int                     nexcl_;
-        //! Exclusions for current test particle.
-        int                    *excl_;
+        t_pbc                   pbc_;
 
         //! Whether grid searching is actually used for the current positions.
         bool                    bGrid_;
@@ -196,33 +221,50 @@ class AnalysisNeighborhoodPairSearchImpl
 {
     public:
         explicit AnalysisNeighborhoodPairSearchImpl(const AnalysisNeighborhoodSearchImpl &search)
-            : search_(search), testIndex_(0)
+            : search_(search)
         {
+            testExclusionIds_ = NULL;
+            nexcl_            = 0;
+            excl_             = NULL;
             clear_rvec(xtest_);
             clear_ivec(testcell_);
-            reset();
+            reset(-1);
         }
 
-        //! Clears the loop indices.
-        void reset();
         //! Initializes a search to find reference positions neighboring \p x.
-        void startSearch(const rvec x, int testIndex);
+        void startSearch(const AnalysisNeighborhoodPositions &positions);
         //! Searches for the next neighbor.
         template <class Action>
         bool searchNext(Action action);
         //! Initializes a pair representing the pair found by searchNext().
         void initFoundPair(AnalysisNeighborhoodPair *pair) const;
+        //! Advances to the next test position, skipping any remaining pairs.
+        void nextTestPosition();
 
     private:
+        //! Clears the loop indices.
+        void reset(int testIndex);
         //! Checks whether a reference positiong should be excluded.
         bool isExcluded(int j);
 
+        //! Parent search object.
         const AnalysisNeighborhoodSearchImpl   &search_;
+        //! Reference to the test positions.
+        ConstArrayRef<rvec>                     testPositions_;
+        //! Reference to the test exclusion indices.
+        const int                              *testExclusionIds_;
+        //! Number of excluded reference positions for current test particle.
+        int                                     nexcl_;
+        //! Exclusions for current test particle.
+        const int                              *excl_;
+        //! Index of the currently active test position in \p testPositions_.
         int                                     testIndex_;
         //! Stores test position during a pair loop.
         rvec                                    xtest_;
         //! Stores the previous returned position during a pair loop.
         int                                     previ_;
+        //! Stores the pair distance corresponding to previ_;
+        real                                    prevr2_;
         //! Stores the current exclusion index during loops.
         int                                     exclind_;
         //! Stores the test particle cell index during loops.
@@ -249,14 +291,12 @@ AnalysisNeighborhoodSearchImpl::AnalysisNeighborhoodSearchImpl(real cutoff)
         bTryGrid_   = false;
     }
     cutoff2_        = sqr(cutoff_);
+    bXY_            = false;
 
-    nref_           = 0;
-    xref_           = NULL;
-    refid_          = NULL;
-    pbc_            = NULL;
-
-    nexcl_          = 0;
-    excl_           = NULL;
+    nref_            = 0;
+    xref_            = NULL;
+    refExclusionIds_ = NULL;
+    std::memset(&pbc_, 0, sizeof(pbc_));
 
     bGrid_          = false;
 
@@ -342,16 +382,16 @@ void AnalysisNeighborhoodSearchImpl::initGridCellNeighborList()
     }
 }
 
-bool AnalysisNeighborhoodSearchImpl::initGridCells(const t_pbc *pbc)
+bool AnalysisNeighborhoodSearchImpl::initGridCells(const t_pbc &pbc)
 {
     const real targetsize =
-        pow(pbc->box[XX][XX] * pbc->box[YY][YY] * pbc->box[ZZ][ZZ]
+        pow(pbc.box[XX][XX] * pbc.box[YY][YY] * pbc.box[ZZ][ZZ]
             * 10 / nref_, static_cast<real>(1./3.));
 
     int cellCount = 1;
     for (int dd = 0; dd < DIM; ++dd)
     {
-        ncelldim_[dd] = static_cast<int>(pbc->box[dd][dd] / targetsize);
+        ncelldim_[dd] = static_cast<int>(pbc.box[dd][dd] / targetsize);
         cellCount    *= ncelldim_[dd];
         if (ncelldim_[dd] < 3)
         {
@@ -372,10 +412,10 @@ bool AnalysisNeighborhoodSearchImpl::initGridCells(const t_pbc *pbc)
     return true;
 }
 
-bool AnalysisNeighborhoodSearchImpl::initGrid(const t_pbc *pbc)
+bool AnalysisNeighborhoodSearchImpl::initGrid(const t_pbc &pbc)
 {
     /* TODO: This check could be improved. */
-    if (0.5*pbc->max_cutoff2 < cutoff2_)
+    if (0.5*pbc.max_cutoff2 < cutoff2_)
     {
         return false;
     }
@@ -385,12 +425,12 @@ bool AnalysisNeighborhoodSearchImpl::initGrid(const t_pbc *pbc)
         return false;
     }
 
-    bTric_ = TRICLINIC(pbc->box);
+    bTric_ = TRICLINIC(pbc.box);
     if (bTric_)
     {
         for (int dd = 0; dd < DIM; ++dd)
         {
-            svmul(1.0 / ncelldim_[dd], pbc->box[dd], cellbox_[dd]);
+            svmul(1.0 / ncelldim_[dd], pbc.box[dd], cellbox_[dd]);
         }
         m_inv_ur0(cellbox_, recipcell_);
     }
@@ -398,7 +438,7 @@ bool AnalysisNeighborhoodSearchImpl::initGrid(const t_pbc *pbc)
     {
         for (int dd = 0; dd < DIM; ++dd)
         {
-            cellbox_[dd][dd]   = pbc->box[dd][dd] / ncelldim_[dd];
+            cellbox_[dd][dd]   = pbc.box[dd][dd] / ncelldim_[dd];
             recipcell_[dd][dd] = 1.0 / cellbox_[dd][dd];
         }
     }
@@ -407,25 +447,52 @@ bool AnalysisNeighborhoodSearchImpl::initGrid(const t_pbc *pbc)
 }
 
 void AnalysisNeighborhoodSearchImpl::mapPointToGridCell(const rvec x,
-                                                        ivec       cell) const
+                                                        ivec       cell,
+                                                        rvec       xout) const
 {
+    rvec xtmp;
+    copy_rvec(x, xtmp);
     if (bTric_)
     {
         rvec tx;
-
-        tmvmul_ur0(recipcell_, x, tx);
+        tmvmul_ur0(recipcell_, xtmp, tx);
         for (int dd = 0; dd < DIM; ++dd)
         {
-            cell[dd] = static_cast<int>(tx[dd]);
+            const int cellCount = ncelldim_[dd];
+            int       cellIndex = static_cast<int>(floor(tx[dd]));
+            while (cellIndex < 0)
+            {
+                cellIndex += cellCount;
+                rvec_add(xtmp, pbc_.box[dd], xtmp);
+            }
+            while (cellIndex >= cellCount)
+            {
+                cellIndex -= cellCount;
+                rvec_sub(xtmp, pbc_.box[dd], xtmp);
+            }
+            cell[dd] = cellIndex;
         }
     }
     else
     {
         for (int dd = 0; dd < DIM; ++dd)
         {
-            cell[dd] = static_cast<int>(x[dd] * recipcell_[dd][dd]);
+            const int cellCount = ncelldim_[dd];
+            int       cellIndex = static_cast<int>(floor(xtmp[dd] * recipcell_[dd][dd]));
+            while (cellIndex < 0)
+            {
+                cellIndex += cellCount;
+                xtmp[dd]  += pbc_.box[dd][dd];
+            }
+            while (cellIndex >= cellCount)
+            {
+                cellIndex -= cellCount;
+                xtmp[dd]  -= pbc_.box[dd][dd];
+            }
+            cell[dd] = cellIndex;
         }
     }
+    copy_rvec(xtmp, xout);
 }
 
 int AnalysisNeighborhoodSearchImpl::getGridCellIndex(const ivec cell) const
@@ -446,16 +513,72 @@ void AnalysisNeighborhoodSearchImpl::addToGridCell(const ivec cell, int i)
     cells_[ci].push_back(i);
 }
 
+int AnalysisNeighborhoodSearchImpl::getNeighboringCell(
+        const ivec sourceCell, int index, rvec shift) const
+{
+    ivec cell;
+    ivec_add(sourceCell, gnboffs_[index], cell);
+
+    // TODO: Consider unifying with the similar shifting code in
+    // mapPointToGridCell().
+    clear_rvec(shift);
+    for (int d = 0; d < DIM; ++d)
+    {
+        const int cellCount = ncelldim_[d];
+        if (cell[d] < 0)
+        {
+            cell[d] += cellCount;
+            rvec_add(shift, pbc_.box[d], shift);
+        }
+        else if (cell[d] >= cellCount)
+        {
+            cell[d] -= cellCount;
+            rvec_sub(shift, pbc_.box[d], shift);
+        }
+    }
+
+    return getGridCellIndex(cell);
+}
+
 void AnalysisNeighborhoodSearchImpl::init(
-        AnalysisNeighborhood::SearchMode mode,
-        const t_pbc *pbc, int n, const rvec x[], const int *refid)
+        AnalysisNeighborhood::SearchMode     mode,
+        bool                                 bXY,
+        const t_blocka                      *excls,
+        const t_pbc                         *pbc,
+        const AnalysisNeighborhoodPositions &positions)
 {
-    pbc_  = const_cast<t_pbc *>(pbc);
-    nref_ = n;
+    GMX_RELEASE_ASSERT(positions.index_ == -1,
+                       "Individual indexed positions not supported as reference");
+    bXY_ = bXY;
+    if (bXY_ && pbc->ePBC != epbcNONE)
+    {
+        if (pbc->ePBC != epbcXY && pbc->ePBC != epbcXYZ)
+        {
+            std::string message =
+                formatString("Computations in the XY plane are not supported with PBC type '%s'",
+                             EPBC(pbc->ePBC));
+            GMX_THROW(NotImplementedError(message));
+        }
+        if (std::fabs(pbc->box[ZZ][XX]) > GMX_REAL_EPS*pbc->box[ZZ][ZZ] ||
+            std::fabs(pbc->box[ZZ][YY]) > GMX_REAL_EPS*pbc->box[ZZ][ZZ])
+        {
+            GMX_THROW(NotImplementedError("Computations in the XY plane are not supported when the last box vector is not parallel to the Z axis"));
+        }
+        set_pbc(&pbc_, epbcXY, const_cast<rvec *>(pbc->box));
+    }
+    else if (pbc != NULL)
+    {
+        pbc_  = *pbc;
+    }
+    else
+    {
+        pbc_.ePBC = epbcNONE;
+    }
+    nref_ = positions.count_;
     // TODO: Consider whether it would be possible to support grid searching in
     // more cases.
     if (mode == AnalysisNeighborhood::eSearchMode_Simple
-        || pbc_ == NULL || pbc_->ePBC != epbcXYZ)
+        || pbc_.ePBC != epbcXYZ)
     {
         bGrid_ = false;
     }
@@ -466,187 +589,202 @@ void AnalysisNeighborhoodSearchImpl::init(
     }
     if (bGrid_)
     {
-        if (xref_nalloc_ < n)
+        if (xref_nalloc_ < nref_)
         {
-            srenew(xref_alloc_, n);
-            xref_nalloc_ = n;
+            srenew(xref_alloc_, nref_);
+            xref_nalloc_ = nref_;
         }
         xref_ = xref_alloc_;
 
-        for (int i = 0; i < n; ++i)
-        {
-            copy_rvec(x[i], xref_alloc_[i]);
-        }
-        put_atoms_in_triclinic_unitcell(ecenterTRIC, pbc_->box, n, xref_alloc_);
-        for (int i = 0; i < n; ++i)
+        for (int i = 0; i < nref_; ++i)
         {
             ivec refcell;
-
-            mapPointToGridCell(xref_[i], refcell);
+            mapPointToGridCell(positions.x_[i], refcell, xref_alloc_[i]);
             addToGridCell(refcell, i);
         }
     }
     else
     {
-        xref_ = x;
+        xref_ = positions.x_;
+    }
+    excls_           = excls;
+    refExclusionIds_ = NULL;
+    if (excls != NULL)
+    {
+        // TODO: Check that the IDs are ascending, or remove the limitation.
+        refExclusionIds_ = positions.exclusionIds_;
+        GMX_RELEASE_ASSERT(refExclusionIds_ != NULL,
+                           "Exclusion IDs must be set for reference positions "
+                           "when exclusions are enabled");
     }
-    refid_ = refid;
-}
-
-#if 0
-/*! \brief
- * Sets the exclusions for the next neighborhood search.
- *
- * \param[in,out] d     Neighborhood search data structure.
- * \param[in]     nexcl Number of reference positions to exclude from next
- *      search.
- * \param[in]     excl  Indices of reference positions to exclude.
- *
- * The set exclusions remain in effect until the next call of this function.
- */
-void
-gmx_ana_nbsearch_set_excl(gmx_ana_nbsearch_t *d, int nexcl, int excl[])
-{
-
-    d->nexcl = nexcl;
-    d->excl  = excl;
 }
-#endif
 
 /********************************************************************
  * AnalysisNeighborhoodPairSearchImpl
  */
 
-void AnalysisNeighborhoodPairSearchImpl::reset()
-{
-    previ_   = -1;
-    exclind_ = 0;
-    prevnbi_ = 0;
-    prevcai_ = -1;
-}
-
-bool AnalysisNeighborhoodPairSearchImpl::isExcluded(int j)
+void AnalysisNeighborhoodPairSearchImpl::reset(int testIndex)
 {
-    if (exclind_ < search_.nexcl_)
+    testIndex_ = testIndex;
+    if (testIndex_ >= 0 && testIndex_ < static_cast<int>(testPositions_.size()))
     {
-        if (search_.refid_)
+        copy_rvec(testPositions_[testIndex_], xtest_);
+        if (search_.bGrid_)
         {
-            while (exclind_ < search_.nexcl_
-                   && search_.excl_[exclind_] < search_.refid_[j])
-            {
-                ++exclind_;
-            }
-            if (exclind_ < search_.nexcl_
-                && search_.refid_[j] == search_.excl_[exclind_])
-            {
-                ++exclind_;
-                return true;
-            }
+            search_.mapPointToGridCell(testPositions_[testIndex], testcell_, xtest_);
         }
         else
         {
-            while (search_.bGrid_ && exclind_ < search_.nexcl_
-                   && search_.excl_[exclind_] < j)
+            copy_rvec(testPositions_[testIndex_], xtest_);
+        }
+        if (search_.excls_ != NULL)
+        {
+            const int exclIndex  = testExclusionIds_[testIndex];
+            if (exclIndex < search_.excls_->nr)
             {
-                ++exclind_;
+                const int startIndex = search_.excls_->index[exclIndex];
+                nexcl_ = search_.excls_->index[exclIndex + 1] - startIndex;
+                excl_  = &search_.excls_->a[startIndex];
             }
-            if (search_.excl_[exclind_] == j)
+            else
             {
-                ++exclind_;
-                return true;
+                nexcl_ = 0;
+                excl_  = NULL;
             }
         }
     }
+    previ_     = -1;
+    prevr2_    = 0.0;
+    exclind_   = 0;
+    prevnbi_   = 0;
+    prevcai_   = -1;
+}
+
+void AnalysisNeighborhoodPairSearchImpl::nextTestPosition()
+{
+    if (testIndex_ < static_cast<int>(testPositions_.size()))
+    {
+        ++testIndex_;
+        reset(testIndex_);
+    }
+}
+
+bool AnalysisNeighborhoodPairSearchImpl::isExcluded(int j)
+{
+    if (exclind_ < nexcl_)
+    {
+        const int refId = search_.refExclusionIds_[j];
+        while (exclind_ < nexcl_ && excl_[exclind_] < refId)
+        {
+            ++exclind_;
+        }
+        if (exclind_ < nexcl_ && refId == excl_[exclind_])
+        {
+            ++exclind_;
+            return true;
+        }
+    }
     return false;
 }
 
-void AnalysisNeighborhoodPairSearchImpl::startSearch(const rvec x, int testIndex)
+void AnalysisNeighborhoodPairSearchImpl::startSearch(
+        const AnalysisNeighborhoodPositions &positions)
 {
-    testIndex_ = testIndex;
-    copy_rvec(x, xtest_);
-    if (search_.bGrid_)
+    testExclusionIds_ = positions.exclusionIds_;
+    GMX_RELEASE_ASSERT(search_.excls_ == NULL || testExclusionIds_ != NULL,
+                       "Exclusion IDs must be set when exclusions are enabled");
+    if (positions.index_ < 0)
     {
-        put_atoms_in_triclinic_unitcell(ecenterTRIC, search_.pbc_->box,
-                                        1, &xtest_);
-        search_.mapPointToGridCell(xtest_, testcell_);
+        testPositions_ = constArrayRefFromArray<rvec>(positions.x_, positions.count_);
+        reset(0);
+    }
+    else
+    {
+        // Somewhat of a hack: setup the array such that only the last position
+        // will be used.
+        testPositions_ = constArrayRefFromArray<rvec>(positions.x_, positions.index_ + 1);
+        reset(positions.index_);
     }
-    reset();
 }
 
 template <class Action>
 bool AnalysisNeighborhoodPairSearchImpl::searchNext(Action action)
 {
-    if (search_.bGrid_)
+    while (testIndex_ < static_cast<int>(testPositions_.size()))
     {
-        int nbi = prevnbi_;
-        int cai = prevcai_ + 1;
-
-        for (; nbi < search_.ngridnb_; ++nbi)
+        if (search_.bGrid_)
         {
-            ivec cell;
+            GMX_RELEASE_ASSERT(!search_.bXY_, "Grid-based XY searches not implemented");
 
-            ivec_add(testcell_, search_.gnboffs_[nbi], cell);
-            cell[XX] = (cell[XX] + search_.ncelldim_[XX]) % search_.ncelldim_[XX];
-            cell[YY] = (cell[YY] + search_.ncelldim_[YY]) % search_.ncelldim_[YY];
-            cell[ZZ] = (cell[ZZ] + search_.ncelldim_[ZZ]) % search_.ncelldim_[ZZ];
+            int nbi = prevnbi_;
+            int cai = prevcai_ + 1;
 
-            const int ci       = search_.getGridCellIndex(cell);
-            const int cellSize = static_cast<int>(search_.cells_[ci].size());
-            /* TODO: Calculate the required PBC shift outside the inner loop */
-            for (; cai < cellSize; ++cai)
+            for (; nbi < search_.ngridnb_; ++nbi)
+            {
+                rvec      shift;
+                const int ci       = search_.getNeighboringCell(testcell_, nbi, shift);
+                const int cellSize = static_cast<int>(search_.cells_[ci].size());
+                for (; cai < cellSize; ++cai)
+                {
+                    const int i = search_.cells_[ci][cai];
+                    if (isExcluded(i))
+                    {
+                        continue;
+                    }
+                    rvec       dx;
+                    rvec_sub(xtest_, search_.xref_[i], dx);
+                    rvec_add(dx, shift, dx);
+                    const real r2 = norm2(dx);
+                    if (r2 <= search_.cutoff2_)
+                    {
+                        if (action(i, r2))
+                        {
+                            prevnbi_ = nbi;
+                            prevcai_ = cai;
+                            previ_   = i;
+                            prevr2_  = r2;
+                            return true;
+                        }
+                    }
+                }
+                exclind_ = 0;
+                cai      = 0;
+            }
+        }
+        else
+        {
+            for (int i = previ_ + 1; i < search_.nref_; ++i)
             {
-                const int i = search_.cells_[ci][cai];
                 if (isExcluded(i))
                 {
                     continue;
                 }
-                rvec       dx;
-                pbc_dx_aiuc(search_.pbc_, xtest_, search_.xref_[i], dx);
-                const real r2 = norm2(dx);
+                rvec dx;
+                if (search_.pbc_.ePBC != epbcNONE)
+                {
+                    pbc_dx(&search_.pbc_, xtest_, search_.xref_[i], dx);
+                }
+                else
+                {
+                    rvec_sub(xtest_, search_.xref_[i], dx);
+                }
+                const real r2
+                    = search_.bXY_
+                        ? dx[XX]*dx[XX] + dx[YY]*dx[YY]
+                        : norm2(dx);
                 if (r2 <= search_.cutoff2_)
                 {
                     if (action(i, r2))
                     {
-                        prevnbi_ = nbi;
-                        prevcai_ = cai;
-                        previ_   = i;
+                        previ_  = i;
+                        prevr2_ = r2;
                         return true;
                     }
                 }
             }
-            exclind_ = 0;
-            cai      = 0;
         }
+        nextTestPosition();
     }
-    else
-    {
-        for (int i = previ_ + 1; i < search_.nref_; ++i)
-        {
-            if (isExcluded(i))
-            {
-                continue;
-            }
-            rvec dx;
-            if (search_.pbc_)
-            {
-                pbc_dx(search_.pbc_, xtest_, search_.xref_[i], dx);
-            }
-            else
-            {
-                rvec_sub(xtest_, search_.xref_[i], dx);
-            }
-            const real r2 = norm2(dx);
-            if (r2 <= search_.cutoff2_)
-            {
-                if (action(i, r2))
-                {
-                    previ_ = i;
-                    return true;
-                }
-            }
-        }
-    }
-    reset();
     return false;
 }
 
@@ -659,7 +797,7 @@ void AnalysisNeighborhoodPairSearchImpl::initFoundPair(
     }
     else
     {
-        *pair = AnalysisNeighborhoodPair(previ_, testIndex_);
+        *pair = AnalysisNeighborhoodPair(previ_, testIndex_, prevr2_);
     }
 }
 
@@ -740,7 +878,7 @@ class AnalysisNeighborhood::Impl
         typedef AnalysisNeighborhoodSearch::ImplPointer SearchImplPointer;
         typedef std::vector<SearchImplPointer> SearchList;
 
-        Impl() : cutoff_(0), mode_(eSearchMode_Automatic)
+        Impl() : cutoff_(0), excls_(NULL), mode_(eSearchMode_Automatic), bXY_(false)
         {
         }
         ~Impl()
@@ -758,7 +896,9 @@ class AnalysisNeighborhood::Impl
         tMPI::mutex             createSearchMutex_;
         SearchList              searchList_;
         real                    cutoff_;
+        const t_blocka         *excls_;
         SearchMode              mode_;
+        bool                    bXY_;
 };
 
 AnalysisNeighborhood::Impl::SearchImplPointer
@@ -800,6 +940,18 @@ void AnalysisNeighborhood::setCutoff(real cutoff)
     impl_->cutoff_ = cutoff;
 }
 
+void AnalysisNeighborhood::setXYMode(bool bXY)
+{
+    impl_->bXY_ = bXY;
+}
+
+void AnalysisNeighborhood::setTopologyExclusions(const t_blocka *excls)
+{
+    GMX_RELEASE_ASSERT(impl_->searchList_.empty(),
+                       "Changing the exclusions after initSearch() not currently supported");
+    impl_->excls_ = excls;
+}
+
 void AnalysisNeighborhood::setMode(SearchMode mode)
 {
     impl_->mode_ = mode;
@@ -811,18 +963,11 @@ AnalysisNeighborhood::SearchMode AnalysisNeighborhood::mode() const
 }
 
 AnalysisNeighborhoodSearch
-AnalysisNeighborhood::initSearch(const t_pbc *pbc, int n, const rvec x[])
-{
-    Impl::SearchImplPointer search(impl_->getSearch());
-    search->init(mode(), pbc, n, x, NULL);
-    return AnalysisNeighborhoodSearch(search);
-}
-
-AnalysisNeighborhoodSearch
-AnalysisNeighborhood::initSearch(const t_pbc *pbc, const gmx_ana_pos_t *p)
+AnalysisNeighborhood::initSearch(const t_pbc                         *pbc,
+                                 const AnalysisNeighborhoodPositions &positions)
 {
     Impl::SearchImplPointer search(impl_->getSearch());
-    search->init(mode(), pbc, p->nr, p->x, p->m.refid);
+    search->init(mode(), impl_->bXY_, impl_->excls_, pbc, positions);
     return AnalysisNeighborhoodSearch(search);
 }
 
@@ -852,24 +997,21 @@ AnalysisNeighborhood::SearchMode AnalysisNeighborhoodSearch::mode() const
             : AnalysisNeighborhood::eSearchMode_Simple);
 }
 
-bool AnalysisNeighborhoodSearch::isWithin(const rvec x) const
+bool AnalysisNeighborhoodSearch::isWithin(
+        const AnalysisNeighborhoodPositions &positions) const
 {
     GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
     internal::AnalysisNeighborhoodPairSearchImpl pairSearch(*impl_);
-    pairSearch.startSearch(x, 0);
+    pairSearch.startSearch(positions);
     return pairSearch.searchNext(&withinAction);
 }
 
-bool AnalysisNeighborhoodSearch::isWithin(const gmx_ana_pos_t *p, int i) const
-{
-    return isWithin(p->x[i]);
-}
-
-real AnalysisNeighborhoodSearch::minimumDistance(const rvec x) const
+real AnalysisNeighborhoodSearch::minimumDistance(
+        const AnalysisNeighborhoodPositions &positions) const
 {
     GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
     internal::AnalysisNeighborhoodPairSearchImpl pairSearch(*impl_);
-    pairSearch.startSearch(x, 0);
+    pairSearch.startSearch(positions);
     real          minDist2     = impl_->cutoffSquared();
     int           closestPoint = -1;
     MindistAction action(&closestPoint, &minDist2);
@@ -877,52 +1019,27 @@ real AnalysisNeighborhoodSearch::minimumDistance(const rvec x) const
     return sqrt(minDist2);
 }
 
-real AnalysisNeighborhoodSearch::minimumDistance(const gmx_ana_pos_t *p, int i) const
-{
-    return minimumDistance(p->x[i]);
-}
-
 AnalysisNeighborhoodPair
-AnalysisNeighborhoodSearch::nearestPoint(const rvec x) const
+AnalysisNeighborhoodSearch::nearestPoint(
+        const AnalysisNeighborhoodPositions &positions) const
 {
     GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
     internal::AnalysisNeighborhoodPairSearchImpl pairSearch(*impl_);
-    pairSearch.startSearch(x, 0);
+    pairSearch.startSearch(positions);
     real          minDist2     = impl_->cutoffSquared();
     int           closestPoint = -1;
     MindistAction action(&closestPoint, &minDist2);
     (void)pairSearch.searchNext(action);
-    return AnalysisNeighborhoodPair(closestPoint, 0);
-}
-
-AnalysisNeighborhoodPair
-AnalysisNeighborhoodSearch::nearestPoint(const gmx_ana_pos_t *p, int i) const
-{
-    GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
-    internal::AnalysisNeighborhoodPairSearchImpl pairSearch(*impl_);
-    pairSearch.startSearch(p->x[i], 0);
-    real          minDist2     = impl_->cutoffSquared();
-    int           closestPoint = -1;
-    MindistAction action(&closestPoint, &minDist2);
-    (void)pairSearch.searchNext(action);
-    return AnalysisNeighborhoodPair(closestPoint, i);
+    return AnalysisNeighborhoodPair(closestPoint, 0, minDist2);
 }
 
 AnalysisNeighborhoodPairSearch
-AnalysisNeighborhoodSearch::startPairSearch(const rvec x)
+AnalysisNeighborhoodSearch::startPairSearch(
+        const AnalysisNeighborhoodPositions &positions) const
 {
     GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
     Impl::PairSearchImplPointer pairSearch(impl_->getPairSearch());
-    pairSearch->startSearch(x, 0);
-    return AnalysisNeighborhoodPairSearch(pairSearch);
-}
-
-AnalysisNeighborhoodPairSearch
-AnalysisNeighborhoodSearch::startPairSearch(const gmx_ana_pos_t *p, int i)
-{
-    GMX_RELEASE_ASSERT(impl_, "Accessing an invalid search object");
-    Impl::PairSearchImplPointer pairSearch(impl_->getPairSearch());
-    pairSearch->startSearch(p->x[i], i);
+    pairSearch->startSearch(positions);
     return AnalysisNeighborhoodPairSearch(pairSearch);
 }
 
@@ -943,4 +1060,9 @@ bool AnalysisNeighborhoodPairSearch::findNextPair(AnalysisNeighborhoodPair *pair
     return bFound;
 }
 
+void AnalysisNeighborhoodPairSearch::skipRemainingPairsForTestPosition()
+{
+    impl_->nextTestPosition();
+}
+
 } // namespace gmx