Anonymous avatar Anonymous committed 53d5053

dr81: #i117446# add interval container types

Comments (0)

Files changed (6)

o3tl/inc/o3tl/interval_map.hxx

+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ * 
+ * Copyright 2000, 2011 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#ifndef INCLUDED_O3TL_INTERVAL_MAP_HXX
+#define INCLUDED_O3TL_INTERVAL_MAP_HXX
+
+#include <algorithm>
+#include <limits>
+#include <utility>
+#include <vector>
+#include <boost/static_assert.hpp>
+#include <osl/diagnose.h>
+
+namespace o3tl {
+
+// ============================================================================
+
+/** A map containing objects keyed by intervals of integer values of type
+    IntType.
+
+    The key type of this map (key_type) is an ordered pair of type
+    ::std::pair<IntType,IntType> defined as interval_type. If K is the key of a
+    value contained in this map, all numbers in the interval [K.first,K.second]
+    are considered being a part of this map, and mapping the same data object.
+
+    On insertion of objects keyed by single values or intervals, intervals
+    already existing in the map will be merged to bigger intervals, if they
+    refer to the same data object. Testing data objects on equalness is done
+    via a comparison functor of type ObjComp.
+    
+    In differenec to a regular map, insertion and deletion of elements
+    invalidates ALL iterators.
+
+    The intervals of the objects in this map are stored in ascending order.
+ */
+template<
+    typename IntType,
+    typename MappedType,
+    typename MappedComp = ::std::equal_to< MappedType >,
+    typename AllocType = ::std::allocator< ::std::pair< ::std::pair< IntType, IntType >, MappedType > >
+    >
+class interval_map
+{
+public:
+    typedef IntType                                         integer_type;
+    typedef ::std::pair< integer_type, integer_type >       interval_type;
+    typedef interval_type                                   key_type;
+    typedef MappedType                                      mapped_type;
+    typedef MappedComp                                      mapped_compare;
+    typedef ::std::pair< key_type, mapped_type >            value_type;
+    typedef AllocType                                       allocator_type;
+    typedef ::std::vector< value_type, allocator_type >     container_type;
+    typedef typename container_type::size_type              size_type;
+    typedef typename container_type::difference_type        difference_type;
+    typedef typename container_type::const_reference        const_reference;
+    typedef typename container_type::const_iterator         const_iterator;
+    typedef typename container_type::const_reverse_iterator const_reverse_iterator;
+
+    inline explicit interval_map(
+            const mapped_compare& rMappedComp = mapped_compare(),
+            const allocator_type& rAlloc = allocator_type() ) :
+        maMappedComp( rMappedComp ), maElements( rAlloc ) {}
+
+    /** Constructs the map from the passed range, by calling insert() for each
+        element in the range. InputIterator must dereference to value_type. */
+    template< typename InputIterator >
+    inline explicit interval_map(
+            InputIterator aBeg, InputIterator aEnd,
+            const mapped_compare& rMappedComp = mapped_compare(),
+            const allocator_type& rAlloc = allocator_type() ) :
+        maMappedComp( rMappedComp ), maElements( rAlloc ) { insert( aBeg, aEnd ); }
+
+    /** Returns true, if the map is empty. */
+    inline bool empty() const { return maElements.empty(); }
+    /** Returns the number of elements in the map. */
+    inline size_type size() const { return maElements.size(); }
+    /** Returns the functor used to compare data objects for equalness. */
+    inline mapped_compare mapped_comp() const { return maMappedComp; }
+    /** Returns the allocator object of the container. */
+    inline allocator_type get_allocator() const { return maElements.get_allocator(); }
+
+    /** Returns an iterator pointing to the beginning of the container. */
+    inline const_iterator begin() const { return maElements.begin(); }
+    /** Returns an iterator pointing to the end of the container. */
+    inline const_iterator end() const { return maElements.end(); }
+    /** Returns a reverse iterator pointing to the end of the container. */
+    inline const_reverse_iterator rbegin() const { return maElements.rbegin(); }
+    /** Returns a reverse iterator pointing to the beginning of the container. */
+    inline const_reverse_iterator rend() const { return maElements.rend(); }
+    /** Returns a reference to the first element in the container. */
+    inline const_reference front() const { return maElements.front(); }
+    /** Returns a reference to the last element in the container. */
+    inline const_reference back() const { return maElements.back(); }
+
+    /** Returns an iterator to an element whose interval contains the passed
+        key, or the first element whose interval starts after the passed key. */
+    inline const_iterator find_bound( integer_type nKey ) const { return ::std::lower_bound( begin(), end(), nKey, interval_compare() ); }
+    /** Returns an iterator to an element whose interval contains the passed key. */
+    inline const_iterator find( integer_type nKey ) const { const_iterator aIt = find_bound( nKey ); return ((aIt != end()) && (aIt->first.first <= nKey)) ? aIt : end(); }
+    /** Returns the number of elements whose interval contains the passed key (0 or 1). */
+    inline size_type count( integer_type nKey ) const { return (find( nKey ) == end()) ? 0 : 1; }
+
+    /** Clears this map and inserts all elements in the passed range.
+        InputIterator must dereference to value_type. */
+    template< typename InputIterator >
+    inline void assign( InputIterator aBeg, InputIterator aEnd ) { clear(); insert( aBeg, aEnd ); }
+
+    /** Inserts the passed data object at the passed key. */
+    inline const_iterator insert( integer_type nKey, const mapped_type& rData ) { return insert( interval_type( nKey, nKey ), rData ); }
+    /** Inserts the passed data object at the passed interval. */
+    const_iterator insert( const interval_type& rKey, const mapped_type& rData );
+    /** Inserts the passed value, consisting of interval and data object. */
+    inline const_iterator insert( const value_type& rValue ) { return insert( rValue.first, rValue.second ); }
+
+    /** Inserts the passed data object at the passed key or interval. */
+    template< typename IntervalType >
+    inline const_iterator insert( const IntervalType& rKey, const mapped_type& rData ) { return insert( interval_type( rKey.first, rKey.second ), rData ); }
+    /** Inserts the passed value, consisting of key or interval, and data object. */
+    template< typename ValueType >
+    inline const_iterator insert( const ValueType& rValue ) { return insert( rValue.first, rValue.second ); }
+    /** Inserts all elements in the passed range. InputIterator must
+        dereference to value_type. */
+    template< typename InputIterator >
+    void insert( InputIterator aBeg, InputIterator aEnd );
+
+    /** Removes the specified key from the container. */
+    inline const_iterator erase( integer_type nKey ) { return erase( interval_type( nKey, nKey ) ); }
+    /** Removes the specified interval from the container. */
+    const_iterator erase( const interval_type& rKey );
+
+    /** Removes the specified element from the container. */
+    inline const_iterator erase( const_iterator aIt ) { return maElements.erase( make_iterator( aIt ) ); }
+    /** Removes the specified range of elements from the container. */
+    inline const_iterator erase( const_iterator aBeg, const_iterator aEnd ) { return maElements.erase( make_iterator( aBeg ), make_iterator( aEnd ) ); }
+
+    /** Removes all elements from the container. */
+    inline void clear() { maElements.clear(); }
+    /** Swaps contents of this map with the contents of the passed map. */
+    inline void swap( interval_map& rMap ) { maElements.swap( rMap.maElements ); }
+
+    /** Returns an intersection of the map with the passed interval. */
+    interval_map make_intersection( const interval_type& rKey ) const;
+
+private:
+    typedef ::std::numeric_limits< integer_type > limits_type;
+    BOOST_STATIC_ASSERT( limits_type::is_integer );
+    typedef typename container_type::iterator iterator;
+
+    /** Comparison functor used to find elements in binary search. */
+    struct interval_compare
+    {
+        inline bool operator()( const typename interval_map::value_type& rValue, typename interval_map::integer_type nKey ) const
+            { return rValue.first.second < nKey; }
+    };
+
+    /** Increases the passed value by one, if it is not the maximum of IntType. */
+    inline integer_type plus1( integer_type nValue ) const { return (nValue < limits_type::max()) ? (nValue + 1) : nValue; }
+
+    /** Converts a const_iterator to an iterator. */
+    inline iterator make_iterator( const_iterator aIt ) { return maElements.begin() + (aIt - begin()); }
+
+    mapped_compare maMappedComp;
+    container_type maElements;
+};
+
+// ----------------------------------------------------------------------------
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType >
+typename interval_map< IntType, MappedType, MappedComp, AllocType >::const_iterator
+interval_map< IntType, MappedType, MappedComp, AllocType >::insert( const interval_type& rKey, const mapped_type& rData )
+{
+    // find the first interval that contains or follows rKey.first
+    OSL_ENSURE( rKey.first <= rKey.second, "interval_map::insert - invalid interval" );
+    iterator aIt = make_iterator( find_bound( rKey.first ) );
+
+    /*  Check if the previous interval can be merged (it must end directly
+        before rKey.first, and its data must be equal to the passed data). If
+        (aIt-1) exists, (aIt-1)->first.second can be increased savely, because
+        (aIt-1) ends before rKey.first. */
+    if( (aIt != maElements.begin()) && ((aIt - 1)->first.second + 1 == rKey.first) && maMappedComp( (aIt - 1)->second, rData ) )
+    {
+        // let aIt point to the element that will contain the new interval rKey
+        --aIt;
+        // update interval end of the existing element aIt points to
+        aIt->first.second = rKey.second;
+    }
+    /*  Check if the interval aIt points to can be merged (must touch or
+        intersect with rKey, and must contain equal data). */
+    else if( (aIt != maElements.end()) && (plus1( rKey.second ) >= aIt->first.first) && maMappedComp( rData, aIt->second ) )
+    {
+        // update interval of the existing element aIt points to
+        aIt->first.first = ::std::min( aIt->first.first, rKey.first );
+        aIt->first.second = ::std::max( aIt->first.second, rKey.second );
+    }
+    /*  The passed data does not match. Check if aIt is completely overwritten
+        by the new interval. */
+    else if( (aIt != maElements.end()) && (rKey.first <= aIt->first.first) && (aIt->first.second <= rKey.second) )
+    {
+        // replace contents of aIt
+        aIt->first = rKey;
+        aIt->second = rData;
+    }
+    // else: a new element needs to be inserted, update interval of existing element before
+    else
+    {
+        // if old element starts before new interval, update end of old interval
+        if( (aIt != maElements.end()) && (aIt->first.first < rKey.first) )
+        {
+            /*  If new element is in the inner part of aIt, the old element
+                must be split. Insert the latter part of old element after
+                aIt, and let aIt still point to old element. */
+            if( rKey.second < aIt->first.second )
+                // rKey.second is less than aIt->first.second, thus rKey.second is less than maximum of IntType
+                aIt = maElements.insert( aIt + 1, value_type( key_type( rKey.second + 1, aIt->first.second ), aIt->second ) ) - 1;
+            // update end of existing element
+            aIt->first.second = rKey.first - 1;
+            // move aIt to next element which is used as insert position of the new element
+            ++aIt;
+        }
+        // insert the new element
+        aIt = maElements.insert( aIt, value_type( rKey, rData ) );
+    }
+
+    /*  aIt points to the element containing rKey. Find the first element
+        following that is not completely covered by the new interval (aIt2). */
+    iterator aIt2 = aIt + 1;
+    while( (aIt2 != maElements.end()) && (aIt2->first.second <= aIt->first.second) ) ++aIt2;
+
+    /*  Check if aIt2 can be merged into the new interval (aIt2 must touch or
+        intersect with aIt, and data must be equal), or if start of aIt2 must
+        be updated (if new element intersects partly). */
+    if( aIt2 != maElements.end() )
+    {
+        // check if aIt2 can be merged with aIt
+        if( (plus1( aIt->first.second ) >= aIt2->first.first) && maMappedComp( rData, aIt2->second ) )
+        {
+            // update end of interval in aIt
+            aIt->first.second = aIt2->first.second;
+            // remove aIt2 from vector too
+            ++aIt2;
+        }
+        // check if start of aIt2 needs update
+        else if( aIt->first.second >= aIt2->first.first )
+        {
+            /*  Update start of interval in aIt2. aIt2 is not covered
+                completely by aIt, thus aIt->first.second is less than maximum
+                of IntType. */
+            aIt2->first.first = aIt->first.second + 1;
+        }
+    }
+
+    // remove all elements covered by the new interval
+    maElements.erase( aIt + 1, aIt2 );
+    return aIt;
+}
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType > template< typename InputIterator >
+void interval_map< IntType, MappedType, MappedComp, AllocType >::insert( InputIterator aBeg, InputIterator aEnd )
+{
+    for( InputIterator aIt = aBeg; aIt != aEnd; ++aIt )
+        insert( *aIt );
+}
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType >
+typename interval_map< IntType, MappedType, MappedComp, AllocType >::const_iterator
+interval_map< IntType, MappedType, MappedComp, AllocType >::erase( const interval_type& rKey )
+{
+    OSL_ENSURE( rKey.first <= rKey.second, "interval_map::erase - invalid interval" );
+    iterator aIt = make_iterator( find_bound( rKey.first ) );
+    // do nothing if passed interval starts behind last element
+    if( aIt != maElements.end() )
+    {
+        // if aIt contains rKey completely, split it
+        if( (aIt->first.first < rKey.first) && (rKey.second < aIt->first.second) )
+        {
+            // insert new element before aIt, let aIt still point to existing element
+            aIt = maElements.insert( aIt, value_type( key_type( aIt->first.first, rKey.first - 1 ), aIt->second ) ) + 1;
+            // update start of old element
+            aIt->first.first = rKey.second + 1;
+            // aIt points to the element following the erased interval
+        }
+        else
+        {
+            // if aIt is covered partly by rKey, update its end index and go to next element
+            if( (aIt->first.first < rKey.first) && (rKey.first <= aIt->first.second) )
+                // rKey.first is greater than aIt->first.first, thus greater than minimum of IntType
+                (aIt++)->first.second = rKey.first - 1;
+            // find first element not completely covered by rKey, erase all covered elements
+            iterator aIt2 = aIt;
+            while( (aIt2 != maElements.end()) && (aIt2->first.second <= rKey.second) ) ++aIt2;
+            aIt = maElements.erase( aIt, aIt2 );
+            // if aIt is covered partly by rKey, update its start index
+            if( (aIt != maElements.end()) && (aIt->first.first <= rKey.second) )
+                // aIt ends after rKey.second, thus rKey.second is less than maximum of IntType
+                aIt->first.first = rKey.second + 1;
+            // aIt points to the element following the erased interval
+        }
+    }
+    return aIt;
+}
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType >
+interval_map< IntType, MappedType, MappedComp, AllocType >
+interval_map< IntType, MappedType, MappedComp, AllocType >::make_intersection( const interval_type& rKey ) const
+{
+    OSL_ENSURE( rKey.first <= rKey.second, "interval_map::make_intersection - invalid interval" );
+    interval_map aMap;
+    for( const_iterator aIt = find_bound( rKey.first ), aEnd = end(); (aIt != aEnd) && (aIt->first.first <= rKey.second); ++aIt )
+        aMap.maElements.push_back( value_type( key_type( ::std::max( aIt->first.first, rKey.first ), ::std::min( aIt->first.second, rKey.second ) ), aIt->second ) );
+    return aMap;
+}
+
+// ============================================================================
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType >
+bool operator==( const interval_map< IntType, MappedType, MappedComp, AllocType >& rMap1, const interval_map< IntType, MappedType, MappedComp, AllocType >& rMap2 )
+{
+    // compare data entries with MappedComp, not with MappedType::operator==
+    if( rMap1.size() != rMap2.size() )
+        return false;
+    MappedComp aMappedComp;
+    for( typename interval_map< IntType, MappedType, MappedComp, AllocType >::const_iterator aIt1 = rMap1.begin(), aEnd1 = rMap1.end(), aIt2 = rMap2.begin(), aEnd2 = rMap2.end(); aIt1 != aEnd1; ++aIt1, ++aIt2 )
+        if( (aIt1->first != aIt2->first) || !aMappedComp( aIt1->second, aIt2->second ) )
+            return false;
+    return true;
+}
+
+template< typename IntType, typename MappedType, typename MappedComp, typename AllocType >
+inline bool operator!=( const interval_map< IntType, MappedType, MappedComp, AllocType >& rMap1, const interval_map< IntType, MappedType, MappedComp, AllocType >& rMap2 )
+{
+    return !(rMap1 == rMap2);
+}
+
+// ============================================================================
+
+} // namespace o3tl
+
+#endif

o3tl/inc/o3tl/interval_set.hxx

+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ * 
+ * Copyright 2000, 2011 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#ifndef INCLUDED_O3TL_INTERVAL_SET_HXX
+#define INCLUDED_O3TL_INTERVAL_SET_HXX
+
+#include <algorithm>
+#include <limits>
+#include <utility>
+#include <vector>
+#include <boost/static_assert.hpp>
+#include <osl/diagnose.h>
+
+namespace o3tl {
+
+// ============================================================================
+
+/** A set containing intervals of integer values of type IntType.
+
+    The value type of this set (value_type) is an ordered pair of type
+    ::std::pair<IntType,IntType> defined as interval_type. If R is a value
+    contained in this set, all numbers in the interval [R.first,R.second] are
+    considered being a part of this set.
+    
+    On insertion of single values or new intervals, intervals already existing
+    in the set will be merged to bigger intervals if possible.
+    
+    In differenec to a regular set, insertion and deletion of elements
+    invalidates ALL iterators.
+
+    All intervals in this set are stored in ascending order.
+ */
+template<
+    typename IntType,
+    typename AllocType = ::std::allocator< ::std::pair< IntType, IntType > >
+    >
+class interval_set
+{
+public:
+    typedef IntType                                         integer_type;
+    typedef ::std::pair< integer_type, integer_type >       interval_type;
+    typedef interval_type                                   value_type;
+    typedef AllocType                                       allocator_type;
+    typedef ::std::vector< value_type, allocator_type >     container_type;
+    typedef typename container_type::size_type              size_type;
+    typedef typename container_type::difference_type        difference_type;
+    typedef typename container_type::const_reference        const_reference;
+    typedef typename container_type::const_iterator         const_iterator;
+    typedef typename container_type::const_reverse_iterator const_reverse_iterator;
+
+    inline explicit interval_set( const allocator_type& rAlloc = allocator_type() ) :
+        maElements( rAlloc ) {}
+
+    /** Constructs the set from the passed range, by calling insert() for each element
+        in the range. InputIterator must dereference to integer_type or interval_type. */
+    template< typename InputIterator >
+    inline interval_set( InputIterator aBeg, InputIterator aEnd, const allocator_type& rAlloc = allocator_type() ) :
+        maElements( rAlloc ) { insert( aBeg, aEnd ); }
+
+    /** Returns true, if the set is empty. */
+    inline bool empty() const { return maElements.empty(); }
+    /** Returns the number of elements in the container. */
+    inline size_type size() const { return maElements.size(); }
+    /** Returns the allocator object of the container. */
+    inline allocator_type get_allocator() const { return maElements.get_allocator(); }
+
+    /** Returns an iterator pointing to the beginning of the container. */
+    inline const_iterator begin() const { return maElements.begin(); }
+    /** Returns an iterator pointing to the end of the container. */
+    inline const_iterator end() const { return maElements.end(); }
+    /** Returns a reverse iterator pointing to the end of the container. */
+    inline const_reverse_iterator rbegin() const { return maElements.rbegin(); }
+    /** Returns a reverse iterator pointing to the beginning of the container. */
+    inline const_reverse_iterator rend() const { return maElements.rend(); }
+    /** Returns a reference to the first element in the container. */
+    inline const_reference front() const { return maElements.front(); }
+    /** Returns a reference to the last element in the container. */
+    inline const_reference back() const { return maElements.back(); }
+
+    /** Returns an iterator to an element (interval) that contains the passed
+        value, or the first element that starts after the passed value. */
+    inline const_iterator find_bound( integer_type nValue ) const { return ::std::lower_bound( begin(), end(), nValue, interval_compare() ); }
+    /** Returns an iterator to an element (interval) containing the passed value. */
+    inline const_iterator find( integer_type nValue ) const { const_iterator aIt = find_bound( nValue ); return ((aIt != end()) && (aIt->first <= nValue)) ? aIt : end(); }
+    /** Returns the number of elements containing the passed value (0 or 1). */
+    inline size_type count( integer_type nValue ) const { return (find( nValue ) == end()) ? 0 : 1; }
+
+    /** Clears this set and inserts all elements in the passed range.
+        InputIterator must dereference to integer_type or interval_type. */
+    template< typename InputIterator >
+    inline void assign( InputIterator aBeg, InputIterator aEnd ) { clear(); insert( aBeg, aEnd ); }
+
+    /** Inserts the passed value into the set. */
+    inline const_iterator insert( integer_type nValue ) { return insert( interval_type( nValue, nValue ) ); }
+    /** Inserts the passed interval into the set. */
+    const_iterator insert( const interval_type& rInt );
+
+    /** Inserts the passed interval into the set. */
+    template< typename IntervalType >
+    inline const_iterator insert( const IntervalType& rInt ) { return insert( interval_type( rInt.first, rInt.second ) ); }
+    /** Inserts all elements in the passed range. InputIterator must
+        dereference to integer_type or to any pair of IntType. */
+    template< typename InputIterator >
+    void insert( InputIterator aBeg, InputIterator aEnd );
+
+    /** Removes the specified value from the container. */
+    inline const_iterator erase( integer_type nValue ) { return erase( interval_type( nValue, nValue ) ); }
+    /** Removes the specified interval from the container. */
+    const_iterator erase( const interval_type& rInt );
+
+    /** Removes the specified element from the container. */
+    inline const_iterator erase( const_iterator aIt ) { return maElements.erase( make_iterator( aIt ) ); }
+    /** Removes the specified range of elements from the container. */
+    inline const_iterator erase( const_iterator aBeg, const_iterator aEnd ) { return maElements.erase( make_iterator( aBeg ), make_iterator( aEnd ) ); }
+
+    /** Removes all elements from the container. */
+    inline void clear() { maElements.clear(); }
+    /** Swaps contents of this set with the contents of the passed set. */
+    inline void swap( interval_set& rSet ) { maElements.swap( rSet.maElements ); }
+
+    /** Returns an intersection of the set with the passed interval. */
+    interval_set make_intersection( const interval_type& rInt ) const;
+
+private:
+    typedef ::std::numeric_limits< integer_type > limits_type;
+    BOOST_STATIC_ASSERT( limits_type::is_integer );
+    typedef typename container_type::iterator iterator;
+
+    /** Comparison functor used to find elements in binary search. */
+    struct interval_compare
+    {
+        inline bool operator()( const typename interval_set::interval_type& rInt, typename interval_set::integer_type nValue ) const
+            { return rInt.second < nValue; }
+    };
+
+    /** Increases the passed value by one, if it is not the maximum of IntType. */
+    inline integer_type plus1( integer_type nValue ) const { return (nValue < limits_type::max()) ? (nValue + 1) : nValue; }
+
+    /** Converts a const_iterator to an iterator. */
+    inline iterator make_iterator( const_iterator aIt ) { return maElements.begin() + (aIt - begin()); }
+
+    container_type maElements;
+};
+
+// ----------------------------------------------------------------------------
+
+template< typename IntType, typename AllocType >
+typename interval_set< IntType, AllocType >::const_iterator
+interval_set< IntType, AllocType >::insert( const interval_type& rInt )
+{
+    // find the first element that contains or follows after rInt.first
+    OSL_ENSURE( rInt.first <= rInt.second, "interval_set::insert - invalid interval" );
+    iterator aIt = make_iterator( find_bound( rInt.first ) );
+
+    /*  Check if the previous interval can be merged (it must end directly
+        before rInt.first). If (aIt-1) exists, (aIt-1)->second can be increased
+        savely, because (aIt-1) ends before rInt.first. */
+    if( (aIt != maElements.begin()) && ((aIt - 1)->second + 1 == rInt.first) )
+    {
+        // let aIt point to the element that will contain the new interval rInt
+        --aIt;
+        // update interval end of the existing element aIt points to
+        aIt->second = rInt.second;
+    }
+    // check if the interval aIt points to can be merged (must touch or intersect with rInt)
+    else if( (aIt != maElements.end()) && (plus1( rInt.second ) >= aIt->first) )
+    {
+        // update interval of the existing element aIt points to
+        aIt->first = ::std::min( aIt->first, rInt.first );
+        aIt->second = ::std::max( aIt->second, rInt.second );
+    }
+    else
+    {
+        // no existing interval can be merged with rInt, insert new element before aIt
+        aIt = maElements.insert( aIt, rInt );
+    }
+
+    /*  aIt points to the element containing rInt. Find the first element
+        following that is not completely covered by the new interval (aIt2). */
+    iterator aIt2 = aIt + 1;
+    while( (aIt2 != maElements.end()) && (aIt2->second <= aIt->second) ) ++aIt2;
+
+    // check if aIt2 can be merged into the new interval
+    if( (aIt2 != maElements.end()) && (plus1( aIt->second ) >= aIt2->first) )
+    {
+        // update end of vector element containing the new interval
+        aIt->second = aIt2->second;
+        // remove aIt2 from vector too
+        ++aIt2;
+    }
+
+    // remove all elements covered by the new interval
+    maElements.erase( aIt + 1, aIt2 );
+    return aIt;
+}
+
+template< typename IntType, typename AllocType > template< typename InputIterator >
+void interval_set< IntType, AllocType >::insert( InputIterator aBeg, InputIterator aEnd )
+{
+    for( InputIterator aIt = aBeg; aIt != aEnd; ++aIt )
+        insert( *aIt );
+}
+
+template< typename IntType, typename AllocType >
+typename interval_set< IntType, AllocType >::const_iterator
+interval_set< IntType, AllocType >::erase( const interval_type& rInt )
+{
+    OSL_ENSURE( rInt.first <= rInt.second, "interval_set::erase - invalid interval" );
+    iterator aIt = make_iterator( find_bound( rInt.first ) );
+    // do nothing if passed interval starts behind last element
+    if( aIt != maElements.end() )
+    {
+        // if aIt contains rInt completely, split it
+        if( (aIt->first < rInt.first) && (rInt.second < aIt->second) )
+        {
+            // insert new element before aIt, let aIt still point to existing element
+            aIt = maElements.insert( aIt, value_type( aIt->first, rInt.first - 1 ) ) + 1;
+            // update start of old element
+            aIt->first = rInt.second + 1;
+            // aIt points to the element following the erased interval
+        }
+        else
+        {
+            // if aIt is covered partly by rInt, update its end index and go to next element
+            if( (aIt->first < rInt.first) && (rInt.first <= aIt->second) )
+                // rInt.first is greater than aIt->first, thus greater than minimum of IntType
+                (aIt++)->second = rInt.first - 1;
+            // find first element not completely covered by rInt, erase all covered elements
+            iterator aIt2 = aIt;
+            while( (aIt2 != maElements.end()) && (aIt2->second <= rInt.second) ) ++aIt2;
+            aIt = maElements.erase( aIt, aIt2 );
+            // if aIt is covered partly by rInt, update its start index
+            if( (aIt != maElements.end()) && (aIt->first <= rInt.second) )
+                // aIt ends after rInt.second, thus rInt.second is less than maximum of IntType
+                aIt->first = rInt.second + 1;
+            // aIt points to the element following the erased interval
+        }
+    }
+    return aIt;
+}
+
+template< typename IntType, typename AllocType >
+interval_set< IntType, AllocType >
+interval_set< IntType, AllocType >::make_intersection( const interval_type& rInt ) const
+{
+    OSL_ENSURE( rInt.first <= rInt.second, "interval_set::make_intersection - invalid interval" );
+    interval_set aSet;
+    for( const_iterator aIt = find_bound( rInt.first ), aEnd = end(); (aIt != aEnd) && (aIt->first <= rInt.second); ++aIt )
+        aSet.maElements.push_back( value_type( ::std::max( aIt->first, rInt.first ), ::std::min( aIt->second, rInt.second ) ) );
+    return aSet;
+}
+
+// ============================================================================
+
+template< typename IntType, typename AllocType >
+inline bool operator==( const interval_set< IntType, AllocType >& rSet1, const interval_set< IntType, AllocType >& rSet2 )
+{
+    if( rSet1.size() != rSet2.size() )
+        return false;
+    for( typename interval_set< IntType, AllocType >::const_iterator aIt1 = rSet1.begin(), aEnd1 = rSet1.end(), aIt2 = rSet2.begin(), aEnd2 = rSet2.end(); aIt1 != aEnd1; ++aIt1, ++aIt2 )
+        if( *aIt1 != *aIt2 )
+            return false;
+    return true;
+}
+
+template< typename IntType, typename AllocType >
+inline bool operator!=( const interval_set< IntType, AllocType >& rSet1, const interval_set< IntType, AllocType >& rSet2 )
+{
+    return !(rSet1 == rSet2);
+}
+
+// ============================================================================
+
+} // namespace o3tl
+
+#endif

o3tl/inc/o3tl/vector_pool.hxx

  *
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  * 
- * Copyright 2008 by Sun Microsystems, Inc.
+ * Copyright 2000, 2010 Oracle and/or its affiliates.
  *
  * OpenOffice.org - a multi-platform office productivity suite
  *
- * $RCSfile: lazy_update.hxx,v $
- * $Revision: 1.3 $
- *
  * This file is part of OpenOffice.org.
  *
  * OpenOffice.org is free software: you can redistribute it and/or modify

o3tl/qa/makefile.mk

 
 # BEGIN ----------------------------------------------------------------
 SHL1OBJS=  \
-	$(SLO)$/cow_wrapper_clients.obj     \
-	$(SLO)$/test-cow_wrapper.obj	    \
-    $(SLO)$/test-vector_pool.obj	\
-    $(SLO)$/test-heap_ptr.obj           \
-    $(SLO)$/test-range.obj
+	$(SLO)$/cow_wrapper_clients.obj \
+	$(SLO)$/test-cow_wrapper.obj \
+	$(SLO)$/test-heap_ptr.obj \
+	$(SLO)$/test-interval_map.obj \
+	$(SLO)$/test-interval_set.obj \
+	$(SLO)$/test-range.obj \
+	$(SLO)$/test-vector_pool.obj
 
 SHL1TARGET= tests
 SHL1STDLIBS= 	$(SALLIB)		 \

o3tl/qa/test-interval_map.cxx

+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2000, 2011 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#include "preextstl.h"
+#include "cppunit/TestAssert.h"
+#include "cppunit/TestFixture.h"
+#include "cppunit/extensions/HelperMacros.h"
+#include "postextstl.h"
+
+#include <o3tl/interval_map.hxx>
+
+// -----------------------------------------------------------------------------
+
+struct Triple { int first; int second; int third; };
+
+class interval_map_test : public CppUnit::TestFixture
+{
+public:
+    void test();
+
+private:
+    typedef ::o3tl::interval_map< int, int > map_type;
+
+    void check_map( const map_type& map, const Triple* triples, size_t len, int line );
+
+    CPPUNIT_TEST_SUITE( interval_map_test );
+    CPPUNIT_TEST( test );
+    CPPUNIT_TEST_SUITE_END();
+};
+
+// -----------------------------------------------------------------------------
+
+void interval_map_test::test()
+{
+    map_type map;
+    CPPUNIT_ASSERT_MESSAGE( "empty", map.empty() );
+    typedef map_type::interval_type interval;
+    map_type::const_iterator it;
+
+#define CALL_CHECK( map, triples ) check_map( map, triples, sizeof(triples)/sizeof(Triple), __LINE__ )
+
+    // insert new ranges
+
+    static const Triple triples1[] = { {20,20,1} };
+    map.insert( 20, 1 ); CALL_CHECK( map, triples1 );
+
+    static const Triple triples2[] = { {20,20,1},{30,39,1} };
+    map.insert( interval( 30, 39 ), 1 ); CALL_CHECK( map, triples2 );
+
+    static const Triple triples3[] = { {0,1,1},{20,20,1},{30,39,1} };
+    map.insert( interval( 0, 1 ), 1 ); CALL_CHECK( map, triples3 );
+
+    static const Triple triples4[] = { {0,1,1},{5,7,1},{20,20,1},{30,39,1} };
+    map.insert( interval( 5, 7 ), 1 ); CALL_CHECK( map, triples4 );
+
+    // insert into existing range
+
+    map.insert( 5, 1 ); CALL_CHECK( map, triples4 );
+    map.insert( 6, 1 ); CALL_CHECK( map, triples4 );
+    map.insert( 7, 1 ); CALL_CHECK( map, triples4 );
+    map.insert( interval( 5, 6 ), 1 ); CALL_CHECK( map, triples4 );
+    map.insert( interval( 6, 7 ), 1 ); CALL_CHECK( map, triples4 );
+    map.insert( interval( 5, 7 ), 1 ); CALL_CHECK( map, triples4 );
+
+    // expand existing range
+
+    static const Triple triples11[] = { {0,1,1},{5,7,1},{19,20,1},{30,39,1} };
+    map.insert( interval( 19, 20 ), 1 ); CALL_CHECK( map, triples11 );
+
+    static const Triple triples12[] = { {0,1,1},{5,7,1},{19,22,1},{30,39,1} };
+    map.insert( interval( 20, 22 ), 1 ); CALL_CHECK( map, triples12 );
+
+    static const Triple triples13[] = { {0,1,1},{5,7,1},{17,24,1},{30,39,1} };
+    map.insert( interval( 17, 24 ), 1 ); CALL_CHECK( map, triples13 );
+
+    static const Triple triples14[] = { {0,1,1},{5,7,1},{15,24,1},{30,39,1} };
+    map.insert( interval( 15, 16 ), 1 ); CALL_CHECK( map, triples14 );
+
+    static const Triple triples15[] = { {0,1,1},{5,7,1},{15,27,1},{30,39,1} };
+    map.insert( interval( 25, 27 ), 1 ); CALL_CHECK( map, triples15 );
+
+    // find, find_bound
+
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( -2 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( -1 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = map.find( 0 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = map.find( 1 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( 2 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( 3 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( 4 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = map.find( 5 )) != map.end()) && (it->first.first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = map.find( 39 )) != map.end()) && (it->first.first == 30) );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( 40 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = map.find( 41 )) == map.end() );
+
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( -2 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( -1 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 0 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 1 )) != map.end()) && (it->first.first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 2 )) != map.end()) && (it->first.first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 3 )) != map.end()) && (it->first.first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 4 )) != map.end()) && (it->first.first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 5 )) != map.end()) && (it->first.first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = map.find_bound( 39 )) != map.end()) && (it->first.first == 30) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", (it = map.find_bound( 40 )) == map.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", (it = map.find_bound( 41 )) == map.end() );
+
+    // make intersection
+
+    static const Triple triples_int[] = { {6,7,1},{15,27,1},{30,33,1} };
+    map_type map2 = map.make_intersection( interval( 6, 33 ) ); CALL_CHECK( map2, triples_int );
+
+    // range c'tor, range insert, insert custom interval type
+
+    struct Pair { int first; int second; };
+    struct ValueType { Pair first; int second; };
+
+    static const Triple triples15a[] = { {7,7,1},{15,26,1} };
+    static const ValueType init1[] = { {{7,7},1},{{15,26},1} };
+    map_type map3( init1, init1 + sizeof(init1)/sizeof(ValueType) ); CALL_CHECK( map3, triples15a );
+
+    static const Triple triples15b[] = { {7,7,1},{15,26,1},{30,31,1} };
+    static const ValueType init2 = {{30,31},1};
+    map3.insert( init2 ); CALL_CHECK( map3, triples15b );
+
+    static const Triple triples15c[] = { {7,7,1},{15,26,1},{30,32,1} };
+    static const Pair init3 = {32,1};
+    map3.insert( init3 ); CALL_CHECK( map3, triples15c );
+
+    static const Pair init4[] = { {33,1},{6,1},{27,1} };
+    map3.insert( init4, init4 + sizeof(init4)/sizeof(Pair) ); CALL_CHECK( map3, triples_int );
+
+    // operator==
+
+    CPPUNIT_ASSERT_MESSAGE( "operator==", map2 == map3 );
+    map3.insert( interval( 30, 33 ), 2 );
+    CPPUNIT_ASSERT_MESSAGE( "operator!=", map2 != map3 );
+    map3.insert( interval( 30, 34 ), 1 );
+    CPPUNIT_ASSERT_MESSAGE( "operator!=", map2 != map3 );
+
+    // merge and overwrite
+
+    static const Triple triples16[] = { {0,8,1},{15,27,1},{30,39,1} };
+    map.insert( interval( 1, 8 ), 1 ); CALL_CHECK( map, triples16 );
+
+    static const Triple triples17[] = { {0,39,1} };
+    map.insert( interval( 9, 29 ), 1 ); CALL_CHECK( map, triples17 );
+
+    // remove inside range
+
+    static const Triple triples18[] = { {0,9,1},{11,19,1},{21,29,1},{31,39,1} };
+    map.erase( 10 ); map.erase( 20 ); map.erase( 30 ); CALL_CHECK( map, triples18 );
+
+    static const Triple triples19[] = { {0,9,1},{11,19,1},{24,29,1},{31,39,1} };
+    map.erase( interval( 21, 23 ) ); CALL_CHECK( map, triples19 );
+
+    static const Triple triples20[] = { {0,9,1},{11,19,1},{24,26,1},{31,39,1} };
+    map.erase( interval( 27, 29 ) ); CALL_CHECK( map, triples20 );
+
+    static const Triple triples21[] = { {0,9,1},{11,19,1},{31,39,1} };
+    map.erase( interval( 24, 26 ) ); CALL_CHECK( map, triples21 );
+
+    // remove outside ranges
+
+    map.erase( -1 ); CALL_CHECK( map, triples21 );
+    map.erase( 10 ); CALL_CHECK( map, triples21 );
+    map.erase( interval( 20, 22 ) ); CALL_CHECK( map, triples21 );
+    map.erase( interval( 29, 30 ) ); CALL_CHECK( map, triples21 );
+    map.erase( interval( 20, 30 ) ); CALL_CHECK( map, triples21 );
+    map.erase( interval( 40, 41 ) ); CALL_CHECK( map, triples21 );
+
+    // remove in several ranges
+
+    static const Triple triples22[] = { {0,6,1},{13,19,1},{31,39,1} };
+    map.erase( interval( 7, 12 ) ); CALL_CHECK( map, triples22 );
+
+    static const Triple triples23[] = { {0,5,1},{33,39,1} };
+    map.erase( interval( 6, 32 ) ); CALL_CHECK( map, triples23 );
+
+    static const Triple triples24[] = { {0,0,1} };
+    map.erase( interval( 1, 44 ) ); CALL_CHECK( map, triples24 );
+
+    map.erase( interval( -1, 1 ) );
+    CPPUNIT_ASSERT_MESSAGE( "empty", map.empty() );
+
+    // insert mixed data
+
+    map.insert( interval( 10, 19 ), 1 );
+    map.insert( interval( 30, 39 ), 1 );
+    map.insert( interval( 50, 59 ), 1 );
+
+    static const Triple triples25[] = { {1,1,2},{10,19,1},{30,39,1},{50,59,1} };
+    map.insert( 1, 2 ); CALL_CHECK( map, triples25 );
+
+    static const Triple triples26[] = { {1,1,2},{10,19,1},{20,21,2},{30,39,1},{50,59,1} };
+    map.insert( interval( 20, 21 ), 2 ); CALL_CHECK( map, triples26 );
+
+    static const Triple triples27[] = { {1,1,2},{10,19,1},{20,21,2},{28,29,2},{30,39,1},{50,59,1} };
+    map.insert( interval( 28, 29 ), 2 ); CALL_CHECK( map, triples27 );
+
+    static const Triple triples28[] = { {1,1,2},{10,19,1},{20,21,2},{28,29,2},{30,39,1},{50,59,1},{60,60,2} };
+    map.insert( 60, 2 ); CALL_CHECK( map, triples28 );
+
+    static const Triple triples29[] = { {1,21,2},{28,29,2},{30,39,1},{50,59,1},{60,60,2} };
+    map.insert( interval( 2, 19 ), 2 ); CALL_CHECK( map, triples29 );
+
+    static const Triple triples30[] = { {1,21,2},{28,30,2},{31,39,1},{50,59,1},{60,60,2} };
+    map.insert( 30, 2 ); CALL_CHECK( map, triples30 );
+
+    static const Triple triples31[] = { {1,21,2},{28,30,2},{31,39,1},{50,58,1},{59,60,2} };
+    map.insert( 59, 2 ); CALL_CHECK( map, triples31 );
+
+    static const Triple triples32[] = { {1,21,2},{28,30,2},{31,39,1},{50,51,2},{52,58,1},{59,60,2} };
+    map.insert( interval( 50, 51 ), 2 ); CALL_CHECK( map, triples32 );
+
+    static const Triple triples33[] = { {1,21,2},{28,30,2},{31,37,1},{38,39,2},{50,51,2},{52,58,1},{59,60,2} };
+    map.insert( interval( 38, 39 ), 2 ); CALL_CHECK( map, triples33 );
+
+    static const Triple triples34[] = { {1,21,2},{28,30,2},{31,34,1},{35,35,2},{36,37,1},{38,39,2},{50,51,2},{52,58,1},{59,60,2} };
+    map.insert( 35, 2 ); CALL_CHECK( map, triples34 );
+
+    static const Triple triples35[] = { {1,21,2},{28,30,2},{31,34,1},{35,39,2},{50,51,2},{52,58,1},{59,60,2} };
+    map.insert( interval( 36, 37 ), 2 ); CALL_CHECK( map, triples35 );
+
+#undef CALL_CHECK
+}
+
+void interval_map_test::check_map( const map_type& map, const Triple* triples, size_t len, int line )
+{
+    const Triple* triplesend = triples + len;
+    map_type::const_iterator it = map.begin(), itend = map.end();
+    int index = 0;
+    char buffer[ 256 ];
+    while( (it != itend) || (triples != triplesend) )
+    {
+        bool itvalid = it != itend;
+        bool triplesvalid = triples != triplesend;
+        if( itvalid && triplesvalid )
+            sprintf( buffer, "line %d; failed: #%d; exp: (%d,%d,%d); found: (%d,%d,%d)", line, index, triples->first, triples->second, triples->third, it->first.first, it->first.second, it->second );
+        else if( itvalid )
+            sprintf( buffer, "line %d; failed: #%d; exp: [end]; found: (%d,%d,%d)", line, index, it->first.first, it->first.second, it->second );
+        else
+            sprintf( buffer, "line %d; failed: #%d; exp: (%d,%d,%d); found: [end]", line, index, triples->first, triples->second, triples->third );
+        CPPUNIT_ASSERT_MESSAGE( buffer, itvalid && triplesvalid && (it->first.first == triples->first) && (it->first.second == triples->second) && (it->second == triples->third) );
+        if( itvalid ) ++it;
+        if( triplesvalid ) ++triples;
+        ++index;
+    }
+}
+
+// -----------------------------------------------------------------------------
+
+CPPUNIT_TEST_SUITE_REGISTRATION(interval_map_test);

o3tl/qa/test-interval_set.cxx

+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2000, 2011 Oracle and/or its affiliates.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#include "preextstl.h"
+#include "cppunit/TestAssert.h"
+#include "cppunit/TestFixture.h"
+#include "cppunit/extensions/HelperMacros.h"
+#include "postextstl.h"
+
+#include <o3tl/interval_set.hxx>
+
+// -----------------------------------------------------------------------------
+
+struct Pair { int first; int second; };
+
+class interval_set_test : public CppUnit::TestFixture
+{
+public:
+    void test();
+
+private:
+    typedef ::o3tl::interval_set< int > set_type;
+
+    void check_set( const set_type& set, const Pair* pairs, size_t len, int line );
+
+    CPPUNIT_TEST_SUITE( interval_set_test );
+    CPPUNIT_TEST( test );
+    CPPUNIT_TEST_SUITE_END();
+};
+
+// -----------------------------------------------------------------------------
+
+void interval_set_test::test()
+{
+    set_type set;
+    CPPUNIT_ASSERT_MESSAGE( "empty", set.empty() );
+    typedef set_type::interval_type interval;
+    set_type::const_iterator it;
+
+#define CALL_CHECK( set, pairs ) check_set( set, pairs, sizeof(pairs)/sizeof(Pair), __LINE__ )
+
+    // insert new ranges
+
+    static const Pair pairs1[] = { {20,20} };
+    set.insert( 20 ); CALL_CHECK( set, pairs1 );
+
+    static const Pair pairs2[] = { {20,20},{30,39} };
+    set.insert( interval( 30, 39 ) ); CALL_CHECK( set, pairs2 );
+
+    static const Pair pairs3[] = { {0,1},{20,20},{30,39} };
+    set.insert( interval( 0, 1 ) ); CALL_CHECK( set, pairs3 );
+
+    static const Pair pairs4[] = { {0,1},{5,7},{20,20},{30,39} };
+    set.insert( interval( 5, 7 ) ); CALL_CHECK( set, pairs4 );
+
+    // insert into existing range
+
+    set.insert( 5 ); CALL_CHECK( set, pairs4 );
+    set.insert( 6 ); CALL_CHECK( set, pairs4 );
+    set.insert( 7 ); CALL_CHECK( set, pairs4 );
+    set.insert( interval( 5, 6 ) ); CALL_CHECK( set, pairs4 );
+    set.insert( interval( 6, 7 ) ); CALL_CHECK( set, pairs4 );
+    set.insert( interval( 5, 7 ) ); CALL_CHECK( set, pairs4 );
+
+    // expand existing range
+
+    static const Pair pairs11[] = { {0,1},{5,7},{19,20},{30,39} };
+    set.insert( interval( 19, 20 ) ); CALL_CHECK( set, pairs11 );
+
+    static const Pair pairs12[] = { {0,1},{5,7},{19,22},{30,39} };
+    set.insert( interval( 20, 22 ) ); CALL_CHECK( set, pairs12 );
+
+    static const Pair pairs13[] = { {0,1},{5,7},{17,24},{30,39} };
+    set.insert( interval( 17, 24 ) ); CALL_CHECK( set, pairs13 );
+
+    static const Pair pairs14[] = { {0,1},{5,7},{15,24},{30,39} };
+    set.insert( interval( 15, 16 ) ); CALL_CHECK( set, pairs14 );
+
+    static const Pair pairs15[] = { {0,1},{5,7},{15,27},{30,39} };
+    set.insert( interval( 25, 27 ) ); CALL_CHECK( set, pairs15 );
+
+    // find, find_bound
+
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( -2 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( -1 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = set.find( 0 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = set.find( 1 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( 2 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( 3 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( 4 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = set.find( 5 )) != set.end()) && (it->first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find", ((it = set.find( 39 )) != set.end()) && (it->first == 30) );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( 40 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find", (it = set.find( 41 )) == set.end() );
+
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( -2 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( -1 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 0 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 1 )) != set.end()) && (it->first == 0) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 2 )) != set.end()) && (it->first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 3 )) != set.end()) && (it->first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 4 )) != set.end()) && (it->first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 5 )) != set.end()) && (it->first == 5) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", ((it = set.find_bound( 39 )) != set.end()) && (it->first == 30) );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", (it = set.find_bound( 40 )) == set.end() );
+    CPPUNIT_ASSERT_MESSAGE( "find_bound", (it = set.find_bound( 41 )) == set.end() );
+
+    // make intersection
+
+    static const Pair pairs_int[] = { {6,7},{15,27},{30,33} };
+    set_type set2 = set.make_intersection( interval( 6, 33 ) ); CALL_CHECK( set2, pairs_int );
+
+    // range c'tor, range insert, insert custom interval type
+
+    static const Pair pairs15a[] = { {7,7},{15,26} };
+    static const Pair init1[] = { {15,26},{7,7} };
+    set_type set3( init1, init1 + sizeof(init1)/sizeof(Pair) ); CALL_CHECK( set3, pairs15a );
+
+    static const Pair pairs15b[] = { {7,7},{15,26},{30,32} };
+    static const Pair init2 = {30,32};
+    set3.insert( init2 ); CALL_CHECK( set3, pairs15b );
+
+    static const int init3[] = {33,6,27};
+    set3.insert( init3, init3 + sizeof(init3)/sizeof(int) ); CALL_CHECK( set3, pairs_int );
+
+    // operator==
+
+    CPPUNIT_ASSERT_MESSAGE( "operator==", set2 == set3 );
+    set3.insert( 35 );
+    CPPUNIT_ASSERT_MESSAGE( "operator!=", set2 != set3 );
+    set3.insert( 34 );
+    CPPUNIT_ASSERT_MESSAGE( "operator!=", set2 != set3 );
+
+    // merge and overwrite
+
+    static const Pair pairs16[] = { {0,8},{15,27},{30,39} };
+    set.insert( interval( 1, 8 ) ); CALL_CHECK( set, pairs16 );
+
+    static const Pair pairs17[] = { {0,39} };
+    set.insert( interval( 9, 29 ) ); CALL_CHECK( set, pairs17 );
+
+    // remove inside range
+
+    static const Pair pairs18[] = { {0,9},{11,19},{21,29},{31,39} };
+    set.erase( 10 ); set.erase( 20 ); set.erase( 30 ); CALL_CHECK( set, pairs18 );
+
+    static const Pair pairs19[] = { {0,9},{11,19},{24,29},{31,39} };
+    set.erase( interval( 21, 23 ) ); CALL_CHECK( set, pairs19 );
+
+    static const Pair pairs20[] = { {0,9},{11,19},{24,26},{31,39} };
+    set.erase( interval( 27, 29 ) ); CALL_CHECK( set, pairs20 );
+
+    static const Pair pairs21[] = { {0,9},{11,19},{31,39} };
+    set.erase( interval( 24, 26 ) ); CALL_CHECK( set, pairs21 );
+
+    // remove outside ranges
+
+    set.erase( -1 ); CALL_CHECK( set, pairs21 );
+    set.erase( 10 ); CALL_CHECK( set, pairs21 );
+    set.erase( interval( 20, 22 ) ); CALL_CHECK( set, pairs21 );
+    set.erase( interval( 29, 30 ) ); CALL_CHECK( set, pairs21 );
+    set.erase( interval( 20, 30 ) ); CALL_CHECK( set, pairs21 );
+    set.erase( interval( 40, 41 ) ); CALL_CHECK( set, pairs21 );
+
+    // remove in several ranges
+
+    static const Pair pairs22[] = { {0,6},{13,19},{31,39} };
+    set.erase( interval( 7, 12 ) ); CALL_CHECK( set, pairs22 );
+
+    static const Pair pairs23[] = { {0,5},{33,39} };
+    set.erase( interval( 6, 32 ) ); CALL_CHECK( set, pairs23 );
+
+    static const Pair pairs24[] = { {0,0} };
+    set.erase( interval( 1, 44 ) ); CALL_CHECK( set, pairs24 );
+
+    set.erase( interval( -1, 1 ) );
+    CPPUNIT_ASSERT_MESSAGE( "empty", set.empty() );
+
+#undef CALL_CHECK
+}
+
+void interval_set_test::check_set( const set_type& set, const Pair* pairs, size_t len, int line )
+{
+    const Pair* pairsend = pairs + len;
+    set_type::const_iterator it = set.begin(), itend = set.end();
+    int index = 0;
+    char buffer[ 256 ];
+    while( (it != itend) || (pairs != pairsend) )
+    {
+        bool itvalid = it != itend;
+        bool pairsvalid = pairs != pairsend;
+        if( itvalid && pairsvalid )
+            sprintf( buffer, "line: %d; failed: #%d; exp: (%d,%d); found: (%d,%d)", line, index, pairs->first, pairs->second, it->first, it->second );
+        else if( itvalid )
+            sprintf( buffer, "line: %d; failed: #%d; exp: [end]; found: (%d,%d)", line, index, it->first, it->second );
+        else
+            sprintf( buffer, "line: %d; failed: #%d; exp: (%d,%d); found: [end]", line, index, pairs->first, pairs->second );
+        CPPUNIT_ASSERT_MESSAGE( buffer, itvalid && pairsvalid && (it->first == pairs->first) && (it->second == pairs->second) );
+        if( itvalid ) ++it;
+        if( pairsvalid ) ++pairs;
+        ++index;
+    }
+}
+
+// -----------------------------------------------------------------------------
+
+CPPUNIT_TEST_SUITE_REGISTRATION(interval_set_test);
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.