IMP  2.3.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-2014 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/kernel/Particle.h>
17 #include <IMP/kernel/Model.h>
18 #include <IMP/Decorator.h>
19 #include <IMP/decorator_macros.h>
20 #include <IMP/kernel/internal/utility.h>
21 #include <IMP/base/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 {
50 
51  public:
52  HierarchyTraits() {}
53  //! Create a HierarchyTraits with the given name
54  HierarchyTraits(std::string name);
55  kernel::ParticleIndexesKey get_children_key() const { return children_; }
56  kernel::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::base::Vector<Hierarchy> GenericHierarchies;
69 #endif
70 
71 //! A decorator for helping deal with a hierarchy.
72 /**
73  See HierarchyTraits for an example of how to define a custom hierarchy
74  and 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(kernel::Model *, kernel::ParticleIndex,
80  HierarchyTraits) {}
81  static void do_setup_particle(kernel::Model *m, kernel::ParticleIndex pi,
82  const kernel::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(kernel::Model *m, kernel::ParticleIndex pi,
90  const kernel::ParticlesTemp &children,
91  HierarchyTraits traits) {
92  do_setup_particle(m, pi, kernel::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  kernel::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  kernel::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 kernel::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  kernel::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  kernel::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  kernel::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  kernel::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  kernel::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 kernel::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  base::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()(kernel::Particle *p, int i) const
337  {
338  if (p==nullptr) return 0;
339  else return i+1;
340  }
341  };
342  \param[in] i 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, typename F::result_type i) {
352  typedef std::pair<typename F::result_type, HD> DP;
353  std::deque<DP> stack;
354  stack.push_back(DP(i, d));
355  // d.show(std::cerr);
356  do {
357  DP cur = stack.front();
358  stack.pop_front();
359  typename F::result_type r = f(cur.second.get_particle(), cur.first);
360  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
361  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
362  stack.push_back(std::make_pair(r, cur.second.get_child(i)));
363  }
364  } while (!stack.empty());
365  return f;
366 }
367 
368 //! Apply functor F to each particle, traversing the hierarchy depth first.
369 /** See visit_breadth_first() for documentation.
370  \ingroup hierarchy
371  \see Hierarchy
372  */
373 template <class HD, class F>
374 inline F visit_depth_first_with_data(HD d, F f, typename F::result_type i) {
375  typedef std::pair<typename F::result_type, HD> DP;
376  base::Vector<DP> stack;
377  stack.push_back(DP(i, d));
378  // d.show(std::cerr);
379  do {
380  DP cur = stack.back();
381  stack.pop_back();
382  typename F::result_type r = f(cur.second, cur.first);
383  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
384  for (int i = cur.second.get_number_of_children() - 1; i >= 0; --i) {
385  stack.push_back(DP(r, cur.second.get_child(i)));
386  }
387  } while (!stack.empty());
388  return f;
389 }
390 
391 //! Print the hierarchy using a given decorator to display each node
392 /** \ingroup hierarchy
393  \see Hierarchy
394  */
395 template <class ND>
396 inline std::ostream &show(Hierarchy h, std::ostream &out = std::cout) {
397  IMP_PRINT_TREE(out, Hierarchy, h, n.get_number_of_children(), n.get_child,
398  ND(n).show(out));
399  return out;
400 }
401 
402 //! A simple functor to count the number of particles in a hierarchy.
403 /** This is a good example of a simple HierarchyVisitor.
404  \ingroup hierarchy
405  \see Hierarchy
406  */
408  HierarchyCounter() : ct_(0) {}
409 
410  //! Increment the counter
412  ++ct_;
413  return true;
414  }
415  //! Return how many nodes have been visited
416  unsigned int get_count() const { return ct_; }
417  IMP_SHOWABLE_INLINE(HierarchyCounter, out << get_count());
418 
419  private:
420  unsigned int ct_;
421 };
422 
424 
425 //! Gather all the particles in the hierarchy that meet some criteria
426 /** Gather all the particles in the hierarchy for which f() returns true
427  and appends them to out
428 
429  @param h hierarchy root
430  @param f boolean function / functor that returns true
431  on desired particles
432  @param out a output iterator for appending the result
433 
434  @return the output iterator
435 
436  \ingroup hierarchy
437  \see Hierarchy
438  */
439 template <class H, class Out, class F>
440 inline Out gather(H h, F f, Out out) {
441  internal::Gather<H, F, Out> gather(f, out);
442  visit_depth_first(h, gather);
443  return gather.get_out();
444 }
445 
446 //! Gather all the uppermost particles in the hierarchy that meet some criteria
447 /** Descent in the tree terminates when a node is gathered so that
448  none of its children are explored.
449 
450  \ingroup hierarchy
451  \see Hierarchy
452  */
453 template <class H, class Out, class F>
454 inline Out gather_slice(H h, F f, Out out) {
455  internal::Gather<H, F, Out, true> gather(f, out);
456  visit_depth_first(h, gather);
457  return gather.get_out();
458 }
459 
460 //! Gather all the particles in the hierarchy which match on an attribute
461 /** \ingroup hierarchy
462  \see Hierarchy
463  */
464 template <class H, class Out, class K, class V>
465 inline Out gather_by_attribute(H h, K k, V v, Out out) {
466  internal::Gather<H, internal::MatchAttribute<K, V>, Out> gather(
467  internal::MatchAttribute<K, V>(k, v), out);
468  visit_depth_first(h, gather);
469  return gather.get_out();
470 }
471 
472 //! Gather all the particles in the hierarchy which match on two attributes
473 /** \ingroup hierarchy
474  \see Hierarchy
475  */
476 template <class H, class Out, class K0, class V0, class K1, class V1>
477 inline Out gather_by_attributes(H h, K0 k0, V0 v0, K1 k1, V1 v1, Out out) {
478  internal::Gather<H, internal::MatchAttributes<K0, V0, K1, V1>, Out> gather(
479  internal::MatchAttributes<K0, V0, K1, V1>(k0, v0, k1, v1), out);
480  visit_depth_first(h, gather);
481  return gather.get_out();
482 }
483 
484 //! Find the first node which matches some criteria
485 /** \ingroup hierarchy
486  \see Hierarchy
487  */
488 template <class HD, class F>
489 inline HD find_breadth_first(HD h, F f) {
490  if (f(h.get_particle())) return h;
491  base::Vector<HD> stack;
492  stack.push_back(h);
493  // d.show(std::cerr);
494  do {
495  HD cur = stack.back();
496  stack.pop_back();
497 
498  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
499  HD hd = cur.get_child(i);
500  if (f(hd.get_particle())) {
501  return hd;
502  } else {
503  stack.push_back(hd);
504  }
505  }
506  } while (!stack.empty());
507  return HD();
508 }
509 
510 //! Get all the leaves of the bit of hierarchy
511 /** The leaves are returned in the obvious order
512  (first child before second child).
513 
514  \see Hierarchy
515  */
516 IMPCOREEXPORT GenericHierarchies get_leaves(Hierarchy mhd);
517 
518 //! Get all the non-leaves of the bit of hierarchy
519 /** \see Hierarchy
520  */
521 IMPCOREEXPORT GenericHierarchies get_internal(Hierarchy mhd);
522 
523 //! Get all the particles in the subtree
524 /** \see Hierarchy
525  */
526 IMPCOREEXPORT GenericHierarchies get_all_descendants(Hierarchy mhd);
527 
528 //! Return the root of the hierarchy
529 /** \see Hierarchy */
531  while (h.get_parent()) {
532  h = h.get_parent();
533  }
534  return h;
535 }
536 
537 IMPCORE_END_NAMESPACE
538 
539 #endif /* IMPCORE_HIERARCHY_H */
F visit_breadth_first(HD d, F f)
Apply the visitor to each particle, breadth first.
Import IMP/kernel/Decorator.h in the namespace.
A visitor for traversal of a hierarchy.
Import IMP/kernel/SingletonModifier.h in the namespace.
ParticleIndex get_particle_index() const
Returns the particle index decorated by this decorator.
ParticleIndexes get_indexes(const ParticlesTemp &ps)
A base class for Keys.
Definition: kernel/Key.h:46
#define IMP_SHOWABLE_INLINE(Name, how_to_show)
Declare the methods needed by an object that can be printed.
F visit_depth_first(HD d, F &f)
Apply functor F to each particle, traversing the hierarchy depth first.
A smart pointer to a ref-counted Object that is a class member.
Definition: Pointer.h:147
HD find_breadth_first(HD h, F f)
Find the first node which matches some criteria.
Model * get_model() const
Returns the Model containing the particle.
F visit_depth_first_with_data(HD d, F f, typename F::result_type i)
Apply functor F to each particle, traversing the hierarchy depth first.
void remove_attribute(TypeKey attribute_key, ParticleIndex particle)
GenericHierarchies get_leaves(Hierarchy mhd)
Get all the leaves of the bit of hierarchy.
Type get_attribute(TypeKey attribute_key, ParticleIndex particle)
#define IMP_DECORATOR_WITH_TRAITS_METHODS(Name, Parent, TraitsType,traits_name, default_traits)
GenericHierarchies get_all_descendants(Hierarchy mhd)
Get all the particles in the subtree.
#define IMP_DECORATOR_TRAITS_SETUP_1(Name, FirstArgumentType,first_argument_name)
A base class for modifiers of kernel::ParticlesTemp.
A visitor which applies a modifier to each kernel::Particle in a hierarchy.
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
Hierarchy get_parent() const
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.
Import IMP/kernel/decorator_macros.h in the namespace.
bool operator()(Hierarchy)
Increment the counter.
#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.
Storage of a model, its restraints, constraints and particles.
GenericHierarchies get_internal(Hierarchy mhd)
Get all the non-leaves of the bit of hierarchy.
Classes to handle individual model particles. (Note that implementation of inline functions in in int...
std::ostream & show(Hierarchy h, std::ostream &out=std::cout)
Print the hierarchy using a given decorator to display each node.
A nullptr-initialized pointer to an IMP Object.
base::Index< ParticleIndexTag > ParticleIndex
unsigned int get_count() const
Return how many nodes have been visited.
Hierarchy get_root(Hierarchy h)
Return the root of the hierarchy.
void add_attribute(TypeKey attribute_key, ParticleIndex particle, Type value)
#define IMP_USAGE_CHECK(expr, message)
A runtime test for incorrect usage of a class or method.
Definition: check_macros.h:170
static bool get_is_setup(kernel::Model *, kernel::ParticleIndex, HierarchyTraits=Hierarchy::get_default_traits())
A decorator for helping deal with a hierarchy.
F visit_breadth_first_with_data(HD d, F f, typename F::result_type i)
Apply functor F to each particle, traversing the hierarchy breadth first.
virtual bool operator()(Hierarchy p)
Return true if the traversal should visit this node's children.
Class for storing model, its restraints, constraints, and particles.
Definition: kernel/Model.h:73