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