Ignore:
Timestamp:
Dec 1, 2010, 10:08:29 PM (12 years ago)
Author:
Peter
Message:

use compare(Segment, Segment) as comparator in SegmentSet? which allows simplifications in SegmentSet? code. Add some tests and docs.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/yat/utility/SegmentSet.h

    r2356 r2357  
    5151    /// value_type same as key_type
    5252    typedef key_type value_type;
     53
    5354    /// key_compare
    54     struct key_compare
     55    class key_compare : public std::binary_function<key_type, key_type, bool>
    5556    {
     57    public:
    5658      /// return true if lhs.begin() < rhs.begin()
    5759      bool operator()(const key_type& lhs, const key_type& rhs) const
    58       { return Compare()(lhs.begin(),rhs.begin()); }
     60      { return compare(lhs,rhs); }
    5961    };
     62
    6063    /// value_compare is same as key_compare
    6164    typedef key_compare value_compare;
     
    8184
    8285    /**
    83        \brief default constructor
     86       \brief creates a set with no segments
    8487     */
    8588    SegmentSet(void) {}
    8689
    8790    /**
     91       \return const iterator to first Segment
     92     */
     93    const_iterator begin(void) const { return set_.begin(); }
     94
     95    /**
    8896       \return iterator to first Segment
    8997     */
    90     const_iterator begin(void) const { return set_.begin(); }
    91 
    92     /**
    93        \return iterator to first Segment
    94      */
    9598    iterator begin(void) { return set_.begin(); }
    9699
    97100    /**
    98        \brief erases all the segments
     101       \brief erases all segments
    99102     */
    100103    void clear(void) { set_.clear(); }
    101104
    102105    /**
    103        \return 1 if there is a set that overlaps with \a vt
    104      */
    105     size_t count(const typename value_type::value_type& vt) const;
    106 
    107     /**
    108        \return \c true if SegmentSet is empty
     106       \return 1 if there is a set that overlaps with \a element
     107     */
     108    size_type count(const T& element) const;
     109
     110    /**
     111       \return \c true
    109112    */
    110113    bool empty(void) const { return set_.empty(); }
     
    124127       vt. If no Segment contains \a vt, end() is returned.
    125128     */
    126     const_iterator find(const typename value_type::value_type& vt) const;
     129    const_iterator find(const T& vt) const;
    127130
    128131    /**
     
    141144    /**
    142145       insert \a segment into set. If there is no gap between \a
    143        segment and neighboring segments the segments are merged. Note
    144        that this might also happen for non-overlapping segments, e.g.,
    145        [0,1) and [1,2) would be merged into [0,2).
     146       segment and neighboring segments the segments are merged.
    146147     */
    147148    const_iterator insert_merge(const value_type& segment);
     149
     150    /**
     151       \return Comparison functor to compare to segments
     152     */
     153    key_compare key_comp(void) const { return key_compare(Compare()); }
    148154
    149155    /**
     
    151157       \a segment or is greater than \a segment.
    152158     */
    153     const_iterator lower_bound(const value_type& segment) const;
     159    const_iterator lower_bound(const key_type& segment) const;
    154160
    155161    /**
    156162       \return number of segments in set
    157163     */
    158     size_t size(void) const { return set_.size(); }
     164    size_type size(void) const { return set_.size(); }
    159165
    160166    /**
     
    162168       \a segment.
    163169     */
    164     const_iterator upper_bound(const value_type& segment) const;
     170    const_iterator upper_bound(const key_type& segment) const;
     171
     172    /**
     173       \return Comparison functor to compare to segments
     174     */
     175    value_compare value_comp(void) const { return key_comp(); }
    165176
    166177  private:
     
    172183       overlap with \a segment.
    173184     */
    174     std::pair<iterator, iterator> overlap_range(const value_type& segment)
     185    // FIXME: can this be removed?
     186    std::pair<iterator, iterator> overlap_range(const key_type& segment)
    175187    {
    176188      iterator first = set_.lower_bound(segment);
     
    187199    }
    188200
    189 
    190     /**
    191        pair.first first (smallest) segment that overlaps with \a
    192        segment and pair.second first (smallest) segment that does not
    193        overlap with \a segment.
    194      */
    195     std::pair<const_iterator, const_iterator>
    196     overlap_range(const value_type& segment) const
    197     {
    198       const_iterator first = set_.lower_bound(segment);
    199       if (first!=begin()) {
    200         --first;
    201         if (compare(*first, segment))
    202           ++first;
    203       }
    204       const_iterator last = first;
    205       while (last!=end() && !compare(segment, *last))
    206         ++last;
    207       return std::make_pair(first, last);
    208     }
    209 
    210201    // using compiler generated copying
    211202    //SegmentSet(const SegmentSet&);
     
    214205
    215206  template<typename T, class Compare>
    216   size_t
    217   SegmentSet<T, Compare>::count(const typename value_type::value_type& vt) const
     207  typename SegmentSet<T, Compare>::size_type
     208  SegmentSet<T, Compare>::count(const T& vt) const
    218209  {
    219210    if (find(vt)==end())
     
    225216  template<typename T, class Compare>
    226217  typename SegmentSet<T, Compare>::const_iterator
    227   SegmentSet<T, Compare>::find(const typename value_type::value_type& vt) const
     218  SegmentSet<T, Compare>::find(const T& vt) const
    228219  {
    229220    Segment<T, Compare> segment(vt, vt);
    230     std::pair<const_iterator, const_iterator> p = overlap_range(segment);
    231     if (p.first == end())
     221    const_iterator iter = lower_bound(segment);
     222    Compare comp;
     223    if (iter==end() || comp(vt, iter->begin()))
    232224      return end();
    233     Compare comp;
    234     if (comp(vt, p.first->begin()))
    235         return end();
    236     return p.first;
     225    return iter;
    237226  }
    238227
     
    242231  SegmentSet<T, Compare>::insert(const value_type& segment)
    243232  {
    244     std::pair<iterator, iterator> p = overlap_range(segment);
    245     std::pair<typename SegmentSet<T, Compare>::iterator, bool> result;
    246     if (p.first==p.second) {
    247       result.first = set_.insert(p.first, segment);
    248       result.second = true;
    249       return result;
    250     }
    251     result.first = p.first;
    252     result.second = false;
    253     return result;
     233    return set_.insert(segment);
    254234  }
    255235
     
    260240  {
    261241    std::pair<iterator, iterator> p = overlap_range(segment);
    262     if (p.first==p.second) {
     242    if (p.first==p.second) { // no overlap between set and segment
    263243      return set_.insert(p.first, segment);
    264244    }
     245    /*
     246      p.first           last         p.second
     247      --->    --->      --->         --->
     248
     249       ----------------------->
     250           segment
     251     */
    265252    Compare comp;
    266     if (comp(segment.begin(), p.first->begin()))
    267       const_cast<value_type&>(*p.first).begin() = segment.begin();
    268 
    269     --p.second;
    270     const_cast<value_type&>(*p.first).end() =
    271       std::max(p.second->end(), segment.end(), comp);
    272     ++p.second;
    273     iterator begin(p.first);
    274     ++begin;
    275     set_.erase(begin, p.second);
    276     return p.first;
     253    iterator last=p.second;
     254    YAT_ASSERT(last==end() || compare(segment, *last));
     255    YAT_ASSERT(last!=begin()); // last!=p.first
     256    --last;
     257    YAT_ASSERT(compare_3way(segment, *last)==0);
     258
     259    Segment<T, Compare> segment2(std::min(p.first->begin(),segment.begin(),comp),
     260                                 std::max(last->end(),segment.end(),comp));
     261    set_.erase(p.first, p.second);
     262    // FIXME: use a better hint than end()
     263    return set_.insert(end(), segment2);
    277264  }
    278265
     
    280267  template<typename T, class Compare>
    281268  typename SegmentSet<T, Compare>::const_iterator
    282   SegmentSet<T, Compare>::lower_bound(const value_type& segment) const
     269  SegmentSet<T, Compare>::lower_bound(const key_type& segment) const
    283270  {
    284271    const_iterator result = set_.lower_bound(segment);
    285     if (result!=begin()) {
    286       --result;
    287       if (compare(*result, segment))
    288         ++result;
    289     }
     272    // result is larger or overlapping with segment (i.e.! result<segment)
     273    YAT_ASSERT(result==end() || !compare(*result,segment));
    290274    return result;
    291275  }
     
    294278  template<typename T, class Compare>
    295279  typename SegmentSet<T, Compare>::const_iterator
    296   SegmentSet<T, Compare>::upper_bound(const value_type& segment) const
    297   {
    298     const_iterator result = set_.lower_bound(segment);
    299     while (result!=end() && !compare(segment, *result))
    300       ++result;
     280  SegmentSet<T, Compare>::upper_bound(const key_type& segment) const
     281  {
     282    const_iterator result = set_.upper_bound(segment);
     283    // result is larger than segment
     284    YAT_ASSERT(result==end() || compare(segment, *result));
    301285    return result;
    302286  }
Note: See TracChangeset for help on using the changeset viewer.