src/gromacs/selection/nbsearch.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2009,2010,2011,2012,2013,2014,2015, by the GROMACS development team, led by
   5  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   6  * and including many others, as listed in the AUTHORS file in the
   7  * top-level source directory and at http://www.gromacs.org.
   8  *
   9  * GROMACS is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public License
  11  * as published by the Free Software Foundation; either version 2.1
  12  * of the License, or (at your option) any later version.
  13  *
  14  * GROMACS is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with GROMACS; if not, see
  21  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  23  *
  24  * If you want to redistribute modifications to GROMACS, please
  25  * consider that scientific software is very special. Version
  26  * control is crucial - bugs must be traceable. We will be happy to
  27  * consider code for inclusion in the official distribution, but
  28  * derived work must not be called official GROMACS. Details are found
  29  * in the README & COPYING files - if they are missing, get the
  30  * official version at http://www.gromacs.org.
  31  *
  32  * To help us fund GROMACS development, we humbly ask that you cite
  33  * the research papers on the package. Check out http://www.gromacs.org.
  34  */
  35 /*! \file
  36  * \brief API for neighborhood searching for analysis.
  37  *
  38  * The main part of the API is the class gmx::AnalysisNeighborhood.
  39  * See \ref page_analysisnbsearch for an overview.
  40  *
  41  * The classes within this file can be used independently of the other parts
  42  * of the selection module.
  43  *
  44  * \author Teemu Murtola <teemu.murtola@gmail.com>
  45  * \inpublicapi
  46  * \ingroup module_selection
  47  */
  48 #ifndef GMX_SELECTION_NBSEARCH_H
  49 #define GMX_SELECTION_NBSEARCH_H
  50
  51 #include <vector>
  52
  53 #include <boost/shared_ptr.hpp>
  54
  55 #include "gromacs/math/vec.h"
  56 #include "gromacs/math/vectypes.h"
  57 #include "gromacs/utility/arrayref.h"
  58 #include "gromacs/utility/classhelpers.h"
  59 #include "gromacs/utility/gmxassert.h"
  60 #include "gromacs/utility/real.h"
  61
  62 struct t_blocka;
  63 struct t_pbc;
  64
  65 namespace gmx
  66 {
  67
  68 namespace internal
  69 {
  70 class AnalysisNeighborhoodSearchImpl;
  71 class AnalysisNeighborhoodPairSearchImpl;
  72 };
  73
  74 class AnalysisNeighborhoodSearch;
  75 class AnalysisNeighborhoodPairSearch;
  76
  77 /*! \brief
  78  * Input positions for neighborhood searching.
  79  *
  80  * This class supports uniformly specifying sets of positions for various
  81  * methods in the analysis neighborhood searching classes
  82  * (AnalysisNeighborhood and AnalysisNeighborhoodSearch).
  83  *
  84  * Note that copies are not made: only a reference to the positions passed to
  85  * the constructors are kept.  The caller is responsible to ensure that those
  86  * positions remain in scope as long as the neighborhood search object requires
  87  * access to them.
  88  *
  89  * Also note that in addition to constructors here, Selection and
  90  * SelectionPosition provide conversions operators to this type.  It is done
  91  * this way to not introduce a cyclic dependency between the selection code and
  92  * the neighborhood search code, which in turn allows splitting this search
  93  * code into a separate lower-level module if desired at some point.
  94  *
  95  * Methods in this class do not throw.
  96  *
  97  * \inpublicapi
  98  * \ingroup module_selection
  99  */
 100 class AnalysisNeighborhoodPositions
 101 {
 102     public:
 103         /*! \brief
 104          * Initializes positions from a single position vector.
 105          *
 106          * For positions initialized this way, AnalysisNeighborhoodPair always
 107          * returns zero in the corresponding index.
 108          *
 109          * This constructor is not explicit to allow directly passing an rvec
 110          * to methods that accept positions.
 111          */
 112         AnalysisNeighborhoodPositions(const rvec &x)
 113             : count_(1), index_(-1), x_(&x), exclusionIds_(NULL), indices_(NULL)
 114         {
 115         }
 116         /*! \brief
 117          * Initializes positions from an array of position vectors.
 118          */
 119         AnalysisNeighborhoodPositions(const rvec x[], int count)
 120             : count_(count), index_(-1), x_(x), exclusionIds_(NULL), indices_(NULL)
 121         {
 122         }
 123         /*! \brief
 124          * Initializes positions from a vector of position vectors.
 125          */
 126         AnalysisNeighborhoodPositions(const std::vector<RVec> &x)
 127             : count_(x.size()), index_(-1), x_(as_rvec_array(&x[0])),
 128               exclusionIds_(NULL), indices_(NULL)
 129         {
 130         }
 131
 132         /*! \brief
 133          * Sets indices to use for mapping exclusions to these positions.
 134          *
 135          * The exclusion IDs can always be set, but they are ignored unless
 136          * actual exclusions have been set with
 137          * AnalysisNeighborhood::setTopologyExclusions().
 138          */
 139         AnalysisNeighborhoodPositions &
 140         exclusionIds(ConstArrayRef<int> ids)
 141         {
 142             GMX_ASSERT(static_cast<int>(ids.size()) == count_,
 143                        "Exclusion id array should match the number of positions");
 144             exclusionIds_ = ids.data();
 145             return *this;
 146         }
 147         /*! \brief
 148          * Sets indices that select a subset of all positions from the array.
 149          *
 150          * If called, selected positions from the array of positions passed to
 151          * the constructor is used instead of the whole array.
 152          * All returned indices from AnalysisNeighborhoodPair objects are
 153          * indices to the \p indices array passed here.
 154          */
 155         AnalysisNeighborhoodPositions &
 156         indexed(ConstArrayRef<int> indices)
 157         {
 158             count_   = indices.size();
 159             indices_ = indices.data();
 160             return *this;
 161         }
 162
 163         /*! \brief
 164          * Selects a single position to use from an array.
 165          *
 166          * If called, a single position from the array of positions passed to
 167          * the constructor is used instead of the whole array.
 168          * In contrast to the AnalysisNeighborhoodPositions(const rvec &)
 169          * constructor, AnalysisNeighborhoodPair objects return \p index
 170          * instead of zero.
 171          *
 172          * If used together with indexed(), \p index references the index array
 173          * passed to indexed() instead of the position array.
 174          */
 175         AnalysisNeighborhoodPositions &selectSingleFromArray(int index)
 176         {
 177             GMX_ASSERT(index >= 0 && index < count_, "Invalid position index");
 178             index_ = index;
 179             return *this;
 180         }
 181
 182     private:
 183         int                     count_;
 184         int                     index_;
 185         const rvec             *x_;
 186         const int              *exclusionIds_;
 187         const int              *indices_;
 188
 189         //! To access the positions for initialization.
 190         friend class internal::AnalysisNeighborhoodSearchImpl;
 191         //! To access the positions for initialization.
 192         friend class internal::AnalysisNeighborhoodPairSearchImpl;
 193 };
 194
 195 /*! \brief
 196  * Neighborhood searching for analysis tools.
 197  *
 198  * See \ref page_analysisnbsearch for an overview.
 199  *
 200  * To use the search, create an object of this type, call setCutoff() to
 201  * initialize it, and then repeatedly call initSearch() to start a search with
 202  * different sets of reference positions.  For each set of reference positions,
 203  * use methods in the returned AnalysisNeighborhoodSearch to find the reference
 204  * positions that are within the given cutoff from a provided position.
 205  *
 206  * initSearch() is thread-safe and can be called from multiple threads.  Each
 207  * call returns a different instance of the search object that can be used
 208  * independently of the others.  The returned AnalysisNeighborhoodSearch
 209  * objects are also thread-safe, and can be used concurrently from multiple
 210  * threads.  It is also possible to create multiple concurrent searches within
 211  * a single thread.
 212  *
 213  * \todo
 214  * Generalize the exclusion machinery to make it easier to use for other cases
 215  * than atom-atom exclusions from the topology.
 216  *
 217  * \inpublicapi
 218  * \ingroup module_selection
 219  */
 220 class AnalysisNeighborhood
 221 {
 222     public:
 223         //! Searching algorithm to use.
 224         enum SearchMode
 225         {
 226             //! Select algorithm based on heuristic efficiency considerations.
 227             eSearchMode_Automatic,
 228             //! Use a simple loop over all pairs.
 229             eSearchMode_Simple,
 230             //! Use grid-based searching whenever possible.
 231             eSearchMode_Grid
 232         };
 233
 234         //! Creates an uninitialized neighborhood search.
 235         AnalysisNeighborhood();
 236         ~AnalysisNeighborhood();
 237
 238         /*! \brief
 239          * Sets cutoff distance for the neighborhood searching.
 240          *
 241          * \param[in]  cutoff Cutoff distance for the search
 242          *   (<=0 stands for no cutoff).
 243          *
 244          * Currently, can only be called before the first call to initSearch().
 245          * If this method is not called, no cutoff is used in the searches.
 246          *
 247          * Does not throw.
 248          */
 249         void setCutoff(real cutoff);
 250         /*! \brief
 251          * Sets the search to only happen in the XY plane.
 252          *
 253          * Z component of the coordinates is not used in the searching,
 254          * and returned distances are computed in the XY plane.
 255          * Only boxes with the third box vector parallel to the Z axis are
 256          * currently implemented.
 257          *
 258          * Does not throw.
 259          */
 260         void setXYMode(bool bXY);
 261         /*! \brief
 262          * Sets atom exclusions from a topology.
 263          *
 264          * The \p excls structure specifies the exclusions from test positions
 265          * to reference positions, i.e., a block starting at `excls->index[i]`
 266          * specifies the exclusions for test position `i`, and the indices in
 267          * `excls->a` are indices of the reference positions.  If `excls->nr`
 268          * is smaller than a test position id, then such test positions do not
 269          * have any exclusions.
 270          * It is assumed that the indices within a block of indices in
 271          * `excls->a` is ascending.
 272          *
 273          * Does not throw.
 274          *
 275          * \see AnalysisNeighborhoodPositions::exclusionIds()
 276          */
 277         void setTopologyExclusions(const t_blocka *excls);
 278         /*! \brief
 279          * Sets the algorithm to use for searching.
 280          *
 281          * \param[in] mode  Search mode to use.
 282          *
 283          * Note that if \p mode is \ref eSearchMode_Grid, it is still only a
 284          * suggestion: grid-based searching may not be possible with the
 285          * provided input, in which case a simple search is still used.
 286          * This is mainly useful for testing purposes to force a mode.
 287          *
 288          * Does not throw.
 289          */
 290         void setMode(SearchMode mode);
 291         //! Returns the currently active search mode.
 292         SearchMode mode() const;
 293
 294         /*! \brief
 295          * Initializes neighborhood search for a set of positions.
 296          *
 297          * \param[in] pbc        PBC information for the frame.
 298          * \param[in] positions  Set of reference positions to use.
 299          * \returns   Search object that can be used to find positions from
 300          *      \p x within the given cutoff.
 301          * \throws    std::bad_alloc if out of memory.
 302          *
 303          * Currently, the input positions cannot use
 304          * AnalysisNeighborhoodPositions::selectSingleFromArray().
 305          */
 306         AnalysisNeighborhoodSearch
 307         initSearch(const t_pbc                         *pbc,
 308                    const AnalysisNeighborhoodPositions &positions);
 309
 310     private:
 311         class Impl;
 312
 313         PrivateImplPointer<Impl> impl_;
 314 };
 315
 316 /*! \brief
 317  * Value type to represent a pair of positions found in neighborhood searching.
 318  *
 319  * Methods in this class do not throw.
 320  *
 321  * \inpublicapi
 322  * \ingroup module_selection
 323  */
 324 class AnalysisNeighborhoodPair
 325 {
 326     public:
 327         //! Initializes an invalid pair.
 328         AnalysisNeighborhoodPair() : refIndex_(-1), testIndex_(0), distance2_(0.0)
 329         {
 330             clear_rvec(dx_);
 331         }
 332         //! Initializes a pair object with the given data.
 333         AnalysisNeighborhoodPair(int refIndex, int testIndex, real distance2,
 334                                  const rvec dx)
 335             : refIndex_(refIndex), testIndex_(testIndex), distance2_(distance2)
 336         {
 337             copy_rvec(dx, dx_);
 338         }
 339
 340         /*! \brief
 341          * Whether this pair is valid.
 342          *
 343          * If isValid() returns false, other methods should not be called.
 344          */
 345         bool isValid() const { return refIndex_ >= 0; }
 346
 347         /*! \brief
 348          * Returns the index of the reference position in the pair.
 349          *
 350          * This index is always the index into the position array provided to
 351          * AnalysisNeighborhood::initSearch().
 352          */
 353         int refIndex() const
 354         {
 355             GMX_ASSERT(isValid(), "Accessing invalid object");
 356             return refIndex_;
 357         }
 358         /*! \brief
 359          * Returns the index of the test position in the pair.
 360          *
 361          * The contents of this index depends on the context (method call) that
 362          * produces the pair.
 363          * If there was no array in the call, this index is zero.
 364          */
 365         int testIndex() const
 366         {
 367             GMX_ASSERT(isValid(), "Accessing invalid object");
 368             return testIndex_;
 369         }
 370         /*! \brief
 371          * Returns the squared distance between the pair of positions.
 372          */
 373         real distance2() const
 374         {
 375             GMX_ASSERT(isValid(), "Accessing invalid object");
 376             return distance2_;
 377         }
 378         /*! \brief
 379          * Returns the shortest vector between the pair of positions.
 380          *
 381          * The vector is from the test position to the reference position.
 382          */
 383         const rvec &dx() const
 384         {
 385             GMX_ASSERT(isValid(), "Accessing invalid object");
 386             return dx_;
 387         }
 388
 389     private:
 390         int                     refIndex_;
 391         int                     testIndex_;
 392         real                    distance2_;
 393         rvec                    dx_;
 394 };
 395
 396 /*! \brief
 397  * Initialized neighborhood search with a fixed set of reference positions.
 398  *
 399  * An instance of this class is obtained through
 400  * AnalysisNeighborhood::initSearch(), and can be used to do multiple searches
 401  * against the provided set of reference positions.
 402  * It is possible to create concurrent pair searches (including from different
 403  * threads), as well as call other methods in this class while a pair search is
 404  * in progress.
 405  *
 406  * This class works like a pointer: copies of it point to the same search.
 407  * In general, avoid creating copies, and only use the copy/assignment support
 408  * for moving the variable around.  With C++11, this class would best be
 409  * movable.
 410  *
 411  * Methods in this class do not throw unless otherwise indicated.
 412  *
 413  * \todo
 414  * Make it such that reset() is not necessary to call in code that repeatedly
 415  * assigns the result of AnalysisNeighborhood::initSearch() to the same
 416  * variable (see sm_distance.cpp).
 417  *
 418  * \todo
 419  * Consider merging nearestPoint() and minimumDistance() by adding the distance
 420  * to AnalysisNeighborhoodPair.
 421  *
 422  * \inpublicapi
 423  * \ingroup module_selection
 424  */
 425 class AnalysisNeighborhoodSearch
 426 {
 427     public:
 428         /*! \brief
 429          * Internal short-hand type for a pointer to the implementation class.
 430          *
 431          * shared_ptr is used here to automatically keep a reference count to
 432          * track whether an implementation class is still used outside the
 433          * AnalysisNeighborhood object.  Ownership currently always stays with
 434          * AnalysisNeighborhood; it always keeps one instance of the pointer.
 435          */
 436         typedef boost::shared_ptr<internal::AnalysisNeighborhoodSearchImpl>
 437             ImplPointer;
 438
 439         /*! \brief
 440          * Initializes an invalid search.
 441          *
 442          * Such an object cannot be used for searching.  It needs to be
 443          * assigned a value from AnalysisNeighborhood::initSearch() before it
 444          * can be used.  Provided to allow declaring a variable to hold the
 445          * search before calling AnalysisNeighborhood::initSearch().
 446          */
 447         AnalysisNeighborhoodSearch();
 448         /*! \brief
 449          * Internally initialize the search.
 450          *
 451          * Used to implement AnalysisNeighborhood::initSearch().
 452          * Cannot be called from user code.
 453          */
 454         explicit AnalysisNeighborhoodSearch(const ImplPointer &impl);
 455
 456         /*! \brief
 457          * Clears this search.
 458          *
 459          * Equivalent to \c "*this = AnalysisNeighborhoodSearch();".
 460          * Currently, this is necessary to avoid unnecessary memory allocation
 461          * if the previous search variable is still in scope when you want to
 462          * call AnalysisNeighborhood::initSearch() again.
 463          */
 464         void reset();
 465
 466         /*! \brief
 467          * Returns the searching algorithm that this search is using.
 468          *
 469          * The return value is never AnalysisNeighborhood::eSearchMode_Automatic.
 470          */
 471         AnalysisNeighborhood::SearchMode mode() const;
 472
 473         /*! \brief
 474          * Check whether a point is within a neighborhood.
 475          *
 476          * \param[in] positions  Set of test positions to use.
 477          * \returns   true if any of the test positions is within the cutoff of
 478          *     any reference position.
 479          */
 480         bool isWithin(const AnalysisNeighborhoodPositions &positions) const;
 481         /*! \brief
 482          * Calculates the minimum distance from the reference points.
 483          *
 484          * \param[in] positions  Set of test positions to use.
 485          * \returns   The distance to the nearest reference position, or the
 486          *     cutoff value if there are no reference positions within the
 487          *     cutoff.
 488          */
 489         real minimumDistance(const AnalysisNeighborhoodPositions &positions) const;
 490         /*! \brief
 491          * Finds the closest reference point.
 492          *
 493          * \param[in] positions  Set of test positions to use.
 494          * \returns   The reference index identifies the reference position
 495          *     that is closest to the test positions.
 496          *     The test index identifies the test position that is closest to
 497          *     the provided test position.  The returned pair is invalid if
 498          *     no reference position is within the cutoff.
 499          */
 500         AnalysisNeighborhoodPair
 501         nearestPoint(const AnalysisNeighborhoodPositions &positions) const;
 502
 503         /*! \brief
 504          * Start a search to find reference positions within a cutoff.
 505          *
 506          * \param[in] positions  Set of test positions to use.
 507          * \returns   Initialized search object to loop through all reference
 508          *     positions within the configured cutoff.
 509          * \throws    std::bad_alloc if out of memory.
 510          */
 511         AnalysisNeighborhoodPairSearch
 512         startPairSearch(const AnalysisNeighborhoodPositions &positions) const;
 513
 514     private:
 515         typedef internal::AnalysisNeighborhoodSearchImpl Impl;
 516
 517         ImplPointer             impl_;
 518 };
 519
 520 /*! \brief
 521  * Initialized neighborhood pair search with a fixed set of positions.
 522  *
 523  * This class is used to loop through pairs of neighbors within the cutoff
 524  * provided to AnalysisNeighborhood.  The following code demonstrates its use:
 525  * \code
 526    gmx::AnalysisNeighborhood       nb;
 527    nb.setCutoff(cutoff);
 528    gmx::AnalysisNeighborhoodPositions refPos(xref, nref);
 529    gmx::AnalysisNeighborhoodSearch search = nb.initSearch(pbc, refPos);
 530    gmx::AnalysisNeighborhoodPairSearch pairSearch = search.startPairSearch(selection);
 531    gmx::AnalysisNeighborhoodPair pair;
 532    while (pairSearch.findNextPair(&pair))
 533    {
 534        // <do something for each found pair the information in pair>
 535    }
 536  * \endcode
 537  *
 538  * It is not possible to use a single search object from multiple threads
 539  * concurrently.
 540  *
 541  * This class works like a pointer: copies of it point to the same search.
 542  * In general, avoid creating copies, and only use the copy/assignment support
 543  * for moving the variable around.  With C++11, this class would best be
 544  * movable.
 545  *
 546  * Methods in this class do not throw.
 547  *
 548  * \inpublicapi
 549  * \ingroup module_selection
 550  */
 551 class AnalysisNeighborhoodPairSearch
 552 {
 553     public:
 554         /*! \brief
 555          * Internal short-hand type for a pointer to the implementation class.
 556          *
 557          * See AnalysisNeighborhoodSearch::ImplPointer for rationale of using
 558          * shared_ptr and ownership semantics.
 559          */
 560         typedef boost::shared_ptr<internal::AnalysisNeighborhoodPairSearchImpl>
 561             ImplPointer;
 562
 563         /*! \brief
 564          * Internally initialize the search.
 565          *
 566          * Used to implement AnalysisNeighborhoodSearch::startPairSearch().
 567          * Cannot be called from user code.
 568          */
 569         explicit AnalysisNeighborhoodPairSearch(const ImplPointer &impl);
 570
 571         /*! \brief
 572          * Finds the next pair within the cutoff.
 573          *
 574          * \param[out] pair  Information about the found pair.
 575          * \returns    false if there were no more pairs.
 576          *
 577          * If the method returns false, \p pair will be invalid.
 578          *
 579          * \see AnalysisNeighborhoodPair
 580          * \see AnalysisNeighborhoodSearch::startPairSearch()
 581          */
 582         bool findNextPair(AnalysisNeighborhoodPair *pair);
 583         /*! \brief
 584          * Skip remaining pairs for a test position in the search.
 585          *
 586          * When called after findNextPair(), makes subsequent calls to
 587          * findNextPair() skip any pairs that have the same test position as
 588          * that previously returned.
 589          * This is useful if the caller wants to search whether any reference
 590          * position within the cutoff satisfies some condition.  This method
 591          * can be used to skip remaining pairs after the first such position
 592          * has been found if the remaining pairs would not have an effect on
 593          * the outcome.
 594          */
 595         void skipRemainingPairsForTestPosition();
 596
 597     private:
 598         ImplPointer             impl_;
 599 };
 600
 601 } // namespace gmx
 602
 603 #endif