1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 3f5256e16dfc425c1d466f6308d4026d529ce9e0bHoward Hinnant// The LLVM Compiler Infrastructure 4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 5b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// This file is dual licensed under the MIT and the University of Illinois Open 6b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// Source Licenses. See LICENSE.TXT for details. 7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// <algorithm> 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 12eb564e76cc3904d811c981a50ecce0659f444cc9Howard Hinnant// template<ForwardIterator Iter> 13eb564e76cc3904d811c981a50ecce0659f444cc9Howard Hinnant// requires LessThanComparable<Iter::value_type> 14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// Iter 15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// is_sorted_until(Iter first, Iter last); 16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <algorithm> 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <cassert> 19bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 2083e2c4d877fe2d7793868b1c6a5d9525a7c4d431Marshall Clow#include "test_iterators.h" 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 22bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnanttemplate <class Iter> 23bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantvoid 24bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnanttest() 25bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 26bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 27bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0}; 28bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 29bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a)) == Iter(a)); 30bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 31bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 32bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 33bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 34bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0}; 35bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 36bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 37bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 38bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 39bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1}; 40bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 41bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 42bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 43bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 44bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0}; 45bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 46bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 47bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 48bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 49bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1}; 50bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 51bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 52bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 53bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 54bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 55bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 0}; 56bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 57bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 58bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 59bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 60bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 1}; 61bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 62bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 63bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 64bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 65bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 0}; 66bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 67bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 68bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 69bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 70bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 1}; 71bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 72bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 73bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 74bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 75bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 0}; 76bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 78bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 79bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 80bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 1}; 81bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 82bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 83bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 84bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 85bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 0}; 86bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 87bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 88bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 89bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 90bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 1}; 91bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 92bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 93bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 94bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 95bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 96bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 0, 0}; 97bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 98bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 99bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 100bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 101bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 0, 1}; 102bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 103bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 104bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 105bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 106bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 1, 0}; 107bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 108bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+3)); 109bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 110bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 111bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 0, 1, 1}; 112bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 113bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 114bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 115bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 116bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 0, 0}; 117bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 118bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 119bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 120bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 121bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 0, 1}; 122bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 123bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 124bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 125bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 126bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 1, 0}; 127bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 128bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+3)); 129bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 130bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 131bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {0, 1, 1, 1}; 132bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 133bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 134bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 135bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 136bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 0, 0}; 137bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 138bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 139bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 140bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 141bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 0, 1}; 142bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 143bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 144bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 145bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 146bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 1, 0}; 147bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 148bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 149bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 150bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 151bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 0, 1, 1}; 152bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 153bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+1)); 154bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 155bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 156bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 0, 0}; 157bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 158bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 159bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 160bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 161bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 0, 1}; 162bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 163bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+2)); 164bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 165bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 166bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 1, 0}; 167bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 168bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+3)); 169bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 170bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant { 171bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant int a[] = {1, 1, 1, 1}; 172bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned sa = sizeof(a) / sizeof(a[0]); 173bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant assert(std::is_sorted_until(Iter(a), Iter(a+sa)) == Iter(a+sa)); 174bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 175bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 176bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 177bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantint main() 178bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 179bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant test<forward_iterator<const int*> >(); 180bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant test<bidirectional_iterator<const int*> >(); 181bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant test<random_access_iterator<const int*> >(); 182bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant test<const int*>(); 183bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 184