KJB
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
l_index.h
Go to the documentation of this file.
1 /* $Id: l_index.h 18278 2014-11-25 01:42:10Z ksimek $ */
2 /* =========================================================================== *
3  |
4  | Copyright (c) 1994-2010 by Kobus Barnard (author)
5  |
6  | Personal and educational use of this code is granted, provided that this
7  | header is kept intact, and that the authorship is not misrepresented, that
8  | its use is acknowledged in publications, and relevant papers are cited.
9  |
10  | For other use contact the author (kobus AT cs DOT arizona DOT edu).
11  |
12  | Please note that the code in this file has not necessarily been adequately
13  | tested. Naturally, there is no guarantee of performance, support, or fitness
14  | for any particular task. Nonetheless, I am interested in hearing about
15  | problems that you encounter.
16  |
17  | Author: Kyle Simek
18  * =========================================================================== */
19 
20 #ifndef KJB_L_CPP_INDEX_H
21 #define KJB_L_CPP_INDEX_H
22 
23 #include <l_cpp/l_exception.h>
24 #include <l/l_debug.h>
25 #include <l_cpp/l_util.h>
26 #include <l_cpp/l_int_vector.h>
27 #include <boost/concept_check.hpp>
28 #include <boost/static_assert.hpp>
29 #include <boost/type_traits.hpp>
30 #include <vector>
31 #include <list>
32 #include <sstream>
33 #include <iterator>
34 #include <algorithm>
35 
36 #include <limits>
37 
38 namespace kjb {
39 
45 // forward declaration
46 class Int_vector;
47 
66 {
67  typedef Index_range Self;
68 public:
69  static const Index_range ALL;
70 
71  struct End_type {};
72  static const End_type END;
73 
78  ranges_(),
79  all_(false)
80  {}
81 
85  Index_range(size_t index) :
86  ranges_(),
87  all_(false)
88  {
89  ranges_.push_back(new Single_element(index));
90  }
91 
95  Index_range(int index) :
96  ranges_(),
97  all_(false)
98  {
99  ranges_.push_back(new Single_element(index));
100  }
101 
105  Index_range(const std::string& str) :
106  ranges_(),
107  all_(false)
108  {
109  init_from_str(str);
110  }
111 
112  Index_range(const char* str) :
113  ranges_(),
114  all_(false)
115  {
116  init_from_str(std::string(str));
117  }
118 
119  Index_range(const Index_range& src ) :
120  ranges_(src.ranges_.size()),
121  all_(src.all_)
122  {
123  for(size_t i = 0; i < src.ranges_.size(); i++)
124  {
125  ranges_[i] = src.ranges_[i]->clone();
126  }
127  }
128 
130  {
131  Index_range tmp(other);
132  swap(tmp);
133  return *this;
134  }
135 
145  std::vector<size_t> expand() const
146  {
147  size_t my_size = size();
148 
149  std::vector<size_t> result(my_size);
150 
151  for(size_t i = 0; i < my_size; i++)
152  {
153  result[i] = operator[](i);
154  }
155 
156  return result;
157  }
158 
159  void swap(Index_range& other)
160  {
161  using std::swap;
162  ranges_.swap(other.ranges_);
163  swap(all_, other.all_);
164  }
165 //
166 // /// create from collection of Range_elements
167 // template <class Input_iterator>
168 // Index_range(Input_iterator begin_, Input_iterator end_) :
169 // ranges_(begin_, end_),
170 // all_(false)
171 // {
172 // }
173 
174  Index_range(const Int_vector& v);
175 
176  template <class Int_type>
177  Index_range(typename std::vector<Int_type> v) :
178  ranges_(),
179  all_(false)
180  {
181  BOOST_STATIC_ASSERT((boost::is_convertible<Int_type, size_t>::value));
182 
183  ranges_.push_back(new Listing_element(v));
184  }
185 
186  template <class Int_type>
187  Index_range(std::list<Int_type> v) :
188  ranges_(),
189  all_(false)
190  {
191  BOOST_STATIC_ASSERT((boost::is_convertible<Int_type, size_t>::value));
192  ranges_.push_back(new Listing_element(v));
193  }
194 
195  Index_range(size_t first, size_t end, size_t interval = 1) :
196  ranges_(),
197  all_(false)
198  {
199  ranges_.push_back(new Interval_element(first, end, interval));
200  }
201 
202 
203  Index_range(size_t first, End_type end, size_t interval = 1) :
204  ranges_(),
205  all_(false)
206  {
207  ranges_.push_back(new Interval_element(first, end, interval));
208  }
209 
211  {
212  for(size_t i = 0; i < other.ranges_.size(); i++)
213  {
214  ranges_.push_back(other.ranges_[i]->clone());
215  }
216  return *this;
217  }
218 
219  size_t max() const
220  {
221  size_t max = 0;
222  for(size_t i = 0; i < ranges_.size(); i++)
223  {
224  size_t cur_max = ranges_[i]->max();
225 
226  if(cur_max > max)
227  {
228  max = cur_max;
229  }
230  }
231  return max;
232  }
233 
234 
236  {
237  for(size_t i = 0; i < ranges_.size(); i++)
238  {
239  delete ranges_[i];
240  }
241  }
242 
243  explicit Index_range(bool all_elements) :
244  ranges_(),
245  all_(all_elements)
246  {}
247 
248  size_t operator[](size_t i) const
249  {
250  if(all()) return i;
251 
252 
253  // iterate through range elements until the i-th index is found.
254  size_t range_i = 0;
255  for(; range_i < ranges_.size(); range_i++)
256  {
257  const size_t range_size = ranges_[range_i]->size();
258  if(i < range_size)
259  break;
260 
261  i -= range_size;
262  }
263 
264  if(range_i == ranges_.size())
265  {
266  // didn't find range that contains the index i
268  }
269 
270  return (*ranges_[range_i])[i];
271  }
272 
273  size_t size() const
274  {
275  if(all())
276  {
277  KJB_THROW_2(Runtime_error, "Can't know the size of an \"all\" range. Determining the size is the responsibility of the caller.");
278  }
279 
280  size_t total = 0;
281 
282  for(size_t i = 0; i < ranges_.size(); i++)
283  {
284  total += ranges_[i]->size();
285  }
286 
287  return total;
288  }
289 
290  bool all() const { return all_; }
291 
292 private:
294  class Range_element
295  {
296  public:
297  virtual ~Range_element() {}
298  virtual size_t operator[](size_t i) const = 0;
299  virtual size_t size() const = 0;
300  virtual Range_element* clone() const = 0;
301  virtual size_t max() const = 0;
302  };
303 
305  class Single_element : public Range_element
306  {
307  public:
308  Single_element(size_t i) : value_(i) {}
309 
310  virtual size_t operator[](size_t i) const
311  {
312  if(i == 0)
313  return value_;
314  KJB_THROW(Index_out_of_bounds);
315  }
316  virtual size_t size() const { return 1; }
317 
318 
319  virtual Range_element* clone() const
320  {
321  return new Single_element(*this);
322  }
323 
324  virtual size_t max() const { return value_; }
325  private:
326  size_t value_;
327  };
328 
329 
331  class Listing_element : public Range_element
332  {
333  public:
334  Listing_element(Int_vector v);
335 
336  Listing_element(std::vector<size_t> v) :
337  indices_(v.begin(), v.end())
338  {}
339 
340  Listing_element(std::list<size_t> v) :
341  indices_(v.begin(), v.end())
342  {}
343 
344  virtual Range_element* clone() const
345  {
346  return new Listing_element(*this);
347  }
348 
349  virtual size_t operator[](size_t i) const
350  {
351  return indices_[i];
352  }
353  virtual size_t size() const
354  {
355  return indices_.size();
356  }
357 
358  virtual size_t max() const
359  {
360  return *std::max_element(indices_.begin(), indices_.end());
361  }
362  private:
363  std::vector<size_t> indices_;
364 
365 
366  };
367 
369 
370  class Interval_element : public Range_element
371  {
372  static const int UNDEFINED_END_INDEX = INT_MAX;
373  public:
374 
375  Interval_element(int begin, int end, int interval) :
376  begin_(begin),
377  end_(end),
378  interval_(interval),
379  size_(0)
380  {
381  size_ = compute_size();
382  }
383 
384  Interval_element(int begin, End_type, int interval) :
385  begin_(begin),
386  end_(UNDEFINED_END_INDEX),
387  interval_(interval),
388  size_(0)
389  {
390  size_ = compute_size();
391  }
392 
393  virtual Range_element* clone() const
394  {
395  return new Interval_element(begin_, end_, interval_);
396  }
397 
398  virtual size_t operator[](size_t i) const
399  {
400  int result = begin_ + i * interval_;
401  if(interval_ > 0)
402  {
403  if(end_ < result)
404  KJB_THROW(Index_out_of_bounds);
405  }
406  else
407  {
408  if(result < end_)
409  KJB_THROW(Index_out_of_bounds);
410  }
411 
412  return result;
413  }
414 
415  virtual size_t size() const
416  {
417  if(end_ == UNDEFINED_END_INDEX)
418  KJB_THROW_2(Runtime_error, "Can't get size of interval with unknown end. Calling context must handle this.");
419 
420  return size_;
421  }
422 
423  virtual size_t max() const
424  {
425  if(end_ == UNDEFINED_END_INDEX)
426  KJB_THROW_2(Runtime_error, "Can't get max of interval with unknown end. Calling context must handle this.");
427 
428  KJB(UNTESTED_CODE());
429  return begin_ + interval_ * (size() - 1);
430  }
431 
432  protected:
433  size_t compute_size() const
434  {
435  int diff = end_ - begin_;
436  return diff / interval_ + 1;
437  }
438 
439  int begin_;
440  int end_;
441  int interval_;
442  size_t size_;
443  };
444 
446  class Matlab_range : public Interval_element
447  {
448  public:
449  Matlab_range(const std::string& str) :
450  Interval_element(0, 0, 1)
451  {
452  using namespace std;
453  // TODO: a real tokenizer would clean up this code
454 
455  // subsplit on colons
456  // convert colons to whitespce..
457  string tmp = str;
458  replace(tmp.begin(), tmp.end(), ':', ' ');
459 
460  // ...then split on whitespace
461  istringstream iss(tmp);
462 
463  // thow exceptions, except on eof
464 // iss.exceptions(istringstream::failbit | istringstream::badbit);
465  iss.exceptions(istringstream::failbit);
466 
467  int values[3];
468  int i = 0;
469  while(!iss.eof())
470  {
471  if(i >= 3) KJB_THROW_2(Runtime_error, "Parse error: token count exceeded 3.");
472 
473  iss >> values[i];
474  i++;
475  }
476 
477  switch(i)
478  {
479  case 0:
480  KJB_THROW_2(Runtime_error, "Parse error: no tokens found.");
481  case 1:
482  begin_ = values[0];
483  end_ = begin_;
484  interval_ = 1;
485  break;
486  case 2:
487  begin_ = values[0];
488  end_ = values[1];
489  interval_ = 1;
490  break;
491  case 3:
492  begin_ = values[0];
493  interval_ = values[1];
494  end_ = values[2];
495  break;
496  default:
497  KJB_THROW(Cant_happen);
498  }
499 
500 
501  if(interval_ == 0)
502  {
503  KJB_THROW_2(Illegal_argument, "Parse error: interval_ must be != 0.");
504  }
505 
506  if(interval_ > 0)
507  {
508  if(end_ < begin_)
509  KJB_THROW_2(Illegal_argument, "Parse error: sign(interval) != sign(end - begin).");
510  }
511  else
512  {
513  if(begin_ < end_)
514  KJB_THROW_2(Illegal_argument, "Parse error: sign(interval) != sign(end - begin).");
515 
516  }
517 
518  size_ = compute_size();
519  }
520 
521  virtual Range_element* clone() const
522  {
523  return new Matlab_range(*this);
524  }
525 
526  };
527 
528 private:
529  void init_from_str(const std::string& str)
530  {
531  using namespace std;
532 
533  if(str == ":")
534  {
535  all_ = true;
536  return;
537  }
538 
539  string tmp = str;
540 
541  // convert delimeters to whitespace
542  replace(tmp.begin(), tmp.end(), ',', ' ');
543  replace(tmp.begin(), tmp.end(), ';', ' ');
544 
545  // split on whitespace
546  istringstream iss(tmp);
547 
548  vector<string> tokens;
549  copy(istream_iterator<string>(iss),
550  istream_iterator<string>(),
551  back_inserter<std::vector<string> >(tokens));
552 
553  // convert tokens to Matlab ranges
554  ranges_.reserve(tokens.size());
555  for(size_t i = 0; i < tokens.size(); i++)
556  {
557  ranges_.push_back(new Matlab_range(tokens[i]));
558  }
559 
560  }
561 
562 protected:
563  std::vector<Range_element*> ranges_;
564  bool all_;
565 };
566 
567 inline void swap(Index_range& r1, Index_range& r2)
568 {
569  r1.swap(r2);
570 }
571 
575 inline std::istream& operator>>(std::istream& ist, Index_range& ir)
576 {
577  std::string line;
578  ist >> line;
579 
580  Index_range result(line);
581  result.swap(ir);
582 
583  return ist;
584 }
585 
588 } // namespace kjb
589 #endif
Object thrown when an index argument exceeds the size of a container.
Definition: l_exception.h:399
size_t max() const
Definition: l_index.h:219
Index_range(size_t index)
Definition: l_index.h:85
Index_range(size_t first, size_t end, size_t interval=1)
Definition: l_index.h:195
Definition: l_index.h:71
#define KJB(x)
Definition: l_util.h:9
size_t size() const
Definition: l_index.h:273
Index_range(const char *str)
Definition: l_index.h:112
#define KJB_THROW(ex)
Definition: l_exception.h:46
bool all() const
Definition: l_index.h:290
~Index_range()
Definition: l_index.h:235
Index_range(std::list< Int_type > v)
Definition: l_index.h:187
std::istream & operator>>(std::istream &ist, Detection_type &type)
Stream in an detection.
Definition: d_type.cpp:91
Index_range & operator=(const Index_range &other)
Definition: l_index.h:129
Index_range & concat(Index_range &other)
Definition: l_index.h:210
Index_range()
Definition: l_index.h:77
static const End_type END
Definition: l_index.h:72
This class implements vectors, in the linear-algebra sense, restricted to integer-valued elements...
Definition: l_int_vector.h:83
std::vector< size_t > expand() const
Definition: l_index.h:145
#define KJB_THROW_2(ex, msg)
Definition: l_exception.h:48
Index_range(bool all_elements)
Definition: l_index.h:243
void swap(kjb::Gsl_Multimin_fdf &m1, kjb::Gsl_Multimin_fdf &m2)
Swap two wrapped multimin objects.
Definition: gsl_multimin.h:693
Index_range(const std::string &str)
Definition: l_index.h:105
Index_range(const Index_range &src)
Definition: l_index.h:119
Definition: l_index.h:65
size_t operator[](size_t i) const
Definition: l_index.h:248
static const Index_range ALL
Definition: l_index.h:69
Index_range(int index)
Definition: l_index.h:95
Index_range(typename std::vector< Int_type > v)
Definition: l_index.h:177
get the indices of edges in each direction for i
Definition: APPgetLargeConnectedEdges.m:48
std::vector< Range_element * > ranges_
Definition: l_index.h:563
void swap(Index_range &other)
Definition: l_index.h:159
Support for error handling exception classes in libKJB.
Definition for the Int_vector class, a thin wrapper on the KJB Int_vector struct and its related func...
Index_range(size_t first, End_type end, size_t interval=1)
Definition: l_index.h:203
Object thrown when computation fails somehow during execution.
Definition: l_exception.h:321
bool all_
Definition: l_index.h:564