// bdlc_packedintarrayutil.h -*-C++-*- #ifndef INCLUDED_BDLC_PACKEDINTARRAYUTIL #define INCLUDED_BDLC_PACKEDINTARRAYUTIL #include <bsls_ident.h> BSLS_IDENT("$Id: $") //@PURPOSE: Provide common non-primitive operations on 'bdlc::PackedIntArray'. // //@CLASSES: // bdlc::PackedIntArrayUtil: non-primitive 'bdlc::PackedIntArray' operations // //@SEE_ALSO: bdlc_packedintarray // //@DESCRIPTION: This component provides a 'struct', 'bdlc::PackedIntArrayUtil', // that serves as a namespace for utility functions that operate on // 'bdlc::PackedIntArray' objects. // // The following list of methods are provided by 'bdlc::PackedIntArrayUtil': //.. // 'isSorted' Returns 'true' if the range from a // 'bdlc::PackedIntArray' is sorted, and 'false' otherwise. // // 'lowerBound' Returns an iterator to the first element in a sorted // range from a 'bdlc::PackedIntArray' that compares // greater than or equal to a specified value. // // 'upperBound' Returns an iterator to the first element in a sorted // range from a 'bdlc::PackedIntArray' that compares // greater than a specified value. //.. // ///Usage ///----- // This section illustrates intended use of this component. // ///Example 1: 'lowerBound' ///- - - - - - - - - - - - // Suppose that given a sorted 'bdlc::PackedIntArray', we want to find the // first value greater than or equal to the value 17. First, create and // populate with sorted data the 'bdlc::PackedIntArray' to be searched: //.. // bdlc::PackedIntArray<int> array; // // array.push_back( 5); // array.push_back( 9); // array.push_back(15); // array.push_back(19); // array.push_back(23); // array.push_back(36); // assert(6 == array.length()); //.. // Then, verify the array's data has sorted values: //.. // assert(bdlc::PackedIntArrayUtil::isSorted(array.begin(), array.end())); //.. // Finally, use 'bdlc::PackedIntArrayUtil::lowerBound' to find the desired // value: //.. // bdlc::PackedIntArrayConstIterator<int> iterator = // bdlc::PackedIntArrayUtil::lowerBound(array.begin(), // array.end(), // 17); // assert(iterator != array.end() && 19 == *iterator); //.. #include <bdlscm_version.h> #include <bdlc_packedintarray.h> #include <bsls_assert.h> namespace BloombergLP { namespace bdlc { // ========================= // struct PackedIntArrayUtil // ========================= struct PackedIntArrayUtil { // This 'struct' provides a namespace for utility functions that provide // non-primitive operations on 'bdlc::PackedIntArray'. public: // CLASS METHODS template <class TYPE> static bool isSorted(PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last); // Return 'true' if the range from the specified 'first' (inclusive) to // the specified 'last' (exclusive) is sorted or empty, and 'false' // otherwise. The behavior is undefined unless 'first <= last'. template <class TYPE> static PackedIntArrayConstIterator<TYPE> lowerBound( PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last, TYPE value); // Return an iterator to the first element in the sorted range from the // specified 'first' (inclusive) to the specified 'last' (exclusive) // that compares greater than or equal to the specified 'value', and // 'last' if no such element exists. The behavior is undefined unless // 'first <= last' and the range is sorted. template <class TYPE> static PackedIntArrayConstIterator<TYPE> upperBound( PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last, TYPE value); // Return an iterator to the first element in the sorted range from the // specified 'first' (inclusive) to the specified 'last' (exclusive) // that compares greater than the specified 'value', and 'last' if no // such element exists. The behavior is undefined unless // 'first <= last' and the range is sorted. }; // ============================================================================ // INLINE DEFINITIONS // ============================================================================ // ------------------------- // struct PackedIntArrayUtil // ------------------------- // CLASS METHODS template <class TYPE> bool PackedIntArrayUtil::isSorted(PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last) { BSLS_ASSERT(first <= last); PackedIntArrayConstIterator<TYPE> at = first; PackedIntArrayConstIterator<TYPE> prev = first; while (at < last) { if (*prev > *at) { return false; // RETURN } prev = at++; } return true; } template <class TYPE> PackedIntArrayConstIterator<TYPE> PackedIntArrayUtil::lowerBound( PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last, TYPE value) { BSLS_ASSERT(first <= last); BSLS_ASSERT_SAFE(isSorted(first, last)); typedef typename PackedIntArrayConstIterator<TYPE>::difference_type difference_type; difference_type count = last - first; while (count > 0) { difference_type step = count / 2; PackedIntArrayConstIterator<TYPE> it = first + step; if (*it < value) { first = ++it; count -= step + 1; } else { count = step; } } return first; } template <class TYPE> PackedIntArrayConstIterator<TYPE> PackedIntArrayUtil::upperBound( PackedIntArrayConstIterator<TYPE> first, PackedIntArrayConstIterator<TYPE> last, TYPE value) { BSLS_ASSERT(first <= last); BSLS_ASSERT_SAFE(isSorted(first, last)); typedef typename PackedIntArrayConstIterator<TYPE>::difference_type difference_type; difference_type count = last - first; while (count > 0) { difference_type step = count / 2; PackedIntArrayConstIterator<TYPE> it = first + step; if (*it <= value) { first = ++it; count -= step + 1; } else { count = step; } } return first; } } // close package namespace } // close enterprise namespace #endif // ---------------------------------------------------------------------------- // Copyright 2015 Bloomberg Finance L.P. // // 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. // ----------------------------- END-OF-FILE ----------------------------------