Segment.h

#ifndef theplu_yat_utility_segment
#define theplu_yat_utility_segment

// $Id: Segment.h 2358 2010-12-02 06:58:40Z 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 "yat_assert.h"

#include <algorithm>
#include <functional>

namespace theplu {
namespace yat {
namespace utility {

  template<typename T, class Compare = std::less<T> >
  class Segment
  {
  public:
    typedef T value_type;

    Segment(void) {}

    Segment(const T& begin, const T& end)
      : begin_(begin), end_(end) {}

    T& begin(void) { return begin_; }

    const T& begin(void) const { return begin_; }

    T& end(void) { return end_; }

    const T& end(void) const { return end_; }
    
  private:
    T begin_;
    T end_;
    
    // using compiler generated copying
    //Segment(const Segment&);
    //Segment& operator=(const Segment&);
  };

  template<typename T, class Compare>
  bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
  {
    Compare c;
    // begin <= end
    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
    // take care of case when both sides are zero segments
    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
      return c(lhs.begin(), rhs.begin());
    }

    return ! c(rhs.begin(), lhs.end());
  }

  template<typename T, class Compare>
  int compare_3way(const Segment<T, Compare>& lhs, 
                   const Segment<T, Compare>& rhs)
  {
    if (compare(lhs, rhs))
      return -1;
    if (compare(rhs, lhs))
      return 1;
    return 0;
  }

  template<typename T, class Compare>
  int compare_3way(const T& element, 
                   const Segment<T, Compare>& segment)
  {
    Compare comp;
    if (comp(element, segment.begin()))
      return -1;
    if (comp(element, segment.end()))
      return 0;
    return 1;
  }

  template<typename T, class Compare>
  Segment<T, Compare> intersection(const Segment<T, Compare>& a, 
                                   const Segment<T, Compare>& b)
  {
    Compare comp;
    Segment<T, Compare> result;

    result.begin() = std::max(a.begin(), b.begin(), comp);
    // the first max is needed in case a and b don't overlap
    result.end() = std::max(result.begin(), 
                            std::min(a.end(), b.end(), comp),
                            comp);
    return result;
  }

  template<typename T, class Compare>
  struct SegmentCompare : 
    public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
  {
    bool operator()(const Segment<T, Compare>& lhs, 
                    const Segment<T, Compare>& rhs) const
    { return compare(lhs, rhs); }
  };

}}}
#endif