YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

// Copyright 2006 Google Inc.

//

// Licensed to the Apache Software Foundation (ASF) under one

// or more contributor license agreements.  See the NOTICE file

// distributed with this work for additional information

// regarding copyright ownership.  The ASF licenses this file

// to you 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.

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

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

//

// ---

//

//

// This file contains some Google extensions to the standard

// <algorithm> C++ header. Many of these algorithms were in the

// original STL before it was proposed for standardization.

#ifndef YB_GUTIL_ALGORITHM_H

#define YB_GUTIL_ALGORITHM_H

#include <algorithm>

#include <functional>

using std::copy;

using std::max;

using std::min;

using std::reverse;

using std::sort;

using std::swap;

using std::binary_function;

using std::less;

using std::back_insert_iterator;

using std::iterator_traits;

using std::make_pair;

using std::pair;

namespace util {

namespace gtl {

// Returns true if [first, last) contains an element equal to value.

// Complexity: linear.

template<typename InputIterator, typename EqualityComparable>

bool contains(InputIterator first, InputIterator last,

              const EqualityComparable& value) {

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

}

// There is no contains_if().  Use any() instead.

template<typename InputIterator, typename ForwardIterator>

bool contains_some_of(InputIterator first1, InputIterator last1,

                      ForwardIterator first2, ForwardIterator last2) {

  return std::find_first_of(first1, last1, first2, last2) != last1;

}

template<typename InputIterator, typename ForwardIterator, typename Predicate>

bool contains_some_of(InputIterator first1, InputIterator last1,

                      ForwardIterator first2, ForwardIterator last2,

                      Predicate pred) {

  return std::find_first_of(first1, last1, first2, last2, pred) != last1;

}

template<typename InputIterator, typename EqualityComparable>

typename std::iterator_traits<InputIterator>::pointer

find_or_null(InputIterator first, InputIterator last,

             const EqualityComparable& value) {

  const InputIterator it = std::find(first, last, value);

  return it != last ? &*it : NULL;

}

template<typename InputIterator, typename Predicate>

typename std::iterator_traits<InputIterator>::pointer

find_if_or_null(InputIterator first, InputIterator last, Predicate pred) {

  const InputIterator it = std::find_if(first, last, pred);

  return it != last ? &*it : NULL;

}

// Copies all elements that satisfy the predicate pred from [first,

// last) to out. This is the complement of remove_copy_if. Complexity:

// exactly last-first applications of pred.

template <typename InputIterator, typename OutputIterator, typename Predicate>

OutputIterator copy_if(InputIterator first, InputIterator last,

                       OutputIterator out,

                       Predicate pred) {

  for (; first != last; ++first) {

    if (pred(*first))

      *out++ = *first;

  }

  return out;

}

// Copies n elements to out.  Equivalent to copy(first, first + n, out) for

// random access iterators and a longer code block for lesser iterators.

template <typename InputIterator, typename Size, typename OutputIterator>

OutputIterator copy_n(InputIterator first, Size n, OutputIterator out) {

  while (n > 0) {

    *out = *first;

    ++out;

    ++first;

    --n;

  }

  return out;

}

// Returns true if pred is true for every element in [first, last). Complexity:

// at most last-first applications of pred.

template <typename InputIterator, typename Predicate>

bool all(InputIterator first, InputIterator last, Predicate pred) {

  for (; first != last; ++first) {

    if (!pred(*first))

      return false;

  }

  return true;

}

// Returns true if pred is false for every element in [first,

// last). Complexity: at most last-first applications of pred.

template <typename InputIterator, typename Predicate>

bool none(InputIterator first, InputIterator last, Predicate pred) {

  return find_if(first, last, pred) == last;

}

// Returns true if pred is true for at least one element in [first, last).

// Complexity: at most last-first applications of pred.

template <typename InputIterator, typename Predicate>

bool any(InputIterator first, InputIterator last, Predicate pred) {

  return !none(first, last, pred);

}

// Returns a pair of iterators p such that p.first points to the

// minimum element in the range and p.second points to the maximum,

// ordered by comp. Complexity: at most floor((3/2) (N-1))

// comparisons. Postcondition: If the return value is <min, max>, min is

// the first iterator i in [first, last) such that comp(*j, *i) is

// false for every other iterator j, and max is the last iterator i

// such that comp(*i, *j) is false for every other iterator j. Or less

// formally, min is the first minimum and max is the last maximum.

template <typename ForwardIter, typename Compare>

std::pair<ForwardIter, ForwardIter> minmax_element(ForwardIter first,

                                                   const ForwardIter last,

                                                   Compare comp) {

  // Initialization: for N<2, set min=max=first. For N >= 2, set min

  // to be the smaller of the first two and max to be the larger. (Taking

  // care that min is the first, and max the second, if the two compare

  // equivalent.)

  ForwardIter min(first);

  ForwardIter max(first);

  if (first != last) {

    ++first;

  }

  if (first != last) {

    max = first;

    if (comp(*max, *min))

      swap(min, max);

    ++first;

  }

  while (first != last) {

    ForwardIter next(first);

    ++next;

    if (next != last) {

      // We have two elements to look at that we haven't seen already,

      // *first and *next. Compare the smaller of them with the

      // current min, and the larger against the current max. The

      // subtle point: write all of the comparisons so that, if the

      // two things being compared are equivalent, we take the first

      // one as the smaller and the last as the larger.

      if (comp(*next, *first)) {

        if (comp(*next, *min))

          min = next;

        if (!comp(*first, *max))

          max = first;

      } else {

        if (comp(*first, *min))

          min = first;

        if (!comp(*next, *max))

          max = next;

      }

    } else {

      // There is only one element left that we haven't seen already, *first.

      // Adjust min or max, as appropriate, and exit the loop.

      if (comp(*first, *min)) {

        min = first;

      } else if (!comp(*first, *max)) {

        max = first;

      }

      break;

    }

    first = next;

    ++first;

  }

  return make_pair(min, max);

}

// Returns a pair of iterators p such that p.first points to the first

// minimum element in the range and p.second points to the last

// maximum, ordered by operator<.

template <typename ForwardIter>

inline std::pair<ForwardIter, ForwardIter> minmax_element(ForwardIter first,

                                                          ForwardIter last) {

  typedef typename std::iterator_traits<ForwardIter>::value_type value_type;

  return util::gtl::minmax_element(first, last, std::less<value_type>());

}

// Returns true if [first, last) is partitioned by pred, i.e. if all

// elements that satisfy pred appear before those that do

// not. Complexity: linear.

template <typename ForwardIterator, typename Predicate>

inline bool is_partitioned(ForwardIterator first, ForwardIterator last,

                           Predicate pred) {

  for (; first != last; ++first) {

    if (!pred(*first)) {

      ++first;

      return util::gtl::none(first, last, pred);

    }

  }

  return true;

}

// Precondition: is_partitioned(first, last, pred). Returns: the

// partition point p, i.e. an iterator mid satisfying the conditions

// all(first, mid, pred) and none(mid, last, pred).  Complexity:

// O(log(last-first)) applications of pred.

template <typename ForwardIterator, typename Predicate>

ForwardIterator partition_point(ForwardIterator first, ForwardIterator last,

                                Predicate pred) {

  typedef typename std::iterator_traits<ForwardIterator>::difference_type diff;

  diff n = distance(first, last);

  // Loop invariant: n == distance(first, last)

  while (first != last) {

    diff half = n/2;

    ForwardIterator mid = first;

    advance(mid, half);

    if (pred(*mid)) {

      first = mid;

      ++first;

      n -= half+1;

    } else {

      n = half;

      last = mid;

    }

  }

  return first;

}

// Copies all elements that satisfy pred to out_true and all elements

// that don't satisfy it to out_false. Returns: a pair p such that

// p.first is the end of the range beginning at out_t and p.second is

// the end of the range beginning at out_f. Complexity: exactly

// last-first applications of pred.

template <typename InputIterator,

          typename OutputIterator1, typename OutputIterator2,

          typename Predicate>

std::pair<OutputIterator1, OutputIterator2>

partition_copy(InputIterator first, InputIterator last,

               OutputIterator1 out_true, OutputIterator2 out_false,

               Predicate pred) {

  for (; first != last; ++first) {

    if (pred(*first))

      *out_true++ = *first;

    else

      *out_false++ = *first;

  }

  return make_pair(out_true, out_false);

}

// Reorders elements in [first, last), so that for each consecutive group

// of duplicate elements (according to eq predicate) the first one is left and

// others are moved at the end of the range. Returns: iterator middle such that

// [first, middle) contains no two consecutive elements that are duplicates and

// [middle, last) contains elements removed from all groups. It's stable for

// range [first, middle) meaning the order of elements are the same as order of

// their corresponding groups in input, but the order in range [middle, last)

// is not preserved. Function is similar to std::unique, but ensures that

// removed elements are properly copied and accessible at the range's end.

// Complexity: exactly last-first-1 applications of eq; at most middle-first-1

// swap operations.

template <typename ForwardIterator, typename Equals>

ForwardIterator unique_partition(ForwardIterator first, ForwardIterator last,

                                 Equals eq) {

  first = adjacent_find(first, last, eq);

  if (first == last)

    return last;

  // Points to right-most element within range of unique elements being built.

  ForwardIterator result = first;

  // 'first' iterator goes through the sequence starting from element after

  // first equal elements pair (found by adjacent_find above).

  ++first;

  while (++first != last) {

    // If we encounter an element that isn't equal to right-most element in

    // result, then extend the range and swap this element into it.

    // Otherwise just continue incrementing 'first'.

    if (!eq(*result, *first)) {

      swap(*++result, *first);

    }

  }

  // Return past-the-end upper-bound of the resulting range.

  return ++result;

}

// Reorders elements in [first, last) range moving duplicates for each

// consecutive group of elements to the end. Equality is checked using ==.

template <typename ForwardIterator>

inline ForwardIterator unique_partition(ForwardIterator first,

                                        ForwardIterator last) {

  typedef typename std::iterator_traits<ForwardIterator>::value_type T;

  return unique_partition(first, last, std::equal_to<T>());

}

// Samples k elements from the next n.

// Elements have the same order in the output stream as they did on input.

//

// This is Algorithm S from section 3.4.2 of Knuth, TAOCP, 2nd edition.

// My k corresponds to Knuth n-m.

// My n corrsponds to Knuth N-t.

//

// RngFunctor is any functor that can be called as:

//   size_t RngFunctor(size_t x)

// The return value is an integral value in the half-open range [0, x)

// such that all values are equally likely.  Behavior is unspecified if x==0.

// (This function never calls RngFunctor with x==0).

template <typename InputIterator, typename OutputIterator, typename RngFunctor>

inline void sample_k_of_n(InputIterator in, size_t k, size_t n,

                          RngFunctor& rng, OutputIterator out) { // NOLINT

  if (k > n) {

    k = n;

  }

  while (k > 0) {

    if (rng(n) < k) {

      *out++ = *in;

      k--;

    }

    ++in;

    --n;

  }

}

// Finds the longest prefix of a range that is a binary max heap with

// respect to a given StrictWeakOrdering.  If first == last, returns last.

// Otherwise, return an iterator it such that [first,it) is a heap but

// no longer prefix is -- in other words, first + i for the lowest i

// such that comp(first[(i-1)/2], first[i]) returns true.

template <typename RandomAccessIterator, typename StrictWeakOrdering>

RandomAccessIterator gtl_is_binary_heap_until(RandomAccessIterator first,

                                              RandomAccessIterator last,

                                              StrictWeakOrdering comp) {

  if (last - first < 2) return last;

  RandomAccessIterator parent = first;

  bool is_right_child = false;

  for (RandomAccessIterator child = first + 1; child != last; ++child) {

    if (comp(*parent, *child)) return child;

    if (is_right_child) ++parent;

    is_right_child = !is_right_child;

  }

  return last;

}

// Special case of gtl_is_binary_heap_until where the order is std::less,

// i.e., where we're working with a simple max heap.

template <typename RandomAccessIterator>

RandomAccessIterator gtl_is_binary_heap_until(RandomAccessIterator first,

                                              RandomAccessIterator last) {

  typedef typename std::iterator_traits<RandomAccessIterator>::value_type T;

  return gtl_is_binary_heap_until(first, last, std::less<T>());

}

// Checks whether a range of values is a binary heap, i.e., checks that

// no node is less (as defined by a StrictWeakOrdering) than a child.

template <typename RandomAccessIterator, typename StrictWeakOrdering>

bool gtl_is_binary_heap(RandomAccessIterator begin,

                        RandomAccessIterator end,

                        StrictWeakOrdering comp) {

  return gtl_is_binary_heap_until(begin, end, comp) == end;

}

// Special case of gtl_is_binary_heap where the order is std::less (i.e.,

// where we're working on a simple max heap).

template <typename RandomAccessIterator>

bool gtl_is_binary_heap(RandomAccessIterator begin,

                        RandomAccessIterator end) {

  return gtl_is_binary_heap_until(begin, end) == end;

}

// Unqualified calls to is_heap are ambiguous with some build types,

// namespace that can clash with names that C++11 added to ::std.

// By calling util::gtl::is_heap, clients can avoid those errors,

// and by using the underlying is_heap call we ensure consistency

// with the standard library's heap implementation just in case a

// standard library ever uses anything other than a binary heap.

#if defined(__GXX_EXPERIMENTAL_CXX0X__) || __cplusplus > 199711L \

  || defined(LIBCXX) || _MSC_VER >= 1600 /* Visual Studio 2010 */

using std::is_heap;

#elif defined __GNUC__

/* using __gnu_cxx::is_heap; */

#elif defined _MSC_VER

// For old versions of MSVC++, we know by inspection that make_heap()

// traffics in binary max heaps, so gtl_is_binary_heap is an acceptable

// implementation for is_heap.

template <typename RandomAccessIterator>

bool is_heap(RandomAccessIterator begin, RandomAccessIterator end) {

  return gtl_is_binary_heap(begin, end);

}

template <typename RandomAccessIterator, typename StrictWeakOrdering>

bool is_heap(RandomAccessIterator begin,

             RandomAccessIterator end,

             StrictWeakOrdering comp) {

  return gtl_is_binary_heap(begin, end, comp);

}

#else

// We need an implementation of is_heap that matches the library's

// implementation of make_heap() and friends.  gtl_is_binary_heap will

// *probably* work, but let's be safe and not make that assumption.

#error No implementation of is_heap defined for this toolchain.

#endif

}  // namespace gtl

}  // namespace util

#endif  // YB_GUTIL_ALGORITHM_H