IMP logo
IMP Reference Guide  develop.1a04b19ae7,2021/11/27
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  //! Signal to the Model that this Hierarchy has changed
96  void update_changed_trigger() const {
97  get_model()->set_trigger_updated(get_changed_key());
98  }
99 
100  public:
102  traits, get_default_traits());
104  /** Setup the particle and add children. */
107 
108  /** Check if the particle has the needed attributes for a
109  cast to succeed */
111  HierarchyTraits = Hierarchy::get_default_traits()) {
112  return true;
113  }
114 
115  //! The key used to signal to the Model that the Hierarchy has changed
116  static TriggerKey get_changed_key();
117 
118  /** \return the parent particle, or Hierarchy()
119  if it has no parent.
120  */
122  if (get_model()->get_has_attribute(get_decorator_traits().get_parent_key(),
123  get_particle_index())) {
125  get_decorator_traits().get_parent_key(), get_particle_index());
126  return Hierarchy(get_model(), VALUE, get_decorator_traits());
127  } else {
128  return Hierarchy();
129  }
130  }
131 
132  unsigned int get_number_of_children() const {
133  if (get_model()->get_has_attribute(
134  get_decorator_traits().get_children_key(), get_particle_index())) {
135  return get_model()
136  ->get_attribute(get_decorator_traits().get_children_key(),
138  .size();
139  } else {
140  return 0;
141  }
142  }
143  Hierarchy get_child(unsigned int i) const {
144  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
145  return Hierarchy(get_model(), get_model()->get_attribute(
146  get_decorator_traits().get_children_key(),
147  get_particle_index())[i],
148  get_decorator_traits());
149  }
150  ParticleIndex get_child_index(unsigned int i) const {
151  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
152  return get_model()->get_attribute(get_decorator_traits().get_children_key(),
153  get_particle_index())[i];
154  }
155  ParticleIndexes get_children_indexes() const {
156  if (get_model()->get_has_attribute(
157  get_decorator_traits().get_children_key(), get_particle_index())) {
158  return get_model()->get_attribute(
159  get_decorator_traits().get_children_key(), get_particle_index());
160  } else {
161  return ParticleIndexes();
162  }
163  }
164  GenericHierarchies get_children() const {
165  GenericHierarchies ret(get_number_of_children());
166  for (unsigned int i = 0; i < ret.size(); ++i) {
167  ret[i] = get_child(i);
168  }
169  return ret;
170  }
171  void remove_child(unsigned int i) {
172  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
173  Hierarchy c = get_child(i);
174  ParticleIndexes &pis = get_model()->access_attribute(
175  get_decorator_traits().get_children_key(), get_particle_index());
176  pis.erase(pis.begin() + i);
177  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
178  c.get_particle_index());
179  update_changed_trigger();
180  }
181  void remove_child(Hierarchy h) { remove_child(h.get_child_index()); }
182  void clear_children() {
183  ParticleIndexes &pis = get_model()->access_attribute(
184  get_decorator_traits().get_children_key(), get_particle_index());
185  for (unsigned int i = 0; i < pis.size(); ++i) {
186  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
187  pis[i]);
188  }
189  get_model()->remove_attribute(get_decorator_traits().get_children_key(),
191  update_changed_trigger();
192  }
193  void add_child(Hierarchy h) const {
194  if (get_model()->get_has_attribute(
195  get_decorator_traits().get_children_key(), get_particle_index())) {
196  get_model()
197  ->access_attribute(get_decorator_traits().get_children_key(),
199  .push_back(h.get_particle_index());
200  } else {
202  get_decorator_traits().get_children_key(), get_particle_index(),
203  ParticleIndexes(1, h.get_particle_index()));
204  }
205  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
206  h.get_particle_index(), get_particle_index());
207  update_changed_trigger();
208  }
209  void add_child_at(Hierarchy h, unsigned int pos) {
210  IMP_USAGE_CHECK(get_number_of_children() >= pos, "Invalid position");
211  if (get_model()->get_has_attribute(
212  get_decorator_traits().get_children_key(), get_particle_index())) {
213  ParticleIndexes &pis = get_model()->access_attribute(
214  get_decorator_traits().get_children_key(), get_particle_index());
215  pis.insert(pis.begin() + pos, h.get_particle_index());
216  } else {
218  get_decorator_traits().get_children_key(), get_particle_index(),
219  ParticleIndexes(1, h.get_particle_index()));
220  }
221  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
222  h.get_particle_index(), get_particle_index());
223  update_changed_trigger();
224  }
225  //! Return i such that `get_parent().get_child(i) == this`
226  int get_child_index() const;
227  //! Get the default hierarchy traits
228  static const HierarchyTraits &get_default_traits();
229 
230  HierarchyTraits get_traits() { return get_decorator_traits(); }
231 };
232 
233 //! A visitor for traversal of a hierarchy
234 /** This works from both C++ and Python
235  \ingroup hierarchy
236  \ingroup decorators
237  \see Hierarchy
238  */
239 class IMPCOREEXPORT HierarchyVisitor {
240  public:
241  HierarchyVisitor() {}
242  //! Return true if the traversal should visit this node's children
243  virtual bool operator()(Hierarchy p) = 0;
244  virtual ~HierarchyVisitor() {}
245 };
246 
247 //! A visitor which applies a modifier to each Particle in a hierarchy
248 /** This works from both C++ and Python
249  \ingroup hierarchy
250  \ingroup decorators
251  \see SingletonModifier
252  \see Hierarchy
253  */
254 class IMPCOREEXPORT ModifierVisitor : public HierarchyVisitor {
256 
257  public:
258  ModifierVisitor(SingletonModifier *sm) : sm_(sm) {}
260  sm_->apply_index(p.get_model(), p.get_particle_index());
261  return true;
262  }
263  virtual ~ModifierVisitor() {}
264 };
265 
266 #if !defined(SWIG) && !defined(IMP_DOXYGEN)
267 namespace internal {
268 template <class H, class F, class Out, bool Slice = false>
269 struct Gather {
270  //! initialize with the function and the container
271  Gather(F f, Out out) : f_(f), out_(out) {}
272  bool operator()(H p) {
273  if (f_(p)) {
274  *out_ = p;
275  ++out_;
276  if (Slice) return false;
277  }
278  return true;
279  }
280  //! Return the container
281  Out get_out() const { return out_; }
282 
283  private:
284  F f_;
285  Out out_;
286 };
287 }
288 #endif
289 
290 //! Apply the visitor to each particle, breadth first.
291 /** \param[in] d The Hierarchy for the tree in question
292  \param[in] f The visitor to be applied. This is passed by reference.
293  A branch of the traversal stops when f returns false.
294  \ingroup hierarchy
295  \see Hierarchy
296  */
297 template <class HD, class F>
298 inline F visit_breadth_first(HD d, F f) {
299  std::deque<HD> stack;
300  stack.push_back(d);
301  // d.show(std::cerr);
302  do {
303  HD cur = stack.front();
304  stack.pop_front();
305  if (f(cur)) {
306  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
307  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
308  stack.push_back(cur.get_child(i));
309  }
310  }
311  } while (!stack.empty());
312  return f;
313 }
314 
315 //! Apply functor F to each particle, traversing the hierarchy depth first.
316 /** See visit_breadth_first() for documentation.
317  \ingroup hierarchy
318  \see Hierarchy
319  */
320 template <class HD, class F>
321 inline F visit_depth_first(HD d, F &f) {
322  Vector<HD> stack;
323  stack.push_back(d);
324  // d.show(std::cerr);
325  do {
326  HD cur = stack.back();
327  stack.pop_back();
328  if (f(cur)) {
329  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
330  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
331  stack.push_back(cur.get_child(i));
332  }
333  }
334  } while (!stack.empty());
335  return f;
336 }
337 
338 //! Apply functor F to each particle, traversing the hierarchy breadth first.
339 /** This method allows data to be associated with each visited node.
340  The data of the parent is passed to each invocation of the child.
341 
342  \param[in] d The Hierarchy for the tree in question
343  \param[in] f The functor to be applied
344  F must define a type Data which is returned by each call.
345  The result of the parent call is passed as the second argument
346  to the operator() of the child. e.g.
347  struct DepthVisitor {
348  typedef int result_type;
349  result_type operator()(Particle *p, int i) const
350  {
351  if (p==nullptr) return 0;
352  else return i+1;
353  }
354  };
355  \param[in] data The data to be used for d (since it has no relevant parent)
356 
357  \return A copy of the functor passed in. Use this if you care about
358  the functor state.
359 
360  \ingroup hierarchy
361  \see Hierarchy
362  */
363 template <class HD, class F>
364 inline F visit_breadth_first_with_data(HD d, F f,
365  typename F::result_type data) {
366  typedef std::pair<typename F::result_type, HD> DP;
367  std::deque<DP> stack;
368  stack.push_back(DP(data, d));
369  // d.show(std::cerr);
370  do {
371  DP cur = stack.front();
372  stack.pop_front();
373  typename F::result_type r = f(cur.second.get_particle(), cur.first);
374  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
375  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
376  stack.push_back(std::make_pair(r, cur.second.get_child(i)));
377  }
378  } while (!stack.empty());
379  return f;
380 }
381 
382 //! Apply functor F to each particle, traversing the hierarchy depth first.
383 /** See visit_breadth_first() for documentation.
384  \ingroup hierarchy
385  \see Hierarchy
386  */
387 template <class HD, class F>
388 inline F visit_depth_first_with_data(HD d, F f, typename F::result_type data) {
389  typedef std::pair<typename F::result_type, HD> DP;
390  Vector<DP> stack;
391  stack.push_back(DP(data, d));
392  // d.show(std::cerr);
393  do {
394  DP cur = stack.back();
395  stack.pop_back();
396  typename F::result_type r = f(cur.second, cur.first);
397  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
398  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
399  stack.push_back(DP(r, cur.second.get_child(i)));
400  }
401  } while (!stack.empty());
402  return f;
403 }
404 
405 //! Print the hierarchy using a given decorator to display each node
406 /** \ingroup hierarchy
407  \see Hierarchy
408  */
409 template <class ND>
410 inline std::ostream &show(Hierarchy h, std::ostream &out = std::cout) {
411  IMP_PRINT_TREE(out, Hierarchy, h, n.get_number_of_children(), n.get_child,
412  ND(n).show(out));
413  return out;
414 }
415 
416 //! A simple functor to count the number of particles in a hierarchy.
417 /** This is a good example of a simple HierarchyVisitor.
418  \ingroup hierarchy
419  \see Hierarchy
420  */
422  HierarchyCounter() : ct_(0) {}
423 
424  //! Increment the counter
426  ++ct_;
427  return true;
428  }
429  //! Return how many nodes have been visited
430  unsigned int get_count() const { return ct_; }
431  IMP_SHOWABLE_INLINE(HierarchyCounter, out << get_count());
432 
433  private:
434  unsigned int ct_;
435 };
436 
438 
439 //! Gather all the particles in the hierarchy that meet some criteria
440 /** Gather all the particles in the hierarchy for which f() returns true
441  and appends them to out
442 
443  @param h hierarchy root
444  @param f boolean function / functor that returns true
445  on desired particles
446  @param out a output iterator for appending the result
447 
448  @return the output iterator
449 
450  \ingroup hierarchy
451  \see Hierarchy
452  */
453 template <class H, class Out, class F>
454 inline Out gather(H h, F f, Out out) {
455  internal::Gather<H, F, Out> gather(f, out);
456  visit_depth_first(h, gather);
457  return gather.get_out();
458 }
459 
460 //! Gather all the uppermost particles in the hierarchy that meet some criteria
461 /** Descent in the tree terminates when a node is gathered so that
462  none of its children are explored.
463 
464  \ingroup hierarchy
465  \see Hierarchy
466  */
467 template <class H, class Out, class F>
468 inline Out gather_slice(H h, F f, Out out) {
469  internal::Gather<H, F, Out, true> gather(f, out);
470  visit_depth_first(h, gather);
471  return gather.get_out();
472 }
473 
474 //! Gather all the particles in the hierarchy which match on an attribute
475 /** \ingroup hierarchy
476  \see Hierarchy
477  */
478 template <class H, class Out, class K, class V>
479 inline Out gather_by_attribute(H h, K k, V v, Out out) {
480  internal::Gather<H, internal::MatchAttribute<K, V>, Out> gather(
481  internal::MatchAttribute<K, V>(k, v), out);
482  visit_depth_first(h, gather);
483  return gather.get_out();
484 }
485 
486 //! Gather all the particles in the hierarchy which match on two attributes
487 /** \ingroup hierarchy
488  \see Hierarchy
489  */
490 template <class H, class Out, class K0, class V0, class K1, class V1>
491 inline Out gather_by_attributes(H h, K0 k0, V0 v0, K1 k1, V1 v1, Out out) {
492  internal::Gather<H, internal::MatchAttributes<K0, V0, K1, V1>, Out> gather(
493  internal::MatchAttributes<K0, V0, K1, V1>(k0, v0, k1, v1), out);
494  visit_depth_first(h, gather);
495  return gather.get_out();
496 }
497 
498 //! Find the first node which matches some criteria
499 /** \ingroup hierarchy
500  \see Hierarchy
501  */
502 template <class HD, class F>
503 inline HD find_breadth_first(HD h, F f) {
504  if (f(h.get_particle())) return h;
505  Vector<HD> stack;
506  stack.push_back(h);
507  // d.show(std::cerr);
508  do {
509  HD cur = stack.back();
510  stack.pop_back();
511 
512  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
513  HD hd = cur.get_child(i);
514  if (f(hd.get_particle())) {
515  return hd;
516  } else {
517  stack.push_back(hd);
518  }
519  }
520  } while (!stack.empty());
521  return HD();
522 }
523 
524 //! Get all the leaves of the bit of hierarchy
525 /** The leaves are returned in the obvious order
526  (first child before second child).
527 
528  \see Hierarchy
529  */
530 IMPCOREEXPORT GenericHierarchies get_leaves(Hierarchy mhd);
531 
532 //! Get all the non-leaves of the bit of hierarchy
533 /** \see Hierarchy
534  */
535 IMPCOREEXPORT GenericHierarchies get_internal(Hierarchy mhd);
536 
537 //! Get all the particles in the subtree
538 /** \see Hierarchy
539  */
540 IMPCOREEXPORT GenericHierarchies get_all_descendants(Hierarchy mhd);
541 
542 //! Return the root of the hierarchy
543 /** \see Hierarchy */
545  while (h.get_parent()) {
546  h = h.get_parent();
547  }
548  return h;
549 }
550 
551 IMPCORE_END_NAMESPACE
552 
553 #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:161
#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:73
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.
void set_trigger_updated(TriggerKey tk)
Update the given trigger.
Definition: Model.h:411
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.
#define IMP_OVERRIDE
Cause a compile error if this method does not override a parent method.