RangeIntersector.hpp

Go to the documentation of this file.

// Copyright 2010 Complete Genomics, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License"); you
// may not use this file except in compliance with the License. You
// may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
// implied. See the License for the specific language governing
// permissions and limitations under the License.

#ifndef CGATOOLS_UTIL_RANGE_INTERSECTOR_HPP_
#define CGATOOLS_UTIL_RANGE_INTERSECTOR_HPP_ 1


#include "cgatools/core.hpp"
#include "cgatools/util/Exception.hpp"

#include <functional>
#include <map>
#include <vector>

namespace cgatools { namespace util {

    template < class TRange, class TValue, class Overlap, class Less = std::less<TRange> >
    class RangeIntersector
    {
    public:
        typedef std::map< TRange, TValue, Less > MapType;

        RangeIntersector(const Overlap& overlap = Overlap(),
                         const Less& less = Less())
            : overlap_(overlap),
              less_(less)
        {
        }

        void put(const TRange& range, const TValue& value)
        {
            // Binary search the trees to find the first tree that does
            // not overlap with range.
            size_t lo = 0, hi = mtrees_.size();
            while (lo<hi)
            {
                size_t mid = (lo+hi)/2;
                MapType& tree = mtrees_[mid];

                typename MapType::iterator iter = tree.lower_bound(range);
                if (iter != tree.end() && overlap_(iter->first, range))
                {
                    lo = mid+1;
                    continue;
                }
                if (iter != tree.begin() && overlap_( (--iter)->first, range ))
                {
                    lo = mid+1;
                    continue;
                }

                // No overlap in this tree.
                hi = mid;
            }

            if (lo < mtrees_.size())
            {
                MapType& tree = mtrees_[lo];
                std::pair<typename MapType::iterator, bool> result =
                    tree.insert(std::make_pair(range, value));
                CGA_ASSERT(result.second);
                return;
            }

            // Overlap in all trees. Create new tree.
            mtrees_.push_back(MapType(less_));
            std::pair<typename MapType::iterator, bool> result =
                mtrees_.back().insert(std::make_pair(range, value));
            CGA_ASSERT(result.second);
        }

        void intersect(const TRange& range,
                       std::vector< typename MapType::const_iterator >& result) const
        {
            result.clear();
            for(size_t ii=0; ii<mtrees_.size(); ii++)
            {
                const MapType& tree = mtrees_[ii];

                typename MapType::const_iterator iter = tree.lower_bound(range);
                typename MapType::const_iterator fiter = iter;
                while (fiter != tree.end() && overlap_(fiter->first, range))
                    result.push_back(fiter++);
                typename MapType::const_iterator riter = iter;
                while (riter != tree.begin() && overlap_( (--riter)->first, range))
                    result.push_back(riter);
            }
        }

        bool intersects(const TRange& range) const
        {
            for(size_t ii=0; ii<mtrees_.size(); ii++)
            {
                const MapType& tree = mtrees_[ii];

                typename MapType::const_iterator iter = tree.lower_bound(range);
                if (iter != tree.end() && overlap_(iter->first, range))
                    return true;
                if (iter != tree.begin() && overlap_( (--iter)->first, range ))
                    return true;
            }

            return false;
        }

        size_t getTreeCount() const
        {
            return mtrees_.size();
        }

    private:
        std::vector< MapType > mtrees_;
        Overlap overlap_;
        Less less_;
    };

} } // cgatools::util

#endif // CGATOOLS_UTIL_RANGE_INTERSECTOR_HPP_

---