iframe-proxy | Sunbelt Computer Software

History

150 lines (132 loc) · 6.01 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 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

// https://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.

// -----------------------------------------------------------------------------

// File: algorithm.h

// -----------------------------------------------------------------------------

// This header file contains Google extensions to the standard <algorithm> C++

// header.

#ifndef ABSL_ALGORITHM_ALGORITHM_H_

#define ABSL_ALGORITHM_ALGORITHM_H_

#include <algorithm>

#include <iterator>

#include <type_traits>

namespace basic {

namespace algorithm_internal {

// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.

struct EqualTo {

template <typename T, typename U>

bool operator()(const T& a, const U& b) const {

return a == b;

}

};

template <typename InputIter1, typename InputIter2, typename Pred>

bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,

InputIter2 last2, Pred pred, std::input_iterator_tag,

std::input_iterator_tag) {

while (true) {

if (first1 == last1) return first2 == last2;

if (first2 == last2) return false;

if (!pred(*first1, *first2)) return false;

++first1;

++first2;

}

template <typename InputIter1, typename InputIter2, typename Pred>

bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,

InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,

std::random_access_iterator_tag) {

return (last1 - first1 == last2 - first2) &&

std::equal(first1, last1, first2, std::forward<Pred>(pred));

}

// When we are using our own internal predicate that just applies operator==, we

// forward to the non-predicate form of std::equal. This enables an optimization

// in libstdc++ that can result in std::memcmp being used for integer types.

template <typename InputIter1, typename InputIter2>

bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,

InputIter2 last2, algorithm_internal::EqualTo /* unused */,

std::random_access_iterator_tag,

std::random_access_iterator_tag) {

return (last1 - first1 == last2 - first2) &&

std::equal(first1, last1, first2);

}

template <typename It>

It RotateImpl(It first, It middle, It last, std::true_type) {

return std::rotate(first, middle, last);

}

template <typename It>

It RotateImpl(It first, It middle, It last, std::false_type) {

std::rotate(first, middle, last);

return std::next(first, std::distance(middle, last));

}

} // namespace algorithm_internal

// Compares the equality of two ranges specified by pairs of iterators, using

// the given predicate, returning true iff for each corresponding iterator i1

// and i2 in the first and second range respectively, pred(*i1, *i2) == true

// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)

// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are

// both random-access iterators, and `last1` - `first1` != `last2` - `first2`,

// then the predicate is never invoked and the function returns false.

// This is a C++11-compatible implementation of C++14 `std::equal`. See

// https://en.cppreference.com/w/cpp/algorithm/equal for more information.

template <typename InputIter1, typename InputIter2, typename Pred>

bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,

InputIter2 last2, Pred&& pred) {

return algorithm_internal::EqualImpl(

first1, last1, first2, last2, std::forward<Pred>(pred),

typename std::iterator_traits<InputIter1>::iterator_category{},

typename std::iterator_traits<InputIter2>::iterator_category{});

}

// Performs comparison of two ranges specified by pairs of iterators using

// operator==.

template <typename InputIter1, typename InputIter2>

bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,

InputIter2 last2) {

return basic::equal(first1, last1, first2, last2,

algorithm_internal::EqualTo{});

}

// Performs a linear search for `value` using the iterator `first` up to

// but not including `last`, returning true if [`first`, `last`) contains an

// element equal to `value`.

// A linear search is of O(n) complexity which is guaranteed to make at most

// n = (`last` - `first`) comparisons. A linear search over short containers

// may be faster than a binary search, even when the container is sorted.

template <typename InputIterator, typename EqualityComparable>

bool linear_search(InputIterator first, InputIterator last,

const EqualityComparable& value) {

return std::find(first, last, value) != last;

}

// Performs a left rotation on a range of elements (`first`, `last`) such that

// `middle` is now the first element. `rotate()` returns an iterator pointing to

// the first element before rotation. This function is exactly the same as

// `std::rotate`, but fixes a bug in gcc

// <= 4.9 where `std::rotate` returns `void` instead of an iterator.

// The complexity of this algorithm is the same as that of `std::rotate`, but if

// `ForwardIterator` is not a random-access iterator, then `basic::rotate`

// performs an additional pass over the range to construct the return value.

template <typename ForwardIterator>

ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,

ForwardIterator last) {

return algorithm_internal::RotateImpl(

first, middle, last,

std::is_same<decltype(std::rotate(first, middle, last)),

ForwardIterator>());

}

} // namespace basic

#endif // ABSL_ALGORITHM_ALGORITHM_H_

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

algorithm.h

Latest commit

History

algorithm.h

File metadata and controls