Changeset 3344


Ignore:
Timestamp:
Nov 6, 2014, 1:09:32 PM (7 years ago)
Author:
Peter
Message:

new function SegmentSet::insert_merge with hint. refs #818

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/test/segment.cc

    r2919 r3344  
    164164  if (!suite.add(set.find(0)!=set.end()))
    165165    suite.err() << "error: set.find(0): expected not end()\n";
    166 } 
     166}
    167167
    168168void test_count(test::Suite& suite)
     
    198198  if (!suite.add(set.size()==1))
    199199    suite.err() << "error: set.size(): " << set.size() << " expected 1\n";
     200  set.insert_merge(set.end(), Segment<double>(200, 1000));
    200201}
    201202
  • trunk/yat/utility/SegmentSet.h

    r3337 r3344  
    6666      std::pair<typename me::iterator, typename me::iterator> p =
    6767        this->overlap_range(segment);
     68      return insert_merge(p, segment);
     69    }
     70
     71    /**
     72       \brief insert with a hint
     73
     74       Similar to insert_merge(1) but \a hint help to find where to
     75       insert \a segment. For the \a hint to be useful, \a segment
     76       should not be greater than element hint points to and not
     77       smaller than element --hint points to.
     78
     79       \since New in yat 0.13
     80     */
     81    typename me::iterator insert_merge(typename me::iterator hint,
     82                                       const typename me::value_type& segment)
     83    {
     84      std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
     85      if (this->container_.empty())
     86        return insert_merge(p, segment);
     87
     88      //.If hint points to an element that is less than segment, hint
     89      //is no good and we ignore the hint.
     90      if (hint!=this->end() && compare(*hint, segment))
     91        return insert_merge(segment);
     92
     93      if (p.first!=this->begin()) {
     94        --p.first;
     95        // If --hint point to an element greater than segment, hint is
     96        // no good.
     97        if (compare(segment, *p.first))
     98          return insert_merge(segment);
     99        // find first element that is smaller than segment
     100        while (p.first!=this->begin() && !compare(*p.first, segment))
     101          --p.first;
     102        YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment));
     103        YAT_ASSERT(p.first!=this->end());
     104        if (compare(*p.first, segment))
     105          ++p.first;
     106      }
     107
     108      // find first element greater than segment
     109      while (p.second!=this->end() && !compare(segment, *p.second))
     110        ++p.second;
     111
     112      return insert_merge(p, segment);
     113    }
     114
     115  private:
     116    // used by public functions insert_merge.
     117    //
     118    // p.first points to the first segment that overlaps with \a segment or
     119    // is greater than segment.
     120    // p.second points to the first segment that is greater than \a segment
     121    typename me::const_iterator
     122    insert_merge(const std::pair<typename me::iterator,
     123                                 typename me::iterator>& p,
     124                 const typename me::value_type& segment)
     125    {
     126      YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
     127      YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
    68128      if (p.first==p.second) { // no overlap between set and segment
    69129        return this->container_.insert(p.first, segment);
     
    91151    }
    92152
    93   private:
    94153    // using compiler generated copying
    95154    //SegmentSet(const SegmentSet&);
Note: See TracChangeset for help on using the changeset viewer.