1 /* 2 * Copyright 2006-2008 The FLWOR Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #pragma once 17 #ifndef ZORBA_STL_UTIL_H 18 #define ZORBA_STL_UTIL_H 19 20 #include <algorithm> 21 #include <cassert> 22 #include <cstring> 23 #include <functional> 24 #include <iterator> 25 #include <limits> 26 #include <set> 27 #include <stack> 28 29 #include <zorba/config.h> 30 #include <zorba/internal/ztd.h> 31 32 #include "cxx_util.h" 33 34 namespace zorba { 35 namespace ztd { 36 37 using internal::ztd::destroy_delete; 38 using internal::ztd::has_insertion_operator; 39 using internal::ztd::less; 40 41 /////////////////////////////////////////////////////////////////////////////// 42 43 /** 44 * A less-verbose way to iterate over a constant sequence. 45 */ 46 #define FOR_EACH(TYPE,IT,SEQ) \ 47 for ( TYPE::const_iterator IT = (SEQ).begin(); IT != (SEQ).end(); ++IT ) 48 49 /** 50 * A less-verbose way to iterate over a mutable sequence. 51 */ 52 #define MUTATE_EACH(TYPE,IT,SEQ) \ 53 for ( TYPE::iterator IT = (SEQ).begin(); IT != (SEQ).end(); ++IT ) 54 55 /////////////////////////////////////////////////////////////////////////////// 56 57 /** 58 * A version of std::back_insert_iterator that's suitable as a base-class (the 59 * standard one is not). 60 * 61 * @tparam ContainerType The type of the container to insert into. 62 * @tparam DerivedType The type of the class deriving from this. 63 */ 64 template<class ContainerType,class DerivedType> 65 class back_insert_iterator_base : 66 public std::iterator<std::output_iterator_tag,void,void,void,void> { 67 public: 68 typedef ContainerType container_type; 69 70 DerivedType& operator*() { 71 return *static_cast<DerivedType*>( this ); 72 } 73 74 DerivedType& operator++() { 75 return *static_cast<DerivedType*>( this ); 76 } 77 78 DerivedType& operator++(int) { 79 return *static_cast<DerivedType*>( this ); 80 } 81 82 protected: back_insert_iterator_base(ContainerType & c)83 back_insert_iterator_base( ContainerType &c ) : container( &c ) { 84 } 85 86 /** 87 * A pointer is used (rather than a reference) so this class can be copy 88 * constructed. 89 */ 90 ContainerType *container; 91 }; 92 93 /////////////////////////////////////////////////////////////////////////////// 94 95 /** 96 * Implementation of SGI's %identity extension. 97 * See: http://www.sgi.com/tech/stl/identity.html 98 */ 99 template<typename T> 100 struct identity : std::unary_function<T,T> { operatoridentity101 T const& operator()( T const &a ) const { 102 return a; 103 } 104 }; 105 106 /** 107 * Implementation of SGI's %select1st extension. 108 * See: http://www.sgi.com/tech/stl/select1st.html 109 */ 110 template<typename PairType> 111 struct select1st : std::unary_function<PairType,typename PairType::first_type> { operatorselect1st112 typename PairType::first_type const& operator()( PairType const &a ) const { 113 return a.first; 114 } 115 }; 116 117 /////////////////////////////////////////////////////////////////////////////// 118 119 /** 120 * Determines whether the given type \c T is efficiently passed by value. 121 */ 122 template<typename T> 123 struct is_passable_by_value { 124 static bool const value = 125 ZORBA_TR1_NS::is_arithmetic<T>::value 126 || ZORBA_TR1_NS::is_enum<T>::value 127 || ZORBA_TR1_NS::is_pointer<T>::value 128 || ZORBA_TR1_NS::is_reference<T>::value 129 || ZORBA_TR1_NS::is_member_function_pointer<T>::value; 130 }; 131 132 /** 133 * Useful traits when declaring functions. 134 * This class is similar to boost::call_traits. 135 * 136 * @tparam T A type that is used for a function formal argument or return type. 137 */ 138 template<typename T,bool = is_passable_by_value<T>::value> 139 struct call_traits { 140 /** 141 * A type that is guaranteed to be the most efficient to use as a formal 142 * argument. 143 */ 144 typedef T const arg_type; 145 }; 146 147 /** 148 * Partial specialization for when \c T is not efficiently passed by value. 149 */ 150 template<typename T> 151 struct call_traits<T,false> { 152 typedef T const& arg_type; 153 }; 154 155 /////////////////////////////////////////////////////////////////////////////// 156 157 /** 158 * A less-verbose way to determine whether the given map or set contains a 159 * particular element. 160 */ 161 template<class ContainerType> inline 162 bool contains( 163 ContainerType const &s, 164 typename call_traits<typename ContainerType::key_type>::arg_type v ) { 165 return s.find( v ) != s.end(); 166 } 167 168 /** 169 * Like std::copy(), but copy at most N elements. 170 */ 171 template<typename InputIterator, typename SizeType, typename OutputIterator> 172 inline OutputIterator copy_n( InputIterator first, SizeType count, 173 OutputIterator result ) { 174 for ( SizeType i = 0; i < count; ++i, *result++ = *first++ ) 175 ; 176 return result; 177 } 178 179 /** 180 * A less-verbose way to copy the given sequence. 181 */ 182 template<class FromSequenceType,class ToSequenceType> inline 183 void copy_seq( FromSequenceType const &from, ToSequenceType &to ) { 184 std::copy( from.begin(), from.end(), std::back_inserter( to ) ); 185 } 186 187 /** 188 * A less-verbose way to copy the given set. 189 */ 190 template<class FromSequenceType,class ToSequenceType> inline 191 void copy_set( FromSequenceType const &from, ToSequenceType &to ) { 192 std::copy( from.begin(), from.end(), std::inserter( to, to.begin() ) ); 193 } 194 195 /** 196 * Given a seq<T*>, deletes all the elements. 197 */ 198 template<class SequenceType> inline 199 void delete_ptr_seq( SequenceType &seq ) { 200 MUTATE_EACH( typename SequenceType, i, seq ) 201 delete *i; 202 } 203 204 /** 205 * Erases all elements in the given container for which the given predicate is 206 * \c true. 207 * 208 * @tparam SequenceType The sequence type. 209 * @tparam PredicateType The predicate type. 210 * @param seq The sequence to modify. 211 * @param pred The predicate to use. 212 * @return Returns the number of elements erased. 213 */ 214 template<class SequenceType,class PredicateType> inline 215 typename SequenceType::size_type erase_if( SequenceType &seq, 216 PredicateType pred ) { 217 typename SequenceType::size_type erased = 0; 218 for ( typename SequenceType::iterator i = seq.begin(); i != seq.end(); ) { 219 if ( pred( *i ) ) { 220 i = seq.erase( i ); 221 ++erased; 222 } else 223 ++i; 224 } 225 return erased; 226 } 227 228 /** 229 * Erases only the first element in the given sequence for which the given 230 * predicate is \c true. 231 * 232 * @tparam SequenceType The sequence type. 233 * @tparam PredicateType The predicate type. 234 * @param seq The sequence to modify. 235 * @param pred The predicate to use. 236 * @return Returns \c true only if an element was erased; \c false otherwise. 237 */ 238 template<class SequenceType,class PredicateType> inline 239 bool erase_1st_if( SequenceType &seq, PredicateType pred ) { 240 MUTATE_EACH( typename SequenceType, i, seq ) { 241 if ( pred( *i ) ) { 242 seq.erase( i ); 243 return true; 244 } 245 } 246 return false; 247 } 248 249 /** 250 * Moves the first element of the first sequence to the back of the second. 251 */ 252 template<class FromSequenceType,class ToSequenceType> inline 253 void move_front_to_back( FromSequenceType &from, ToSequenceType &to ) { 254 to.push_back( from.front() ); 255 from.pop_front(); 256 } 257 258 /** 259 * Same as std::strdup(3) except it uses C++'s \c new[] rather than malloc(3). 260 * 261 * @param s The C string to duplicate. 262 * @return Returns a copy of \a s. Deallocation via \c delete[] is the 263 * responsibility of the caller. 264 */ 265 inline char* new_strdup( char const *s ) { 266 return std::strcpy( new char[ std::strlen( s ) + 1 ], s ); 267 } 268 269 /** 270 * A less-verbose way to pop the first element from a sequence. 271 */ 272 template<class SequenceType> inline 273 typename SequenceType::value_type pop_front( SequenceType &seq ) { 274 assert( !seq.empty() ); 275 typename SequenceType::value_type const value( seq.front() ); 276 seq.pop_front(); 277 return value; 278 } 279 280 /** 281 * A less-verbose way to pop an element from a stack. 282 */ 283 template<class StackType> inline 284 typename StackType::value_type pop_stack( StackType &s ) { 285 assert( !s.empty() ); 286 typename StackType::value_type const value( s.top() ); 287 s.pop(); 288 return value; 289 } 290 291 /** 292 * A less verbose way to compare the top value of a stack for equality with a 293 * given value. 294 */ 295 template<class StackType> inline 296 bool top_stack_equals( 297 StackType const &s, 298 typename call_traits<typename StackType::value_type>::arg_type v ) { 299 return !s.empty() && s.top() == v; 300 } 301 302 /////////////////////////////////////////////////////////////////////////////// 303 304 template<typename NumericType> inline 305 typename std::enable_if<ZORBA_TR1_NS::is_arithmetic<NumericType>::value, 306 bool>::type 307 gt0( NumericType n ) { // for completeness 308 return n > 0; 309 } 310 311 template<typename NumericType> inline 312 typename std::enable_if<ZORBA_TR1_NS::is_signed<NumericType>::value,bool>::type 313 ge0( NumericType n ) { 314 return n >= 0; 315 } 316 317 template<typename IntType> inline 318 typename std::enable_if<ZORBA_TR1_NS::is_unsigned<IntType>::value,bool>::type 319 ge0( IntType ) { 320 return true; 321 } 322 323 template<typename NumericType> inline 324 typename std::enable_if<ZORBA_TR1_NS::is_signed<NumericType>::value,bool>::type 325 lt0( NumericType n ) { 326 return n < 0; 327 } 328 329 template<typename IntType> inline 330 typename std::enable_if<ZORBA_TR1_NS::is_unsigned<IntType>::value,bool>::type 331 lt0( IntType ) { 332 return false; 333 } 334 335 template<typename NumericType> inline 336 typename std::enable_if<ZORBA_TR1_NS::is_signed<NumericType>::value,bool>::type 337 le0( NumericType n ) { 338 return n <= 0; 339 } 340 341 template<typename IntType> inline 342 typename std::enable_if<ZORBA_TR1_NS::is_unsigned<IntType>::value,bool>::type 343 le0( IntType n ) { 344 return n == 0; 345 } 346 347 /////////////////////////////////////////////////////////////////////////////// 348 349 // 350 // These functions are used to test whether a value of numeric type N1 is 351 // within the range of another numeric type N2. It correctly handles the 352 // cases where the "signed-ness" of N1 and N2 differ such that the code is 353 // warning-free. 354 // 355 // Note: the use of "!!" is to work around a compiler problem on Windows; 356 // see: http://stackoverflow.com/questions/9285657/sfinae-differentiation-between-signed-and-unsigned 357 // 358 359 template<typename N1,typename N2> inline 360 typename std::enable_if<ZORBA_TR1_NS::is_signed<N1>::value 361 && ZORBA_TR1_NS::is_signed<N2>::value,bool>::type 362 ge_min( N1 n1, N2 ) { 363 return n1 >= std::numeric_limits<N2>::min(); 364 } 365 366 template<typename N1,typename N2> inline 367 typename std::enable_if<ZORBA_TR1_NS::is_signed<N1>::value 368 && !!ZORBA_TR1_NS::is_unsigned<N2>::value,bool>::type 369 ge_min( N1 n1, N2 ) { 370 return n1 >= 0; 371 } 372 373 template<typename N1,typename N2> inline 374 typename std::enable_if<!!ZORBA_TR1_NS::is_unsigned<N1>::value 375 && ZORBA_TR1_NS::is_signed<N2>::value,bool>::type 376 ge_min( N1, N2 ) { 377 return true; 378 } 379 380 template<typename N1,typename N2> inline 381 typename std::enable_if<!!ZORBA_TR1_NS::is_unsigned<N1>::value 382 && !!ZORBA_TR1_NS::is_unsigned<N2>::value,bool>::type 383 ge_min( N1, N2 ) { 384 return true; 385 } 386 387 template<typename N1,typename N2> inline 388 typename std::enable_if<ZORBA_TR1_NS::is_signed<N1>::value 389 && ZORBA_TR1_NS::is_signed<N2>::value,bool>::type 390 le_max( N1 n1, N2 ) { 391 return n1 <= std::numeric_limits<N2>::max(); 392 } 393 394 template<typename N1,typename N2> inline 395 typename std::enable_if<ZORBA_TR1_NS::is_signed<N1>::value 396 && !!ZORBA_TR1_NS::is_unsigned<N2>::value,bool>::type 397 le_max( N1 n1, N2 ) { 398 return n1 <= 0 || static_cast<N2>( n1 ) <= std::numeric_limits<N2>::max(); 399 } 400 401 template<typename N1,typename N2> inline 402 typename std::enable_if<!!ZORBA_TR1_NS::is_unsigned<N1>::value 403 && ZORBA_TR1_NS::is_signed<N2>::value,bool>::type 404 le_max( N1 n1, N2 ) { 405 return n1 <= static_cast<N1>( std::numeric_limits<N2>::max() ); 406 } 407 408 template<typename N1,typename N2> inline 409 typename std::enable_if<!!ZORBA_TR1_NS::is_unsigned<N1>::value 410 && !!ZORBA_TR1_NS::is_unsigned<N2>::value,bool>::type 411 le_max( N1 n1, N2 ) { 412 return n1 <= std::numeric_limits<N2>::max(); 413 } 414 415 #define ZORBA_GE_MIN(N,T) \ 416 ::zorba::ztd::ge_min( N, static_cast<T>(0) ) 417 418 #define ZORBA_LE_MAX(N,T) \ 419 ::zorba::ztd::le_max( N, static_cast<T>(0) ) 420 421 #define ZORBA_IN_RANGE(N,T) \ 422 ( ZORBA_GE_MIN(N,T) && ZORBA_LE_MAX(N,T) ) 423 424 /////////////////////////////////////////////////////////////////////////////// 425 426 template<typename T> class stack_generator { 427 std::stack<T> &stk; 428 public: 429 stack_generator (std::stack<T> &stk_) : stk (stk_) { } 430 T operator()() { 431 assert( !stk.empty() ); 432 T const x = stk.top(); 433 stk.pop(); 434 return x; 435 } 436 }; 437 438 template<typename T> inline 439 stack_generator<T> stack_to_generator(std::stack<T> &stk) { 440 return stack_generator<T>( stk ); 441 } 442 443 /////////////////////////////////////////////////////////////////////////////// 444 445 } // namespace ztd 446 } // namespace zorba 447 #endif /* ZORBA_STL_UTIL_H */ 448 /* vim:set et sw=2 ts=2: */ 449