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, 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 the class documentation for usage.
  40  *
  41  * The classes within this file can be used independently of the other parts
  42  * of the library.
  43  * The library also uses the classes internally.
  44  *
  45  * \author Teemu Murtola <teemu.murtola@gmail.com>
  46  * \inpublicapi
  47  * \ingroup module_selection
  48  */
  49 #ifndef GMX_SELECTION_NBSEARCH_H
  50 #define GMX_SELECTION_NBSEARCH_H
  51
  52 #include <boost/shared_ptr.hpp>
  53
  54 #include "../math/vectypes.h"
  55 #include "../utility/common.h"
  56 #include "../utility/gmxassert.h"
  57 #include "../utility/real.h"
  58
  59 struct t_pbc;
  60
  61 namespace gmx
  62 {
  63
  64 namespace internal
  65 {
  66 class AnalysisNeighborhoodSearchImpl;
  67 class AnalysisNeighborhoodPairSearchImpl;
  68 };
  69
  70 class AnalysisNeighborhoodSearch;
  71 class AnalysisNeighborhoodPairSearch;
  72
  73 /*! \brief
  74  * Input positions for neighborhood searching.
  75  *
  76  * This class supports uniformly specifying sets of positions for various
  77  * methods in the analysis neighborhood searching classes
  78  * (AnalysisNeighborhood and AnalysisNeighborhoodSearch).
  79  *
  80  * Note that copies are not made: only a reference to the positions passed to
  81  * the constructors are kept.  The caller is responsible to ensure that those
  82  * positions remain in scope as long as the neighborhood search object requires
  83  * access to them.
  84  *
  85  * Also note that in addition to constructors here, Selection and
  86  * SelectionPosition provide conversions operators to this type.  It is done
  87  * this way to not introduce a cyclic dependency between the selection code and
  88  * the neighborhood search code, which in turn allows splitting this search
  89  * code into a separate lower-level module if desired at some point.
  90  *
  91  * Methods in this class do not throw.
  92  *
  93  * \inpublicapi
  94  * \ingroup module_selection
  95  */
  96 class AnalysisNeighborhoodPositions
  97 {
  98     public:
  99         /*! \brief
 100          * Initializes positions from a single position vector.
 101          *
 102          * For positions initialized this way, AnalysisNeighborhoodPair always
 103          * returns zero in the corresponding index.
 104          *
 105          * This constructor is not explicit to allow directly passing an rvec
 106          * to methods that accept positions.
 107          */
 108         AnalysisNeighborhoodPositions(const rvec &x)
 109             : count_(1), index_(-1), x_(&x)
 110         {
 111         }
 112         /*! \brief
 113          * Initializes positions from an array of position vectors.
 114          */
 115         AnalysisNeighborhoodPositions(const rvec x[], int count)
 116             : count_(count), index_(-1), x_(x)
 117         {
 118         }
 119
 120         /*! \brief
 121          * Selects a single position to use from an array.
 122          *
 123          * If called, a single position from the array of positions passed to
 124          * the constructor is used instead of the whole array.
 125          * In contrast to the AnalysisNeighborhoodPositions(const rvec &)
 126          * constructor, AnalysisNeighborhoodPair objects return \p index
 127          * instead of zero.
 128          */
 129         AnalysisNeighborhoodPositions &selectSingleFromArray(int index)
 130         {
 131             GMX_ASSERT(index >= 0 && index < count_, "Invalid position index");
 132             index_ = index;
 133             return *this;
 134         }
 135
 136     private:
 137         int                     count_;
 138         int                     index_;
 139         const rvec             *x_;
 140
 141         //! To access the positions for initialization.
 142         friend class internal::AnalysisNeighborhoodSearchImpl;
 143         //! To access the positions for initialization.
 144         friend class internal::AnalysisNeighborhoodPairSearchImpl;
 145 };
 146
 147 /*! \brief
 148  * Neighborhood searching for analysis tools.
 149  *
 150  * This class implements neighborhood searching routines for analysis tools.
 151  * The emphasis is in flexibility and ease of use; one main driver is to have
 152  * a common implementation of grid-based searching to avoid replicating this in
 153  * multiple tools (and to make more tools take advantage of the significant
 154  * performance improvement this allows).
 155  *
 156  * To use the search, create an object of this type, call setCutoff() to
 157  * initialize it, and then repeatedly call initSearch() to start a search with
 158  * different sets of reference positions.  For each set of reference positions,
 159  * use methods in the returned AnalysisNeighborhoodSearch to find the reference
 160  * positions that are within the given cutoff from a provided position.
 161  *
 162  * initSearch() is thread-safe and can be called from multiple threads.  Each
 163  * call returns a different instance of the search object that can be used
 164  * independently of the others.  The returned AnalysisNeighborhoodSearch
 165  * objects are also thread-safe, and can be used concurrently from multiple
 166  * threads.  It is also possible to create multiple concurrent searches within
 167  * a single thread.
 168  *
 169  * \todo
 170  * Support for exclusions.
 171  * The 4.5/4.6 C API had very low-level support for exclusions, which was not
 172  * very convenient to use, and hadn't been tested much.  The internal code that
 173  * it used to do the exclusion during the search itself is still there, but it
 174  * needs more thought on what would be a convenient way to initialize it.
 175  * Can be implemented once there is need for it in some calling code.
 176  *
 177  * \inpublicapi
 178  * \ingroup module_selection
 179  */
 180 class AnalysisNeighborhood
 181 {
 182     public:
 183         //! Searching algorithm to use.
 184         enum SearchMode
 185         {
 186             //! Select algorithm based on heuristic efficiency considerations.
 187             eSearchMode_Automatic,
 188             //! Use a simple loop over all pairs.
 189             eSearchMode_Simple,
 190             //! Use grid-based searching whenever possible.
 191             eSearchMode_Grid
 192         };
 193
 194         //! Creates an uninitialized neighborhood search.
 195         AnalysisNeighborhood();
 196         ~AnalysisNeighborhood();
 197
 198         /*! \brief
 199          * Sets cutoff distance for the neighborhood searching.
 200          *
 201          * \param[in]  cutoff Cutoff distance for the search
 202          *   (<=0 stands for no cutoff).
 203          *
 204          * Currently, can only be called before the first call to initSearch().
 205          * If this method is not called, no cutoff is used in the searches.
 206          *
 207          * Does not throw.
 208          */
 209         void setCutoff(real cutoff);
 210         /*! \brief
 211          * Sets the search to only happen in the XY plane.
 212          *
 213          * Z component of the coordinates is not used in the searching,
 214          * and returned distances are computed in the XY plane.
 215          * Only boxes with the third box vector parallel to the Z axis are
 216          * currently implemented.
 217          *
 218          * Does not throw.
 219          */
 220         void setXYMode(bool bXY);
 221         /*! \brief
 222          * Sets the algorithm to use for searching.
 223          *
 224          * \param[in] mode  Search mode to use.
 225          *
 226          * Note that if \p mode is \ref eSearchMode_Grid, it is still only a
 227          * suggestion: grid-based searching may not be possible with the
 228          * provided input, in which case a simple search is still used.
 229          * This is mainly useful for testing purposes to force a mode.
 230          *
 231          * Does not throw.
 232          */
 233         void setMode(SearchMode mode);
 234         //! Returns the currently active search mode.
 235         SearchMode mode() const;
 236
 237         /*! \brief
 238          * Initializes neighborhood search for a set of positions.
 239          *
 240          * \param[in] pbc        PBC information for the frame.
 241          * \param[in] positions  Set of reference positions to use.
 242          * \returns   Search object that can be used to find positions from
 243          *      \p x within the given cutoff.
 244          * \throws    std::bad_alloc if out of memory.
 245          *
 246          * Currently, the input positions cannot use
 247          * AnalysisNeighborhoodPositions::selectSingleFromArray().
 248          */
 249         AnalysisNeighborhoodSearch
 250         initSearch(const t_pbc                         *pbc,
 251                    const AnalysisNeighborhoodPositions &positions);
 252
 253     private:
 254         class Impl;
 255
 256         PrivateImplPointer<Impl> impl_;
 257 };
 258
 259 /*! \brief
 260  * Value type to represent a pair of positions found in neighborhood searching.
 261  *
 262  * Methods in this class do not throw.
 263  *
 264  * \inpublicapi
 265  * \ingroup module_selection
 266  */
 267 class AnalysisNeighborhoodPair
 268 {
 269     public:
 270         //! Initializes an invalid pair.
 271         AnalysisNeighborhoodPair() : refIndex_(-1), testIndex_(0), distance2_(0.0) {}
 272         //! Initializes a pair object with the given data.
 273         AnalysisNeighborhoodPair(int refIndex, int testIndex, real distance2)
 274             : refIndex_(refIndex), testIndex_(testIndex), distance2_(distance2)
 275         {
 276         }
 277
 278         /*! \brief
 279          * Whether this pair is valid.
 280          *
 281          * If isValid() returns false, other methods should not be called.
 282          */
 283         bool isValid() const { return refIndex_ >= 0; }
 284
 285         /*! \brief
 286          * Returns the index of the reference position in the pair.
 287          *
 288          * This index is always the index into the position array provided to
 289          * AnalysisNeighborhood::initSearch().
 290          */
 291         int refIndex() const
 292         {
 293             GMX_ASSERT(isValid(), "Accessing invalid object");
 294             return refIndex_;
 295         }
 296         /*! \brief
 297          * Returns the index of the test position in the pair.
 298          *
 299          * The contents of this index depends on the context (method call) that
 300          * produces the pair.
 301          * If there was no array in the call, this index is zero.
 302          */
 303         int testIndex() const
 304         {
 305             GMX_ASSERT(isValid(), "Accessing invalid object");
 306             return testIndex_;
 307         }
 308         /*! \brief
 309          * Returns the squared distance between the pair of positions.
 310          */
 311         real distance2() const
 312         {
 313             GMX_ASSERT(isValid(), "Accessing invalid object");
 314             return distance2_;
 315         }
 316
 317     private:
 318         int                     refIndex_;
 319         int                     testIndex_;
 320         real                    distance2_;
 321 };
 322
 323 /*! \brief
 324  * Initialized neighborhood search with a fixed set of reference positions.
 325  *
 326  * An instance of this class is obtained through
 327  * AnalysisNeighborhood::initSearch(), and can be used to do multiple searches
 328  * against the provided set of reference positions.
 329  * It is possible to create concurrent pair searches (including from different
 330  * threads), as well as call other methods in this class while a pair search is
 331  * in progress.
 332  *
 333  * This class works like a pointer: copies of it point to the same search.
 334  * In general, avoid creating copies, and only use the copy/assignment support
 335  * for moving the variable around.  With C++11, this class would best be
 336  * movable.
 337  *
 338  * Methods in this class do not throw unless otherwise indicated.
 339  *
 340  * \todo
 341  * Make it such that reset() is not necessary to call in code that repeatedly
 342  * assigns the result of AnalysisNeighborhood::initSearch() to the same
 343  * variable (see sm_distance.cpp).
 344  *
 345  * \todo
 346  * Consider merging nearestPoint() and minimumDistance() by adding the distance
 347  * to AnalysisNeighborhoodPair.
 348  *
 349  * \inpublicapi
 350  * \ingroup module_selection
 351  */
 352 class AnalysisNeighborhoodSearch
 353 {
 354     public:
 355         /*! \brief
 356          * Internal short-hand type for a pointer to the implementation class.
 357          *
 358          * shared_ptr is used here to automatically keep a reference count to
 359          * track whether an implementation class is still used outside the
 360          * AnalysisNeighborhood object.  Ownership currently always stays with
 361          * AnalysisNeighborhood; it always keeps one instance of the pointer.
 362          */
 363         typedef boost::shared_ptr<internal::AnalysisNeighborhoodSearchImpl>
 364             ImplPointer;
 365
 366         /*! \brief
 367          * Initializes an invalid search.
 368          *
 369          * Such an object cannot be used for searching.  It needs to be
 370          * assigned a value from AnalysisNeighborhood::initSearch() before it
 371          * can be used.  Provided to allow declaring a variable to hold the
 372          * search before calling AnalysisNeighborhood::initSearch().
 373          */
 374         AnalysisNeighborhoodSearch();
 375         /*! \brief
 376          * Internally initialize the search.
 377          *
 378          * Used to implement AnalysisNeighborhood::initSearch().
 379          * Cannot be called from user code.
 380          */
 381         explicit AnalysisNeighborhoodSearch(const ImplPointer &impl);
 382
 383         /*! \brief
 384          * Clears this search.
 385          *
 386          * Equivalent to \c "*this = AnalysisNeighborhoodSearch();".
 387          * Currently, this is necessary to avoid unnecessary memory allocation
 388          * if the previous search variable is still in scope when you want to
 389          * call AnalysisNeighborhood::initSearch() again.
 390          */
 391         void reset();
 392
 393         /*! \brief
 394          * Returns the searching algorithm that this search is using.
 395          *
 396          * The return value is never AnalysisNeighborhood::eSearchMode_Automatic.
 397          */
 398         AnalysisNeighborhood::SearchMode mode() const;
 399
 400         /*! \brief
 401          * Check whether a point is within a neighborhood.
 402          *
 403          * \param[in] positions  Set of test positions to use.
 404          * \returns   true if any of the test positions is within the cutoff of
 405          *     any reference position.
 406          */
 407         bool isWithin(const AnalysisNeighborhoodPositions &positions) const;
 408         /*! \brief
 409          * Calculates the minimum distance from the reference points.
 410          *
 411          * \param[in] positions  Set of test positions to use.
 412          * \returns   The distance to the nearest reference position, or the
 413          *     cutoff value if there are no reference positions within the
 414          *     cutoff.
 415          */
 416         real minimumDistance(const AnalysisNeighborhoodPositions &positions) const;
 417         /*! \brief
 418          * Finds the closest reference point.
 419          *
 420          * \param[in] positions  Set of test positions to use.
 421          * \returns   The reference index identifies the reference position
 422          *     that is closest to the test positions.
 423          *     The test index identifies the test position that is closest to
 424          *     the provided test position.  The returned pair is invalid if
 425          *     no reference position is within the cutoff.
 426          */
 427         AnalysisNeighborhoodPair
 428         nearestPoint(const AnalysisNeighborhoodPositions &positions) const;
 429
 430         /*! \brief
 431          * Start a search to find reference positions within a cutoff.
 432          *
 433          * \param[in] positions  Set of test positions to use.
 434          * \returns   Initialized search object to loop through all reference
 435          *     positions within the configured cutoff.
 436          * \throws    std::bad_alloc if out of memory.
 437          */
 438         AnalysisNeighborhoodPairSearch
 439         startPairSearch(const AnalysisNeighborhoodPositions &positions) const;
 440
 441     private:
 442         typedef internal::AnalysisNeighborhoodSearchImpl Impl;
 443
 444         ImplPointer             impl_;
 445 };
 446
 447 /*! \brief
 448  * Initialized neighborhood pair search with a fixed set of positions.
 449  *
 450  * This class is used to loop through pairs of neighbors within the cutoff
 451  * provided to AnalysisNeighborhood.  The following code demonstrates its use:
 452  * \code
 453    gmx::AnalysisNeighborhood       nb;
 454    nb.setCutoff(cutoff);
 455    gmx::AnalysisNeighborhoodPositions refPos(xref, nref);
 456    gmx::AnalysisNeighborhoodSearch search = nb.initSearch(pbc, refPos);
 457    gmx::AnalysisNeighborhoodPairSearch pairSearch = search.startPairSearch(selection);
 458    gmx::AnalysisNeighborhoodPair pair;
 459    while (pairSearch.findNextPair(&pair))
 460    {
 461        // <do something for each found pair the information in pair>
 462    }
 463  * \endcode
 464  *
 465  * It is not possible to use a single search object from multiple threads
 466  * concurrently.
 467  *
 468  * This class works like a pointer: copies of it point to the same search.
 469  * In general, avoid creating copies, and only use the copy/assignment support
 470  * for moving the variable around.  With C++11, this class would best be
 471  * movable.
 472  *
 473  * Methods in this class do not throw.
 474  *
 475  * \inpublicapi
 476  * \ingroup module_selection
 477  */
 478 class AnalysisNeighborhoodPairSearch
 479 {
 480     public:
 481         /*! \brief
 482          * Internal short-hand type for a pointer to the implementation class.
 483          *
 484          * See AnalysisNeighborhoodSearch::ImplPointer for rationale of using
 485          * shared_ptr and ownership semantics.
 486          */
 487         typedef boost::shared_ptr<internal::AnalysisNeighborhoodPairSearchImpl>
 488             ImplPointer;
 489
 490         /*! \brief
 491          * Internally initialize the search.
 492          *
 493          * Used to implement AnalysisNeighborhoodSearch::startPairSearch().
 494          * Cannot be called from user code.
 495          */
 496         explicit AnalysisNeighborhoodPairSearch(const ImplPointer &impl);
 497
 498         /*! \brief
 499          * Finds the next pair within the cutoff.
 500          *
 501          * \param[out] pair  Information about the found pair.
 502          * \returns    false if there were no more pairs.
 503          *
 504          * If the method returns false, \p pair will be invalid.
 505          *
 506          * \see AnalysisNeighborhoodPair
 507          * \see AnalysisNeighborhoodSearch::startPairSearch()
 508          */
 509         bool findNextPair(AnalysisNeighborhoodPair *pair);
 510         /*! \brief
 511          * Skip remaining pairs for a test position in the search.
 512          *
 513          * When called after findNextPair(), makes subsequent calls to
 514          * findNextPair() skip any pairs that have the same test position as
 515          * that previously returned.
 516          * This is useful if the caller wants to search whether any reference
 517          * position within the cutoff satisfies some condition.  This method
 518          * can be used to skip remaining pairs after the first such position
 519          * has been found if the remaining pairs would not have an effect on
 520          * the outcome.
 521          */
 522         void skipRemainingPairsForTestPosition();
 523
 524     private:
 525         ImplPointer             impl_;
 526 };
 527
 528 } // namespace gmx
 529
 530 #endif