source: trunk/yat/utility/SegmentTree.h @ 2360

#ifndef theplu_yat_utility_segment_tree
#define theplu_yat_utility_segment_tree

// $Id: SegmentTree.h 2360 2010-12-04 01:04:45Z 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>

namespace theplu {
namespace yat {
namespace utility {

  /**
     \brief Base Class for SegmentSet and SegmentMap

     - Container: underlying container (set or map)
     - Compare: functor comparing elements (same as in Segment)
     - Value2Key: functor translating a \c const_reference to \c
       key_type (or \c const&)
   */
  template<class Container, class Compare, class Value2Key>
  class SegmentTree 
  {
  public:
    /// \brief key type
    typedef typename Container::key_type key_type;
    /// \brief value type
    typedef typename Container::value_type value_type;
    /// \brief element type
    typedef typename key_type::value_type element_type;

    /// \brief key compare
    typedef typename Container::key_compare key_compare;
    /// \brief calue compare
    typedef typename Container::value_compare value_compare;
    /// \brief element compare
    typedef Compare element_compare;

    /// \brief pointer
    typedef typename Container::pointer pointer;
    /// \brief reference
    typedef typename Container::reference reference;
    /// \brief const reference
    typedef typename Container::const_reference const_reference;
    /// \brief size_type
    typedef typename Container::size_type size_type;
    /// \brief difference_type
    typedef typename Container::difference_type difference_type;
    /// \brief iterator
    typedef typename Container::iterator iterator;
    /// \brief const_iterator
    typedef typename Container::const_iterator const_iterator;

    /**
       \brief creates a container with no segments
     */
    SegmentTree(void) {}

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

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

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

    /**
       \return 1 if there is a set that overlaps with \a element
     */
    size_type count(const element_type& element) const;

    /**
       \return \c true 
    */
    bool empty(void) const { return container_.empty(); }

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

    /**
       \return end of set
     */
    iterator end(void) { return container_.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 element_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.
     */
    const_iterator insert_merge(const value_type& segment);

    /**
       \return Comparison functor to compare to segments
     */
    key_compare key_comp(void) const 
    { 
      return key_compare(compare);
    }

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

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

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

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

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

    /**
       \return Comparison functor to compare to segments
     */
    value_compare value_comp(void) const { return key_comp(); }

  protected:
    /// underlying container
    Container container_;

    /**
       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 key_type& segment) 
    {
      iterator first = container_.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);
    }

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

  template<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::size_type 
  SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
  {
    if (find(element)==end())
      return 0;
    return 1;
  }


  template<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::const_iterator 
  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
  {
    const_iterator iter = lower_bound(vt);
    element_compare comp;
    //    if (iter==end() || comp(vt, iter->begin()))
    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
      return end();
    return iter;
  }


  template<typename T, class Compare, class Value2Key>
  std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool> 
  SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
  {
    return container_.insert(segment);
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::iterator
  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
  {
    key_type segment(element, element);
    iterator result = container_.lower_bound(segment);
    // result is larger or overlapping with segment (i.e.! result<segment)
    YAT_ASSERT(result==end() 
               || !compare(Value2Key()(*result),segment));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::const_iterator
  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
  {
    key_type segment(element, element);
    const_iterator result = container_.lower_bound(segment);
    // result is larger or overlapping with segment (i.e.! result<segment)
    YAT_ASSERT(result==end() 
               || !compare(Value2Key()(*result),segment));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::iterator
  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
  {
    key_type segment(element, element);
    iterator result = container_.upper_bound(segment);
    Compare comp;
    if (result==end() || comp(element, result->begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, *result));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::const_iterator
  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
  {
    Segment<T, Compare> segment(element, element);
    const_iterator result = container_.upper_bound(segment);
    Compare comp;
    if (result==end() || comp(element, result->begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, *result));
    return result;
  }

}}}
#endif