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