IMP logo
IMP Reference Guide  develop.b99932598c,2021/06/14
The Integrative Modeling Platform
core/Hierarchy.h
Go to the documentation of this file.
1 /**
2  * \file IMP/core/Hierarchy.h \brief Decorator for helping deal with
3  * a hierarchy.
4  *
5  * Copyright 2007-2021 IMP Inventors. All rights reserved.
6  *
7  */
8 
9 #ifndef IMPCORE_HIERARCHY_H
10 #define IMPCORE_HIERARCHY_H
11 
12 #include <IMP/core/core_config.h>
13 #include "internal/hierarchy_helpers.h"
14 
15 #include <IMP/SingletonModifier.h>
16 #include <IMP/Particle.h>
17 #include <IMP/Model.h>
18 #include <IMP/Decorator.h>
19 #include <IMP/decorator_macros.h>
20 #include <IMP/internal/utility.h>
21 #include <IMP/Pointer.h>
22 
23 #include <boost/tuple/tuple.hpp>
24 
25 #include <limits>
26 #include <vector>
27 #include <deque>
28 
29 IMPCORE_BEGIN_NAMESPACE
30 
31 /** \defgroup hierarchy Hierarchies of particles
32  \brief Manipulate particles representing molecules at multiple levels.
33  */
34 #ifndef SWIG
35 class Hierarchy;
36 #endif
37 
38 //! Define the type for a type of hierarchy
39 /** The hierarchy class is identified by the passed string so two
40  hierarchies created with the same initialization string will be
41  the same.
42 
43  This example shows how to make and use a custom hierarchy:
44  \include custom_hierarchy.py
45  \see Hierarchy
46 */
47 class IMPCOREEXPORT HierarchyTraits {
48  ParticleIndexesKey children_;
49  ParticleIndexKey parent_;
50 
51  public:
52  HierarchyTraits() {}
53  //! Create a HierarchyTraits with the given name
54  HierarchyTraits(std::string name);
55  ParticleIndexesKey get_children_key() const { return children_; }
56  ParticleIndexKey get_parent_key() const { return parent_; }
57  bool operator==(const HierarchyTraits &o) const {
58  return parent_ == o.parent_;
59  }
60  IMP_SHOWABLE_INLINE(HierarchyTraits, out << parent_);
61 };
62 
64 
65 class Hierarchy;
66 
67 #ifndef IMP_DOXYGEN
68 typedef IMP::Vector<Hierarchy> GenericHierarchies;
69 #endif
70 
71 //! A decorator for helping deal with a generalized hierarchy.
72 /**
73  See HierarchyTraits for an example of how to define a custom hierarchy
74  and IMP::atom::Hierarchy for a hierarchy for molecules.
75  \ingroup hierarchy
76  \see HierarchyTraits
77  */
78 class IMPCOREEXPORT Hierarchy : public Decorator {
79  static void do_setup_particle(Model *, ParticleIndex,
80  HierarchyTraits) {}
81  static void do_setup_particle(Model *m, ParticleIndex pi,
82  const ParticleIndexes &children,
83  HierarchyTraits traits) {
84  for (unsigned int i = 0; i < children.size(); ++i) {
85  m->add_attribute(traits.get_parent_key(), children[i], pi);
86  }
87  m->add_attribute(traits.get_children_key(), pi, children);
88  }
89  static void do_setup_particle(Model *m, ParticleIndex pi,
90  const ParticlesTemp &children,
91  HierarchyTraits traits) {
92  do_setup_particle(m, pi, get_indexes(children), traits);
93  }
94 
95  public:
97  traits, get_default_traits());
99  /** Setup the particle and add children. */
102 
103  /** Check if the particle has the needed attributes for a
104  cast to succeed */
106  HierarchyTraits = Hierarchy::get_default_traits()) {
107  return true;
108  }
109  /** \return the parent particle, or Hierarchy()
110  if it has no parent.
111  */
113  if (get_model()->get_has_attribute(get_decorator_traits().get_parent_key(),
114  get_particle_index())) {
116  get_decorator_traits().get_parent_key(), get_particle_index());
117  return Hierarchy(get_model(), VALUE, get_decorator_traits());
118  } else {
119  return Hierarchy();
120  }
121  }
122 
123  unsigned int get_number_of_children() const {
124  if (get_model()->get_has_attribute(
125  get_decorator_traits().get_children_key(), get_particle_index())) {
126  return get_model()
127  ->get_attribute(get_decorator_traits().get_children_key(),
129  .size();
130  } else {
131  return 0;
132  }
133  }
134  Hierarchy get_child(unsigned int i) const {
135  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
136  return Hierarchy(get_model(), get_model()->get_attribute(
137  get_decorator_traits().get_children_key(),
138  get_particle_index())[i],
139  get_decorator_traits());
140  }
141  ParticleIndex get_child_index(unsigned int i) const {
142  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
143  return get_model()->get_attribute(get_decorator_traits().get_children_key(),
144  get_particle_index())[i];
145  }
146  ParticleIndexes get_children_indexes() const {
147  if (get_model()->get_has_attribute(
148  get_decorator_traits().get_children_key(), get_particle_index())) {
149  return get_model()->get_attribute(
150  get_decorator_traits().get_children_key(), get_particle_index());
151  } else {
152  return ParticleIndexes();
153  }
154  }
155  GenericHierarchies get_children() const {
156  GenericHierarchies ret(get_number_of_children());
157  for (unsigned int i = 0; i < ret.size(); ++i) {
158  ret[i] = get_child(i);
159  }
160  return ret;
161  }
162  void remove_child(unsigned int i) {
163  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
164  Hierarchy c = get_child(i);
165  ParticleIndexes &pis = get_model()->access_attribute(
166  get_decorator_traits().get_children_key(), get_particle_index());
167  pis.erase(pis.begin() + i);
168  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
169  c.get_particle_index());
170  }
171  void remove_child(Hierarchy h) { remove_child(h.get_child_index()); }
172  void clear_children() {
173  ParticleIndexes &pis = get_model()->access_attribute(
174  get_decorator_traits().get_children_key(), get_particle_index());
175  for (unsigned int i = 0; i < pis.size(); ++i) {
176  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
177  pis[i]);
178  }
179  get_model()->remove_attribute(get_decorator_traits().get_children_key(),
181  }
182  void add_child(Hierarchy h) const {
183  if (get_model()->get_has_attribute(
184  get_decorator_traits().get_children_key(), get_particle_index())) {
185  get_model()
186  ->access_attribute(get_decorator_traits().get_children_key(),
188  .push_back(h.get_particle_index());
189  } else {
191  get_decorator_traits().get_children_key(), get_particle_index(),
192  ParticleIndexes(1, h.get_particle_index()));
193  }
194  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
195  h.get_particle_index(), get_particle_index());
196  }
197  void add_child_at(Hierarchy h, unsigned int pos) {
198  IMP_USAGE_CHECK(get_number_of_children() >= pos, "Invalid position");
199  if (get_model()->get_has_attribute(
200  get_decorator_traits().get_children_key(), get_particle_index())) {
201  ParticleIndexes &pis = get_model()->access_attribute(
202  get_decorator_traits().get_children_key(), get_particle_index());
203  pis.insert(pis.begin() + pos, h.get_particle_index());
204  } else {
206  get_decorator_traits().get_children_key(), get_particle_index(),
207  ParticleIndexes(1, h.get_particle_index()));
208  }
209  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
210  h.get_particle_index(), get_particle_index());
211  }
212  //! Return i such that `get_parent().get_child(i) == this`
213  int get_child_index() const;
214  //! Get the default hierarchy traits
215  static const HierarchyTraits &get_default_traits();
216 
217  HierarchyTraits get_traits() { return get_decorator_traits(); }
218 };
219 
220 //! A visitor for traversal of a hierarchy
221 /** This works from both C++ and Python
222  \ingroup hierarchy
223  \ingroup decorators
224  \see Hierarchy
225  */
226 class IMPCOREEXPORT HierarchyVisitor {
227  public:
228  HierarchyVisitor() {}
229  //! Return true if the traversal should visit this node's children
230  virtual bool operator()(Hierarchy p) = 0;
231  virtual ~HierarchyVisitor() {}
232 };
233 
234 //! A visitor which applies a modifier to each Particle in a hierarchy
235 /** This works from both C++ and Python
236  \ingroup hierarchy
237  \ingroup decorators
238  \see SingletonModifier
239  \see Hierarchy
240  */
241 class IMPCOREEXPORT ModifierVisitor : public HierarchyVisitor {
243 
244  public:
245  ModifierVisitor(SingletonModifier *sm) : sm_(sm) {}
246  virtual bool operator()(Hierarchy p) {
247  sm_->apply_index(p.get_model(), p.get_particle_index());
248  return true;
249  }
250  virtual ~ModifierVisitor() {}
251 };
252 
253 #if !defined(SWIG) && !defined(IMP_DOXYGEN)
254 namespace internal {
255 template <class H, class F, class Out, bool Slice = false>
256 struct Gather {
257  //! initialize with the function and the container
258  Gather(F f, Out out) : f_(f), out_(out) {}
259  bool operator()(H p) {
260  if (f_(p)) {
261  *out_ = p;
262  ++out_;
263  if (Slice) return false;
264  }
265  return true;
266  }
267  //! Return the container
268  Out get_out() const { return out_; }
269 
270  private:
271  F f_;
272  Out out_;
273 };
274 }
275 #endif
276 
277 //! Apply the visitor to each particle, breadth first.
278 /** \param[in] d The Hierarchy for the tree in question
279  \param[in] f The visitor to be applied. This is passed by reference.
280  A branch of the traversal stops when f returns false.
281  \ingroup hierarchy
282  \see Hierarchy
283  */
284 template <class HD, class F>
285 inline F visit_breadth_first(HD d, F f) {
286  std::deque<HD> stack;
287  stack.push_back(d);
288  // d.show(std::cerr);
289  do {
290  HD cur = stack.front();
291  stack.pop_front();
292  if (f(cur)) {
293  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
294  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
295  stack.push_back(cur.get_child(i));
296  }
297  }
298  } while (!stack.empty());
299  return f;
300 }
301 
302 //! Apply functor F to each particle, traversing the hierarchy depth first.
303 /** See visit_breadth_first() for documentation.
304  \ingroup hierarchy
305  \see Hierarchy
306  */
307 template <class HD, class F>
308 inline F visit_depth_first(HD d, F &f) {
309  Vector<HD> stack;
310  stack.push_back(d);
311  // d.show(std::cerr);
312  do {
313  HD cur = stack.back();
314  stack.pop_back();
315  if (f(cur)) {
316  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
317  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
318  stack.push_back(cur.get_child(i));
319  }
320  }
321  } while (!stack.empty());
322  return f;
323 }
324 
325 //! Apply functor F to each particle, traversing the hierarchy breadth first.
326 /** This method allows data to be associated with each visited node.
327  The data of the parent is passed to each invocation of the child.
328 
329  \param[in] d The Hierarchy for the tree in question
330  \param[in] f The functor to be applied
331  F must define a type Data which is returned by each call.
332  The result of the parent call is passed as the second argument
333  to the operator() of the child. e.g.
334  struct DepthVisitor {
335  typedef int result_type;
336  result_type operator()(Particle *p, int i) const
337  {
338  if (p==nullptr) return 0;
339  else return i+1;
340  }
341  };
342  \param[in] data The data to be used for d (since it has no relevant parent)
343 
344  \return A copy of the functor passed in. Use this if you care about
345  the functor state.
346 
347  \ingroup hierarchy
348  \see Hierarchy
349  */
350 template <class HD, class F>
351 inline F visit_breadth_first_with_data(HD d, F f,
352  typename F::result_type data) {
353  typedef std::pair<typename F::result_type, HD> DP;
354  std::deque<DP> stack;
355  stack.push_back(DP(data, d));
356  // d.show(std::cerr);
357  do {
358  DP cur = stack.front();
359  stack.pop_front();
360  typename F::result_type r = f(cur.second.get_particle(), cur.first);
361  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
362  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
363  stack.push_back(std::make_pair(r, cur.second.get_child(i)));
364  }
365  } while (!stack.empty());
366  return f;
367 }
368 
369 //! Apply functor F to each particle, traversing the hierarchy depth first.
370 /** See visit_breadth_first() for documentation.
371  \ingroup hierarchy
372  \see Hierarchy
373  */
374 template <class HD, class F>
375 inline F visit_depth_first_with_data(HD d, F f, typename F::result_type data) {
376  typedef std::pair<typename F::result_type, HD> DP;
377  Vector<DP> stack;
378  stack.push_back(DP(data, d));
379  // d.show(std::cerr);
380  do {
381  DP cur = stack.back();
382  stack.pop_back();
383  typename F::result_type r = f(cur.second, cur.first);
384  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
385  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
386  stack.push_back(DP(r, cur.second.get_child(i)));
387  }
388  } while (!stack.empty());
389  return f;
390 }
391 
392 //! Print the hierarchy using a given decorator to display each node
393 /** \ingroup hierarchy
394  \see Hierarchy
395  */
396 template <class ND>
397 inline std::ostream &show(Hierarchy h, std::ostream &out = std::cout) {
398  IMP_PRINT_TREE(out, Hierarchy, h, n.get_number_of_children(), n.get_child,
399  ND(n).show(out));
400  return out;
401 }
402 
403 //! A simple functor to count the number of particles in a hierarchy.
404 /** This is a good example of a simple HierarchyVisitor.
405  \ingroup hierarchy
406  \see Hierarchy
407  */
409  HierarchyCounter() : ct_(0) {}
410 
411  //! Increment the counter
413  ++ct_;
414  return true;
415  }
416  //! Return how many nodes have been visited
417  unsigned int get_count() const { return ct_; }
418  IMP_SHOWABLE_INLINE(HierarchyCounter, out << get_count());
419 
420  private:
421  unsigned int ct_;
422 };
423 
425 
426 //! Gather all the particles in the hierarchy that meet some criteria
427 /** Gather all the particles in the hierarchy for which f() returns true
428  and appends them to out
429 
430  @param h hierarchy root
431  @param f boolean function / functor that returns true
432  on desired particles
433  @param out a output iterator for appending the result
434 
435  @return the output iterator
436 
437  \ingroup hierarchy
438  \see Hierarchy
439  */
440 template <class H, class Out, class F>
441 inline Out gather(H h, F f, Out out) {
442  internal::Gather<H, F, Out> gather(f, out);
443  visit_depth_first(h, gather);
444  return gather.get_out();
445 }
446 
447 //! Gather all the uppermost particles in the hierarchy that meet some criteria
448 /** Descent in the tree terminates when a node is gathered so that
449  none of its children are explored.
450 
451  \ingroup hierarchy
452  \see Hierarchy
453  */
454 template <class H, class Out, class F>
455 inline Out gather_slice(H h, F f, Out out) {
456  internal::Gather<H, F, Out, true> gather(f, out);
457  visit_depth_first(h, gather);
458  return gather.get_out();
459 }
460 
461 //! Gather all the particles in the hierarchy which match on an attribute
462 /** \ingroup hierarchy
463  \see Hierarchy
464  */
465 template <class H, class Out, class K, class V>
466 inline Out gather_by_attribute(H h, K k, V v, Out out) {
467  internal::Gather<H, internal::MatchAttribute<K, V>, Out> gather(
468  internal::MatchAttribute<K, V>(k, v), out);
469  visit_depth_first(h, gather);
470  return gather.get_out();
471 }
472 
473 //! Gather all the particles in the hierarchy which match on two attributes
474 /** \ingroup hierarchy
475  \see Hierarchy
476  */
477 template <class H, class Out, class K0, class V0, class K1, class V1>
478 inline Out gather_by_attributes(H h, K0 k0, V0 v0, K1 k1, V1 v1, Out out) {
479  internal::Gather<H, internal::MatchAttributes<K0, V0, K1, V1>, Out> gather(
480  internal::MatchAttributes<K0, V0, K1, V1>(k0, v0, k1, v1), out);
481  visit_depth_first(h, gather);
482  return gather.get_out();
483 }
484 
485 //! Find the first node which matches some criteria
486 /** \ingroup hierarchy
487  \see Hierarchy
488  */
489 template <class HD, class F>
490 inline HD find_breadth_first(HD h, F f) {
491  if (f(h.get_particle())) return h;
492  Vector<HD> stack;
493  stack.push_back(h);
494  // d.show(std::cerr);
495  do {
496  HD cur = stack.back();
497  stack.pop_back();
498 
499  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
500  HD hd = cur.get_child(i);
501  if (f(hd.get_particle())) {
502  return hd;
503  } else {
504  stack.push_back(hd);
505  }
506  }
507  } while (!stack.empty());
508  return HD();
509 }
510 
511 //! Get all the leaves of the bit of hierarchy
512 /** The leaves are returned in the obvious order
513  (first child before second child).
514 
515  \see Hierarchy
516  */
517 IMPCOREEXPORT GenericHierarchies get_leaves(Hierarchy mhd);
518 
519 //! Get all the non-leaves of the bit of hierarchy
520 /** \see Hierarchy
521  */
522 IMPCOREEXPORT GenericHierarchies get_internal(Hierarchy mhd);
523 
524 //! Get all the particles in the subtree
525 /** \see Hierarchy
526  */
527 IMPCOREEXPORT GenericHierarchies get_all_descendants(Hierarchy mhd);
528 
529 //! Return the root of the hierarchy
530 /** \see Hierarchy */
532  while (h.get_parent()) {
533  h = h.get_parent();
534  }
535  return h;
536 }
537 
538 IMPCORE_END_NAMESPACE
539 
540 #endif /* IMPCORE_HIERARCHY_H */
F visit_breadth_first(HD d, F f)
Apply the visitor to each particle, breadth first.
The base class for decorators.
A base class for modifiers of ParticlesTemp.
A visitor for traversal of a hierarchy.
A Modifier on ParticlesTemp.
ParticleIndex get_particle_index() const
Returns the particle index decorated by this decorator.
Definition: Decorator.h:188
#define IMP_SHOWABLE_INLINE(Name, how_to_show)
Declare the methods needed by an object that can be printed.
static bool get_is_setup(Model *, ParticleIndex, HierarchyTraits=Hierarchy::get_default_traits())
F visit_depth_first(HD d, F &f)
Apply functor F to each particle, traversing the hierarchy depth first.
Model * get_model() const
Returns the Model containing the particle.
Definition: Decorator.h:191
Storage of a model, its restraints, constraints and particles.
HD find_breadth_first(HD h, F f)
Find the first node which matches some criteria.
void remove_attribute(TypeKey attribute_key, ParticleIndex particle)
remove particle attribute with the specied key
Index< ParticleIndexTag > ParticleIndex
Definition: base_types.h:158
#define IMP_DECORATOR_TRAITS_SETUP_1(Name, FirstArgumentType,first_argument_name)
A more IMP-like version of the std::vector.
Definition: Vector.h:40
GenericHierarchies get_all_descendants(Hierarchy mhd)
Get all the particles in the subtree.
A visitor which applies a modifier to each Particle in a hierarchy.
Class for storing model, its restraints, constraints, and particles.
Definition: Model.h:72
Out gather_by_attributes(H h, K0 k0, V0 v0, K1 k1, V1 v1, Out out)
Gather all the particles in the hierarchy which match on two attributes.
#define IMP_VALUES(Name, PluralName)
Define the type for storing sets of values.
Definition: value_macros.h:23
F visit_depth_first_with_data(HD d, F f, typename F::result_type data)
Apply functor F to each particle, traversing the hierarchy depth first.
Hierarchy get_root(Hierarchy h)
Return the root of the hierarchy.
Hierarchy get_parent() const
void add_attribute(TypeKey attribute_key, ParticleIndex particle, Type value)
add particle atribute with the specied key and initial value
F visit_breadth_first_with_data(HD d, F f, typename F::result_type data)
Apply functor F to each particle, traversing the hierarchy breadth first.
Out gather_slice(H h, F f, Out out)
Gather all the uppermost particles in the hierarchy that meet some criteria.
A simple functor to count the number of particles in a hierarchy.
Define the type for a type of hierarchy.
Helper macros for implementing Decorators.
A smart pointer to a ref-counted Object that is a class member.
Definition: Pointer.h:146
#define IMP_DECORATOR_TRAITS_SETUP_0(Name)
bool operator()(Hierarchy)
Increment the counter.
Out gather(H h, F f, Out out)
Gather all the particles in the hierarchy that meet some criteria.
Out gather_by_attribute(H h, K k, V v, Out out)
Gather all the particles in the hierarchy which match on an attribute.
GenericHierarchies get_internal(Hierarchy mhd)
Get all the non-leaves of the bit of hierarchy.
Interface to specialized Particle types (e.g. atoms)
Definition: Decorator.h:118
Classes to handle individual model particles. (Note that implementation of inline functions is in int...
#define IMP_DECORATOR_WITH_TRAITS_METHODS(Name, Parent, TraitsType,traits_name, default_traits)
void show(Hierarchy h, std::ostream &out=std::cout)
Print out a molecular hierarchy.
A nullptr-initialized pointer to an IMP Object.
unsigned int get_count() const
Return how many nodes have been visited.
#define IMP_USAGE_CHECK(expr, message)
A runtime test for incorrect usage of a class or method.
Definition: check_macros.h:168
A decorator for helping deal with a generalized hierarchy.
Hierarchies get_leaves(Hierarchy h)
Type get_attribute(TypeKey attribute_key, ParticleIndex particle)
get the value of the particle attribute with the specified key
ParticleIndexes get_indexes(const ParticlesTemp &ps)
Get the indexes from a list of particles.
virtual bool operator()(Hierarchy p)
Return true if the traversal should visit this node's children.