source: trunk/yat/utility/Segment.h @ 3451

#ifndef theplu_yat_utility_segment
#define theplu_yat_utility_segment

// $Id: Segment.h 3451 2015-12-07 07:15:09Z 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 {

  /**
     \brief a class for a Segment or Interval

     A Segment is defined by its \a begin and \a end. The end is not
     included in the Segment, i.e., you could write the Segment as
     [begin, end). Type T must be comparable, optionally with a
     comparator Compare, which should implement <a
     href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
     Strict Weak Ordering.</a>.

     \since new in yat 0.7
   */
  template<typename T, class Compare = std::less<T> >
  class Segment
  {
  public:
    /**
       type the Segment holds
     */
    typedef T value_type;

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

    /**
       \brief Constructor

       Creates a segment [begin, end)
     */
    Segment(const T& begin, const T& end)
      : begin_(begin), end_(end) {}

    /**
       \return reference to first element in Segment
     */
    T& begin(void) { return begin_; }

    /**
       \return const reference to first element in Segment
     */
    const T& begin(void) const { return begin_; }

    /**
       \return reference to first element greater than Segment
     */
    T& end(void) { return end_; }

    /**
       \return const reference to first element greater than Segment
     */
    const T& end(void) const { return end_; }

  private:
    T begin_;
    T end_;

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


  /**
     \brief Inequality operator

     Inequality operator is defined via the operator< of T or in the
     general case Compare.

     \return true if Compare returns true for either when comparing
     lhs.begin() and rhs.begin() or when comparing lhs.end() and
     rhs.end().

     \relates Segment

     \since New in yat 0.14
  */
  template<typename T, class Compare>
  bool operator!=(const Segment<T, Compare>& lhs,
                  const Segment<T, Compare>& rhs)
  {
    Compare comp;
    return comp(lhs.begin(), rhs.begin()) ||  comp(rhs.begin(), lhs.begin())
      || comp(lhs.end(), rhs.end()) || comp(rhs.end(), lhs.end());
  }


  /**
     \return true if Compare returns false when comparing lhs.begin()
     and rhs.begin() as well as when comparing lhs.end() and
     rhs.end().

     \relates Segment

     \since New in yat 0.14
  */
  template<typename T, class Compare>
  bool operator==(const Segment<T, Compare>& lhs,
                  const Segment<T, Compare>& rhs)
  {
    return !(lhs!=rhs);
  }


  /**
     This function takes two Segment and compare them with comparator
     Compare. If all elements in \a lhs is less than all elements in
     \a rhs, \c true is returned. In other words, \c false is returned
     if \a rhs.begin() is less than \a lhs.end().

     The exception is if both \a lhs and \a rhs are empty Segment
     (i.e. begin equals end) and their begins and ends are equal, in
     which case \c false is returned. This exception implies that
     compare(x,x) always returns false.

     \relates Segment

     \since new in yat 0.7
   */
  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());
  }

  /**
     \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
     lhs) is \c true, and 0 otherwise

     \relates Segment

     \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)

     \since new in yat 0.7
   */
  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;
  }

  /**
     \return -1 if \a element is less than all elements in \a segment,
     0 if \a element overlaps with \a segment, and 1 otherwise.

     \relates Segment

     \since new in yat 0.7
   */
  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;
  }

  /**
     \return intersection of \a a and \a b. If \a a and \a b do not
     overlap an empty Section is returned (begin==end), but the exact
     value of begin is undefined.

     \relates Segment

     \since new in yat 0.7
   */
  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;
  }

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

}}}
#endif