SegmentTree.h

#ifndef theplu_yat_utility_segment_tree
#define theplu_yat_utility_segment_tree

// $Id: SegmentTree.h 2681 2012-01-12 21:41:15Z peter $

/*
  Copyright (C) 2010, 2011, 2012 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 {

  template<class Container, class Compare, class Value2Key>
  class SegmentTree
  {
  public:
    typedef typename Container::key_type key_type;

    typedef typename Container::value_type value_type;

    typedef typename key_type::value_type element_type;

    typedef typename Container::key_compare key_compare;
    typedef typename Container::value_compare value_compare;
    typedef Compare element_compare;

    typedef typename Container::pointer pointer;
    typedef typename Container::reference reference;
    typedef typename Container::const_reference const_reference;
    typedef typename Container::size_type size_type;
    typedef typename Container::difference_type difference_type;
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;

    SegmentTree(void) {}

    virtual ~SegmentTree(void) {}

    const_iterator begin(void) const { return container_.begin(); }

    iterator begin(void) { return container_.begin(); }

    void clear(void) { container_.clear(); }

    size_type count(const element_type& element) const;

    bool empty(void) const { return container_.empty(); }

    const_iterator end(void) const { return container_.end(); }

    iterator end(void) { return container_.end(); }

    void erase(iterator first, iterator last) { container_.erase(first, last);}

    void erase(iterator pos) { container_.erase(pos); }

    iterator find(const element_type& element);

    const_iterator find(const element_type& vt) const;

    std::pair<iterator, bool> insert(const value_type& value);

    key_compare key_comp(void) const
    {
      return key_compare(compare);
    }

    iterator lower_bound(const element_type& element);

    const_iterator lower_bound(const element_type& element) const;

    size_type size(void) const { return container_.size(); }

    iterator upper_bound(const element_type& element);

    const_iterator upper_bound(const element_type& element) const;

    value_compare value_comp(void) const { return key_comp(); }

  protected:
    Container container_;

    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<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::iterator
  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
  {
    iterator iter = lower_bound(vt);
    element_compare comp;
    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;
    Value2Key value2key;
    if (result==end() || comp(element, value2key(*result).begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, value2key(*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<element_type, Compare> segment(element, element);
    const_iterator result = container_.upper_bound(segment);
    Compare comp;
    Value2Key value2key;
    if (result==end() || comp(element, value2key(*result).begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
    return result;
  }

}}}
#endif