IMP  2.2.1
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  These functions and classes aid in manipulating particles representing
33  molecules at multiple levels.
34  */
35 #ifndef SWIG
36 class Hierarchy;
37 #endif
38 
39 //! Define the type for a type of hierarchy
40 /** The hierarchy class is identified by the passed string so two
41  hierarchies created with the same initialization string will be
42  the same.
43 
44  This example shows how to make and use a custom hierarchy:
45  \include custom_hierarchy.py
46  \see Hierarchy
47 */
48 class IMPCOREEXPORT HierarchyTraits {
51 
52  public:
53  HierarchyTraits() {}
54  //! Create a HierarchyTraits with the given name
55  HierarchyTraits(std::string name);
56  kernel::ParticleIndexesKey get_children_key() const { return children_; }
57  kernel::ParticleIndexKey get_parent_key() const { return parent_; }
58  bool operator==(const HierarchyTraits &o) const {
59  return parent_ == o.parent_;
60  }
61  IMP_SHOWABLE_INLINE(HierarchyTraits, out << parent_);
62 };
63 
65 
66 class Hierarchy;
67 
68 #ifndef IMP_DOXYGEN
69 typedef IMP::base::Vector<Hierarchy> GenericHierarchies;
70 #endif
71 
72 //! A decorator for helping deal with a hierarchy.
73 /**
74  See HierarchyTraits for an example of how to define a custom hierarchy
75  and Hierarchy for a hierarchy for molecules.
76  \ingroup hierarchy
77  \see HierarchyTraits
78  */
79 class IMPCOREEXPORT Hierarchy : public Decorator {
80  static void do_setup_particle(kernel::Model *, kernel::ParticleIndex,
81  HierarchyTraits) {}
82  static void do_setup_particle(kernel::Model *m, kernel::ParticleIndex pi,
83  const kernel::ParticleIndexes &children,
84  HierarchyTraits traits) {
85  for (unsigned int i = 0; i < children.size(); ++i) {
86  m->add_attribute(traits.get_parent_key(), children[i], pi);
87  }
88  m->add_attribute(traits.get_children_key(), pi, children);
89  }
90  static void do_setup_particle(kernel::Model *m, kernel::ParticleIndex pi,
91  const kernel::ParticlesTemp &children,
92  HierarchyTraits traits) {
93  do_setup_particle(m, pi, kernel::get_indexes(children), traits);
94  }
95 
96  public:
98  traits, get_default_traits());
100  /** Setup the particle and add children. */
103 
104  /** Check if the particle has the needed attributes for a
105  cast to succeed */
107  HierarchyTraits = Hierarchy::get_default_traits()) {
108  return true;
109  }
110  /** \return the parent particle, or Hierarchy()
111  if it has no parent.
112  */
114  if (get_model()->get_has_attribute(get_decorator_traits().get_parent_key(),
115  get_particle_index())) {
117  get_decorator_traits().get_parent_key(), get_particle_index());
118  return Hierarchy(get_model(), VALUE, get_decorator_traits());
119  } else {
120  return Hierarchy();
121  }
122  }
123 
124  unsigned int get_number_of_children() const {
125  if (get_model()->get_has_attribute(
126  get_decorator_traits().get_children_key(), get_particle_index())) {
127  return get_model()
128  ->get_attribute(get_decorator_traits().get_children_key(),
130  .size();
131  } else {
132  return 0;
133  }
134  }
135  Hierarchy get_child(unsigned int i) const {
136  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
137  return Hierarchy(get_model(), get_model()->get_attribute(
138  get_decorator_traits().get_children_key(),
139  get_particle_index())[i],
140  get_decorator_traits());
141  }
142  kernel::ParticleIndex get_child_index(unsigned int i) const {
143  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
144  return get_model()->get_attribute(get_decorator_traits().get_children_key(),
145  get_particle_index())[i];
146  }
147  kernel::ParticleIndexes get_children_indexes() const {
148  if (get_model()->get_has_attribute(
149  get_decorator_traits().get_children_key(), get_particle_index())) {
150  return get_model()->get_attribute(
151  get_decorator_traits().get_children_key(), get_particle_index());
152  } else {
153  return kernel::ParticleIndexes();
154  }
155  }
156  GenericHierarchies get_children() const {
157  GenericHierarchies ret(get_number_of_children());
158  for (unsigned int i = 0; i < ret.size(); ++i) {
159  ret[i] = get_child(i);
160  }
161  return ret;
162  }
163  void remove_child(unsigned int i) {
164  IMP_USAGE_CHECK(i < get_number_of_children(), "Invalid child requested");
165  Hierarchy c = get_child(i);
166  kernel::ParticleIndexes &pis = get_model()->access_attribute(
167  get_decorator_traits().get_children_key(), get_particle_index());
168  pis.erase(pis.begin() + i);
169  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
170  c.get_particle_index());
171  }
172  void remove_child(Hierarchy h) { remove_child(h.get_child_index()); }
173  void clear_children() {
174  kernel::ParticleIndexes &pis = get_model()->access_attribute(
175  get_decorator_traits().get_children_key(), get_particle_index());
176  for (unsigned int i = 0; i < pis.size(); ++i) {
177  get_model()->remove_attribute(get_decorator_traits().get_parent_key(),
178  pis[i]);
179  }
180  get_model()->remove_attribute(get_decorator_traits().get_children_key(),
182  }
183  void add_child(Hierarchy h) const {
184  if (get_model()->get_has_attribute(
185  get_decorator_traits().get_children_key(), get_particle_index())) {
186  get_model()
187  ->access_attribute(get_decorator_traits().get_children_key(),
189  .push_back(h.get_particle_index());
190  } else {
192  get_decorator_traits().get_children_key(), get_particle_index(),
193  kernel::ParticleIndexes(1, h.get_particle_index()));
194  }
195  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
196  h.get_particle_index(), get_particle_index());
197  }
198  void add_child_at(Hierarchy h, unsigned int pos) {
199  IMP_USAGE_CHECK(get_number_of_children() >= pos, "Invalid position");
200  if (get_model()->get_has_attribute(
201  get_decorator_traits().get_children_key(), get_particle_index())) {
202  kernel::ParticleIndexes &pis = get_model()->access_attribute(
203  get_decorator_traits().get_children_key(), get_particle_index());
204  pis.insert(pis.begin() + pos, h.get_particle_index());
205  } else {
207  get_decorator_traits().get_children_key(), get_particle_index(),
208  kernel::ParticleIndexes(1, h.get_particle_index()));
209  }
210  get_model()->add_attribute(get_decorator_traits().get_parent_key(),
211  h.get_particle_index(), get_particle_index());
212  }
213  /** Return i such that `get_parent().get_child(i) == this` */
214  int get_child_index() const;
215  //! Get the default hierarchy traits
216  static const HierarchyTraits &get_default_traits();
217 
218  HierarchyTraits get_traits() { return get_decorator_traits(); }
219 };
220 
221 //! A visitor for traversal of a hierarchy
222 /** This works from both C++ and Python
223  \ingroup hierarchy
224  \ingroup decorators
225  \see Hierarchy
226  */
227 class IMPCOREEXPORT HierarchyVisitor {
228  public:
229  HierarchyVisitor() {}
230  //! Return true if the traversal should visit this node's children
231  virtual bool operator()(Hierarchy p) = 0;
232  virtual ~HierarchyVisitor() {}
233 };
234 
235 //! A visitor which applies a modifier to each kernel::Particle in a hierarchy
236 /** This works from both C++ and Python
237  \ingroup hierarchy
238  \ingroup decorators
239  \see SingletonModifier
240  \see Hierarchy
241  */
242 class IMPCOREEXPORT ModifierVisitor : public HierarchyVisitor {
244 
245  public:
246  ModifierVisitor(SingletonModifier *sm) : sm_(sm) {}
247  virtual bool operator()(Hierarchy p) {
248  sm_->apply_index(p.get_model(), p.get_particle_index());
249  return true;
250  }
251  virtual ~ModifierVisitor() {}
252 };
253 
254 #if !defined(SWIG) && !defined(IMP_DOXYGEN)
255 namespace internal {
256 template <class H, class F, class Out, bool Slice = false>
257 struct Gather {
258  //! initialize with the function and the container
259  Gather(F f, Out out) : f_(f), out_(out) {}
260  bool operator()(H p) {
261  if (f_(p)) {
262  *out_ = p;
263  ++out_;
264  if (Slice) return false;
265  }
266  return true;
267  }
268  //! Return the container
269  Out get_out() const { return out_; }
270 
271  private:
272  F f_;
273  Out out_;
274 };
275 }
276 #endif
277 
278 //! Apply the visitor to each particle, breadth first.
279 /** \param[in] d The Hierarchy for the tree in question
280  \param[in] f The visitor to be applied. This is passed by reference.
281  A branch of the traversal stops when f returns false.
282  \ingroup hierarchy
283  See Hierarchy
284  */
285 template <class HD, class F>
286 inline F visit_breadth_first(HD d, F f) {
287  std::deque<HD> stack;
288  stack.push_back(d);
289  // d.show(std::cerr);
290  do {
291  HD cur = stack.front();
292  stack.pop_front();
293  if (f(cur)) {
294  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
295  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
296  stack.push_back(cur.get_child(i));
297  }
298  }
299  } while (!stack.empty());
300  return f;
301 }
302 
303 //! Apply functor F to each particle, traversing the hierarchy depth first.
304 /** See breadth_first_traversal() for documentation.
305  \ingroup hierarchy
306  See Hierarchy
307  */
308 template <class HD, class F>
309 inline F visit_depth_first(HD d, F f) {
310  base::Vector<HD> stack;
311  stack.push_back(d);
312  // d.show(std::cerr);
313  do {
314  HD cur = stack.back();
315  stack.pop_back();
316  if (f(cur)) {
317  // std::cerr << "Visiting particle " << cur.get_particle() << std::endl;
318  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
319  stack.push_back(cur.get_child(i));
320  }
321  }
322  } while (!stack.empty());
323  return f;
324 }
325 
326 //! Apply functor F to each particle, traversing the hierarchy breadth first.
327 /** This method allows data to be associated with each visited node.
328  The data of the parent is passed to each invocation of the child.
329 
330  \param[in] d The Hierarchy for the tree in question
331  \param[in] f The functor to be applied
332  F must define a type Data which is returned by each call.
333  The result of the parent call is passed as the second argument
334  to the operator() of the child. e.g.
335  struct DepthVisitor {
336  typedef int result_type;
337  result_type operator()(kernel::Particle *p, int i) const
338  {
339  if (p==nullptr) return 0;
340  else return i+1;
341  }
342  };
343  \param[in] i The data to be used for d (since it has no relevant parent)
344 
345  \return A copy of the functor passed in. Use this if you care about
346  the functor state.
347 
348  \ingroup hierarchy
349  See Hierarchy
350  */
351 template <class HD, class F>
352 inline F visit_breadth_first_with_data(HD d, F f, typename F::result_type i) {
353  typedef std::pair<typename F::result_type, HD> DP;
354  std::deque<DP> stack;
355  stack.push_back(DP(i, 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 breadth_first_traversal 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 i) {
376  typedef std::pair<typename F::result_type, HD> DP;
377  base::Vector<DP> stack;
378  stack.push_back(DP(i, 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 as to display each node
393 /** The last argument limits how deep will be printed out.
394  \ingroup hierarchy
395  See Hierarchy
396  */
397 template <class ND>
398 inline std::ostream &show(Hierarchy h, std::ostream &out = std::cout) {
399  IMP_PRINT_TREE(out, Hierarchy, h, n.get_number_of_children(), n.get_child,
400  ND(n).show(out));
401  return out;
402 }
403 
404 //! A simple functor to count the number of particles in a hierarchy.
405 /** This is a good example of a simple HierarchyVisitor.
406  \ingroup hierarchy
407  \see Hierarchy
408  */
410  HierarchyCounter() : ct_(0) {}
411 
412  //! Increment the counter
414  ++ct_;
415  return true;
416  }
417  //! Return how many nodes have been visited
418  unsigned int get_count() const { return ct_; }
419  IMP_SHOWABLE_INLINE(HierarchyCounter, out << get_count());
420 
421  private:
422  unsigned int ct_;
423 };
424 
426 
427 //! Gather all the particles in the hierarchy which meet some criteria
428 /** \ingroup hierarchy
429  See Hierarchy
430  */
431 template <class H, class Out, class F>
432 inline Out gather(H h, F f, Out out) {
433  internal::Gather<H, F, Out> gather(f, out);
434  visit_depth_first(h, gather);
435  return gather.get_out();
436 }
437 
438 //! Gather all the particles in the hierarchy which meet some criteria
439 /** Descent in the tree terminates when a node is gathered so that
440  none of its children are explored.
441 
442  \ingroup hierarchy
443  See Hierarchy
444  */
445 template <class H, class Out, class F>
446 inline Out gather_slice(H h, F f, Out out) {
447  internal::Gather<H, F, Out, true> gather(f, out);
448  visit_depth_first(h, gather);
449  return gather.get_out();
450 }
451 
452 //! Gather all the particles in the hierarchy which match on an attribute
453 /** \ingroup hierarchy
454  See Hierarchy
455  */
456 template <class H, class Out, class K, class V>
457 inline Out gather_by_attribute(H h, K k, V v, Out out) {
458  internal::Gather<H, internal::MatchAttribute<K, V>, Out> gather(
459  internal::MatchAttribute<K, V>(k, v), out);
460  visit_depth_first(h, gather);
461  return gather.get_out();
462 }
463 
464 //! Gather all the particles in the hierarchy which match on two attributes
465 /** \ingroup hierarchy
466  See Hierarchy
467  */
468 template <class H, class Out, class K0, class V0, class K1, class V1>
469 inline Out gather_by_attributes(H h, K0 k0, V0 v0, K1 k1, V1 v1, Out out) {
470  internal::Gather<H, internal::MatchAttributes<K0, V0, K1, V1>, Out> gather(
471  internal::MatchAttributes<K0, V0, K1, V1>(k0, v0, k1, v1), out);
472  visit_depth_first(h, gather);
473  return gather.get_out();
474 }
475 
476 //! Find the first node which matches some criteria
477 /** \ingroup hierarchy
478  See Hierarchy
479  */
480 template <class HD, class F>
481 inline HD find_breadth_first(HD h, F f) {
482  if (f(h.get_particle())) return h;
483  base::Vector<HD> stack;
484  stack.push_back(h);
485  // d.show(std::cerr);
486  do {
487  HD cur = stack.back();
488  stack.pop_back();
489 
490  for (int i = cur.get_number_of_children() - 1; i >= 0; --i) {
491  HD hd = cur.get_child(i);
492  if (f(hd.get_particle())) {
493  return hd;
494  } else {
495  stack.push_back(hd);
496  }
497  }
498  } while (!stack.empty());
499  return HD();
500 }
501 
502 //! Get all the leaves of the bit of hierarchy
503 /** The leaves are returned in the obvious order
504  (first child before second child).
505 
506  See Hierarchy
507  */
508 IMPCOREEXPORT GenericHierarchies get_leaves(Hierarchy mhd);
509 
510 //! Get all the non-leaves of the bit of hierarchy
511 /** See Hierarchy
512  */
513 IMPCOREEXPORT GenericHierarchies get_internal(Hierarchy mhd);
514 
515 //! Get all the particles in the subtree
516 /** See Hierarchy
517  */
518 IMPCOREEXPORT GenericHierarchies get_all_descendants(Hierarchy mhd);
519 
520 //! Return the root of the hierarchy
521 /** See Hierarchy */
523  while (h.get_parent()) {
524  h = h.get_parent();
525  }
526  return h;
527 }
528 
529 IMPCORE_END_NAMESPACE
530 
531 #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
ParticleIndexes get_indexes(const ParticlesTemp &ps)
A base class for Keys.
Definition: kernel/Key.h:46
A nullptr-initialized pointer to an IMP Object.
A smart pointer to a ref-counted Object that is a class memeber.
Definition: base/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.
#define IMP_VALUES(Name, PluralName)
Define the type for storing sets of values.
#define IMP_SHOWABLE_INLINE(Name, how_to_show)
Declare the methods needed by an object that can be printed.
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.
#define IMP_USAGE_CHECK(expr, message)
A runtime test for incorrect usage of a class or method.
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.
Hierarchy get_parent() const
Out gather_slice(H h, F f, Out out)
Gather all the particles in the hierarchy which meet some criteria.
F visit_depth_first(HD d, F f)
Apply functor F to each particle, traversing the hierarchy depth first.
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 which 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.
std::ostream & show(Hierarchy h, std::ostream &out=std::cout)
Print the hierarchy using a given decorator as to display each node.
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)
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:72