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