source: soft/giet_vm/memo/include/libelfpp/dpp/interval_set @ 238

Last change on this file since 238 was 163, checked in by karaoui, 12 years ago

changing mover to memo
changing soft.bin to soft.elf
...

File size: 21.2 KB
Line 
1/* -*- c++ -*-
2
3   C++ Interval set template with boolean operations.
4
5   This file is part of the dpp library of C++ template classes
6
7   doc: http://diaxen.ssji.net/dpp/index.html
8   repo: https://www.ssji.net/svn/projets/trunk/libdpp
9
10   This program is free software: you can redistribute it and/or
11   modify it under the terms of the GNU Lesser General Public License
12   as published by the Free Software Foundation, either version 3 of
13   the License, or (at your option) any later version.
14
15   This program is distributed in the hope that it will be useful, but
16   WITHOUT ANY WARRANTY; without even the implied warranty of
17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18   Lesser General Public License for more details.
19
20   You should have received a copy of the GNU Lesser General Public
21   License along with this program.  If not, see
22   <http://www.gnu.org/licenses/>.
23
24   (c) 2008 Alexandre Becoulet <alexandre.becoulet@free.fr>
25
26*/
27
28#ifndef DPP_INTERVAL_SET_HH_
29#define DPP_INTERVAL_SET_HH_
30
31#include <cassert>
32#include <vector>
33#include <stdexcept>
34#include <limits>
35#include <ios>
36
37/** @file @module{Interval set} */
38
39namespace dpp {
40
41  template <typename X>
42  class interval_bound;
43
44  template <typename X>
45  class interval_bound_inclusive;
46
47  template <typename X>
48  class interval_bound_exclusive;
49
50  template <typename X>
51  class interval_scalar_limits;
52
53  template <typename X, class Bound = interval_bound<X> >
54  class interval;
55
56  template <typename X, class Bound = interval_bound<X>,
57            class Limits = interval_scalar_limits<X> >
58  class interval_set;
59
60//////////////////////////////////////////////////////////////////////
61//      interval bound classes
62//////////////////////////////////////////////////////////////////////
63
64  /** @short Default interval bound class
65      @module {Interval set}
66      @header dpp/interval_set
67
68      @This may be used with the @ref interval and @ref interval_set
69      classes to specify interval bounds inclusivity.
70
71      This class must be used to handles both inclusive and exclusive
72      interval bounds in the same interval set. This is the default
73      behavior and more generic choice but @ref interval_bound_inclusive
74      and @ref interval_bound_exclusive may be used instead to allow
75      further optimization of the code.
76  */
77
78  template <typename X>
79  class interval_bound
80  {
81    template <typename, class> friend class interval;
82    template <typename, class, class> friend class interval_set;
83
84    X _bound;
85    bool _inclusive;
86
87    interval_bound()
88    {
89    }
90
91    interval_bound(const X bound, bool inclusive)
92      : _bound(bound),
93        _inclusive(inclusive)
94    {
95    }
96
97    X bound() const
98    {
99      return _bound;
100    }
101
102    void set_bound(X b)
103    {
104      _bound = b;
105    }
106
107    bool inclusive() const
108    {
109      return _inclusive;
110    }
111
112    void set_inclusive(bool i)
113    {
114      _inclusive = i;
115    }
116
117    bool operator==(const interval_bound &b) const
118    {
119      return _bound == b._bound && _inclusive == b._inclusive;
120    }
121
122    static const bool default_inc = true;
123  };
124
125  /** @short Inclusive interval bound class
126      @module {Interval set}
127      @header dpp/interval_set
128
129      @This may be used with the @ref interval and @ref interval_set
130      classes to specify interval bounds inclusivity.
131
132      When used this specify @b inclusive bounds and @ref interval bound values
133      will always be considered as included in the interval.
134
135      @see interval_bound
136      @see interval_bound_exclusive
137  */
138
139  template <typename X>
140  class interval_bound_inclusive
141  {
142    template <typename, class> friend class interval;
143    template <typename, class, class> friend class interval_set;
144
145    X _bound;
146
147    interval_bound_inclusive()
148    {
149    }
150
151    interval_bound_inclusive(const X bound, bool inclusive)
152      : _bound(bound)
153    {
154    }
155
156    X bound() const
157    {
158      return _bound;
159    }
160
161    void set_bound(X b)
162    {
163      _bound = b;
164    }
165
166    bool inclusive() const
167    {
168      return true;
169    }
170
171    void set_inclusive(bool i)
172    {
173      assert(i);
174    }
175
176    bool operator==(const interval_bound_inclusive &b) const
177    {
178      return _bound == b._bound;
179    }
180
181    static const bool default_inc = true;
182  };
183
184  /** @short Exclusive interval bound class
185      @module {Interval set}
186      @header dpp/interval_set
187
188      @This may be used with the @ref interval and @ref interval_set
189      classes to specify interval bounds inclusivity.
190
191      When used this specify @b exclusive bounds and @ref interval bound values
192      will always be considered as excluded from the interval.
193
194      @see interval_bound
195      @see interval_bound_inclusive
196  */
197
198  template <typename X>
199  class interval_bound_exclusive
200  {
201    template <typename, class> friend class interval;
202    template <typename, class, class> friend class interval_set;
203
204    X _bound;
205
206    interval_bound_exclusive()
207    {
208    }
209
210    interval_bound_exclusive(X bound, bool inclusive)
211      : _bound(bound)
212    {
213    }
214
215    X bound() const
216    {
217      return _bound;
218    }
219
220    void set_bound(X b)
221    {
222      _bound = b;
223    }
224
225    bool inclusive() const
226    {
227      return false;
228    }
229
230    void set_inclusive(bool i)
231    {
232      assert(!i);
233    }
234
235    bool operator==(const interval_bound_exclusive &b) const
236    {
237      return _bound == b._bound;
238    }
239
240    static const bool default_inc = false;
241  };
242
243//////////////////////////////////////////////////////////////////////
244//      interval bound limits
245//////////////////////////////////////////////////////////////////////
246
247  /** @short Interval limits class for standard scalar types
248      @module {Interval set}
249      @header dpp/interval_set
250
251      This class specify upper and lower limits for scalar types and
252      is the default limits definition class used by the @ref interval_set class.
253
254      Similar classes must be defined when using the @ref interval_set
255      class with user defined non scalar types.
256  */
257
258  template <typename X>
259  class interval_scalar_limits
260  {
261  public:
262    /** @This returns interval maximum value */
263    static X upper()
264    {
265      if (!std::numeric_limits<X>::is_integer && std::numeric_limits<X>::has_infinity)
266        return std::numeric_limits<X>::infinity();
267      else
268        return std::numeric_limits<X>::max();
269    }
270
271    /** @This returns interval minimum value */
272    static X lower()
273    {
274      if (std::numeric_limits<X>::is_integer)
275        return std::numeric_limits<X>::min();
276      else
277        return -upper();
278    }
279  };
280
281//////////////////////////////////////////////////////////////////////
282//      interval (bound pair) class
283//////////////////////////////////////////////////////////////////////
284
285  /** @short Interval class
286      @module {Interval set}
287      @header dpp/interval_set
288      @main
289      @showvalue
290
291      @This defines an interval with its low and high bounds for a
292      given type and bound inclusivity.
293
294      @tt X can be a standard scalar type or an user defined type.
295
296      Acceptable values for @tt Bound template parameter are
297      @ref interval_bound (default), @ref interval_bound_inclusive and
298      @ref interval_bound_exclusive
299
300      This class is used as an @ref interval_set element.
301  */
302
303  template <typename X, class Bound>
304  class interval
305  {
306    template <typename, class, class> friend class interval_set;
307
308    Bound _low;
309    Bound _high;
310
311  public:
312
313    /** @This creates a non initialized interval object. */
314    interval()
315    {
316    }
317
318    /** @This creates a new {@tt low, @tt high } interval.
319        Bounds are inclusive by default when @ref interval_bound_exclusive is not used.
320        @alias interval_1
321    */
322    interval(const X low, const X high)
323      : _low(low, Bound::default_inc),
324        _high(high, Bound::default_inc)
325    {
326      assert(low < high || low == high);
327    }
328
329    /** @This creates a new {@tt low, @tt high } interval with specified inclusivity.
330        @alias interval_2
331     */
332    interval(const X low, bool low_inclusive,
333             const X high, bool high_inclusive)
334      : _low(low, low_inclusive),
335        _high(high, high_inclusive)     
336    {
337      assert(low < high || (low == high && low_inclusive && high_inclusive));
338    }
339
340    /** @This returns the low bound value. */
341    X low_bound() const
342    {
343      return _low.bound();
344    }
345
346    /** @This returns the high bound value. */
347    X high_bound() const
348    {
349      return _high.bound();
350    }
351
352    /** @This tests if low bound is inclusive. */
353    bool low_inclusive() const
354    {
355      return _low.inclusive();
356    }
357
358    /** @This tests if high bound is inclusive. */
359    bool high_inclusive() const
360    {
361      return _high.inclusive();
362    }
363
364    /** @This tests if specified value is included in interval range. */
365    bool contains(const X a) const
366    {
367      if (a == _low.bound())
368        return _low.inclusive();
369      else if (a == _high.bound())
370        return _high.inclusive();
371      else
372        return (!(a < _low.bound()) && a < _high.bound());
373    }
374
375    /** @This tests if two intervals are equals. */
376    bool operator==(const interval &i) const
377    {
378      return _low == i._low && _high == i._high;
379    }
380
381    /** @This prints an interval to stream in the form "@tt {[low, high]}".
382        Square brackets or parenthesis may be used depending on inclusivity.
383        @alias print
384    */
385    friend std::ostream & operator<<(std::ostream &o, const interval<X, Bound> &i)
386    {
387      o << (i.low_inclusive() ? "[" : "(") << i.low_bound()
388        << ", " << i.high_bound() << (i.high_inclusive() ? "]" : ")");
389      return o;
390    }
391  };
392
393
394//////////////////////////////////////////////////////////////////////
395//      interval set class
396//////////////////////////////////////////////////////////////////////
397
398  /** @short Interval set class
399      @module {Interval set}
400      @header dpp/interval_set
401      @main
402      @showvalue
403
404      @This may contain several @ref interval objects to act as an
405      interval set.
406
407      It provides several common boolean set operations like union,
408      intersection, complement and value inclusion test.
409
410      No extra value can be attached to intervals in set; it wouldn't
411      make sense because interval may be splited, joined, created or
412      destroyed by boolean operations.
413
414      @tt X can be a standard scalar type or an user defined type.
415      When a user defined type is used, a custom @tt Limits
416      class parameter must be provided to define upper and lower value
417      limits. The @ref interval_scalar_limits is used by default.
418
419      @tt Bound specify interval bounds inclusivity policy.
420      Acceptable values for @tt Bound template parameter are
421      @ref interval_bound (default), @ref interval_bound_inclusive and
422      @ref interval_bound_exclusive.
423  */
424
425  template <typename X, class Bound, class Limits>
426  class interval_set
427  {
428  public:
429
430    /** Associated @ref interval type */
431    typedef interval<X, Bound> interval_type;
432
433  private:
434    typedef std::vector<interval_type> set_container;
435
436  public:
437    /** Value type */
438    typedef X value_type;
439    /** @ref interval iterator */
440    typedef typename set_container::iterator iterator;
441    /** @ref interval const iterator */
442    typedef typename set_container::const_iterator const_iterator;
443    /** @ref interval set limits class */
444    typedef Limits limits_type;
445
446  private:
447
448    static void union_glob(const set_container &a, unsigned int &i,
449                           const set_container &b, unsigned int &j,
450                           set_container &c, unsigned int &k)
451    {
452      // skip all included intervals
453      while (j < b.size() && b[j]._high.bound() < c[k]._high.bound())
454        j++;
455
456      if (j < b.size())
457        {
458          // if interval end equal to next interval start
459          if (((c[k]._high.bound() == b[j]._low.bound())
460               && (c[k]._high.inclusive() || b[j]._low.inclusive()))
461          // or interval end greater than next interval start
462              || (b[j]._low.bound() < c[k]._high.bound()))
463            {
464              // join intervals
465              c[k]._high = b[j++]._high;
466              // terminal recursion
467              return union_glob(b, j, a, i, c, k);
468            }
469        }
470    }
471
472    static interval_set union_(const set_container &a, const set_container &b)
473    {
474      interval_set res;
475      set_container &c = res._set;
476
477      unsigned int i, j, k;
478
479      c.resize(a.size() + b.size());
480
481      for (i = j = k = 0; i < a.size() && j < b.size(); k++)
482        {
483          if (a[i]._low.bound() == b[j]._low.bound())
484            {
485              c[k] = a[i];
486              c[k]._low.set_inclusive(a[i]._low.inclusive() | b[j]._low.inclusive());
487              i++;
488              union_glob(a, i, b, j, c, k);
489            }
490          else if (a[i]._low.bound() < b[j]._low.bound())
491            {
492              c[k] = a[i++];
493              union_glob(a, i, b, j, c, k);
494            }
495          else // if (a[i]._low._bound > b[j]._low._bound)
496            {
497              c[k] = b[j++];
498              union_glob(b, j, a, i, c, k);
499            }
500        }
501
502      for (; i < a.size(); i++, k++)
503        c[k] = a[i];
504
505      for (; j < b.size(); j++, k++)
506        c[k] = b[j];
507
508      res._set.resize(k);
509
510      return res;
511    }
512
513    static bool pair_intersect(const interval_type &a, const interval_type &b, interval_type &r)
514    {
515      if (b._low.bound() < a._low.bound())
516        r._low = a._low;
517      else // if (a._low.bound() <= b._low.bound())
518        {
519          r._low = b._low;
520          if (!a._low.inclusive() && a._low.bound() == b._low.bound())
521            r._low.set_inclusive(false);
522        }
523
524      if (a._high.bound() < b._high.bound())
525        r._high = a._high;
526      else // if (b._high.bound() <= a._high.bound())
527        {
528          r._high = b._high;
529          if (!a._high.inclusive() && a._high.bound() == b._high.bound())
530            r._high.set_inclusive(false);
531        }
532
533      if (r._high.bound() == r._low.bound())
534        return r._low.inclusive() && r._high.inclusive();
535      else
536        return(r._low.bound() < r._high.bound());
537    }
538
539    static interval_set intersection(const set_container &a, const set_container &b)
540    {
541      interval_set res;
542      set_container &c = res._set;
543
544      unsigned int i, j, k;
545
546      c.resize(a.size() + b.size());
547
548      for (i = j = k = 0; i < a.size() && j < b.size(); )
549        {
550          if (b[j]._high.bound() < a[i]._low.bound())
551            while (j < b.size() && b[j]._high.bound() < a[i]._low.bound())
552              j++;
553          else if (a[i]._high.bound() < b[j]._low.bound())
554            while (i < a.size() && a[i]._high.bound() < b[j]._low.bound())
555              i++;
556          else 
557            {
558              if (pair_intersect(a[i], b[j], c[k]))
559                k++;
560
561              if (a[i]._high.bound() == b[j]._high.bound())
562                j++, i++;
563              else if (a[i]._high.bound() < b[j]._high.bound())
564                i++;
565              else
566                j++;
567            }
568        }
569
570      res._set.resize(k);
571
572      return res;
573    }
574
575    static interval_set complement(const set_container &a)
576    {
577      if (a.empty())
578        return interval_set(true);
579
580      unsigned int i, j;
581      interval_set res;
582      set_container &r = res._set;
583
584      if (a[0]._low.bound() == limits_type::lower() && a[0]._low.inclusive())
585        {
586          r.resize(a.size());
587          r[0]._low.set_bound(a[0]._high.bound());
588          r[0]._low.set_inclusive(!a[0]._high.inclusive());
589          j = 1;
590        }
591      else
592        {
593          r.resize(a.size() + 1);
594          r[0]._low.set_bound(limits_type::lower());
595          r[0]._low.set_inclusive(true);
596          j = 0;
597        }
598
599      for (i = 0; i < r.size() - 1; i++, j++)
600        {
601          r[i]._high.set_bound(a[j]._low.bound());
602          r[i]._high.set_inclusive(!a[j]._low.inclusive());
603          r[i+1]._low.set_bound(a[j]._high.bound());
604          r[i+1]._low.set_inclusive(!a[j]._high.inclusive());
605        }
606
607      assert(j >= 1);
608
609      if (a[j-1]._high.bound() == limits_type::upper() && a[j-1]._high.inclusive())
610        {
611          r.pop_back();
612        }
613      else
614        {
615          r[i]._high.set_bound(limits_type::upper());
616          r[i]._high.set_inclusive(true);
617        }
618
619      return res;
620    }
621
622    unsigned int dicho(const X a) const
623    {
624      unsigned int min_idx = 0;
625      unsigned int max_idx = _set.size();
626
627      assert(!_set.empty());
628
629      // dichotomic search
630      while (max_idx - min_idx > 1)
631        {
632          unsigned int p = (max_idx + min_idx) / 2;
633
634          if (a < _set[p]._low.bound())
635            max_idx = p;
636          else
637            min_idx = p;
638        }
639
640      return min_idx;
641    }
642
643  public:
644
645    /** @This creates an empty interval set */
646    interval_set()
647    {
648    }
649
650    /** @This creates an empty or whole interval set */
651    interval_set(bool whole)
652    {
653      if (whole)
654        _set.push_back(interval_type(limits_type::lower(),
655                                     limits_type::upper()));
656    }
657
658    /** @This creates an interval set including values in given @ref interval */
659    interval_set(const interval_type &i)
660    {
661      _set.push_back(i);
662    }
663
664    /** @This creates an interval set including values in [@tt low, @tt high] range.
665        @see interval::__interval_1__ */
666    interval_set(const X low, const X high)
667    {
668      _set.push_back(interval_type(low, high));
669    }
670
671    /** @This creates an interval set including values in range {@tt low, @tt high} with given inclusivity
672        @see interval::__interval_2__ */
673    interval_set(const X low, bool low_inclusive,
674                 const X high, bool high_inclusive)
675    {
676      _set.push_back(interval_type(low, low_inclusive, high, high_inclusive));
677    }
678
679    /** @This resets the interval set to empty state */
680    void clear()
681    {
682      _set.clear();
683    }
684
685    /** @This tests if interval set is empty */
686    bool empty()
687    {
688      return _set.empty();
689    }
690
691    /** @This tests if interval set is whole */
692    bool whole()
693    {
694      return (!_set.empty()
695              && _set.back()._low.bound() == limits_type::lower()
696              && _set.back()._high.bound() == limits_type::upper());
697    }
698
699    /** @This returns a new interval set being the union of the two interval sets */
700    interval_set operator|(const interval_set &i) const
701    {
702      return union_(_set, i._set);
703    }
704
705    /** @This replaces the current interval set by the union with given interval set */
706    interval_set & operator|=(const interval_set &i)
707    {
708      return *this = *this | i; // FIXME write optimized version
709    }
710
711    /** @This replaces the current interval set by the union with given interval */
712    interval_set & operator|=(const interval_type &i)
713    {
714      return *this = *this | interval_set(i); // FIXME write optimized version
715    }
716
717    /** @This returns a new interval set being the intersection of the two interval sets */
718    interval_set operator&(const interval_set &i) const
719    {
720      return intersection(_set, i._set);
721    }
722
723    /** @This replaces the current interval set by the intersection with given interval set */
724    interval_set & operator&=(const interval_set &i)
725    {
726      return *this = *this & i; // FIXME write optimized version
727    }
728
729    /** @This replaces the current interval set by the intersection with given interval */
730    interval_set & operator&=(const interval_type &i)
731    {
732      return *this = *this & interval_set(i); // FIXME write optimized version
733    }
734
735    /** @This returns the complementary interval set */
736    interval_set operator~() const
737    {
738      return complement(_set);
739    }
740
741    /** @This returns a new interval set being the exclusive or of the two interval sets */
742    interval_set operator^(const interval_set &i) const
743    {
744      return (*this & ~i) | (~*this & i);
745    }
746
747    /** @This replaces the current interval set by the exclusive or with given interval set */
748    interval_set & operator^=(const interval_set &i)
749    {
750      return *this = *this ^ i;
751    }
752
753    /** @This replaces the current interval set by the exclusive or with given interval */
754    interval_set & operator^=(const interval_type &i)
755    {
756      return *this = *this ^ interval_set(i);
757    }
758
759    /** @This returns the interval which contains the given value.
760        This throws a @ref std::out_of_range exception if no matching
761        interval is available in set. */
762    interval_type get_interval(const X a) const throw (std::out_of_range)
763    {
764      if (_set.empty())
765        throw std::out_of_range("empty interval_set");
766
767      unsigned int p = dicho(a);
768
769      if (!_set[p].contains(a))
770        throw std::out_of_range("no matching interval found");
771
772      return _set[p];
773    }
774
775    /** @This tests if specified value is included in interval set
776        @alias contains_1
777     */
778    bool contains(const X a) const
779    {
780      return !_set.empty() && _set[dicho(a)].contains(a);
781    }
782
783    /** @This tests if specified interval set is included in interval set */
784    bool contains(const interval_set &i) const
785    {
786      return (i & *this) == i; // FIXME write optimized version
787    }
788
789    /** @This is a shortcut for @ref __contains_1__ */
790    bool operator[](const X a) const
791    {
792      return contains(a);
793    }
794
795    /** @This tests if two interval sets are equals */
796    bool operator==(const interval_set &i) const
797    {
798      if (_set.size() != i._set.size())
799        return false;
800
801      for (unsigned int j = 0; j < _set.size(); j++)
802        if (!(_set[j] == i._set[j]))
803          return false;
804
805      return true;
806    }
807
808    /** @This returns an interval set iterator. It can be
809        used to iterator over all @ref interval contained in the set. */
810    iterator begin()
811    {
812      return _set.begin();
813    }
814
815    /** @This returns an interval set end iterator. */
816    iterator end()
817    {
818      return _set.end();
819    }
820
821    /** @This returns an interval set const iterator. It can be
822        used to iterator over all @ref interval contained in the set. */
823    const_iterator begin() const
824    {
825      return _set.begin();
826    }
827
828    /** @This returns an interval set end iterator. */
829    const_iterator end() const
830    {
831      return _set.end();
832    }
833
834    /** @This prints interval set to stream by iterating over all @ref interval
835        present in the set using @ref interval::__print__
836    */
837    friend std::ostream & operator<<(std::ostream &o, const interval_set<X, Bound, Limits> &is)
838    {
839      for (typename interval_set<X, Bound, Limits>::const_iterator i = is.begin(); i != is.end(); i++)
840        o << *i;
841      return o;
842    }
843
844  private:
845
846    set_container _set;
847  };
848
849}
850
851#endif
852
Note: See TracBrowser for help on using the repository browser.