MOAB: Mesh Oriented datABase  (version 5.2.1)
RangeMap.hpp
Go to the documentation of this file.
00001 /*
00002  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
00003  * storing and accessing finite element mesh data.
00004  *
00005  * Copyright 2004 Sandia Corporation.  Under the terms of Contract
00006  * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
00007  * retains certain rights in this software.
00008  *
00009  * This library is free software; you can redistribute it and/or
00010  * modify it under the terms of the GNU Lesser General Public
00011  * License as published by the Free Software Foundation; either
00012  * version 2.1 of the License, or (at your option) any later version.
00013  *
00014  */
00015 
00016 /**\file RangeMap.hpp
00017  *\author Jason Kraftcheck (kraftche@cae.wisc.edu)
00018  *\date 2007-04-25
00019  */
00020 
00021 #ifndef MOAB_RANGE_MAP_HPP
00022 #define MOAB_RANGE_MAP_HPP
00023 
00024 #include <vector>
00025 #include <algorithm>
00026 
00027 namespace moab
00028 {
00029 
00030 /**\brief Map ranges of values
00031  *
00032  * This class provides a map between ranges of values, such as
00033  * a map between file IDs and EntityHandles.  It is intended
00034  * for use in situations where there are relatively few insertions
00035  * of large contiguous ranges of values.
00036  */
00037 template < typename KeyType, typename ValType, ValType NullVal = 0 >
00038 class RangeMap
00039 {
00040   public:
00041     typedef KeyType key_type;
00042     typedef ValType value_type;
00043 
00044     struct Range
00045     {
00046         KeyType begin, count;
00047         ValType value;
00048         bool operator<( const Range& other ) const
00049         {
00050             return begin + count <= other.begin;
00051         }  // equal if overlapping!
00052     };
00053     typedef typename std::vector< Range > RangeList;
00054     typedef typename RangeList::const_iterator iterator;
00055     typedef typename RangeList::const_iterator const_iterator;
00056 
00057     inline bool empty() const
00058     {
00059         return data.empty();
00060     }
00061 
00062     inline const Range& back() const
00063     {
00064         return data.back();
00065     }
00066     inline const Range& front() const
00067     {
00068         return data.front();
00069     }
00070 
00071     /**\brief Insert mapping between range of keys and range of values
00072      *
00073      * Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)
00074      *
00075      * Input range of keys many not overlap any other input range.  If it does overlap
00076      * an existing range, the second value of the pair will be returned as false
00077      * and the iterator will point to (one of) the overlapping ranges.
00078      */
00079     inline std::pair< iterator, bool > insert( KeyType first_key, ValType first_val, KeyType count );
00080 
00081     /**\brief Insert mapping between range of keys and range of values
00082      *
00083      * Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)
00084      *
00085      * Input range of keys many not overlap any other input range.  If it does overlap
00086      * an existing range, the second value of the pair will be returned as false
00087      * and the iterator will point to (one of) the overlapping ranges.
00088      */
00089     inline bool merge( const RangeMap< KeyType, ValType, NullVal >& other );
00090 
00091     /** Find the value corresponding to the specified key.  Returns NullVal if not found */
00092     inline ValType find( KeyType key ) const;
00093 
00094     /** Find the value corresponding to the specified key.  Returns false if not found */
00095     inline bool find( KeyType key, ValType& val_out ) const;
00096 
00097     /** Check if range contains key */
00098     inline bool exists( KeyType key ) const;
00099 
00100     /** Check if range contains key */
00101     inline bool intersects( KeyType start, KeyType count ) const;
00102 
00103     /** Remove a block of values */
00104     inline iterator erase( KeyType beg, KeyType count );
00105 
00106     inline unsigned num_ranges() const
00107     {
00108         return data.size();
00109     }
00110 
00111     inline iterator begin() const
00112     {
00113         return data.begin();
00114     }
00115     inline iterator end() const
00116     {
00117         return data.end();
00118     }
00119     inline iterator lower_bound( KeyType key ) const
00120     {
00121         Range b = { key, 1, NullVal };
00122         return std::lower_bound( begin(), end(), b );
00123     }
00124     static inline iterator lower_bound( iterator s, iterator e, KeyType key )
00125     {
00126         Range b = { key, 1, NullVal };
00127         return std::lower_bound( s, e, b );
00128     }
00129     inline iterator upper_bound( KeyType key ) const
00130     {
00131         Range b = { key, 1, NullVal };
00132         return std::upper_bound( begin(), end(), b );
00133     }
00134     static inline iterator upper_bound( iterator s, iterator e, KeyType key )
00135     {
00136         Range b = { key, 1, NullVal };
00137         return std::upper_bound( s, e, b );
00138     }
00139     inline std::pair< iterator, iterator > equal_range( KeyType key ) const
00140     {
00141         Range b = { key, 1, NullVal };
00142         return std::equal_range( begin(), end(), b );
00143     }
00144 
00145     inline void clear()
00146     {
00147         data.clear();
00148     }
00149 
00150   protected:
00151     RangeList data;
00152 };
00153 
00154 template < typename KeyType, typename ValType, ValType NullVal >
00155 inline std::pair< typename RangeMap< KeyType, ValType, NullVal >::iterator, bool > RangeMap<
00156     KeyType, ValType, NullVal >::insert( KeyType first_key, ValType first_val, KeyType count )
00157 {
00158     Range block                    = { first_key, count, first_val };
00159     typename RangeList::iterator i = std::lower_bound( data.begin(), data.end(), block );
00160 
00161     if( i == data.end() )
00162     {
00163         if( i != data.begin() )
00164         {
00165             --i;
00166             if( i->begin + i->count == first_key && i->value + i->count == first_val )
00167             {
00168                 i->count += count;
00169                 return std::pair< iterator, bool >( i, true );
00170             }
00171         }
00172         data.push_back( block );
00173         return std::pair< iterator, bool >( data.end() - 1, true );
00174     }
00175 
00176     if( i->begin < first_key + count ) return std::pair< iterator, bool >( i, false );
00177 
00178     if( i->begin == first_key + count && i->value == first_val + count )
00179     {
00180         i->begin = first_key;
00181         i->value = first_val;
00182         i->count += count;
00183         if( i != data.begin() )
00184         {
00185             count = i->count;
00186             --i;
00187             if( i->begin + i->count == first_key && i->value + i->count == first_val )
00188             {
00189                 i->count += count;
00190                 ++i;
00191                 i = data.erase( i );
00192                 --i;
00193             }
00194         }
00195         return std::pair< iterator, bool >( i, true );
00196     }
00197 
00198     if( i != data.begin() )
00199     {
00200         --i;
00201         if( i->begin + i->count == first_key && i->value + i->count == first_val )
00202         {
00203             i->count += count;
00204             return std::pair< iterator, bool >( i, true );
00205         }
00206         ++i;
00207     }
00208 
00209     return std::pair< iterator, bool >( data.insert( i, block ), true );
00210 }
00211 
00212 template < typename KeyType, typename ValType, ValType NullVal >
00213 inline bool RangeMap< KeyType, ValType, NullVal >::merge( const RangeMap< KeyType, ValType, NullVal >& other )
00214 {
00215     // grow map sufficiently to hold new ranges
00216     RangeList new_data;
00217     new_data.reserve( other.data.size() + data.size() );
00218 
00219     // merge
00220     typename RangeList::const_iterator i = other.data.begin();
00221     typename RangeList::const_iterator j = data.begin();
00222     typename RangeList::const_iterator k;
00223     while( i != other.data.end() || j != data.end() )
00224     {
00225         if( j != data.end() && ( i == other.data.end() || j->begin < i->begin ) )
00226         {
00227             k = j;
00228             ++j;
00229         }
00230         else if( i != other.data.end() )
00231         {
00232             k = i;
00233             ++i;
00234         }
00235 
00236         // check if we need to merge with the end of the previous block
00237         if( new_data.empty() )
00238             new_data.push_back( *k );
00239         else if( new_data.back().begin + new_data.back().count > k->begin )
00240             return false;
00241         else if( new_data.back().begin + new_data.back().count == k->begin &&
00242                  new_data.back().value + new_data.back().count == k->value )
00243             new_data.back().count += k->count;
00244         else
00245             new_data.push_back( *k );
00246     }
00247 
00248     data.swap( new_data );
00249     return true;
00250 }
00251 
00252 template < typename KeyType, typename ValType, ValType NullVal >
00253 inline ValType RangeMap< KeyType, ValType, NullVal >::find( KeyType key ) const
00254 {
00255     Range search                         = { key, 1, NullVal };
00256     typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00257     if( i == data.end() || i->begin > key ) return NullVal;
00258 
00259     return i->value + key - i->begin;
00260 }
00261 
00262 template < typename KeyType, typename ValType, ValType NullVal >
00263 inline bool RangeMap< KeyType, ValType, NullVal >::find( KeyType key, ValType& val ) const
00264 {
00265     Range search                         = { key, 1, NullVal };
00266     typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00267     if( i == data.end() || i->begin > key )
00268     {
00269         val = NullVal;
00270         return false;
00271     }
00272 
00273     val = i->value + key - i->begin;
00274     return true;
00275 }
00276 
00277 template < typename KeyType, typename ValType, ValType NullVal >
00278 inline bool RangeMap< KeyType, ValType, NullVal >::exists( KeyType key ) const
00279 {
00280     Range search                         = { key, 1, NullVal };
00281     typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00282     return i != data.end() && key >= i->begin;
00283 }
00284 
00285 template < typename KeyType, typename ValType, ValType NullVal >
00286 inline bool RangeMap< KeyType, ValType, NullVal >::intersects( KeyType start, KeyType count ) const
00287 {
00288     Range search                         = { start, count, NullVal };
00289     typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00290     return i != data.end() && start + count > i->begin && i->begin + i->count > start;
00291 }
00292 
00293 template < typename KeyType, typename ValType, ValType NullVal >
00294 inline typename RangeMap< KeyType, ValType, NullVal >::iterator RangeMap< KeyType, ValType, NullVal >::erase(
00295     KeyType key, KeyType count )
00296 {
00297     Range search = { key, 1, NullVal };
00298     typename RangeList::iterator i, j;
00299     i = std::lower_bound( data.begin(), data.end(), search );
00300 
00301     if( i == data.end() ) return i;
00302 
00303     if( key > i->begin )
00304     {
00305         KeyType offset = key - i->begin;
00306         // special case - split existing entry
00307         if( ( offset + count ) < i->count )
00308         {
00309             Range ins = { i->begin, offset, i->value };
00310             offset += count;
00311             i->begin += offset;
00312             i->value += offset;
00313             i->count -= offset;
00314             return data.insert( i, ins ) + 1;
00315         }
00316         // otherwise remove the latter part of i
00317         i->count = offset;
00318         ++i;
00319     }
00320 
00321     // remove any entries entirely convered by the input range
00322     for( j = i; j != data.end() && ( j->begin + j->count ) <= ( key + count ); ++j )
00323         ;
00324     i = data.erase( i, j );
00325 
00326     // remove beginning of last block
00327     if( i != data.end() && ( key + count ) >= i->begin )
00328     {
00329         KeyType offset = key + count - i->begin;
00330         i->begin += offset;
00331         i->value += offset;
00332         i->count -= offset;
00333     }
00334 
00335     return i;
00336 }
00337 
00338 }  // namespace moab
00339 
00340 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines