source: trunk/yat/utility/SegmentSet.h @ 2356

#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 2356 2010-11-30 23:15:41Z peter $

/*
  Copyright (C) 2010 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "Segment.h"
#include "yat_assert.h"

#include <algorithm>
#include <functional>
#include <set>

namespace theplu {
namespace yat {
namespace utility {

  /**
     \brief a set of Segments

     A container that holds a set of Segment. The Segments cannot overlap.

     \since new in yat 0.7
   */
  template<typename T, class Compare = std::less<T> >
  class SegmentSet
  {
  public:
    /// element type
    typedef T element_type;
    /// key_type
    typedef Segment<element_type, Compare> key_type;
    /// value_type same as key_type
    typedef key_type value_type;
    /// key_compare
    struct key_compare
    {
      /// return true if lhs.begin() < rhs.begin()
      bool operator()(const key_type& lhs, const key_type& rhs) const
      { return Compare()(lhs.begin(),rhs.begin()); }
    };
    /// value_compare is same as key_compare
    typedef key_compare value_compare;

  private:
    typedef std::set<value_type, value_compare> Set_;

  public:
    /// \brief pointer
    typedef typename Set_::pointer pointer;
    /// \brief reference
    typedef typename Set_::reference reference;
    /// \brief const_reference
    typedef typename Set_::const_reference const_reference;
    /// \brief size_type
    typedef typename Set_::size_type size_type;
    /// \brief difference_type
    typedef typename Set_::difference_type difference_type;
    /// \brief iterator
    typedef typename Set_::iterator iterator;
    /// \brief const_iterator
    typedef typename Set_::const_iterator const_iterator;

    /**
       \brief default constructor
     */
    SegmentSet(void) {}

    /**
       \return iterator to first Segment
     */
    const_iterator begin(void) const { return set_.begin(); }

    /**
       \return iterator to first Segment
     */
    iterator begin(void) { return set_.begin(); }

    /**
       \brief erases all the segments
     */
    void clear(void) { set_.clear(); }

    /**
       \return 1 if there is a set that overlaps with \a vt
     */
    size_t count(const typename value_type::value_type& vt) const;

    /**
       \return \c true if SegmentSet is empty
    */
    bool empty(void) const { return set_.empty(); }

    /**
       \return end of set
     */
    const_iterator end(void) const { return set_.end(); }

    /**
       \return end of set
     */
    iterator end(void) { return set_.end(); }

    /**
       \return an iterator pointing to the Segment that contains \a
       vt. If no Segment contains \a vt, end() is returned.
     */
    const_iterator find(const typename value_type::value_type& vt) const;

    /**
       \brief insert set 

       if \a segment does not overlap with any segment in set, insert
       segment; otherwise do nothing.

       \return a pair where pair.first points to the added \a segment
       or if \a segment was not added it points to a Segment in set
       that overlaps with \a segment; pair.second is true if \a
       segment was added.
     */
    std::pair<iterator, bool> insert(const value_type& segment);

    /**
       insert \a segment into set. If there is no gap between \a
       segment and neighboring segments the segments are merged. Note
       that this might also happen for non-overlapping segments, e.g.,
       [0,1) and [1,2) would be merged into [0,2).
     */
    const_iterator insert_merge(const value_type& segment);

    /**
       \return iterator pointing to first segment that overlaps with
       \a segment or is greater than \a segment.
     */
    const_iterator lower_bound(const value_type& segment) const;

    /**
       \return number of segments in set
     */
    size_t size(void) const { return set_.size(); }

    /**
       \return iterator pointing to first segment that is greater than
       \a segment.
     */
    const_iterator upper_bound(const value_type& segment) const;

  private:
    Set_ set_;
    
    /**
       pair.first first (smallest) segment that overlaps with \a
       segment and pair.second first (smallest) segment that does not
       overlap with \a segment.
     */
    std::pair<iterator, iterator> overlap_range(const value_type& segment) 
    {
      iterator first = set_.lower_bound(segment);
      if (first!=begin()) {
        --first;
        if (compare(*first, segment))
          ++first;
      }
      iterator last = first;
      while (last!=end() && !compare(segment, *last))
        ++last;
      YAT_ASSERT(last==end() || compare(segment, *last));
      return std::make_pair(first, last);
    }


    /**
       pair.first first (smallest) segment that overlaps with \a
       segment and pair.second first (smallest) segment that does not
       overlap with \a segment.
     */
    std::pair<const_iterator, const_iterator> 
    overlap_range(const value_type& segment) const
    {
      const_iterator first = set_.lower_bound(segment);
      if (first!=begin()) {
        --first;
        if (compare(*first, segment))
          ++first;
      }
      const_iterator last = first;
      while (last!=end() && !compare(segment, *last))
        ++last;
      return std::make_pair(first, last);
    }

    // using compiler generated copying
    //SegmentSet(const SegmentSet&);
    //SegmentSet& operator=(const SegmentSet&);
  };

  template<typename T, class Compare>
  size_t 
  SegmentSet<T, Compare>::count(const typename value_type::value_type& vt) const
  {
    if (find(vt)==end())
      return 0;
    return 1;
  }


  template<typename T, class Compare>
  typename SegmentSet<T, Compare>::const_iterator 
  SegmentSet<T, Compare>::find(const typename value_type::value_type& vt) const
  {
    Segment<T, Compare> segment(vt, vt);
    std::pair<const_iterator, const_iterator> p = overlap_range(segment);
    if (p.first == end())
      return end();
    Compare comp;
    if (comp(vt, p.first->begin()))
        return end();
    return p.first;
  }


  template<typename T, class Compare>
  std::pair<typename SegmentSet<T, Compare>::iterator, bool> 
  SegmentSet<T, Compare>::insert(const value_type& segment)
  {
    std::pair<iterator, iterator> p = overlap_range(segment);
    std::pair<typename SegmentSet<T, Compare>::iterator, bool> result;
    if (p.first==p.second) {
      result.first = set_.insert(p.first, segment);
      result.second = true;
      return result;
    }
    result.first = p.first;
    result.second = false;
    return result;
  }


  template<typename T, class Compare>
  typename SegmentSet<T, Compare>::const_iterator
  SegmentSet<T, Compare>::insert_merge(const value_type& segment)
  {
    std::pair<iterator, iterator> p = overlap_range(segment);
    if (p.first==p.second) {
      return set_.insert(p.first, segment);
    }
    Compare comp;
    if (comp(segment.begin(), p.first->begin()))
      const_cast<value_type&>(*p.first).begin() = segment.begin();

    --p.second;
    const_cast<value_type&>(*p.first).end() = 
      std::max(p.second->end(), segment.end(), comp);
    ++p.second;
    iterator begin(p.first);
    ++begin;
    set_.erase(begin, p.second); 
    return p.first;
  }


  template<typename T, class Compare>
  typename SegmentSet<T, Compare>::const_iterator
  SegmentSet<T, Compare>::lower_bound(const value_type& segment) const
  {
    const_iterator result = set_.lower_bound(segment);
    if (result!=begin()) {
      --result;
      if (compare(*result, segment))
        ++result;
    }
    return result;
  }


  template<typename T, class Compare>
  typename SegmentSet<T, Compare>::const_iterator
  SegmentSet<T, Compare>::upper_bound(const value_type& segment) const
  {
    const_iterator result = set_.lower_bound(segment);
    while (result!=end() && !compare(segment, *result))
      ++result;
    return result;
  }

}}}
#endif