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