LArSoft  v06_85_00
Liquid Argon Software toolkit - http://larsoft.org/
indexing_suite_detail.hpp
Go to the documentation of this file.
1 // (C) Copyright Joel de Guzman 2003.
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 
6 #ifndef INDEXING_SUITE_DETAIL_JDG20036_HPP
7 # define INDEXING_SUITE_DETAIL_JDG20036_HPP
8 
9 # include <boost/python/extract.hpp>
10 # include <boost/scoped_ptr.hpp>
11 # include <boost/get_pointer.hpp>
12 # include <boost/detail/binary_search.hpp>
13 # include <boost/numeric/conversion/cast.hpp>
14 # include <boost/type_traits/is_pointer.hpp>
15 # include <vector>
16 # include <map>
17 #include <iostream>
18 
19 namespace boost { namespace python { namespace detail {
20 
21 #if defined(NDEBUG)
22 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT
23 #else
24 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT check_invariant()
25 #endif
26 
27  template <class Proxy>
29  {
30  // This functor compares a proxy and an index.
31  // This is used by proxy_group::first_proxy to
32  // get first proxy with index i.
33 
34  template <class Index>
35  bool operator()(PyObject* prox, Index i) const
36  {
37  typedef typename Proxy::policies_type policies_type;
38  Proxy& proxy = extract<Proxy&>(prox)();
39  return policies_type::
40  compare_index(proxy.get_container(), proxy.get_index(), i);
41  }
42  };
43 
44  // The proxy_group class holds a vector of container element
45  // proxies. First, what is a container element proxy? A container
46  // element proxy acts like a smart pointer holding a reference to
47  // a container and an index (see container_element, for details).
48  //
49  // The proxies are held in a vector always sorted by its index.
50  // Various functions manage the addition, removal and searching
51  // of proxies from the vector.
52  //
53  template <class Proxy>
55  {
56  public:
57 
60  typedef typename Proxy::index_type index_type;
61  typedef typename Proxy::policies_type policies_type;
62 
63  iterator
64  first_proxy(index_type i)
65  {
66  // Return the first proxy with index <= i
67  return boost::detail::lower_bound(
68  proxies.begin(), proxies.end(),
70  }
71 
72  void
73  remove(Proxy& proxy)
74  {
75  // Remove a proxy
76  for (iterator iter = first_proxy(proxy.get_index());
77  iter != proxies.end(); ++iter)
78  {
79  if (&extract<Proxy&>(*iter)() == &proxy)
80  {
81  proxies.erase(iter);
82  break;
83  }
84  }
86  }
87 
88  void
89  add(PyObject* prox)
90  {
92  // Add a proxy
93  proxies.insert(
94  first_proxy(extract<Proxy&>(prox)().get_index()), prox);
96  }
97 
98  void
99  erase(index_type i, mpl::false_)
100  {
102  // Erase the proxy with index i
103  replace(i, i+1, 0);
105  }
106 
107  void
108  erase(index_type i, mpl::true_)
109  {
111  // Erase the proxy with index i
112 
113  iterator iter = first_proxy(i);
114  extract<Proxy&> p(*iter);
115 
116  if (iter != proxies.end() && p().get_index() == i)
117  {
118  extract<Proxy&> p(*iter);
119  p().detach();
120  proxies.erase(iter);
121  }
123  }
124 
125  void
126  erase(index_type from, index_type to)
127  {
128  // note: this cannot be called when container is not sliceable
129 
131  // Erase all proxies with indexes from..to
132  replace(from, to, 0);
134  }
135 
136  void
138  index_type from,
139  index_type to,
140  typename std::vector<PyObject*>::size_type len)
141  {
142  // note: this cannot be called when container is not sliceable
143 
145  // Erase all proxies with indexes from..to.
146  // Adjust the displaced indexes such that the
147  // final effect is that we have inserted *len*
148  // number of proxies in the vacated region. This
149  // procedure involves adjusting the indexes of
150  // the proxies.
151 
152  iterator left = first_proxy(from);
153  iterator right = proxies.end(); // we'll adjust this later
154 
155  for (iterator iter = left; iter != right; ++iter)
156  {
157  if (extract<Proxy&>(*iter)().get_index() > to)
158  {
159  right = iter; // adjust right
160  break;
161  }
162  extract<Proxy&> p(*iter);
163  p().detach();
164  }
165 
166  typename std::vector<PyObject*>::size_type
167  offset = left-proxies.begin();
168  proxies.erase(left, right);
169  right = proxies.begin()+offset;
170 
171  while (right != proxies.end())
172  {
173  typedef typename Proxy::container_type::difference_type difference_type;
174  extract<Proxy&> p(*right);
175  p().set_index(
176  extract<Proxy&>(*right)().get_index()
177  - (difference_type(to) - from - len)
178  );
179 
180  ++right;
181  }
183  }
184 
185  PyObject*
186  find(index_type i)
187  {
189  // Find the proxy with *exact* index i.
190  // Return 0 (null) if no proxy with the
191  // given index is found.
192  iterator iter = first_proxy(i);
193  if (iter != proxies.end()
194  && extract<Proxy&>(*iter)().get_index() == i)
195  {
197  return *iter;
198  }
200  return 0;
201  }
202 
203  typename std::vector<PyObject*>::size_type
204  size() const
205  {
207  // How many proxies are there so far?
208  return proxies.size();
209  }
210 
211  private:
212 
213 #if !defined(NDEBUG)
214  void
216  {
217  for (const_iterator i = proxies.begin(); i != proxies.end(); ++i)
218  {
219  if ((*i)->ob_refcnt <= 0)
220  {
221  PyErr_SetString(PyExc_RuntimeError,
222  "Invariant: Proxy vector in an inconsistent state");
223  throw_error_already_set();
224  }
225 
226  if (i+1 != proxies.end())
227  {
228  if (extract<Proxy&>(*(i+1))().get_index() ==
229  extract<Proxy&>(*(i))().get_index())
230  {
231  PyErr_SetString(PyExc_RuntimeError,
232  "Invariant: Proxy vector in an inconsistent state (duplicate proxy)");
233  throw_error_already_set();
234  }
235  }
236  }
237  }
238 #endif
239 
240  std::vector<PyObject*> proxies;
241  };
242 
243  // proxy_links holds a map of Container pointers (keys)
244  // with proxy_group(s) (data). Various functions manage
245  // the addition, removal and searching of proxies from
246  // the map.
247  //
248  template <class Proxy, class Container>
250  {
251  public:
252 
253  typedef std::map<Container*, proxy_group<Proxy> > links_t;
254  typedef typename Proxy::index_type index_type;
255 
256  void
257  remove(Proxy& proxy)
258  {
259  // Remove a proxy.
260  typename links_t::iterator r = links.find(&proxy.get_container());
261  if (r != links.end())
262  {
263  r->second.remove(proxy);
264  if (r->second.size() == 0)
265  links.erase(r);
266  }
267  }
268 
269  void
270  add(PyObject* prox, Container& container)
271  {
272  // Add a proxy
273  links[&container].add(prox);
274  }
275 
276  template <class NoSlice>
277  void erase(Container& container, index_type i, NoSlice no_slice)
278  {
279  // Erase the proxy with index i
280  typename links_t::iterator r = links.find(&container);
281  if (r != links.end())
282  {
283  r->second.erase(i, no_slice);
284  if (r->second.size() == 0)
285  links.erase(r);
286  }
287  }
288 
289  void
290  erase(Container& container, index_type from, index_type to)
291  {
292  // Erase all proxies with indexes from..to
293  typename links_t::iterator r = links.find(&container);
294  if (r != links.end())
295  {
296  r->second.erase(from, to);
297  if (r->second.size() == 0)
298  links.erase(r);
299  }
300  }
301 
302  void
304  Container& container,
305  index_type from, index_type to, index_type len)
306  {
307  // Erase all proxies with indexes from..to.
308  // Adjust the displaced indexes such that the
309  // final effect is that we have inserted *len*
310  // number of proxies in the vacated region. This
311  // procedure involves adjusting the indexes of
312  // the proxies.
313 
314  typename links_t::iterator r = links.find(&container);
315  if (r != links.end())
316  {
317  r->second.replace(from, to, len);
318  if (r->second.size() == 0)
319  links.erase(r);
320  }
321  }
322 
323  PyObject*
324  find(Container& container, index_type i)
325  {
326  // Find the proxy with *exact* index i.
327  // Return 0 (null) if no proxy with the given
328  // index is found.
329  typename links_t::iterator r = links.find(&container);
330  if (r != links.end())
331  return r->second.find(i);
332  return 0;
333  }
334 
335  private:
336 
337  links_t links;
338  };
339 
340  // container_element is our container proxy class.
341  // This class acts like a smart pointer to a container
342  // element. The class holds an index and a reference to
343  // a container. Dereferencing the smart pointer will
344  // retrieve the nth (index) element from the container.
345  //
346  // A container_element can also be detached from the
347  // container. In such a detached state, the container_element
348  // holds a copy of the nth (index) element, which it
349  // returns when dereferenced.
350  //
351  template <class Container, class Index, class Policies>
353  {
354  public:
355 
356  typedef Index index_type;
357  typedef Container container_type;
358  typedef typename Policies::data_type element_type;
359  typedef Policies policies_type;
362 
363  container_element(object container, Index index)
364  : ptr()
365  , container(container)
366  , index(index)
367  {
368  }
369 
371  : ptr(ce.ptr.get() == 0 ? 0 : new element_type(*ce.ptr.get()))
372  , container(ce.container)
373  , index(ce.index)
374  {
375  }
376 
378  {
379  if (!is_detached())
380  get_links().remove(*this);
381  }
382 
383  element_type& operator*() const
384  {
385  if (is_detached())
386  return *get_pointer(ptr);
387  return Policies::get_item(get_container(), index);
388  }
389 
390  element_type* get() const
391  {
392  if (is_detached())
393  return get_pointer(ptr);
394  return &Policies::get_item(get_container(), index);
395  }
396 
397  void
399  {
400  if (!is_detached())
401  {
402  ptr.reset(
403  new element_type(
404  Policies::get_item(get_container(), index)));
405  container = object(); // free container. reset it to None
406  }
407  }
408 
409  bool
410  is_detached() const
411  {
412  return get_pointer(ptr) != 0;
413  }
414 
415  Container&
417  {
418  return extract<Container&>(container)();
419  }
420 
421  Index
422  get_index() const
423  {
424  return index;
425  }
426 
427  void
428  set_index(Index i)
429  {
430  index = i;
431  }
432 
435  {
436  // All container_element(s) maintain links to
437  // its container in a global map (see proxy_links).
438  // This global "links" map is a singleton.
439 
440  static proxy_links<self_t, Container> links;
441  return links; // singleton
442  }
443 
444  private:
445 
446  container_element& operator=(container_element const& ce);
447 
448  scoped_ptr<element_type> ptr;
449  object container;
450  Index index;
451  };
452 
453  template <
454  class Container
455  , class DerivedPolicies
456  , class ContainerElement
457  , class Index
458  >
460  {
461  static void
463  {
464  }
465 
466  template <class DataType>
467  static object
468  base_get_item_helper(DataType const& p, mpl::true_)
469  {
470  return object(ptr(p));
471  }
472 
473  template <class DataType>
474  static object
475  base_get_item_helper(DataType const& x, mpl::false_)
476  {
477  return object(x);
478  }
479 
480  static object
481  base_get_item_(back_reference<Container&> const& container, PyObject* i)
482  {
483  return base_get_item_helper(
484  DerivedPolicies::get_item(
485  container.get(), DerivedPolicies::
486  convert_index(container.get(), i))
487  , is_pointer<BOOST_DEDUCED_TYPENAME Container::value_type>()
488  );
489  }
490 
491  static void
493  Container& container, Index from,
494  Index to, Index n)
495  {
496  }
497 
498  template <class NoSlice>
499  static void
501  Container& container, Index i, NoSlice no_slice)
502  {
503  }
504 
505  static void
506  base_erase_indexes(Container& container, Index from, Index to)
507  {
508  }
509  };
510 
511  template <
512  class Container
513  , class DerivedPolicies
514  , class ContainerElement
515  , class Index
516  >
518  {
519  static void
521  {
522  register_ptr_to_python<ContainerElement>();
523  }
524 
525  static object
526  base_get_item_(back_reference<Container&> const& container, PyObject* i)
527  {
528  // Proxy
529  Index idx = DerivedPolicies::convert_index(container.get(), i);
530 
531  if (PyObject* shared =
532  ContainerElement::get_links().find(container.get(), idx))
533  {
534  handle<> h(python::borrowed(shared));
535  return object(h);
536  }
537  else
538  {
539  object prox(ContainerElement(container.source(), idx));
540  ContainerElement::
541  get_links().add(prox.ptr(), container.get());
542  return prox;
543  }
544  }
545 
546  static void
548  Container& container, Index from,
549  Index to, Index n)
550  {
551  ContainerElement::get_links().replace(container, from, to, n);
552  }
553 
554  template <class NoSlice>
555  static void
557  Container& container, Index i, NoSlice no_slice)
558  {
559  ContainerElement::get_links().erase(container, i, no_slice);
560  }
561 
562  static void
564  Container& container, Index from, Index to)
565  {
566  ContainerElement::get_links().erase(container, from, to);
567  }
568  };
569 
570  template <
571  class Container
572  , class DerivedPolicies
573  , class ProxyHandler
574  , class Data
575  , class Index
576  >
578  {
579  static object
580  base_get_slice(Container& container, PySliceObject* slice)
581  {
582  Index from, to;
583  base_get_slice_data(container, slice, from, to);
584  return DerivedPolicies::get_slice(container, from, to);
585  }
586 
587  static void
589  Container& container, PySliceObject* slice, Index& from_, Index& to_)
590  {
591  if (Py_None != slice->step) {
592  PyErr_SetString( PyExc_IndexError, "slice step size not supported.");
593  throw_error_already_set();
594  }
595 
596  Index min_index = DerivedPolicies::get_min_index(container);
597  Index max_index = DerivedPolicies::get_max_index(container);
598 
599  if (Py_None == slice->start) {
600  from_ = min_index;
601  }
602  else {
603  long from = extract<long>( slice->start);
604  if (from < 0) // Negative slice index
605  from += max_index;
606  if (from < 0) // Clip lower bounds to zero
607  from = 0;
608  from_ = boost::numeric_cast<Index>(from);
609  if (from_ > max_index) // Clip upper bounds to max_index.
610  from_ = max_index;
611  }
612 
613  if (Py_None == slice->stop) {
614  to_ = max_index;
615  }
616  else {
617  long to = extract<long>( slice->stop);
618  if (to < 0)
619  to += max_index;
620  if (to < 0)
621  to = 0;
622  to_ = boost::numeric_cast<Index>(to);
623  if (to_ > max_index)
624  to_ = max_index;
625  }
626  }
627 
628  static void
629  base_set_slice(Container& container, PySliceObject* slice, PyObject* v)
630  {
631  Index from, to;
632  base_get_slice_data(container, slice, from, to);
633 
634  extract<Data&> elem(v);
635  // try if elem is an exact Data
636  if (elem.check())
637  {
638  ProxyHandler::base_replace_indexes(container, from, to, 1);
639  DerivedPolicies::set_slice(container, from, to, elem());
640  }
641  else
642  {
643  // try to convert elem to Data
644  extract<Data> elem(v);
645  if (elem.check())
646  {
647  ProxyHandler::base_replace_indexes(container, from, to, 1);
648  DerivedPolicies::set_slice(container, from, to, elem());
649  }
650  else
651  {
652  // Otherwise, it must be a list or some container
653  handle<> l_(python::borrowed(v));
654  object l(l_);
655 
656  std::vector<Data> temp;
657  for (int i = 0; i < l.attr("__len__")(); i++)
658  {
659  object elem(l[i]);
660  extract<Data const&> x(elem);
661  // try if elem is an exact Data type
662  if (x.check())
663  {
664  temp.push_back(x());
665  }
666  else
667  {
668  // try to convert elem to Data type
669  extract<Data> x(elem);
670  if (x.check())
671  {
672  temp.push_back(x());
673  }
674  else
675  {
676  PyErr_SetString(PyExc_TypeError,
677  "Invalid sequence element");
678  throw_error_already_set();
679  }
680  }
681  }
682 
683  ProxyHandler::base_replace_indexes(container, from, to,
684  temp.end()-temp.begin());
685  DerivedPolicies::set_slice(container, from, to,
686  temp.begin(), temp.end());
687  }
688  }
689  }
690 
691  static void
692  base_delete_slice(Container& container, PySliceObject* slice)
693  {
694  Index from, to;
695  base_get_slice_data(container, slice, from, to);
696  ProxyHandler::base_erase_indexes(container, from, to);
697  DerivedPolicies::delete_slice(container, from, to);
698  }
699  };
700 
701  template <
702  class Container
703  , class DerivedPolicies
704  , class ProxyHandler
705  , class Data
706  , class Index
707  >
709  {
710  static void
712  {
713  PyErr_SetString(PyExc_RuntimeError, "Slicing not supported");
714  throw_error_already_set();
715  }
716 
717  static object
718  base_get_slice(Container& container, PySliceObject* slice)
719  {
720  slicing_not_suported();
721  return object();
722  }
723 
724  static void
725  base_set_slice(Container& container, PySliceObject* slice, PyObject* v)
726  {
727  slicing_not_suported();
728  }
729 
730  static void
731  base_delete_slice(Container& container, PySliceObject* slice)
732  {
733  slicing_not_suported();
734  }
735  };
736 
737 #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
738 }} // namespace python::detail
739 #endif
740 
741  template <class Container, class Index, class Policies>
742  inline typename Policies::data_type*
745  {
746  // Get the pointer of a container_element smart pointer
747  return p.get();
748  }
749 
750 #ifndef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
751  // Don't hide these other get_pointer overloads
753  using boost::get_pointer;
754 }} // namespace python::detail
755 #endif
756 
757 } // namespace boost
758 
759 #endif // INDEXING_SUITE_DETAIL_JDG20036_HPP
Float_t x
Definition: compare.C:6
container_element< Container, Index, Policies > self_t
static void base_delete_slice(Container &container, PySliceObject *slice)
bool operator()(PyObject *prox, Index i) const
constexpr auto const & right(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:112
std::vector< PyObject * >::const_iterator const_iterator
static void base_set_slice(Container &container, PySliceObject *slice, PyObject *v)
intermediate_table::iterator iterator
static void base_erase_index(Container &container, Index i, NoSlice no_slice)
void erase(index_type from, index_type to)
Policies::data_type * get_pointer(python::detail::container_element< Container, Index, Policies > const &p)
static object base_get_item_helper(DataType const &x, mpl::false_)
static proxy_links< self_t, Container > & get_links()
void erase(index_type i, mpl::true_)
intermediate_table::const_iterator const_iterator
static void base_erase_indexes(Container &container, Index from, Index to)
static void base_set_slice(Container &container, PySliceObject *slice, PyObject *v)
Encloses LArSoft data product proxy objects and utilities.See this doxygen module for an introduction...
static void base_erase_index(Container &container, Index i, NoSlice no_slice)
static void base_replace_indexes(Container &container, Index from, Index to, Index n)
static void base_erase_indexes(Container &container, Index from, Index to)
container_element(object container, Index index)
void erase(index_type i, mpl::false_)
constexpr auto const & left(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:104
std::vector< PyObject * >::iterator iterator
static void base_delete_slice(Container &container, PySliceObject *slice)
static object base_get_item_helper(DataType const &p, mpl::true_)
static object base_get_item_(back_reference< Container & > const &container, PyObject *i)
static void base_replace_indexes(Container &container, Index from, Index to, Index n)
static object base_get_slice(Container &container, PySliceObject *slice)
void replace(index_type from, index_type to, typename std::vector< PyObject * >::size_type len)
Char_t n[5]
static void base_get_slice_data(Container &container, PySliceObject *slice, Index &from_, Index &to_)
std::vector< PyObject * >::size_type size() const
static object base_get_item_(back_reference< Container & > const &container, PyObject *i)
#define BOOST_PYTHON_INDEXING_CHECK_INVARIANT
static object base_get_slice(Container &container, PySliceObject *slice)