17ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// 27ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 37ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// The LLVM Compiler Infrastructure 47ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 57ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file is distributed under the University of Illinois Open Source 67ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// License. See LICENSE.TXT for details. 77ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 87ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 97ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file contains some templates that are useful if you are working with the 117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// STL at all. 127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// No library is required when using these functions. 147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#ifndef LLVM_ADT_STLEXTRAS_H 187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#define LLVM_ADT_STLEXTRAS_H 197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <algorithm> // for std::all_of 217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cassert> 227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cstddef> // for std::size_t 237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cstdlib> // for qsort 247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <functional> 257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <iterator> 267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <memory> 272df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens#include <tuple> 287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <utility> // for std::pair 297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/Optional.h" 317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/iterator.h" 327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/iterator_range.h" 337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/Compiler.h" 347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensnamespace llvm { 362df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 372df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens// Only used by compiler if both template types are the same. Useful when 382df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens// using SFINAE to test for the existence of member functions. 392df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename T, T> struct SameType; 402df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensnamespace detail { 427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename RangeT> 442df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensusing IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} // End detail namespace 477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions to <functional> 507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<class Ty> 537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct identity : public std::unary_function<Ty, Ty> { 547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ty &operator()(Ty &self) const { 557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return self; 567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const Ty &operator()(const Ty &self) const { 587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return self; 597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<class Ty> 637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct less_ptr : public std::binary_function<Ty, Ty, bool> { 647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator()(const Ty* left, const Ty* right) const { 657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *left < *right; 667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<class Ty> 707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct greater_ptr : public std::binary_function<Ty, Ty, bool> { 717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator()(const Ty* left, const Ty* right) const { 727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *right < *left; 737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// An efficient, type-erasing, non-owning reference to a callable. This is 777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// intended for use as the type of a function parameter that is not used 787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// after the function in question returns. 797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This class does not own the callable, so it is not in general safe to store 817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// a function_ref. 827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename Fn> class function_ref; 837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename Ret, typename ...Params> 857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass function_ref<Ret(Params...)> { 867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ret (*callback)(intptr_t callable, Params ...params); 877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens intptr_t callable; 887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template<typename Callable> 907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static Ret callback_fn(intptr_t callable, Params ...params) { 917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return (*reinterpret_cast<Callable*>(callable))( 927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::forward<Params>(params)...); 937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename Callable> 977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens function_ref(Callable &&callable, 987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::enable_if< 997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens !std::is_same<typename std::remove_reference<Callable>::type, 1007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens function_ref>::value>::type * = nullptr) 1017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : callback(callback_fn<typename std::remove_reference<Callable>::type>), 1027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens callable(reinterpret_cast<intptr_t>(&callable)) {} 1037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Ret operator()(Params ...params) const { 1047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return callback(callable, std::forward<Params>(params)...); 1057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 1077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// deleter - Very very very simple method that is used to invoke operator 1097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// delete on something. It is used like this: 1107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 1117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// for_each(V.begin(), B.end(), deleter<Interval>); 1127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 1137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T> 1147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline void deleter(T *Ptr) { 1157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens delete Ptr; 1167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 1217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions to <iterator> 1227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 1237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// mapped_iterator - This is a simple iterator adapter that causes a function to 1257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// be dereferenced whenever operator* is invoked on the iterator. 1267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 1277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class RootIt, class UnaryFunc> 1287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass mapped_iterator { 1297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens RootIt current; 1307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens UnaryFunc Fn; 1317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 1327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef typename std::iterator_traits<RootIt>::iterator_category 1337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens iterator_category; 1347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef typename std::iterator_traits<RootIt>::difference_type 1357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens difference_type; 1367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef typename std::result_of< 1377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens UnaryFunc(decltype(*std::declval<RootIt>()))> 1387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ::type value_type; 1397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef void pointer; 1417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens //typedef typename UnaryFunc::result_type *pointer; 1427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef void reference; // Can't modify value returned by fn 1437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef RootIt iterator_type; 1457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens inline const RootIt &getCurrent() const { return current; } 1477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens inline const UnaryFunc &getFunc() const { return Fn; } 1487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 1507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : current(I), Fn(F) {} 1517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens inline value_type operator*() const { // All this work to do this 1537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return Fn(*current); // little change 1547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator &operator++() { 1577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++current; 1587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 1597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator &operator--() { 1617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --current; 1627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 1637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator operator++(int) { 1657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator __tmp = *this; 1667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++current; 1677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return __tmp; 1687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator operator--(int) { 1707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator __tmp = *this; 1717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --current; 1727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return __tmp; 1737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator operator+(difference_type n) const { 1757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return mapped_iterator(current + n, Fn); 1767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator &operator+=(difference_type n) { 1787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens current += n; 1797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 1807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator operator-(difference_type n) const { 1827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return mapped_iterator(current - n, Fn); 1837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens mapped_iterator &operator-=(difference_type n) { 1857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens current -= n; 1867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 1877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens reference operator[](difference_type n) const { return *(*this + n); } 1897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 1917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator==(const mapped_iterator &X) const { 1927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return current == X.current; 1937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool operator<(const mapped_iterator &X) const { return current < X.current; } 1957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens difference_type operator-(const mapped_iterator &X) const { 1977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return current - X.current; 1987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class Iterator, class Func> 2027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline mapped_iterator<Iterator, Func> 2037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensoperator+(typename mapped_iterator<Iterator, Func>::difference_type N, 2047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const mapped_iterator<Iterator, Func> &X) { 2057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 2067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// map_iterator - Provide a convenient way to create mapped_iterators, just like 2107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// make_pair is useful for creating pairs... 2117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 2127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class ItTy, class FuncTy> 2137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 2147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return mapped_iterator<ItTy, FuncTy>(I, F); 2157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Helper to determine if type T has a member called rbegin(). 2187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename Ty> class has_rbegin_impl { 2197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef char yes[1]; 2207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef char no[2]; 2217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename Inner> 2237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); 2247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename> 2267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static no& test(...); 2277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 2297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 2307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Metafunction to determine if T& or T has a member called rbegin(). 2337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename Ty> 2347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { 2357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Returns an iterator_range over the given container which iterates in reverse. 2387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Note that the container must have rbegin()/rend() methods for this to work. 2397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename ContainerTy> 2407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensauto reverse(ContainerTy &&C, 2417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 2427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 2437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return make_range(C.rbegin(), C.rend()); 2447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Returns a std::reverse_iterator wrapped around the given iterator. 2477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename IteratorTy> 2487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstd::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 2497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::reverse_iterator<IteratorTy>(It); 2507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Returns an iterator_range over the given container which iterates in reverse. 2537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Note that the container must have begin()/end() methods which return 2547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// bidirectional iterators for this to work. 2557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename ContainerTy> 2567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensauto reverse( 2577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ContainerTy &&C, 2587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 2597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 2607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens llvm::make_reverse_iterator(std::begin(C)))) { 2617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return make_range(llvm::make_reverse_iterator(std::end(C)), 2627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens llvm::make_reverse_iterator(std::begin(C))); 2637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 2647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// An iterator adaptor that filters the elements of given inner iterators. 2667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 2677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// The predicate parameter should be a callable object that accepts the wrapped 2687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// iterator's reference type and returns a bool. When incrementing or 2697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// decrementing the iterator, it will call the predicate on each element and 2707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// skip any where it returns false. 2717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 2727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \code 2737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// int A[] = { 1, 2, 3, 4 }; 2747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); 2757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// // R contains { 1, 3 }. 2767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \endcode 2777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename WrappedIteratorT, typename PredicateT> 2787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensclass filter_iterator 2797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : public iterator_adaptor_base< 2807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 2817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::common_type< 2827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::forward_iterator_tag, 2837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits< 2847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT>::iterator_category>::type> { 2857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using BaseT = iterator_adaptor_base< 2867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 2877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::common_type< 2887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::forward_iterator_tag, 2897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: 2907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens type>; 2917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens struct PayloadType { 2937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens WrappedIteratorT End; 2947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens PredicateT Pred; 2957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens }; 2967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Optional<PayloadType> Payload; 2987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void findNextValid() { 3007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(Payload && "Payload should be engaged when findNextValid is called"); 3017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (this->I != Payload->End && !Payload->Pred(*this->I)) 3027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::operator++(); 3037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Construct the begin iterator. The begin iterator requires to know where end 3067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // is, so that it can properly stop when it hits end. 3077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) 3087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens : BaseT(std::move(Begin)), 3097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens Payload(PayloadType{std::move(End), std::move(Pred)}) { 3107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens findNextValid(); 3117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Construct the end iterator. It's not incrementable, so Payload doesn't 3147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // have to be engaged. 3157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator(WrappedIteratorT End) : BaseT(End) {} 3167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 3187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using BaseT::operator++; 3197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator &operator++() { 3217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BaseT::operator++(); 3227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens findNextValid(); 3237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return *this; 3247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 3257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename RT, typename PT> 3277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> 3287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens make_filter_range(RT &&, PT); 3297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 3307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Convenience function that takes a range of elements and a predicate, 3327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// and return a new filter_iterator range. 3337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 3347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the 3357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// lifetime of that temporary is not kept by the returned range object, and the 3367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// temporary is going to be dropped on the floor after the make_iterator_range 3377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// full expression that contains this function call. 3387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename RangeT, typename PredicateT> 3397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensiterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 3407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensmake_filter_range(RangeT &&Range, PredicateT Pred) { 3417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens using FilterIteratorT = 3427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; 3437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), 3447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::end(std::forward<RangeT>(Range)), 3457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::move(Pred)), 3467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens FilterIteratorT(std::end(std::forward<RangeT>(Range)))); 3477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 3487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 3492df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens// forward declarations required by zip_shortest/zip_first 3502df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 3512df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensbool all_of(R &&range, UnaryPredicate P); 3522df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3532df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <size_t... I> struct index_sequence; 3542df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3552df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class... Ts> struct index_sequence_for; 3562df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3572df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensnamespace detail { 3582df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename... Iters> class zip_first { 3592df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 3602df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef std::input_iterator_tag iterator_category; 3612df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef std::tuple<decltype(*std::declval<Iters>())...> value_type; 3622df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::tuple<Iters...> iterators; 3632df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3642df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensprivate: 3652df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <size_t... Ns> value_type deres(index_sequence<Ns...>) { 3662df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return value_type(*std::get<Ns>(iterators)...); 3672df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 3682df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3692df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <size_t... Ns> decltype(iterators) tup_inc(index_sequence<Ns...>) { 3702df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); 3712df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 3722df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3732df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 3742df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens value_type operator*() { return deres(index_sequence_for<Iters...>{}); } 3752df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3762df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens void operator++() { iterators = tup_inc(index_sequence_for<Iters...>{}); } 3772df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3782df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens bool operator!=(const zip_first<Iters...> &other) const { 3792df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::get<0>(iterators) != std::get<0>(other.iterators); 3802df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 3812df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens zip_first(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} 3822df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 3832df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3842df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename... Iters> class zip_shortest : public zip_first<Iters...> { 3852df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <size_t... Ns> 3862df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens bool test(const zip_first<Iters...> &other, index_sequence<Ns...>) const { 3872df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != 3882df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::get<Ns>(other.iterators)...}, 3892df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens identity<bool>{}); 3902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 3912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 3922df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 3932df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens bool operator!=(const zip_first<Iters...> &other) const { 3942df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return test(other, index_sequence_for<Iters...>{}); 3952df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 3962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens zip_shortest(Iters &&... ts) 3972df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens : zip_first<Iters...>(std::forward<Iters>(ts)...) {} 3982df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 3992df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4002df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <template <typename...> class ItType, typename... Args> class zippy { 4012df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 4022df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ItType<decltype(std::begin(std::declval<Args>()))...> iterator; 4032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4042df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensprivate: 4052df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::tuple<Args...> ts; 4062df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4072df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { 4082df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return iterator(std::begin(std::get<Ns>(ts))...); 4092df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 4102df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { 4112df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return iterator(std::end(std::get<Ns>(ts))...); 4122df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 4132df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4142df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 4152df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator begin() { return begin_impl(index_sequence_for<Args...>{}); } 4162df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator end() { return end_impl(index_sequence_for<Args...>{}); } 4172df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 4182df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 4192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} // End detail namespace 4202df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4212df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// zip iterator for two or more iteratable types. 4222df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename T, typename U, typename... Args> 4232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensdetail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, 4242df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens Args &&... args) { 4252df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return detail::zippy<detail::zip_shortest, T, U, Args...>( 4262df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 4272df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 4282df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4292df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// zip iterator that, for the sake of efficiency, assumes the first iteratee to 4302df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// be the shortest. 4312df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename T, typename U, typename... Args> 4322df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensdetail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, 4332df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens Args &&... args) { 4342df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return detail::zippy<detail::zip_first, T, U, Args...>( 4352df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 4362df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 4372df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 4397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions to <utility> 4407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 4417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Function object to check whether the first component of a std::pair 4437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// compares less than the first component of another std::pair. 4447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct less_first { 4457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename T> bool operator()(const T &lhs, const T &rhs) const { 4467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return lhs.first < rhs.first; 4477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 4497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Function object to check whether the second component of a std::pair 4517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// compares less than the second component of another std::pair. 4527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct less_second { 4537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename T> bool operator()(const T &lhs, const T &rhs) const { 4547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return lhs.second < rhs.second; 4557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 4567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 4577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// A subset of N3658. More stuff can be added as-needed. 4597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Represents a compile-time sequence of integers. 4617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T, T... I> struct integer_sequence { 4627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens typedef T value_type; 4637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4642df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static constexpr size_t size() { return sizeof...(I); } 4657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 4667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Alias for the common case of a sequence of size_ts. 4687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <size_t... I> 4697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct index_sequence : integer_sequence<std::size_t, I...> {}; 4707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <std::size_t N, std::size_t... I> 4727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 4737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <std::size_t... I> 4747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct build_index_impl<0, I...> : index_sequence<I...> {}; 4757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Creates a compile-time integer sequence for a parameter pack. 4777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class... Ts> 4787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 4797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Utility type to build an inheritance chain that makes it easy to rank 4817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// overload candidates. 4827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <int N> struct rank : rank<N - 1> {}; 4837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <> struct rank<0> {}; 4847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 4852df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \brief traits class for checking whether type T is one of any of the given 4862df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// types in the variadic list. 4872df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename T, typename... Ts> struct is_one_of { 4882df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const bool value = false; 4892df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 4902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename T, typename U, typename... Ts> 4922df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensstruct is_one_of<T, U, Ts...> { 4932df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const bool value = 4942df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::is_same<T, U>::value || is_one_of<T, Ts...>::value; 4952df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 4962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 4977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 4987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions for arrays 4997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 5007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Find the length of an array. 5027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T, std::size_t N> 5032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensconstexpr inline size_t array_lengthof(T (&)[N]) { 5047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N; 5057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Adapt std::less<T> for array_pod_sort. 5087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename T> 5097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline int array_pod_sort_comparator(const void *P1, const void *P2) { 5107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (std::less<T>()(*reinterpret_cast<const T*>(P1), 5117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens *reinterpret_cast<const T*>(P2))) 5127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return -1; 5137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (std::less<T>()(*reinterpret_cast<const T*>(P2), 5147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens *reinterpret_cast<const T*>(P1))) 5157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return 1; 5167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return 0; 5177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// get_array_pod_sort_comparator - This is an internal helper function used to 5207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// get type deduction of T right. 5217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename T> 5227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline int (*get_array_pod_sort_comparator(const T &)) 5237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (const void*, const void*) { 5247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return array_pod_sort_comparator<T>; 5257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// array_pod_sort - This sorts an array with the specified start and end 5297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// extent. This is just like std::sort, except that it calls qsort instead of 5307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// using an inlined template. qsort is slightly slower than std::sort, but 5317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// most sorts are not performance critical in LLVM and std::sort has to be 5327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// template instantiated for each type, leading to significant measured code 5337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// bloat. This function should generally be used instead of std::sort where 5347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// possible. 5357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 5367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This function assumes that you have simple POD-like types that can be 5377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// compared with std::less and can be moved with memcpy. If this isn't true, 5387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// you should use std::sort. 5397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 5407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// NOTE: If qsort_r were portable, we could allow a custom comparator and 5417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// default to std::less. 5427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<class IteratorTy> 5437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline void array_pod_sort(IteratorTy Start, IteratorTy End) { 5447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Don't inefficiently call qsort with one element or trigger undefined 5457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // behavior with an empty sequence. 5467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens auto NElts = End - Start; 5477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (NElts <= 1) return; 5487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 5497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class IteratorTy> 5527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensinline void array_pod_sort( 5537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens IteratorTy Start, IteratorTy End, 5547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens int (*Compare)( 5557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const typename std::iterator_traits<IteratorTy>::value_type *, 5567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const typename std::iterator_traits<IteratorTy>::value_type *)) { 5577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Don't inefficiently call qsort with one element or trigger undefined 5587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // behavior with an empty sequence. 5597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens auto NElts = End - Start; 5607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (NElts <= 1) return; 5617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens qsort(&*Start, NElts, sizeof(*Start), 5627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 5637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 5667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions to <algorithm> 5677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 5687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// For a container of pointers, deletes the pointers and then clears the 5707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// container. 5717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename Container> 5727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid DeleteContainerPointers(Container &C) { 5732df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens for (auto V : C) 5742df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens delete V; 5757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens C.clear(); 5767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// In a container of pairs (usually a map) whose second element is a pointer, 5797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// deletes the second elements and then clears the container. 5807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename Container> 5817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid DeleteContainerSeconds(Container &C) { 5822df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens for (auto &V : C) 5832df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens delete V.second; 5847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens C.clear(); 5857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::all_of which take ranges instead of having to pass 5887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// begin/end explicitly. 5892df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 5902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensbool all_of(R &&Range, UnaryPredicate P) { 5912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::all_of(std::begin(Range), std::end(Range), P); 5927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 5937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 5947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::any_of which take ranges instead of having to pass 5957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// begin/end explicitly. 5962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 5972df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensbool any_of(R &&Range, UnaryPredicate P) { 5982df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::any_of(std::begin(Range), std::end(Range), P); 5997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::none_of which take ranges instead of having to pass 6027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// begin/end explicitly. 6032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 6042df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensbool none_of(R &&Range, UnaryPredicate P) { 6052df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::none_of(std::begin(Range), std::end(Range), P); 6067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::find which take ranges instead of having to pass 6097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// begin/end explicitly. 6102df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename T> 6112df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto find(R &&Range, const T &Val) -> decltype(std::begin(Range)) { 6122df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::find(std::begin(Range), std::end(Range), Val); 6137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::find_if which take ranges instead of having to pass 6167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// begin/end explicitly. 6172df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 6182df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 6192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::find_if(std::begin(Range), std::end(Range), P); 6202df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 6212df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 6222df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 6232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 6242df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::find_if_not(std::begin(Range), std::end(Range), P); 6257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Provide wrappers to std::remove_if which take ranges instead of having to 6287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// pass begin/end explicitly. 6292df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename UnaryPredicate> 6302df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 6312df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::remove_if(std::begin(Range), std::end(Range), P); 6327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Wrapper function around std::find to detect if an element exists 6357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// in a container. 6367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename R, typename E> 6377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensbool is_contained(R &&Range, const E &Element) { 6382df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::find(std::begin(Range), std::end(Range), Element) != 6392df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::end(Range); 6402df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 6412df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 6422df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Wrapper function around std::count to count the number of times an element 6432df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \p Element occurs in the given range \p Range. 6442df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename E> 6452df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto count(R &&Range, const E &Element) -> typename std::iterator_traits< 6462df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens decltype(std::begin(Range))>::difference_type { 6472df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::count(std::begin(Range), std::end(Range), Element); 6487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Wrapper function around std::count_if to count the number of times an 6517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// element satisfying a given predicate occurs in a range. 6527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename R, typename UnaryPredicate> 6532df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< 6542df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens decltype(std::begin(Range))>::difference_type { 6552df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::count_if(std::begin(Range), std::end(Range), P); 6567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Wrapper function around std::transform to apply a function to a range and 6597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// store the result elsewhere. 6602df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R, typename OutputIt, typename UnaryPredicate> 6612df178997d17474042e8c3704cc93ab2db6619bfNicolas CapensOutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { 6622df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::transform(std::begin(Range), std::end(Range), d_first, P); 6637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 6667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Extra additions to <memory> 6677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 6687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// Implement make_unique according to N3656. 6707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Constructs a `new T()` with the given args and returns a 6727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// `unique_ptr<T>` which owns the object. 6737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 6747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Example: 6757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 6767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// auto p = make_unique<int>(); 6777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// auto p = make_unique<std::tuple<int, int>>(0, 1); 6787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T, class... Args> 6797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstypename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 6807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensmake_unique(Args &&... args) { 6817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 6827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \brief Constructs a `new T[n]` with the given args and returns a 6857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// `unique_ptr<T[]>` which owns the object. 6867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 6877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \param n size of the new array. 6887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 6897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Example: 6907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 6917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 6927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T> 6937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstypename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 6947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens std::unique_ptr<T>>::type 6957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensmake_unique(size_t n) { 6967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 6977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 6987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 6997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This function isn't used and is only here to provide better compile errors. 7007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <class T, class... Args> 7017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstypename std::enable_if<std::extent<T>::value != 0>::type 7027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensmake_unique(Args &&...) = delete; 7037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct FreeDeleter { 7057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void operator()(void* v) { 7067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ::free(v); 7077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 7087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 7097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename First, typename Second> 7117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct pair_hash { 7127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens size_t operator()(const std::pair<First, Second> &P) const { 7137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 7147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 7157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 7167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// A functor like C++14's std::less<void> in its absence. 7187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct less { 7197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename A, typename B> bool operator()(A &&a, B &&b) const { 7207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::forward<A>(a) < std::forward<B>(b); 7217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 7227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 7237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// A functor like C++14's std::equal<void> in its absence. 7257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct equal { 7267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename A, typename B> bool operator()(A &&a, B &&b) const { 7277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return std::forward<A>(a) == std::forward<B>(b); 7287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 7297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 7307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Binary functor that adapts to any other binary functor after dereferencing 7327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// operands. 7337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate <typename T> struct deref { 7347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens T func; 7357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Could be further improved to cope with non-derivable functors and 7367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // non-binary functors (should be a variadic template member function 7377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // operator()). 7387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens template <typename A, typename B> 7397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 7407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(lhs); 7417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(rhs); 7427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return func(*lhs, *rhs); 7437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 7447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 7457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 7462df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensnamespace detail { 7472df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R> class enumerator_impl { 7482df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 7492df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <typename X> struct result_pair { 7502df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens result_pair(std::size_t Index, X Value) : Index(Index), Value(Value) {} 7512df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7522df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens const std::size_t Index; 7532df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens X Value; 7542df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens }; 7552df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7562df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens class iterator { 7572df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef 7582df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typename std::iterator_traits<IterOfRange<R>>::reference iter_reference; 7592df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef result_pair<iter_reference> result_type; 7602df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7612df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens public: 7622df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator(IterOfRange<R> &&Iter, std::size_t Index) 7632df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens : Iter(Iter), Index(Index) {} 7642df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7652df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens result_type operator*() const { return result_type(Index, *Iter); } 7662df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7672df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator &operator++() { 7682df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens ++Iter; 7692df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens ++Index; 7702df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return *this; 7712df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 7722df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7732df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens bool operator!=(const iterator &RHS) const { return Iter != RHS.Iter; } 7742df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7752df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens private: 7762df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens IterOfRange<R> Iter; 7772df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::size_t Index; 7782df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens }; 7792df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7802df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenspublic: 7812df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens explicit enumerator_impl(R &&Range) : Range(std::forward<R>(Range)) {} 7822df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7832df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator begin() { return iterator(std::begin(Range), 0); } 7842df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens iterator end() { return iterator(std::end(Range), std::size_t(-1)); } 7852df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7862df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensprivate: 7872df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens R Range; 7882df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 7892df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 7902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 7912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Given an input range, returns a new range whose values are are pair (A,B) 7922df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// such that A is the 0-based index of the item in the sequence, and B is 7932df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// the value from the original sequence. Example: 7942df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 7952df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// std::vector<char> Items = {'A', 'B', 'C', 'D'}; 7962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// for (auto X : enumerate(Items)) { 7972df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// printf("Item %d - %c\n", X.Index, X.Value); 7982df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// } 7992df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 8002df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Output: 8012df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Item 0 - A 8022df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Item 1 - B 8032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Item 2 - C 8042df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Item 3 - D 8052df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 8062df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename R> detail::enumerator_impl<R> enumerate(R &&Range) { 8072df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return detail::enumerator_impl<R>(std::forward<R>(Range)); 8082df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 8092df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 8102df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensnamespace detail { 8112df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename F, typename Tuple, std::size_t... I> 8122df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>) 8132df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { 8142df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); 8152df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 8162df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 8172df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 8182df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Given an input tuple (a1, a2, ..., an), pass the arguments of the 8192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// tuple variadically to f as if by calling f(a1, a2, ..., an) and 8202df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// return the result. 8212df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename F, typename Tuple> 8222df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensauto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( 8232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::forward<F>(f), std::forward<Tuple>(t), 8242df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens build_index_impl< 8252df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { 8262df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens using Indices = build_index_impl< 8272df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens std::tuple_size<typename std::decay<Tuple>::type>::value>; 8282df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 8292df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), 8302df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens Indices{}); 8312df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} 8327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} // End llvm namespace 8337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 8347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#endif 835