/lab4/.minix-src/include/c++/algorithm - Annotate - LCOM1920-T02G10 - FEUP Project Manager

13

up20180614

// -*- C++ -*-

2

//===-------------------------- algorithm ---------------------------------===//

3

//

4

//                     The LLVM Compiler Infrastructure

5

//

6

// This file is dual licensed under the MIT and the University of Illinois Open

7

// Source Licenses. See LICENSE.TXT for details.

8

//

9

//===----------------------------------------------------------------------===//

10

11

#ifndef _LIBCPP_ALGORITHM

12

#define _LIBCPP_ALGORITHM

13

14

/*

15

    algorithm synopsis

16

17

#include <initializer_list>

18

19

namespace std

20

21

22

template <class InputIterator, class Predicate>

23

    bool

24

    all_of(InputIterator first, InputIterator last, Predicate pred);

25

26

template <class InputIterator, class Predicate>

27

    bool

28

    any_of(InputIterator first, InputIterator last, Predicate pred);

29

30

template <class InputIterator, class Predicate>

31

    bool

32

    none_of(InputIterator first, InputIterator last, Predicate pred);

33

34

template <class InputIterator, class Function>

35

    Function

36

    for_each(InputIterator first, InputIterator last, Function f);

37

38

template <class InputIterator, class T>

39

    InputIterator

40

    find(InputIterator first, InputIterator last, const T& value);

41

42

template <class InputIterator, class Predicate>

43

    InputIterator

44

    find_if(InputIterator first, InputIterator last, Predicate pred);

45

46

template<class InputIterator, class Predicate>

47

    InputIterator

48

    find_if_not(InputIterator first, InputIterator last, Predicate pred);

49

50

template <class ForwardIterator1, class ForwardIterator2>

51

    ForwardIterator1

52

    find_end(ForwardIterator1 first1, ForwardIterator1 last1,

53

             ForwardIterator2 first2, ForwardIterator2 last2);

54

55

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

56

    ForwardIterator1

57

    find_end(ForwardIterator1 first1, ForwardIterator1 last1,

58

             ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

59

60

template <class ForwardIterator1, class ForwardIterator2>

61

    ForwardIterator1

62

    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,

63

                  ForwardIterator2 first2, ForwardIterator2 last2);

64

65

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

66

    ForwardIterator1

67

    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,

68

                  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

69

70

template <class ForwardIterator>

71

    ForwardIterator

72

    adjacent_find(ForwardIterator first, ForwardIterator last);

73

74

template <class ForwardIterator, class BinaryPredicate>

75

    ForwardIterator

76

    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

77

78

template <class InputIterator, class T>

79

    typename iterator_traits<InputIterator>::difference_type

80

    count(InputIterator first, InputIterator last, const T& value);

81

82

template <class InputIterator, class Predicate>

83

    typename iterator_traits<InputIterator>::difference_type

84

    count_if(InputIterator first, InputIterator last, Predicate pred);

85

86

template <class InputIterator1, class InputIterator2>

87

    pair<InputIterator1, InputIterator2>

88

    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

89

90

template <class InputIterator1, class InputIterator2>

91

    pair<InputIterator1, InputIterator2>

92

    mismatch(InputIterator1 first1, InputIterator1 last1,

93

             InputIterator2 first2, InputIterator2 last2); // **C++14**

94

95

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

96

    pair<InputIterator1, InputIterator2>

97

    mismatch(InputIterator1 first1, InputIterator1 last1,

98

             InputIterator2 first2, BinaryPredicate pred);

99

100

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

101

    pair<InputIterator1, InputIterator2>

102

    mismatch(InputIterator1 first1, InputIterator1 last1,

103

             InputIterator2 first2, InputIterator2 last2,

104

             BinaryPredicate pred); // **C++14**

105

106

template <class InputIterator1, class InputIterator2>

107

    bool

108

    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

109

110

template <class InputIterator1, class InputIterator2>

111

    bool

112

    equal(InputIterator1 first1, InputIterator1 last1,

113

          InputIterator2 first2, InputIterator2 last2); // **C++14**

114

115

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

116

    bool

117

    equal(InputIterator1 first1, InputIterator1 last1,

118

          InputIterator2 first2, BinaryPredicate pred);

119

120

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

121

    bool

122

    equal(InputIterator1 first1, InputIterator1 last1,

123

          InputIterator2 first2, InputIterator2 last2,

124

          BinaryPredicate pred); // **C++14**

125

126

template<class ForwardIterator1, class ForwardIterator2>

127

    bool

128

    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

129

                   ForwardIterator2 first2);

130

131

template<class ForwardIterator1, class ForwardIterator2>

132

    bool

133

    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

134

                   ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**

135

136

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

137

    bool

138

    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

139

                   ForwardIterator2 first2, BinaryPredicate pred);

140

141

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

142

    bool

143

    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

144

                   ForwardIterator2 first2, ForwardIterator2 last2,

145

                   BinaryPredicate pred);  // **C++14**

146

147

template <class ForwardIterator1, class ForwardIterator2>

148

    ForwardIterator1

149

    search(ForwardIterator1 first1, ForwardIterator1 last1,

150

           ForwardIterator2 first2, ForwardIterator2 last2);

151

152

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

153

    ForwardIterator1

154

    search(ForwardIterator1 first1, ForwardIterator1 last1,

155

           ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

156

157

template <class ForwardIterator, class Size, class T>

158

    ForwardIterator

159

    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);

160

161

template <class ForwardIterator, class Size, class T, class BinaryPredicate>

162

    ForwardIterator

163

    search_n(ForwardIterator first, ForwardIterator last,

164

             Size count, const T& value, BinaryPredicate pred);

165

166

template <class InputIterator, class OutputIterator>

167

    OutputIterator

168

    copy(InputIterator first, InputIterator last, OutputIterator result);

169

170

template<class InputIterator, class OutputIterator, class Predicate>

171

    OutputIterator

172

    copy_if(InputIterator first, InputIterator last,

173

            OutputIterator result, Predicate pred);

174

175

template<class InputIterator, class Size, class OutputIterator>

176

    OutputIterator

177

    copy_n(InputIterator first, Size n, OutputIterator result);

178

179

template <class BidirectionalIterator1, class BidirectionalIterator2>

180

    BidirectionalIterator2

181

    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,

182

                  BidirectionalIterator2 result);

183

184

template <class ForwardIterator1, class ForwardIterator2>

185

    ForwardIterator2

186

    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

187

188

template <class ForwardIterator1, class ForwardIterator2>

189

    void

190

    iter_swap(ForwardIterator1 a, ForwardIterator2 b);

191

192

template <class InputIterator, class OutputIterator, class UnaryOperation>

193

    OutputIterator

194

    transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);

195

196

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>

197

    OutputIterator

198

    transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,

199

              OutputIterator result, BinaryOperation binary_op);

200

201

template <class ForwardIterator, class T>

202

    void

203

    replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

204

205

template <class ForwardIterator, class Predicate, class T>

206

    void

207

    replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

208

209

template <class InputIterator, class OutputIterator, class T>

210

    OutputIterator

211

    replace_copy(InputIterator first, InputIterator last, OutputIterator result,

212

                 const T& old_value, const T& new_value);

213

214

template <class InputIterator, class OutputIterator, class Predicate, class T>

215

    OutputIterator

216

    replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

217

218

template <class ForwardIterator, class T>

219

    void

220

    fill(ForwardIterator first, ForwardIterator last, const T& value);

221

222

template <class OutputIterator, class Size, class T>

223

    OutputIterator

224

    fill_n(OutputIterator first, Size n, const T& value);

225

226

template <class ForwardIterator, class Generator>

227

    void

228

    generate(ForwardIterator first, ForwardIterator last, Generator gen);

229

230

template <class OutputIterator, class Size, class Generator>

231

    OutputIterator

232

    generate_n(OutputIterator first, Size n, Generator gen);

233

234

template <class ForwardIterator, class T>

235

    ForwardIterator

236

    remove(ForwardIterator first, ForwardIterator last, const T& value);

237

238

template <class ForwardIterator, class Predicate>

239

    ForwardIterator

240

    remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

241

242

template <class InputIterator, class OutputIterator, class T>

243

    OutputIterator

244

    remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

245

246

template <class InputIterator, class OutputIterator, class Predicate>

247

    OutputIterator

248

    remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

249

250

template <class ForwardIterator>

251

    ForwardIterator

252

    unique(ForwardIterator first, ForwardIterator last);

253

254

template <class ForwardIterator, class BinaryPredicate>

255

    ForwardIterator

256

    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

257

258

template <class InputIterator, class OutputIterator>

259

    OutputIterator

260

    unique_copy(InputIterator first, InputIterator last, OutputIterator result);

261

262

template <class InputIterator, class OutputIterator, class BinaryPredicate>

263

    OutputIterator

264

    unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);

265

266

template <class BidirectionalIterator>

267

    void

268

    reverse(BidirectionalIterator first, BidirectionalIterator last);

269

270

template <class BidirectionalIterator, class OutputIterator>

271

    OutputIterator

272

    reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

273

274

template <class ForwardIterator>

275

    ForwardIterator

276

    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

277

278

template <class ForwardIterator, class OutputIterator>

279

    OutputIterator

280

    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

281

282

template <class RandomAccessIterator>

283

    void

284

    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14

285

286

template <class RandomAccessIterator, class RandomNumberGenerator>

287

    void

288

    random_shuffle(RandomAccessIterator first, RandomAccessIterator last,

289

                   RandomNumberGenerator& rand);  // deprecated in C++14

290

291

template<class RandomAccessIterator, class UniformRandomNumberGenerator>

292

    void shuffle(RandomAccessIterator first, RandomAccessIterator last,

293

                 UniformRandomNumberGenerator&& g);

294

295

template <class InputIterator, class Predicate>

296

    bool

297

    is_partitioned(InputIterator first, InputIterator last, Predicate pred);

298

299

template <class ForwardIterator, class Predicate>

300

    ForwardIterator

301

    partition(ForwardIterator first, ForwardIterator last, Predicate pred);

302

303

template <class InputIterator, class OutputIterator1,

304

          class OutputIterator2, class Predicate>

305

    pair<OutputIterator1, OutputIterator2>

306

    partition_copy(InputIterator first, InputIterator last,

307

                   OutputIterator1 out_true, OutputIterator2 out_false,

308

                   Predicate pred);

309

310

template <class ForwardIterator, class Predicate>

311

    ForwardIterator

312

    stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

313

314

template<class ForwardIterator, class Predicate>

315

    ForwardIterator

316

    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

317

318

template <class ForwardIterator>

319

    bool

320

    is_sorted(ForwardIterator first, ForwardIterator last);

321

322

template <class ForwardIterator, class Compare>

323

    bool

324

    is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

325

326

template<class ForwardIterator>

327

    ForwardIterator

328

    is_sorted_until(ForwardIterator first, ForwardIterator last);

329

330

template <class ForwardIterator, class Compare>

331

    ForwardIterator

332

    is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);

333

334

template <class RandomAccessIterator>

335

    void

336

    sort(RandomAccessIterator first, RandomAccessIterator last);

337

338

template <class RandomAccessIterator, class Compare>

339

    void

340

    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

341

342

template <class RandomAccessIterator>

343

    void

344

    stable_sort(RandomAccessIterator first, RandomAccessIterator last);

345

346

template <class RandomAccessIterator, class Compare>

347

    void

348

    stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

349

350

template <class RandomAccessIterator>

351

    void

352

    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

353

354

template <class RandomAccessIterator, class Compare>

355

    void

356

    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

357

358

template <class InputIterator, class RandomAccessIterator>

359

    RandomAccessIterator

360

    partial_sort_copy(InputIterator first, InputIterator last,

361

                      RandomAccessIterator result_first, RandomAccessIterator result_last);

362

363

template <class InputIterator, class RandomAccessIterator, class Compare>

364

    RandomAccessIterator

365

    partial_sort_copy(InputIterator first, InputIterator last,

366

                      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

367

368

template <class RandomAccessIterator>

369

    void

370

    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

371

372

template <class RandomAccessIterator, class Compare>

373

    void

374

    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

375

376

template <class ForwardIterator, class T>

377

    ForwardIterator

378

    lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

379

380

template <class ForwardIterator, class T, class Compare>

381

    ForwardIterator

382

    lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

383

384

template <class ForwardIterator, class T>

385

    ForwardIterator

386

    upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

387

388

template <class ForwardIterator, class T, class Compare>

389

    ForwardIterator

390

    upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

391

392

template <class ForwardIterator, class T>

393

    pair<ForwardIterator, ForwardIterator>

394

    equal_range(ForwardIterator first, ForwardIterator last, const T& value);

395

396

template <class ForwardIterator, class T, class Compare>

397

    pair<ForwardIterator, ForwardIterator>

398

    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

399

400

template <class ForwardIterator, class T>

401

    bool

402

    binary_search(ForwardIterator first, ForwardIterator last, const T& value);

403

404

template <class ForwardIterator, class T, class Compare>

405

    bool

406

    binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

407

408

template <class InputIterator1, class InputIterator2, class OutputIterator>

409

    OutputIterator

410

    merge(InputIterator1 first1, InputIterator1 last1,

411

          InputIterator2 first2, InputIterator2 last2, OutputIterator result);

412

413

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

414

    OutputIterator

415

    merge(InputIterator1 first1, InputIterator1 last1,

416

          InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

417

418

template <class BidirectionalIterator>

419

    void

420

    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

421

422

template <class BidirectionalIterator, class Compare>

423

    void

424

    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

425

426

template <class InputIterator1, class InputIterator2>

427

    bool

428

    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

429

430

template <class InputIterator1, class InputIterator2, class Compare>

431

    bool

432

    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

433

434

template <class InputIterator1, class InputIterator2, class OutputIterator>

435

    OutputIterator

436

    set_union(InputIterator1 first1, InputIterator1 last1,

437

              InputIterator2 first2, InputIterator2 last2, OutputIterator result);

438

439

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

440

    OutputIterator

441

    set_union(InputIterator1 first1, InputIterator1 last1,

442

              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

443

444

template <class InputIterator1, class InputIterator2, class OutputIterator>

445

    OutputIterator

446

    set_intersection(InputIterator1 first1, InputIterator1 last1,

447

                     InputIterator2 first2, InputIterator2 last2, OutputIterator result);

448

449

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

450

    OutputIterator

451

    set_intersection(InputIterator1 first1, InputIterator1 last1,

452

                     InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

453

454

template <class InputIterator1, class InputIterator2, class OutputIterator>

455

    OutputIterator

456

    set_difference(InputIterator1 first1, InputIterator1 last1,

457

                   InputIterator2 first2, InputIterator2 last2, OutputIterator result);

458

459

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

460

    OutputIterator

461

    set_difference(InputIterator1 first1, InputIterator1 last1,

462

                   InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

463

464

template <class InputIterator1, class InputIterator2, class OutputIterator>

465

    OutputIterator

466

    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,

467

                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);

468

469

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

470

    OutputIterator

471

    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,

472

                             InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

473

474

template <class RandomAccessIterator>

475

    void

476

    push_heap(RandomAccessIterator first, RandomAccessIterator last);

477

478

template <class RandomAccessIterator, class Compare>

479

    void

480

    push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

481

482

template <class RandomAccessIterator>

483

    void

484

    pop_heap(RandomAccessIterator first, RandomAccessIterator last);

485

486

template <class RandomAccessIterator, class Compare>

487

    void

488

    pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

489

490

template <class RandomAccessIterator>

491

    void

492

    make_heap(RandomAccessIterator first, RandomAccessIterator last);

493

494

template <class RandomAccessIterator, class Compare>

495

    void

496

    make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

497

498

template <class RandomAccessIterator>

499

    void

500

    sort_heap(RandomAccessIterator first, RandomAccessIterator last);

501

502

template <class RandomAccessIterator, class Compare>

503

    void

504

    sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

505

506

template <class RandomAccessIterator>

507

    bool

508

    is_heap(RandomAccessIterator first, RandomAccessiterator last);

509

510

template <class RandomAccessIterator, class Compare>

511

    bool

512

    is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);

513

514

template <class RandomAccessIterator>

515

    RandomAccessIterator

516

    is_heap_until(RandomAccessIterator first, RandomAccessiterator last);

517

518

template <class RandomAccessIterator, class Compare>

519

    RandomAccessIterator

520

    is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);

521

522

template <class ForwardIterator>

523

    ForwardIterator

524

    min_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14

525

526

template <class ForwardIterator, class Compare>

527

    ForwardIterator

528

    min_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14

529

530

template <class T>

531

    const T&

532

    min(const T& a, const T& b);  // constexpr in C++14

533

534

template <class T, class Compare>

535

    const T&

536

    min(const T& a, const T& b, Compare comp);  // constexpr in C++14

537

538

template<class T>

539

540

    min(initializer_list<T> t);  // constexpr in C++14

541

542

template<class T, class Compare>

543

544

    min(initializer_list<T> t, Compare comp);  // constexpr in C++14

545

546

template <class ForwardIterator>

547

    ForwardIterator

548

    max_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14

549

550

template <class ForwardIterator, class Compare>

551

    ForwardIterator

552

    max_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14

553

554

template <class T>

555

    const T&

556

    max(const T& a, const T& b); // constexpr in C++14

557

558

template <class T, class Compare>

559

    const T&

560

    max(const T& a, const T& b, Compare comp);  // constexpr in C++14

561

562

template<class T>

563

564

    max(initializer_list<T> t);  // constexpr in C++14

565

566

template<class T, class Compare>

567

568

    max(initializer_list<T> t, Compare comp);  // constexpr in C++14

569

570

template<class ForwardIterator>

571

    pair<ForwardIterator, ForwardIterator>

572

    minmax_element(ForwardIterator first, ForwardIterator last);   // constexpr in C++14

573

574

template<class ForwardIterator, class Compare>

575

    pair<ForwardIterator, ForwardIterator>

576

    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);   // constexpr in C++14

577

578

template<class T>

579

    pair<const T&, const T&>

580

    minmax(const T& a, const T& b);  // constexpr in C++14

581

582

template<class T, class Compare>

583

    pair<const T&, const T&>

584

    minmax(const T& a, const T& b, Compare comp);  // constexpr in C++14

585

586

template<class T>

587

    pair<T, T>

588

    minmax(initializer_list<T> t);  // constexpr in C++14

589

590

template<class T, class Compare>

591

    pair<T, T>

592

    minmax(initializer_list<T> t, Compare comp);  // constexpr in C++14

593

594

template <class InputIterator1, class InputIterator2>

595

    bool

596

    lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

597

598

template <class InputIterator1, class InputIterator2, class Compare>

599

    bool

600

    lexicographical_compare(InputIterator1 first1, InputIterator1 last1,

601

                            InputIterator2 first2, InputIterator2 last2, Compare comp);

602

603

template <class BidirectionalIterator>

604

    bool

605

    next_permutation(BidirectionalIterator first, BidirectionalIterator last);

606

607

template <class BidirectionalIterator, class Compare>

608

    bool

609

    next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

610

611

template <class BidirectionalIterator>

612

    bool

613

    prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

614

615

template <class BidirectionalIterator, class Compare>

616

    bool

617

    prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

618

619

}  // std

620

621

*/

622

623

#include <__config>

624

#include <initializer_list>

625

#include <type_traits>

626

#include <cstring>

627

#include <utility>

628

#include <memory>

629

#include <iterator>

630

#include <cstddef>

631

632

#if defined(__IBMCPP__)

633

#include "support/ibm/support.h"

634

#endif

635

#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)

636

#include "support/win32/support.h"

637

#endif

638

639

#include <__undef_min_max>

640

641

#include <__debug>

642

643

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

644

#pragma GCC system_header

645

#endif

646

647

_LIBCPP_BEGIN_NAMESPACE_STD

648

649

// I'd like to replace these with _VSTD::equal_to<void>, but can't because:

650

//   * That only works with C++14 and later, and

651

//   * We haven't included <functional> here.

652

template <class _T1, class _T2 = _T1>

653

struct __equal_to

654

655

    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

656

    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}

657

    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}

658

    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}

659

};

660

661

template <class _T1>

662

struct __equal_to<_T1, _T1>

663

664

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

665

    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

666

};

667

668

template <class _T1>

669

struct __equal_to<const _T1, _T1>

670

671

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

672

    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

673

};

674

675

template <class _T1>

676

struct __equal_to<_T1, const _T1>

677

678

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

679

    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

680

};

681

682

template <class _T1, class _T2 = _T1>

683

struct __less

684

685

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

686

    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

687

688

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

689

    bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}

690

691

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

692

    bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}

693

694

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

695

    bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}

696

};

697

698

template <class _T1>

699

struct __less<_T1, _T1>

700

701

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

702

    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

703

};

704

705

template <class _T1>

706

struct __less<const _T1, _T1>

707

708

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

709

    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

710

};

711

712

template <class _T1>

713

struct __less<_T1, const _T1>

714

715

    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

716

    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

717

};

718

719

template <class _Predicate>

720

class __negate

721

722

private:

723

    _Predicate __p_;

724

public:

725

    _LIBCPP_INLINE_VISIBILITY __negate() {}

726

727

    _LIBCPP_INLINE_VISIBILITY

728

    explicit __negate(_Predicate __p) : __p_(__p) {}

729

730

    template <class _T1>

731

    _LIBCPP_INLINE_VISIBILITY

732

    bool operator()(const _T1& __x) {return !__p_(__x);}

733

734

    template <class _T1, class _T2>

735

    _LIBCPP_INLINE_VISIBILITY

736

    bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}

737

};

738

739

#ifdef _LIBCPP_DEBUG

740

741

template <class _Compare>

742

struct __debug_less

743

744

    _Compare __comp_;

745

    __debug_less(_Compare& __c) : __comp_(__c) {}

746

    template <class _Tp, class _Up>

747

    bool operator()(const _Tp& __x, const _Up& __y)

748

749

        bool __r = __comp_(__x, __y);

750

        if (__r)

751

            _LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");

752

        return __r;

753

754

};

755

756

#endif  // _LIBCPP_DEBUG

757

758

// Precondition:  __x != 0

759

inline _LIBCPP_INLINE_VISIBILITY

760

unsigned

761

__ctz(unsigned __x)

762

763

    return static_cast<unsigned>(__builtin_ctz(__x));

764

765

766

inline _LIBCPP_INLINE_VISIBILITY

767

unsigned long

768

__ctz(unsigned long __x)

769

770

    return static_cast<unsigned long>(__builtin_ctzl(__x));

771

772

773

inline _LIBCPP_INLINE_VISIBILITY

774

unsigned long long

775

__ctz(unsigned long long __x)

776

777

    return static_cast<unsigned long long>(__builtin_ctzll(__x));

778

779

780

// Precondition:  __x != 0

781

inline _LIBCPP_INLINE_VISIBILITY

782

unsigned

783

__clz(unsigned __x)

784

785

    return static_cast<unsigned>(__builtin_clz(__x));

786

787

788

inline _LIBCPP_INLINE_VISIBILITY

789

unsigned long

790

__clz(unsigned long __x)

791

792

    return static_cast<unsigned long>(__builtin_clzl (__x));

793

794

795

inline _LIBCPP_INLINE_VISIBILITY

796

unsigned long long

797

__clz(unsigned long long __x)

798

799

    return static_cast<unsigned long long>(__builtin_clzll(__x));

800

801

802

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned           __x) {return __builtin_popcount  (__x);}

803

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned      long __x) {return __builtin_popcountl (__x);}

804

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}

805

806

// all_of

807

808

template <class _InputIterator, class _Predicate>

809

inline _LIBCPP_INLINE_VISIBILITY

810

bool

811

all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

812

813

    for (; __first != __last; ++__first)

814

        if (!__pred(*__first))

815

            return false;

816

    return true;

817

818

819

// any_of

820

821

template <class _InputIterator, class _Predicate>

822

inline _LIBCPP_INLINE_VISIBILITY

823

bool

824

any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

825

826

    for (; __first != __last; ++__first)

827

        if (__pred(*__first))

828

            return true;

829

    return false;

830

831

832

// none_of

833

834

template <class _InputIterator, class _Predicate>

835

inline _LIBCPP_INLINE_VISIBILITY

836

bool

837

none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

838

839

    for (; __first != __last; ++__first)

840

        if (__pred(*__first))

841

            return false;

842

    return true;

843

844

845

// for_each

846

847

template <class _InputIterator, class _Function>

848

inline _LIBCPP_INLINE_VISIBILITY

849

_Function

850

for_each(_InputIterator __first, _InputIterator __last, _Function __f)

851

852

    for (; __first != __last; ++__first)

853

        __f(*__first);

854

    return _LIBCPP_EXPLICIT_MOVE(__f);  // explicitly moved for (emulated) C++03

855

856

857

// find

858

859

template <class _InputIterator, class _Tp>

860

inline _LIBCPP_INLINE_VISIBILITY

861

_InputIterator

862

find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)

863

864

    for (; __first != __last; ++__first)

865

        if (*__first == __value_)

866

            break;

867

    return __first;

868

869

870

// find_if

871

872

template <class _InputIterator, class _Predicate>

873

inline _LIBCPP_INLINE_VISIBILITY

874

_InputIterator

875

find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)

876

877

    for (; __first != __last; ++__first)

878

        if (__pred(*__first))

879

            break;

880

    return __first;

881

882

883

// find_if_not

884

885

template<class _InputIterator, class _Predicate>

886

inline _LIBCPP_INLINE_VISIBILITY

887

_InputIterator

888

find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)

889

890

    for (; __first != __last; ++__first)

891

        if (!__pred(*__first))

892

            break;

893

    return __first;

894

895

896

// find_end

897

898

template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>

899

_ForwardIterator1

900

__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

901

           _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,

902

           forward_iterator_tag, forward_iterator_tag)

903

904

    // modeled after search algorithm

905

    _ForwardIterator1 __r = __last1;  // __last1 is the "default" answer

906

    if (__first2 == __last2)

907

        return __r;

908

    while (true)

909

910

        while (true)

911

912

            if (__first1 == __last1)         // if source exhausted return last correct answer

913

                return __r;                  //    (or __last1 if never found)

914

            if (__pred(*__first1, *__first2))

915

                break;

916

            ++__first1;

917

918

        // *__first1 matches *__first2, now match elements after here

919

        _ForwardIterator1 __m1 = __first1;

920

        _ForwardIterator2 __m2 = __first2;

921

        while (true)

922

923

            if (++__m2 == __last2)

924

            {                         // Pattern exhaused, record answer and search for another one

925

                __r = __first1;

926

                ++__first1;

927

                break;

928

929

            if (++__m1 == __last1)     // Source exhausted, return last answer

930

                return __r;

931

            if (!__pred(*__m1, *__m2))  // mismatch, restart with a new __first

932

933

                ++__first1;

934

                break;

935

            }  // else there is a match, check next elements

template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>

941

_BidirectionalIterator1

942

__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,

943

           _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,

944

           bidirectional_iterator_tag, bidirectional_iterator_tag)

945

946

    // modeled after search algorithm (in reverse)

947

    if (__first2 == __last2)

948

        return __last1;  // Everything matches an empty sequence

949

    _BidirectionalIterator1 __l1 = __last1;

950

    _BidirectionalIterator2 __l2 = __last2;

951

    --__l2;

952

    while (true)

953

954

        // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks

955

        while (true)

956

957

            if (__first1 == __l1)  // return __last1 if no element matches *__first2

958

                return __last1;

959

            if (__pred(*--__l1, *__l2))

960

                break;

961

962

        // *__l1 matches *__l2, now match elements before here

963

        _BidirectionalIterator1 __m1 = __l1;

964

        _BidirectionalIterator2 __m2 = __l2;

965

        while (true)

966

967

            if (__m2 == __first2)  // If pattern exhausted, __m1 is the answer (works for 1 element pattern)

968

                return __m1;

969

            if (__m1 == __first1)  // Otherwise if source exhaused, pattern not found

970

                return __last1;

971

            if (!__pred(*--__m1, *--__m2))  // if there is a mismatch, restart with a new __l1

972

973

                break;

974

            }  // else there is a match, check next elements

template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>

980

_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1

981

__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,

982

           _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,

983

           random_access_iterator_tag, random_access_iterator_tag)

984

985

    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern

986

    typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;

987

    if (__len2 == 0)

988

        return __last1;

989

    typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;

990

    if (__len1 < __len2)

991

        return __last1;

992

    const _RandomAccessIterator1 __s = __first1 + (__len2 - 1);  // End of pattern match can't go before here

993

    _RandomAccessIterator1 __l1 = __last1;

994

    _RandomAccessIterator2 __l2 = __last2;

995

    --__l2;

996

    while (true)

997

998

        while (true)

999

1000

            if (__s == __l1)

1001

                return __last1;

1002

            if (__pred(*--__l1, *__l2))

1003

                break;

1004

1005

        _RandomAccessIterator1 __m1 = __l1;

1006

        _RandomAccessIterator2 __m2 = __l2;

1007

        while (true)

1008

1009

            if (__m2 == __first2)

1010

                return __m1;

1011

                                 // no need to check range on __m1 because __s guarantees we have enough source

1012

            if (!__pred(*--__m1, *--__m2))

1013

1014

                break;

template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1021

inline _LIBCPP_INLINE_VISIBILITY

1022

_ForwardIterator1

1023

find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1024

         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)

1025

1026

    return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>

1027

                         (__first1, __last1, __first2, __last2, __pred,

1028

                          typename iterator_traits<_ForwardIterator1>::iterator_category(),

1029

                          typename iterator_traits<_ForwardIterator2>::iterator_category());

1030

1031

1032

template <class _ForwardIterator1, class _ForwardIterator2>

1033

inline _LIBCPP_INLINE_VISIBILITY

1034

_ForwardIterator1

1035

find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1036

         _ForwardIterator2 __first2, _ForwardIterator2 __last2)

1037

1038

    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;

1039

    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;

1040

    return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());

1041

1042

1043

// find_first_of

1044

1045

template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1046

_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1

1047

__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1048

              _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)

1049

1050

    for (; __first1 != __last1; ++__first1)

1051

        for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)

1052

            if (__pred(*__first1, *__j))

1053

                return __first1;

1054

    return __last1;

template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1059

inline _LIBCPP_INLINE_VISIBILITY

1060

_ForwardIterator1

1061

find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1062

              _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)

1063

1064

    return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);

1065

1066

1067

template <class _ForwardIterator1, class _ForwardIterator2>

1068

inline _LIBCPP_INLINE_VISIBILITY

1069

_ForwardIterator1

1070

find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1071

              _ForwardIterator2 __first2, _ForwardIterator2 __last2)

1072

1073

    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;

1074

    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;

1075

    return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());

1076

1077

1078

// adjacent_find

1079

1080

template <class _ForwardIterator, class _BinaryPredicate>

1081

inline _LIBCPP_INLINE_VISIBILITY

1082

_ForwardIterator

1083

adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)

1084

1085

    if (__first != __last)

1086

1087

        _ForwardIterator __i = __first;

1088

        while (++__i != __last)

1089

1090

            if (__pred(*__first, *__i))

1091

                return __first;

1092

            __first = __i;

1093

1094

1095

    return __last;

1096

1097

1098

template <class _ForwardIterator>

1099

inline _LIBCPP_INLINE_VISIBILITY

1100

_ForwardIterator

1101

adjacent_find(_ForwardIterator __first, _ForwardIterator __last)

1102

1103

    typedef typename iterator_traits<_ForwardIterator>::value_type __v;

1104

    return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());

1105

1106

1107

// count

1108

1109

template <class _InputIterator, class _Tp>

1110

inline _LIBCPP_INLINE_VISIBILITY

1111

typename iterator_traits<_InputIterator>::difference_type

1112

count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)

1113

1114

    typename iterator_traits<_InputIterator>::difference_type __r(0);

1115

    for (; __first != __last; ++__first)

1116

        if (*__first == __value_)

1117

            ++__r;

1118

    return __r;

1119

1120

1121

// count_if

1122

1123

template <class _InputIterator, class _Predicate>

1124

inline _LIBCPP_INLINE_VISIBILITY

1125

typename iterator_traits<_InputIterator>::difference_type

1126

count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)

1127

1128

    typename iterator_traits<_InputIterator>::difference_type __r(0);

1129

    for (; __first != __last; ++__first)

1130

        if (__pred(*__first))

1131

            ++__r;

1132

    return __r;

1133

1134

1135

// mismatch

1136

1137

template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>

1138

inline _LIBCPP_INLINE_VISIBILITY

1139

pair<_InputIterator1, _InputIterator2>

1140

mismatch(_InputIterator1 __first1, _InputIterator1 __last1,

1141

         _InputIterator2 __first2, _BinaryPredicate __pred)

1142

1143

    for (; __first1 != __last1; ++__first1, (void) ++__first2)

1144

        if (!__pred(*__first1, *__first2))

1145

            break;

1146

    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);

1147

1148

1149

template <class _InputIterator1, class _InputIterator2>

1150

inline _LIBCPP_INLINE_VISIBILITY

1151

pair<_InputIterator1, _InputIterator2>

1152

mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)

1153

1154

    typedef typename iterator_traits<_InputIterator1>::value_type __v1;

1155

    typedef typename iterator_traits<_InputIterator2>::value_type __v2;

1156

    return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());

1157

1158

1159

#if _LIBCPP_STD_VER > 11

1160

template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>

1161

inline _LIBCPP_INLINE_VISIBILITY

1162

pair<_InputIterator1, _InputIterator2>

1163

mismatch(_InputIterator1 __first1, _InputIterator1 __last1,

1164

         _InputIterator2 __first2, _InputIterator2 __last2,

1165

         _BinaryPredicate __pred)

1166

1167

    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)

1168

        if (!__pred(*__first1, *__first2))

1169

            break;

1170

    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);

1171

1172

1173

template <class _InputIterator1, class _InputIterator2>

1174

inline _LIBCPP_INLINE_VISIBILITY

1175

pair<_InputIterator1, _InputIterator2>

1176

mismatch(_InputIterator1 __first1, _InputIterator1 __last1,

1177

         _InputIterator2 __first2, _InputIterator2 __last2)

1178

1179

    typedef typename iterator_traits<_InputIterator1>::value_type __v1;

1180

    typedef typename iterator_traits<_InputIterator2>::value_type __v2;

1181

    return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());

1182

1183

#endif

1184

1185

// equal

1186

1187

template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>

1188

inline _LIBCPP_INLINE_VISIBILITY

1189

bool

1190

equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)

1191

1192

    for (; __first1 != __last1; ++__first1, (void) ++__first2)

1193

        if (!__pred(*__first1, *__first2))

1194

            return false;

1195

    return true;

1196

1197

1198

template <class _InputIterator1, class _InputIterator2>

1199

inline _LIBCPP_INLINE_VISIBILITY

1200

bool

1201

equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)

1202

1203

    typedef typename iterator_traits<_InputIterator1>::value_type __v1;

1204

    typedef typename iterator_traits<_InputIterator2>::value_type __v2;

1205

    return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());

1206

1207

1208

#if _LIBCPP_STD_VER > 11

1209

template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>

1210

inline _LIBCPP_INLINE_VISIBILITY

1211

bool

1212

__equal(_InputIterator1 __first1, _InputIterator1 __last1,

1213

        _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,

1214

        input_iterator_tag, input_iterator_tag )

1215

1216

    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)

1217

        if (!__pred(*__first1, *__first2))

1218

            return false;

1219

    return __first1 == __last1 && __first2 == __last2;

1220

1221

1222

template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>

1223

inline _LIBCPP_INLINE_VISIBILITY

1224

bool

1225

__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,

1226

        _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,

1227

      random_access_iterator_tag, random_access_iterator_tag )

1228

1229

    if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))

1230

        return false;

1231

    return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,

1232

                        typename add_lvalue_reference<_BinaryPredicate>::type>

1233

                       (__first1, __last1, __first2, __pred );

1234

1235

1236

template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>

1237

inline _LIBCPP_INLINE_VISIBILITY

1238

bool

1239

equal(_InputIterator1 __first1, _InputIterator1 __last1,

1240

      _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )

1241

1242

    return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>

1243

       (__first1, __last1, __first2, __last2, __pred,

1244

        typename iterator_traits<_InputIterator1>::iterator_category(),

1245

        typename iterator_traits<_InputIterator2>::iterator_category());

1246

1247

1248

template <class _InputIterator1, class _InputIterator2>

1249

inline _LIBCPP_INLINE_VISIBILITY

1250

bool

1251

equal(_InputIterator1 __first1, _InputIterator1 __last1,

1252

      _InputIterator2 __first2, _InputIterator2 __last2)

1253

1254

    typedef typename iterator_traits<_InputIterator1>::value_type __v1;

1255

    typedef typename iterator_traits<_InputIterator2>::value_type __v2;

1256

    return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),

1257

        typename iterator_traits<_InputIterator1>::iterator_category(),

1258

        typename iterator_traits<_InputIterator2>::iterator_category());

1259

1260

#endif

1261

1262

// is_permutation

1263

1264

template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1265

bool

1266

is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1267

               _ForwardIterator2 __first2, _BinaryPredicate __pred)

1268

1269

    // shorten sequences as much as possible by lopping of any equal parts

1270

    for (; __first1 != __last1; ++__first1, (void) ++__first2)

1271

        if (!__pred(*__first1, *__first2))

1272

            goto __not_done;

1273

    return true;

1274

__not_done:

1275

    // __first1 != __last1 && *__first1 != *__first2

1276

    typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;

1277

    _D1 __l1 = _VSTD::distance(__first1, __last1);

1278

    if (__l1 == _D1(1))

1279

        return false;

1280

    _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);

1281

    // For each element in [f1, l1) see if there are the same number of

1282

    //    equal elements in [f2, l2)

1283

    for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)

1284

1285

        // Have we already counted the number of *__i in [f1, l1)?

1286

        for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)

1287

            if (__pred(*__j, *__i))

1288

                goto __next_iter;

1289

1290

            // Count number of *__i in [f2, l2)

1291

            _D1 __c2 = 0;

1292

            for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)

1293

                if (__pred(*__i, *__j))

1294

                    ++__c2;

1295

            if (__c2 == 0)

1296

                return false;

1297

            // Count number of *__i in [__i, l1) (we can start with 1)

1298

            _D1 __c1 = 1;

1299

            for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)

1300

                if (__pred(*__i, *__j))

1301

                    ++__c1;

1302

            if (__c1 != __c2)

1303

                return false;

1304

1305

__next_iter:;

1306

1307

    return true;

1308

1309

1310

template<class _ForwardIterator1, class _ForwardIterator2>

1311

inline _LIBCPP_INLINE_VISIBILITY

1312

bool

1313

is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1314

               _ForwardIterator2 __first2)

1315

1316

    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;

1317

    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;

1318

    return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());

1319

1320

1321

#if _LIBCPP_STD_VER > 11

1322

template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>

1323

bool

1324

__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1325

                 _ForwardIterator2 __first2, _ForwardIterator2 __last2,

1326

                 _BinaryPredicate __pred,

1327

                 forward_iterator_tag, forward_iterator_tag )

1328

1329

    // shorten sequences as much as possible by lopping of any equal parts

1330

    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)

1331

        if (!__pred(*__first1, *__first2))

1332

            goto __not_done;

1333

    return __first1 == __last1 && __first2 == __last2;

1334

__not_done:

1335

    // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2

1336

    typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;

1337

    _D1 __l1 = _VSTD::distance(__first1, __last1);

1338

1339

    typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;

1340

    _D2 __l2 = _VSTD::distance(__first2, __last2);

1341

    if (__l1 != __l2)

1342

        return false;

1343

1344

    // For each element in [f1, l1) see if there are the same number of

1345

    //    equal elements in [f2, l2)

1346

    for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)

1347

1348

        // Have we already counted the number of *__i in [f1, l1)?

1349

        for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)

1350

            if (__pred(*__j, *__i))

1351

                goto __next_iter;

1352

1353

            // Count number of *__i in [f2, l2)

1354

            _D1 __c2 = 0;

1355

            for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)

1356

                if (__pred(*__i, *__j))

1357

                    ++__c2;

1358

            if (__c2 == 0)

1359

                return false;

1360

            // Count number of *__i in [__i, l1) (we can start with 1)

1361

            _D1 __c1 = 1;

1362

            for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)

1363

                if (__pred(*__i, *__j))

1364

                    ++__c1;

1365

            if (__c1 != __c2)

1366

                return false;

1367

1368

__next_iter:;

1369

1370

    return true;

1371

1372

1373

template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>

1374

bool

1375

__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,

1376

               _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,

1377

               _BinaryPredicate __pred,

1378

               random_access_iterator_tag, random_access_iterator_tag )

1379

1380

    if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))

1381

        return false;

1382

    return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,

1383

                                 typename add_lvalue_reference<_BinaryPredicate>::type>

1384

                                (__first1, __last1, __first2, __pred );

1385

1386

1387

template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1388

inline _LIBCPP_INLINE_VISIBILITY

1389

bool

1390

is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1391

               _ForwardIterator2 __first2, _ForwardIterator2 __last2,

1392

               _BinaryPredicate __pred )

1393

1394

    return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>

1395

       (__first1, __last1, __first2, __last2, __pred,

1396

        typename iterator_traits<_ForwardIterator1>::iterator_category(),

1397

        typename iterator_traits<_ForwardIterator2>::iterator_category());

1398

1399

1400

template<class _ForwardIterator1, class _ForwardIterator2>

1401

inline _LIBCPP_INLINE_VISIBILITY

1402

bool

1403

is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1404

               _ForwardIterator2 __first2, _ForwardIterator2 __last2)

1405

1406

    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;

1407

    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;

1408

    return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,

1409

        __equal_to<__v1, __v2>(),

1410

        typename iterator_traits<_ForwardIterator1>::iterator_category(),

1411

        typename iterator_traits<_ForwardIterator2>::iterator_category());

1412

1413

#endif

1414

1415

// search

1416

1417

template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>

1418

_ForwardIterator1

1419

__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1420

         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,

1421

         forward_iterator_tag, forward_iterator_tag)

1422

1423

    if (__first2 == __last2)

1424

        return __first1;  // Everything matches an empty sequence

1425

    while (true)

1426

1427

        // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks

1428

        while (true)

1429

1430

            if (__first1 == __last1)  // return __last1 if no element matches *__first2

1431

                return __last1;

1432

            if (__pred(*__first1, *__first2))

1433

                break;

1434

            ++__first1;

1435

1436

        // *__first1 matches *__first2, now match elements after here

1437

        _ForwardIterator1 __m1 = __first1;

1438

        _ForwardIterator2 __m2 = __first2;

1439

        while (true)

1440

1441

            if (++__m2 == __last2)  // If pattern exhausted, __first1 is the answer (works for 1 element pattern)

1442

                return __first1;

1443

            if (++__m1 == __last1)  // Otherwise if source exhaused, pattern not found

1444

                return __last1;

1445

            if (!__pred(*__m1, *__m2))  // if there is a mismatch, restart with a new __first1

1446

1447

                ++__first1;

1448

                break;

1449

            }  // else there is a match, check next elements

template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>

1455

_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1

1456

__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,

1457

           _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,

1458

           random_access_iterator_tag, random_access_iterator_tag)

1459

1460

    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1;

1461

    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2;

1462

    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern

1463

    _D2 __len2 = __last2 - __first2;

1464

    if (__len2 == 0)

1465

        return __first1;

1466

    _D1 __len1 = __last1 - __first1;

1467

    if (__len1 < __len2)

1468

        return __last1;

1469

    const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here

1470

    while (true)

1471

1472

#if !_LIBCPP_UNROLL_LOOPS

1473

        while (true)

1474

1475

            if (__first1 == __s)

1476

                return __last1;

1477

            if (__pred(*__first1, *__first2))

1478

                break;

1479

            ++__first1;

1480

1481

#else  // !_LIBCPP_UNROLL_LOOPS

1482

        for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)

1483

1484

            if (__pred(*__first1, *__first2))

1485

                goto __phase2;

1486

            if (__pred(*++__first1, *__first2))

1487

                goto __phase2;

1488

            if (__pred(*++__first1, *__first2))

1489

                goto __phase2;

1490

            if (__pred(*++__first1, *__first2))

1491

                goto __phase2;

1492

            ++__first1;

1493

1494

        switch (__s - __first1)

1495

1496

        case 3:

1497

            if (__pred(*__first1, *__first2))

1498

                break;

1499

            ++__first1;

1500

        case 2:

1501

            if (__pred(*__first1, *__first2))

1502

                break;

1503

            ++__first1;

1504

        case 1:

1505

            if (__pred(*__first1, *__first2))

1506

                break;

1507

        case 0:

1508

            return __last1;

1509

1510

    __phase2:

1511

#endif  // !_LIBCPP_UNROLL_LOOPS

1512

        _RandomAccessIterator1 __m1 = __first1;

1513

        _RandomAccessIterator2 __m2 = __first2;

1514

#if !_LIBCPP_UNROLL_LOOPS

1515

         while (true)

1516

1517

             if (++__m2 == __last2)

1518

                 return __first1;

1519

             ++__m1;          // no need to check range on __m1 because __s guarantees we have enough source

1520

             if (!__pred(*__m1, *__m2))

1521

1522

                 ++__first1;

1523

                 break;

1524

1525

1526

#else  // !_LIBCPP_UNROLL_LOOPS

1527

        ++__m2;

1528

        ++__m1;

1529

        for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)

1530

1531

            if (!__pred(*__m1, *__m2))

1532

                goto __continue;

1533

            if (!__pred(*++__m1, *++__m2))

1534

                goto __continue;

1535

            if (!__pred(*++__m1, *++__m2))

1536

                goto __continue;

1537

            if (!__pred(*++__m1, *++__m2))

1538

                goto __continue;

1539

            ++__m1;

1540

            ++__m2;

1541

1542

        switch (__last2 - __m2)

1543

1544

        case 3:

1545

            if (!__pred(*__m1, *__m2))

1546

                break;

1547

            ++__m1;

1548

            ++__m2;

1549

        case 2:

1550

            if (!__pred(*__m1, *__m2))

1551

                break;

1552

            ++__m1;

1553

            ++__m2;

1554

        case 1:

1555

            if (!__pred(*__m1, *__m2))

1556

                break;

1557

        case 0:

1558

            return __first1;

1559

1560

    __continue:

1561

        ++__first1;

1562

#endif  // !_LIBCPP_UNROLL_LOOPS

template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>

1567

inline _LIBCPP_INLINE_VISIBILITY

1568

_ForwardIterator1

1569

search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1570

       _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)

1571

1572

    return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>

1573

                         (__first1, __last1, __first2, __last2, __pred,

1574

                          typename std::iterator_traits<_ForwardIterator1>::iterator_category(),

1575

                          typename std::iterator_traits<_ForwardIterator2>::iterator_category());

1576

1577

1578

template <class _ForwardIterator1, class _ForwardIterator2>

1579

inline _LIBCPP_INLINE_VISIBILITY

1580

_ForwardIterator1

1581

search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

1582

       _ForwardIterator2 __first2, _ForwardIterator2 __last2)

1583

1584

    typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1;

1585

    typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2;

1586

    return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());

1587

1588

1589

// search_n

1590

1591

template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>

1592

_ForwardIterator

1593

__search_n(_ForwardIterator __first, _ForwardIterator __last,

1594

           _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)

1595

1596

    if (__count <= 0)

1597

        return __first;

1598

    while (true)

1599

1600

        // Find first element in sequence that matchs __value_, with a mininum of loop checks

1601

        while (true)

1602

1603

            if (__first == __last)  // return __last if no element matches __value_

1604

                return __last;

1605

            if (__pred(*__first, __value_))

1606

                break;

1607

            ++__first;

1608

1609

        // *__first matches __value_, now match elements after here

1610

        _ForwardIterator __m = __first;

1611

        _Size __c(0);

1612

        while (true)

1613

1614

            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)

1615

                return __first;

1616

            if (++__m == __last)  // Otherwise if source exhaused, pattern not found

1617

                return __last;

1618

            if (!__pred(*__m, __value_))  // if there is a mismatch, restart with a new __first

1619

1620

                __first = __m;

1621

                ++__first;

1622

                break;

1623

            }  // else there is a match, check next elements

template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>

1629

_RandomAccessIterator

1630

__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,

1631

           _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)

1632

1633

    if (__count <= 0)

1634

        return __first;

1635

    _Size __len = static_cast<_Size>(__last - __first);

1636

    if (__len < __count)

1637

        return __last;

1638

    const _RandomAccessIterator __s = __last - (__count - 1);  // Start of pattern match can't go beyond here

1639

    while (true)

1640

1641

        // Find first element in sequence that matchs __value_, with a mininum of loop checks

1642

        while (true)

1643

1644

            if (__first >= __s)  // return __last if no element matches __value_

1645

                return __last;

1646

            if (__pred(*__first, __value_))

1647

                break;

1648

            ++__first;

1649

1650

        // *__first matches __value_, now match elements after here

1651

        _RandomAccessIterator __m = __first;

1652

        _Size __c(0);

1653

        while (true)

1654

1655

            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)

1656

                return __first;

1657

             ++__m;          // no need to check range on __m because __s guarantees we have enough source

1658

            if (!__pred(*__m, __value_))  // if there is a mismatch, restart with a new __first

1659

1660

                __first = __m;

1661

                ++__first;

1662

                break;

1663

            }  // else there is a match, check next elements

template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>

1669

inline _LIBCPP_INLINE_VISIBILITY

1670

_ForwardIterator

1671

search_n(_ForwardIterator __first, _ForwardIterator __last,

1672

         _Size __count, const _Tp& __value_, _BinaryPredicate __pred)

1673

1674

    return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>

1675

           (__first, __last, __convert_to_integral(__count), __value_, __pred,

1676

           typename iterator_traits<_ForwardIterator>::iterator_category());

1677

1678

1679

template <class _ForwardIterator, class _Size, class _Tp>

1680

inline _LIBCPP_INLINE_VISIBILITY

1681

_ForwardIterator

1682

search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)

1683

1684

    typedef typename iterator_traits<_ForwardIterator>::value_type __v;

1685

    return _VSTD::search_n(__first, __last, __convert_to_integral(__count),

1686

                           __value_, __equal_to<__v, _Tp>());

1687

1688

1689

// copy

1690

1691

template <class _Iter>

1692

struct __libcpp_is_trivial_iterator

1693

1694

    static const bool value = is_pointer<_Iter>::value;

1695

};

1696

1697

template <class _Iter>

1698

struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >

1699

1700

    static const bool value = is_pointer<_Iter>::value;

1701

};

1702

1703

template <class _Iter>

1704

struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >

1705

1706

    static const bool value = is_pointer<_Iter>::value;

1707

};

1708

1709

template <class _Iter>

1710

inline _LIBCPP_INLINE_VISIBILITY

1711

_Iter

1712

__unwrap_iter(_Iter __i)

1713

1714

    return __i;

1715

1716

1717

template <class _Tp>

1718

inline _LIBCPP_INLINE_VISIBILITY

1719

typename enable_if

1720

1721

    is_trivially_copy_assignable<_Tp>::value,

1722

    _Tp*

1723

>::type

1724

__unwrap_iter(move_iterator<_Tp*> __i)

1725

1726

    return __i.base();

1727

1728

1729

#if _LIBCPP_DEBUG_LEVEL < 2

1730

1731

template <class _Tp>

1732

inline _LIBCPP_INLINE_VISIBILITY

1733

typename enable_if

1734

1735

    is_trivially_copy_assignable<_Tp>::value,

1736

    _Tp*

1737

>::type

1738

__unwrap_iter(__wrap_iter<_Tp*> __i)

1739

1740

    return __i.base();

1741

1742

1743

#endif  // _LIBCPP_DEBUG_LEVEL < 2

1744

1745

template <class _InputIterator, class _OutputIterator>

1746

inline _LIBCPP_INLINE_VISIBILITY

1747

_OutputIterator

1748

__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

1749

1750

    for (; __first != __last; ++__first, (void) ++__result)

1751

        *__result = *__first;

1752

    return __result;

1753

1754

1755

template <class _Tp, class _Up>

1756

inline _LIBCPP_INLINE_VISIBILITY

1757

typename enable_if

1758

1759

    is_same<typename remove_const<_Tp>::type, _Up>::value &&

1760

    is_trivially_copy_assignable<_Up>::value,

1761

    _Up*

1762

>::type

1763

__copy(_Tp* __first, _Tp* __last, _Up* __result)

1764

1765

    const size_t __n = static_cast<size_t>(__last - __first);

1766

    if (__n > 0)

1767

        _VSTD::memmove(__result, __first, __n * sizeof(_Up));

1768

    return __result + __n;

1769

1770

1771

template <class _InputIterator, class _OutputIterator>

1772

inline _LIBCPP_INLINE_VISIBILITY

1773

_OutputIterator

1774

copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

1775

1776

    return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));

1777

1778

1779

// copy_backward

1780

1781

template <class _BidirectionalIterator, class _OutputIterator>

1782

inline _LIBCPP_INLINE_VISIBILITY

1783

_OutputIterator

1784

__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)

1785

1786

    while (__first != __last)

1787

        *--__result = *--__last;

1788

    return __result;

1789

1790

1791

template <class _Tp, class _Up>

1792

inline _LIBCPP_INLINE_VISIBILITY

1793

typename enable_if

1794

1795

    is_same<typename remove_const<_Tp>::type, _Up>::value &&

1796

    is_trivially_copy_assignable<_Up>::value,

1797

    _Up*

1798

>::type

1799

__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)

1800

1801

    const size_t __n = static_cast<size_t>(__last - __first);

1802

    if (__n > 0)

1803

1804

        __result -= __n;

1805

        _VSTD::memmove(__result, __first, __n * sizeof(_Up));

1806

1807

    return __result;

1808

1809

1810

template <class _BidirectionalIterator1, class _BidirectionalIterator2>

1811

inline _LIBCPP_INLINE_VISIBILITY

1812

_BidirectionalIterator2

1813

copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,

1814

              _BidirectionalIterator2 __result)

1815

1816

    return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));

1817

1818

1819

// copy_if

1820

1821

template<class _InputIterator, class _OutputIterator, class _Predicate>

1822

inline _LIBCPP_INLINE_VISIBILITY

1823

_OutputIterator

1824

copy_if(_InputIterator __first, _InputIterator __last,

1825

        _OutputIterator __result, _Predicate __pred)

1826

1827

    for (; __first != __last; ++__first)

1828

1829

        if (__pred(*__first))

1830

1831

            *__result = *__first;

1832

            ++__result;

1833

1834

1835

    return __result;

1836

1837

1838

// copy_n

1839

1840

template<class _InputIterator, class _Size, class _OutputIterator>

1841

inline _LIBCPP_INLINE_VISIBILITY

1842

typename enable_if

1843

1844

    __is_input_iterator<_InputIterator>::value &&

1845

   !__is_random_access_iterator<_InputIterator>::value,

1846

    _OutputIterator

1847

>::type

1848

copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)

1849

1850

    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;

1851

    _IntegralSize __n = __orig_n;

1852

    if (__n > 0)

1853

1854

        *__result = *__first;

1855

        ++__result;

1856

        for (--__n; __n > 0; --__n)

1857

1858

            ++__first;

1859

            *__result = *__first;

1860

            ++__result;

1861

1862

1863

    return __result;

1864

1865

1866

template<class _InputIterator, class _Size, class _OutputIterator>

1867

inline _LIBCPP_INLINE_VISIBILITY

1868

typename enable_if

1869

1870

    __is_random_access_iterator<_InputIterator>::value,

1871

    _OutputIterator

1872

>::type

1873

copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)

1874

1875

    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;

1876

    _IntegralSize __n = __orig_n;

1877

    return _VSTD::copy(__first, __first + __n, __result);

1878

1879

1880

// move

1881

1882

template <class _InputIterator, class _OutputIterator>

1883

inline _LIBCPP_INLINE_VISIBILITY

1884

_OutputIterator

1885

__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

1886

1887

    for (; __first != __last; ++__first, (void) ++__result)

1888

        *__result = _VSTD::move(*__first);

1889

    return __result;

1890

1891

1892

template <class _Tp, class _Up>

1893

inline _LIBCPP_INLINE_VISIBILITY

1894

typename enable_if

1895

1896

    is_same<typename remove_const<_Tp>::type, _Up>::value &&

1897

    is_trivially_copy_assignable<_Up>::value,

1898

    _Up*

1899

>::type

1900

__move(_Tp* __first, _Tp* __last, _Up* __result)

1901

1902

    const size_t __n = static_cast<size_t>(__last - __first);

1903

    if (__n > 0)

1904

        _VSTD::memmove(__result, __first, __n * sizeof(_Up));

1905

    return __result + __n;

1906

1907

1908

template <class _InputIterator, class _OutputIterator>

1909

inline _LIBCPP_INLINE_VISIBILITY

1910

_OutputIterator

1911

move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

1912

1913

    return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));

1914

1915

1916

// move_backward

1917

1918

template <class _InputIterator, class _OutputIterator>

1919

inline _LIBCPP_INLINE_VISIBILITY

1920

_OutputIterator

1921

__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

1922

1923

    while (__first != __last)

1924

        *--__result = _VSTD::move(*--__last);

1925

    return __result;

1926

1927

1928

template <class _Tp, class _Up>

1929

inline _LIBCPP_INLINE_VISIBILITY

1930

typename enable_if

1931

1932

    is_same<typename remove_const<_Tp>::type, _Up>::value &&

1933

    is_trivially_copy_assignable<_Up>::value,

1934

    _Up*

1935

>::type

1936

__move_backward(_Tp* __first, _Tp* __last, _Up* __result)

1937

1938

    const size_t __n = static_cast<size_t>(__last - __first);

1939

    if (__n > 0)

1940

1941

        __result -= __n;

1942

        _VSTD::memmove(__result, __first, __n * sizeof(_Up));

1943

1944

    return __result;

1945

1946

1947

template <class _BidirectionalIterator1, class _BidirectionalIterator2>

1948

inline _LIBCPP_INLINE_VISIBILITY

1949

_BidirectionalIterator2

1950

move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,

1951

              _BidirectionalIterator2 __result)

1952

1953

    return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));

1954

1955

1956

// iter_swap

1957

1958

// moved to <type_traits> for better swap / noexcept support

1959

1960

// transform

1961

1962

template <class _InputIterator, class _OutputIterator, class _UnaryOperation>

1963

inline _LIBCPP_INLINE_VISIBILITY

1964

_OutputIterator

1965

transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)

1966

1967

    for (; __first != __last; ++__first, (void) ++__result)

1968

        *__result = __op(*__first);

1969

    return __result;

1970

1971

1972

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>

1973

inline _LIBCPP_INLINE_VISIBILITY

1974

_OutputIterator

1975

transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,

1976

          _OutputIterator __result, _BinaryOperation __binary_op)

1977

1978

    for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)

1979

        *__result = __binary_op(*__first1, *__first2);

1980

    return __result;

1981

1982

1983

// replace

1984

1985

template <class _ForwardIterator, class _Tp>

1986

inline _LIBCPP_INLINE_VISIBILITY

1987

void

1988

replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)

1989

1990

    for (; __first != __last; ++__first)

1991

        if (*__first == __old_value)

1992

            *__first = __new_value;

1993

1994

1995

// replace_if

1996

1997

template <class _ForwardIterator, class _Predicate, class _Tp>

1998

inline _LIBCPP_INLINE_VISIBILITY

1999

void

2000

replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)

2001

2002

    for (; __first != __last; ++__first)

2003

        if (__pred(*__first))

2004

            *__first = __new_value;

2005

2006

2007

// replace_copy

2008

2009

template <class _InputIterator, class _OutputIterator, class _Tp>

2010

inline _LIBCPP_INLINE_VISIBILITY

2011

_OutputIterator

2012

replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,

2013

             const _Tp& __old_value, const _Tp& __new_value)

2014

2015

    for (; __first != __last; ++__first, (void) ++__result)

2016

        if (*__first == __old_value)

2017

            *__result = __new_value;

2018

        else

2019

            *__result = *__first;

2020

    return __result;

2021

2022

2023

// replace_copy_if

2024

2025

template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>

2026

inline _LIBCPP_INLINE_VISIBILITY

2027

_OutputIterator

2028

replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,

2029

                _Predicate __pred, const _Tp& __new_value)

2030

2031

    for (; __first != __last; ++__first, (void) ++__result)

2032

        if (__pred(*__first))

2033

            *__result = __new_value;

2034

        else

2035

            *__result = *__first;

2036

    return __result;

2037

2038

2039

// fill_n

2040

2041

template <class _OutputIterator, class _Size, class _Tp>

2042

inline _LIBCPP_INLINE_VISIBILITY

2043

_OutputIterator

2044

__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)

2045

2046

    for (; __n > 0; ++__first, (void) --__n)

2047

        *__first = __value_;

2048

    return __first;

2049

2050

2051

template <class _Tp, class _Size, class _Up>

2052

inline _LIBCPP_INLINE_VISIBILITY

2053

typename enable_if

2054

2055

    is_integral<_Tp>::value && sizeof(_Tp) == 1 &&

2056

    !is_same<_Tp, bool>::value &&

2057

    is_integral<_Up>::value && sizeof(_Up) == 1,

2058

    _Tp*

2059

>::type

2060

__fill_n(_Tp* __first, _Size __n,_Up __value_)

2061

2062

    if (__n > 0)

2063

        _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));

2064

    return __first + __n;

2065

2066

2067

template <class _OutputIterator, class _Size, class _Tp>

2068

inline _LIBCPP_INLINE_VISIBILITY

2069

_OutputIterator

2070

fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)

2071

2072

   return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);

2073

2074

2075

// fill

2076

2077

template <class _ForwardIterator, class _Tp>

2078

inline _LIBCPP_INLINE_VISIBILITY

2079

void

2080

__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)

2081

2082

    for (; __first != __last; ++__first)

2083

        *__first = __value_;

2084

2085

2086

template <class _RandomAccessIterator, class _Tp>

2087

inline _LIBCPP_INLINE_VISIBILITY

2088

void

2089

__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)

2090

2091

    _VSTD::fill_n(__first, __last - __first, __value_);

2092

2093

2094

template <class _ForwardIterator, class _Tp>

2095

inline _LIBCPP_INLINE_VISIBILITY

2096

void

2097

fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

2098

2099

    _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());

2100

2101

2102

// generate

2103

2104

template <class _ForwardIterator, class _Generator>

2105

inline _LIBCPP_INLINE_VISIBILITY

2106

void

2107

generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)

2108

2109

    for (; __first != __last; ++__first)

2110

        *__first = __gen();

2111

2112

2113

// generate_n

2114

2115

template <class _OutputIterator, class _Size, class _Generator>

2116

inline _LIBCPP_INLINE_VISIBILITY

2117

_OutputIterator

2118

generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)

2119

2120

    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;

2121

    _IntegralSize __n = __orig_n;

2122

    for (; __n > 0; ++__first, (void) --__n)

2123

        *__first = __gen();

2124

    return __first;

2125

2126

2127

// remove

2128

2129

template <class _ForwardIterator, class _Tp>

2130

_ForwardIterator

2131

remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

2132

2133

    __first = _VSTD::find(__first, __last, __value_);

2134

    if (__first != __last)

2135

2136

        _ForwardIterator __i = __first;

2137

        while (++__i != __last)

2138

2139

            if (!(*__i == __value_))

2140

2141

                *__first = _VSTD::move(*__i);

2142

                ++__first;

    return __first;

2147

2148

2149

// remove_if

2150

2151

template <class _ForwardIterator, class _Predicate>

2152

_ForwardIterator

2153

remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)

2154

2155

    __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>

2156

                           (__first, __last, __pred);

2157

    if (__first != __last)

2158

2159

        _ForwardIterator __i = __first;

2160

        while (++__i != __last)

2161

2162

            if (!__pred(*__i))

2163

2164

                *__first = _VSTD::move(*__i);

2165

                ++__first;

    return __first;

2170

2171

2172

// remove_copy

2173

2174

template <class _InputIterator, class _OutputIterator, class _Tp>

2175

inline _LIBCPP_INLINE_VISIBILITY

2176

_OutputIterator

2177

remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)

2178

2179

    for (; __first != __last; ++__first)

2180

2181

        if (!(*__first == __value_))

2182

2183

            *__result = *__first;

2184

            ++__result;

2185

2186

2187

    return __result;

2188

2189

2190

// remove_copy_if

2191

2192

template <class _InputIterator, class _OutputIterator, class _Predicate>

2193

inline _LIBCPP_INLINE_VISIBILITY

2194

_OutputIterator

2195

remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)

2196

2197

    for (; __first != __last; ++__first)

2198

2199

        if (!__pred(*__first))

2200

2201

            *__result = *__first;

2202

            ++__result;

2203

2204

2205

    return __result;

2206

2207

2208

// unique

2209

2210

template <class _ForwardIterator, class _BinaryPredicate>

2211

_ForwardIterator

2212

unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)

2213

2214

    __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>

2215

                                 (__first, __last, __pred);

2216

    if (__first != __last)

2217

2218

        // ...  a  a  ?  ...

2219

        //      f     i

2220

        _ForwardIterator __i = __first;

2221

        for (++__i; ++__i != __last;)

2222

            if (!__pred(*__first, *__i))

2223

                *++__first = _VSTD::move(*__i);

2224

        ++__first;

2225

2226

    return __first;

2227

2228

2229

template <class _ForwardIterator>

2230

inline _LIBCPP_INLINE_VISIBILITY

2231

_ForwardIterator

2232

unique(_ForwardIterator __first, _ForwardIterator __last)

2233

2234

    typedef typename iterator_traits<_ForwardIterator>::value_type __v;

2235

    return _VSTD::unique(__first, __last, __equal_to<__v>());

2236

2237

2238

// unique_copy

2239

2240

template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>

2241

_OutputIterator

2242

__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,

2243

              input_iterator_tag, output_iterator_tag)

2244

2245

    if (__first != __last)

2246

2247

        typename iterator_traits<_InputIterator>::value_type __t(*__first);

2248

        *__result = __t;

2249

        ++__result;

2250

        while (++__first != __last)

2251

2252

            if (!__pred(__t, *__first))

2253

2254

                __t = *__first;

2255

                *__result = __t;

2256

                ++__result;

    return __result;

2261

2262

2263

template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>

2264

_OutputIterator

2265

__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,

2266

              forward_iterator_tag, output_iterator_tag)

2267

2268

    if (__first != __last)

2269

2270

        _ForwardIterator __i = __first;

2271

        *__result = *__i;

2272

        ++__result;

2273

        while (++__first != __last)

2274

2275

            if (!__pred(*__i, *__first))

2276

2277

                *__result = *__first;

2278

                ++__result;

2279

                __i = __first;

    return __result;

2284

2285

2286

template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>

2287

_ForwardIterator

2288

__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,

2289

              input_iterator_tag, forward_iterator_tag)

2290

2291

    if (__first != __last)

2292

2293

        *__result = *__first;

2294

        while (++__first != __last)

2295

            if (!__pred(*__result, *__first))

2296

                *++__result = *__first;

2297

        ++__result;

2298

2299

    return __result;

2300

2301

2302

template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>

2303

inline _LIBCPP_INLINE_VISIBILITY

2304

_OutputIterator

2305

unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)

2306

2307

    return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>

2308

                              (__first, __last, __result, __pred,

2309

                               typename iterator_traits<_InputIterator>::iterator_category(),

2310

                               typename iterator_traits<_OutputIterator>::iterator_category());

2311

2312

2313

template <class _InputIterator, class _OutputIterator>

2314

inline _LIBCPP_INLINE_VISIBILITY

2315

_OutputIterator

2316

unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

2317

2318

    typedef typename iterator_traits<_InputIterator>::value_type __v;

2319

    return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());

2320

2321

2322

// reverse

2323

2324

template <class _BidirectionalIterator>

2325

inline _LIBCPP_INLINE_VISIBILITY

2326

void

2327

__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)

2328

2329

    while (__first != __last)

2330

2331

        if (__first == --__last)

2332

            break;

2333

        swap(*__first, *__last);

2334

        ++__first;

template <class _RandomAccessIterator>

2339

inline _LIBCPP_INLINE_VISIBILITY

2340

void

2341

__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)

2342

2343

    if (__first != __last)

2344

        for (; __first < --__last; ++__first)

2345

            swap(*__first, *__last);

2346

2347

2348

template <class _BidirectionalIterator>

2349

inline _LIBCPP_INLINE_VISIBILITY

2350

void

2351

reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)

2352

2353

    _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());

2354

2355

2356

// reverse_copy

2357

2358

template <class _BidirectionalIterator, class _OutputIterator>

2359

inline _LIBCPP_INLINE_VISIBILITY

2360

_OutputIterator

2361

reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)

2362

2363

    for (; __first != __last; ++__result)

2364

        *__result = *--__last;

2365

    return __result;

2366

2367

2368

// rotate

2369

2370

template <class _ForwardIterator>

2371

_ForwardIterator

2372

__rotate_left(_ForwardIterator __first, _ForwardIterator __last)

2373

2374

    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;

2375

    value_type __tmp = _VSTD::move(*__first);

2376

    _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);

2377

    *__lm1 = _VSTD::move(__tmp);

2378

    return __lm1;

2379

2380

2381

template <class _BidirectionalIterator>

2382

_BidirectionalIterator

2383

__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)

2384

2385

    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;

2386

    _BidirectionalIterator __lm1 = _VSTD::prev(__last);

2387

    value_type __tmp = _VSTD::move(*__lm1);

2388

    _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);

2389

    *__first = _VSTD::move(__tmp);

2390

    return __fp1;

2391

2392

2393

template <class _ForwardIterator>

2394

_ForwardIterator

2395

__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)

2396

2397

    _ForwardIterator __i = __middle;

2398

    while (true)

2399

2400

        swap(*__first, *__i);

2401

        ++__first;

2402

        if (++__i == __last)

2403

            break;

2404

        if (__first == __middle)

2405

            __middle = __i;

2406

2407

    _ForwardIterator __r = __first;

2408

    if (__first != __middle)

2409

2410

        __i = __middle;

2411

        while (true)

2412

2413

            swap(*__first, *__i);

2414

            ++__first;

2415

            if (++__i == __last)

2416

2417

                if (__first == __middle)

2418

                    break;

2419

                __i = __middle;

2420

2421

            else if (__first == __middle)

2422

                __middle = __i;

2423

2424

2425

    return __r;

2426

2427

2428

template<typename _Integral>

2429

inline _LIBCPP_INLINE_VISIBILITY

2430

_Integral

2431

__gcd(_Integral __x, _Integral __y)

2432

2433

do

2434

2435

        _Integral __t = __x % __y;

2436

        __x = __y;

2437

        __y = __t;

2438

    } while (__y);

2439

    return __x;

2440

2441

2442

template<typename _RandomAccessIterator>

2443

_RandomAccessIterator

2444

__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)

2445

2446

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

2447

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

2448

2449

    const difference_type __m1 = __middle - __first;

2450

    const difference_type __m2 = __last - __middle;

2451

    if (__m1 == __m2)

2452

2453

        _VSTD::swap_ranges(__first, __middle, __middle);

2454

        return __middle;

2455

2456

    const difference_type __g = _VSTD::__gcd(__m1, __m2);

2457

    for (_RandomAccessIterator __p = __first + __g; __p != __first;)

2458

2459

        value_type __t(_VSTD::move(*--__p));

2460

        _RandomAccessIterator __p1 = __p;

2461

        _RandomAccessIterator __p2 = __p1 + __m1;

2462

do

2463

2464

            *__p1 = _VSTD::move(*__p2);

2465

            __p1 = __p2;

2466

            const difference_type __d = __last - __p2;

2467

            if (__m1 < __d)

2468

                __p2 += __m1;

2469

            else

2470

                __p2 = __first + (__m1 - __d);

2471

        } while (__p2 != __p);

2472

        *__p1 = _VSTD::move(__t);

2473

2474

    return __first + __m2;

2475

2476

2477

template <class _ForwardIterator>

2478

inline _LIBCPP_INLINE_VISIBILITY

2479

_ForwardIterator

2480

__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,

2481

         _VSTD::forward_iterator_tag)

2482

2483

    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;

2484

    if (_VSTD::is_trivially_move_assignable<value_type>::value)

2485

2486

        if (_VSTD::next(__first) == __middle)

2487

            return _VSTD::__rotate_left(__first, __last);

2488

2489

    return _VSTD::__rotate_forward(__first, __middle, __last);

2490

2491

2492

template <class _BidirectionalIterator>

2493

inline _LIBCPP_INLINE_VISIBILITY

2494

_BidirectionalIterator

2495

__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,

2496

         _VSTD::bidirectional_iterator_tag)

2497

2498

    typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;

2499

    if (_VSTD::is_trivially_move_assignable<value_type>::value)

2500

2501

        if (_VSTD::next(__first) == __middle)

2502

            return _VSTD::__rotate_left(__first, __last);

2503

        if (_VSTD::next(__middle) == __last)

2504

            return _VSTD::__rotate_right(__first, __last);

2505

2506

    return _VSTD::__rotate_forward(__first, __middle, __last);

2507

2508

2509

template <class _RandomAccessIterator>

2510

inline _LIBCPP_INLINE_VISIBILITY

2511

_RandomAccessIterator

2512

__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,

2513

         _VSTD::random_access_iterator_tag)

2514

2515

    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;

2516

    if (_VSTD::is_trivially_move_assignable<value_type>::value)

2517

2518

        if (_VSTD::next(__first) == __middle)

2519

            return _VSTD::__rotate_left(__first, __last);

2520

        if (_VSTD::next(__middle) == __last)

2521

            return _VSTD::__rotate_right(__first, __last);

2522

        return _VSTD::__rotate_gcd(__first, __middle, __last);

2523

2524

    return _VSTD::__rotate_forward(__first, __middle, __last);

2525

2526

2527

template <class _ForwardIterator>

2528

inline _LIBCPP_INLINE_VISIBILITY

2529

_ForwardIterator

2530

rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)

2531

2532

    if (__first == __middle)

2533

        return __last;

2534

    if (__middle == __last)

2535

        return __first;

2536

    return _VSTD::__rotate(__first, __middle, __last,

2537

                           typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());

2538

2539

2540

// rotate_copy

2541

2542

template <class _ForwardIterator, class _OutputIterator>

2543

inline _LIBCPP_INLINE_VISIBILITY

2544

_OutputIterator

2545

rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)

2546

2547

    return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));

2548

2549

2550

// min_element

2551

2552

template <class _ForwardIterator, class _Compare>

2553

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2554

_ForwardIterator

2555

min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

2556

2557

    if (__first != __last)

2558

2559

        _ForwardIterator __i = __first;

2560

        while (++__i != __last)

2561

            if (__comp(*__i, *__first))

2562

                __first = __i;

2563

2564

    return __first;

2565

2566

2567

template <class _ForwardIterator>

2568

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2569

_ForwardIterator

2570

min_element(_ForwardIterator __first, _ForwardIterator __last)

2571

2572

    return _VSTD::min_element(__first, __last,

2573

              __less<typename iterator_traits<_ForwardIterator>::value_type>());

2574

2575

2576

// min

2577

2578

template <class _Tp, class _Compare>

2579

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2580

const _Tp&

2581

min(const _Tp& __a, const _Tp& __b, _Compare __comp)

2582

2583

    return __comp(__b, __a) ? __b : __a;

2584

2585

2586

template <class _Tp>

2587

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2588

const _Tp&

2589

min(const _Tp& __a, const _Tp& __b)

2590

2591

    return _VSTD::min(__a, __b, __less<_Tp>());

2592

2593

2594

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2595

2596

template<class _Tp, class _Compare>

2597

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2598

_Tp

2599

min(initializer_list<_Tp> __t, _Compare __comp)

2600

2601

    return *_VSTD::min_element(__t.begin(), __t.end(), __comp);

2602

2603

2604

template<class _Tp>

2605

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2606

_Tp

2607

min(initializer_list<_Tp> __t)

2608

2609

    return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());

2610

2611

2612

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2613

2614

// max_element

2615

2616

template <class _ForwardIterator, class _Compare>

2617

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2618

_ForwardIterator

2619

max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

2620

2621

    if (__first != __last)

2622

2623

        _ForwardIterator __i = __first;

2624

        while (++__i != __last)

2625

            if (__comp(*__first, *__i))

2626

                __first = __i;

2627

2628

    return __first;

template <class _ForwardIterator>

2633

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2634

_ForwardIterator

2635

max_element(_ForwardIterator __first, _ForwardIterator __last)

2636

2637

    return _VSTD::max_element(__first, __last,

2638

              __less<typename iterator_traits<_ForwardIterator>::value_type>());

2639

2640

2641

// max

2642

2643

template <class _Tp, class _Compare>

2644

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2645

const _Tp&

2646

max(const _Tp& __a, const _Tp& __b, _Compare __comp)

2647

2648

    return __comp(__a, __b) ? __b : __a;

2649

2650

2651

template <class _Tp>

2652

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2653

const _Tp&

2654

max(const _Tp& __a, const _Tp& __b)

2655

2656

    return _VSTD::max(__a, __b, __less<_Tp>());

2657

2658

2659

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2660

2661

template<class _Tp, class _Compare>

2662

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2663

_Tp

2664

max(initializer_list<_Tp> __t, _Compare __comp)

2665

2666

    return *_VSTD::max_element(__t.begin(), __t.end(), __comp);

2667

2668

2669

template<class _Tp>

2670

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2671

_Tp

2672

max(initializer_list<_Tp> __t)

2673

2674

    return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());

2675

2676

2677

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2678

2679

// minmax_element

2680

2681

template <class _ForwardIterator, class _Compare>

2682

_LIBCPP_CONSTEXPR_AFTER_CXX11

2683

std::pair<_ForwardIterator, _ForwardIterator>

2684

minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

2685

2686

  std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);

2687

  if (__first != __last)

2688

2689

      if (++__first != __last)

2690

2691

          if (__comp(*__first, *__result.first))

2692

              __result.first = __first;

2693

          else

2694

              __result.second = __first;

2695

          while (++__first != __last)

2696

2697

              _ForwardIterator __i = __first;

2698

              if (++__first == __last)

2699

2700

                  if (__comp(*__i, *__result.first))

2701

                      __result.first = __i;

2702

                  else if (!__comp(*__i, *__result.second))

2703

                      __result.second = __i;

2704

                  break;

2705

2706

              else

2707

2708

                  if (__comp(*__first, *__i))

2709

2710

                      if (__comp(*__first, *__result.first))

2711

                          __result.first = __first;

2712

                      if (!__comp(*__i, *__result.second))

2713

                          __result.second = __i;

2714

2715

                  else

2716

2717

                      if (__comp(*__i, *__result.first))

2718

                          __result.first = __i;

2719

                      if (!__comp(*__first, *__result.second))

2720

                          __result.second = __first;

  return __result;

2727

2728

2729

template <class _ForwardIterator>

2730

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2731

std::pair<_ForwardIterator, _ForwardIterator>

2732

minmax_element(_ForwardIterator __first, _ForwardIterator __last)

2733

2734

    return _VSTD::minmax_element(__first, __last,

2735

              __less<typename iterator_traits<_ForwardIterator>::value_type>());

2736

2737

2738

// minmax

2739

2740

template<class _Tp, class _Compare>

2741

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2742

pair<const _Tp&, const _Tp&>

2743

minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)

2744

2745

    return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :

2746

                              pair<const _Tp&, const _Tp&>(__a, __b);

2747

2748

2749

template<class _Tp>

2750

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2751

pair<const _Tp&, const _Tp&>

2752

minmax(const _Tp& __a, const _Tp& __b)

2753

2754

    return _VSTD::minmax(__a, __b, __less<_Tp>());

2755

2756

2757

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2758

2759

template<class _Tp, class _Compare>

2760

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2761

pair<_Tp, _Tp>

2762

minmax(initializer_list<_Tp> __t, _Compare __comp)

2763

2764

    typedef typename initializer_list<_Tp>::const_iterator _Iter;

2765

    _Iter __first = __t.begin();

2766

    _Iter __last  = __t.end();

2767

    std::pair<_Tp, _Tp> __result(*__first, *__first);

2768

2769

    ++__first;

2770

    if (__t.size() % 2 == 0)

2771

2772

        if (__comp(*__first,  __result.first))

2773

            __result.first  = *__first;

2774

        else

2775

            __result.second = *__first;

2776

        ++__first;

2777

2778

2779

    while (__first != __last)

2780

2781

        _Tp __prev = *__first++;

2782

        if (__comp(*__first, __prev)) {

2783

            if ( __comp(*__first, __result.first)) __result.first  = *__first;

2784

            if (!__comp(__prev, __result.second))  __result.second = __prev;

2785

2786

        else {

2787

            if ( __comp(__prev, __result.first))    __result.first  = __prev;

2788

            if (!__comp(*__first, __result.second)) __result.second = *__first;

2789

2790

2791

        __first++;

2792

2793

    return __result;

2794

2795

2796

template<class _Tp>

2797

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

2798

pair<_Tp, _Tp>

2799

minmax(initializer_list<_Tp> __t)

2800

2801

    return _VSTD::minmax(__t, __less<_Tp>());

2802

2803

2804

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

2805

2806

// random_shuffle

2807

2808

// __independent_bits_engine

2809

2810

template <unsigned long long _Xp, size_t _Rp>

2811

struct __log2_imp

2812

2813

    static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp

2814

                                           : __log2_imp<_Xp, _Rp - 1>::value;

2815

};

2816

2817

template <unsigned long long _Xp>

2818

struct __log2_imp<_Xp, 0>

2819

2820

    static const size_t value = 0;

2821

};

2822

2823

template <size_t _Rp>

2824

struct __log2_imp<0, _Rp>

2825

2826

    static const size_t value = _Rp + 1;

2827

};

2828

2829

template <class _UI, _UI _Xp>

2830

struct __log2

2831

2832

    static const size_t value = __log2_imp<_Xp,

2833

                                         sizeof(_UI) * __CHAR_BIT__ - 1>::value;

2834

};

2835

2836

template<class _Engine, class _UIntType>

2837

class __independent_bits_engine

2838

2839

public:

2840

    // types

2841

    typedef _UIntType result_type;

2842

2843

private:

2844

    typedef typename _Engine::result_type _Engine_result_type;

2845

    typedef typename conditional

2846

2847

            sizeof(_Engine_result_type) <= sizeof(result_type),

2848

                result_type,

2849

                _Engine_result_type

2850

        >::type _Working_result_type;

2851

2852

    _Engine& __e_;

2853

    size_t __w_;

2854

    size_t __w0_;

2855

    size_t __n_;

2856

    size_t __n0_;

2857

    _Working_result_type __y0_;

2858

    _Working_result_type __y1_;

2859

    _Engine_result_type __mask0_;

2860

    _Engine_result_type __mask1_;

2861

2862

#ifdef _LIBCPP_HAS_NO_CONSTEXPR

2863

    static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min

2864

                                          + _Working_result_type(1);

2865

#else

2866

    static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()

2867

                                                      + _Working_result_type(1);

2868

#endif

2869

    static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;

2870

    static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;

2871

    static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;

2872

2873

public:

2874

    // constructors and seeding functions

2875

    __independent_bits_engine(_Engine& __e, size_t __w);

2876

2877

    // generating functions

2878

    result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}

2879

2880

private:

2881

    result_type __eval(false_type);

2882

    result_type __eval(true_type);

2883

};

2884

2885

template<class _Engine, class _UIntType>

2886

__independent_bits_engine<_Engine, _UIntType>

2887

    ::__independent_bits_engine(_Engine& __e, size_t __w)

2888

        : __e_(__e),

2889

          __w_(__w)

2890

2891

    __n_ = __w_ / __m + (__w_ % __m != 0);

2892

    __w0_ = __w_ / __n_;

2893

    if (_Rp == 0)

2894

        __y0_ = _Rp;

2895

    else if (__w0_ < _WDt)

2896

        __y0_ = (_Rp >> __w0_) << __w0_;

2897

    else

2898

        __y0_ = 0;

2899

    if (_Rp - __y0_ > __y0_ / __n_)

2900

2901

        ++__n_;

2902

        __w0_ = __w_ / __n_;

2903

        if (__w0_ < _WDt)

2904

            __y0_ = (_Rp >> __w0_) << __w0_;

2905

        else

2906

            __y0_ = 0;

2907

2908

    __n0_ = __n_ - __w_ % __n_;

2909

    if (__w0_ < _WDt - 1)

2910

        __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);

2911

    else

2912

        __y1_ = 0;

2913

    __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :

2914

                          _Engine_result_type(0);

2915

    __mask1_ = __w0_ < _EDt - 1 ?

2916

                               _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :

2917

                               _Engine_result_type(~0);

2918

2919

2920

template<class _Engine, class _UIntType>

2921

inline

2922

_UIntType

2923

__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)

2924

2925

    return static_cast<result_type>(__e_() & __mask0_);

2926

2927

2928

template<class _Engine, class _UIntType>

2929

_UIntType

2930

__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)

2931

2932

    result_type _Sp = 0;

2933

    for (size_t __k = 0; __k < __n0_; ++__k)

2934

2935

        _Engine_result_type __u;

2936

do

2937

2938

            __u = __e_() - _Engine::min();

2939

        } while (__u >= __y0_);

2940

        if (__w0_ < _WDt)

2941

            _Sp <<= __w0_;

2942

        else

2943

            _Sp = 0;

2944

        _Sp += __u & __mask0_;

2945

2946

    for (size_t __k = __n0_; __k < __n_; ++__k)

2947

2948

        _Engine_result_type __u;

2949

do

2950

2951

            __u = __e_() - _Engine::min();

2952

        } while (__u >= __y1_);

2953

        if (__w0_ < _WDt - 1)

2954

            _Sp <<= __w0_ + 1;

2955

        else

2956

            _Sp = 0;

2957

        _Sp += __u & __mask1_;

2958

2959

    return _Sp;

2960

2961

2962

// uniform_int_distribution

2963

2964

template<class _IntType = int>

2965

class uniform_int_distribution

2966

2967

public:

2968

    // types

2969

    typedef _IntType result_type;

2970

2971

    class param_type

2972

2973

        result_type __a_;

2974

        result_type __b_;

2975

    public:

2976

        typedef uniform_int_distribution distribution_type;

2977

2978

        explicit param_type(result_type __a = 0,

2979

                            result_type __b = numeric_limits<result_type>::max())

2980

            : __a_(__a), __b_(__b) {}

2981

2982

        result_type a() const {return __a_;}

2983

        result_type b() const {return __b_;}

2984

2985

        friend bool operator==(const param_type& __x, const param_type& __y)

2986

            {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}

2987

        friend bool operator!=(const param_type& __x, const param_type& __y)

2988

            {return !(__x == __y);}

2989

};

2990

2991

private:

2992

    param_type __p_;

2993

2994

public:

2995

    // constructors and reset functions

2996

    explicit uniform_int_distribution(result_type __a = 0,

2997

                                      result_type __b = numeric_limits<result_type>::max())

2998

        : __p_(param_type(__a, __b)) {}

2999

    explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}

3000

    void reset() {}

3001

3002

    // generating functions

3003

    template<class _URNG> result_type operator()(_URNG& __g)

3004

        {return (*this)(__g, __p_);}

3005

    template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);

3006

3007

    // property functions

3008

    result_type a() const {return __p_.a();}

3009

    result_type b() const {return __p_.b();}

3010

3011

    param_type param() const {return __p_;}

3012

    void param(const param_type& __p) {__p_ = __p;}

3013

3014

    result_type min() const {return a();}

3015

    result_type max() const {return b();}

3016

3017

    friend bool operator==(const uniform_int_distribution& __x,

3018

                           const uniform_int_distribution& __y)

3019

        {return __x.__p_ == __y.__p_;}

3020

    friend bool operator!=(const uniform_int_distribution& __x,

3021

                           const uniform_int_distribution& __y)

3022

            {return !(__x == __y);}

3023

};

3024

3025

template<class _IntType>

3026

template<class _URNG>

3027

typename uniform_int_distribution<_IntType>::result_type

3028

uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)

3029

3030

    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),

3031

                                            uint32_t, uint64_t>::type _UIntType;

3032

    const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);

3033

    if (_Rp == 1)

3034

        return __p.a();

3035

    const size_t _Dt = numeric_limits<_UIntType>::digits;

3036

    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;

3037

    if (_Rp == 0)

3038

        return static_cast<result_type>(_Eng(__g, _Dt)());

3039

    size_t __w = _Dt - __clz(_Rp) - 1;

3040

    if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)

3041

        ++__w;

3042

    _Eng __e(__g, __w);

3043

    _UIntType __u;

3044

do

3045

3046

        __u = __e();

3047

    } while (__u >= _Rp);

3048

    return static_cast<result_type>(__u + __p.a());

3049

3050

3051

class _LIBCPP_TYPE_VIS __rs_default;

3052

3053

_LIBCPP_FUNC_VIS __rs_default __rs_get();

3054

3055

class _LIBCPP_TYPE_VIS __rs_default

3056

3057

    static unsigned __c_;

3058

3059

    __rs_default();

3060

public:

3061

    typedef uint_fast32_t result_type;

3062

3063

    static const result_type _Min = 0;

3064

    static const result_type _Max = 0xFFFFFFFF;

3065

3066

    __rs_default(const __rs_default&);

3067

    ~__rs_default();

3068

3069

    result_type operator()();

3070

3071

    static _LIBCPP_CONSTEXPR result_type min() {return _Min;}

3072

    static _LIBCPP_CONSTEXPR result_type max() {return _Max;}

3073

3074

    friend _LIBCPP_FUNC_VIS __rs_default __rs_get();

3075

};

3076

3077

_LIBCPP_FUNC_VIS __rs_default __rs_get();

3078

3079

template <class _RandomAccessIterator>

3080

void

3081

random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)

3082

3083

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

3084

    typedef uniform_int_distribution<ptrdiff_t> _Dp;

3085

    typedef typename _Dp::param_type _Pp;

3086

    difference_type __d = __last - __first;

3087

    if (__d > 1)

3088

3089

        _Dp __uid;

3090

        __rs_default __g = __rs_get();

3091

        for (--__last, --__d; __first < __last; ++__first, --__d)

3092

3093

            difference_type __i = __uid(__g, _Pp(0, __d));

3094

            if (__i != difference_type(0))

3095

                swap(*__first, *(__first + __i));

template <class _RandomAccessIterator, class _RandomNumberGenerator>

3101

void

3102

random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,

3103

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

3104

               _RandomNumberGenerator&& __rand)

3105

#else

3106

               _RandomNumberGenerator& __rand)

3107

#endif

3108

3109

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

3110

    difference_type __d = __last - __first;

3111

    if (__d > 1)

3112

3113

        for (--__last; __first < __last; ++__first, --__d)

3114

3115

            difference_type __i = __rand(__d);

3116

            swap(*__first, *(__first + __i));

template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>

3122

    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,

3123

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

3124

                 _UniformRandomNumberGenerator&& __g)

3125

#else

3126

                 _UniformRandomNumberGenerator& __g)

3127

#endif

3128

3129

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

3130

    typedef uniform_int_distribution<ptrdiff_t> _Dp;

3131

    typedef typename _Dp::param_type _Pp;

3132

    difference_type __d = __last - __first;

3133

    if (__d > 1)

3134

3135

        _Dp __uid;

3136

        for (--__last, --__d; __first < __last; ++__first, --__d)

3137

3138

            difference_type __i = __uid(__g, _Pp(0, __d));

3139

            if (__i != difference_type(0))

3140

                swap(*__first, *(__first + __i));

template <class _InputIterator, class _Predicate>

3146

bool

3147

is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)

3148

3149

    for (; __first != __last; ++__first)

3150

        if (!__pred(*__first))

3151

            break;

3152

    if ( __first == __last )

3153

        return true;

3154

    ++__first;

3155

    for (; __first != __last; ++__first)

3156

        if (__pred(*__first))

3157

            return false;

3158

    return true;

3159

3160

3161

// partition

3162

3163

template <class _Predicate, class _ForwardIterator>

3164

_ForwardIterator

3165

__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)

3166

3167

    while (true)

3168

3169

        if (__first == __last)

3170

            return __first;

3171

        if (!__pred(*__first))

3172

            break;

3173

        ++__first;

3174

3175

    for (_ForwardIterator __p = __first; ++__p != __last;)

3176

3177

        if (__pred(*__p))

3178

3179

            swap(*__first, *__p);

3180

            ++__first;

3181

3182

3183

    return __first;

3184

3185

3186

template <class _Predicate, class _BidirectionalIterator>

3187

_BidirectionalIterator

3188

__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,

3189

            bidirectional_iterator_tag)

3190

3191

    while (true)

3192

3193

        while (true)

3194

3195

            if (__first == __last)

3196

                return __first;

3197

            if (!__pred(*__first))

3198

                break;

3199

            ++__first;

3200

3201

do

3202

3203

            if (__first == --__last)

3204

                return __first;

3205

        } while (!__pred(*__last));

3206

        swap(*__first, *__last);

3207

        ++__first;

template <class _ForwardIterator, class _Predicate>

3212

inline _LIBCPP_INLINE_VISIBILITY

3213

_ForwardIterator

3214

partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)

3215

3216

    return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>

3217

                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());

3218

3219

3220

// partition_copy

3221

3222

template <class _InputIterator, class _OutputIterator1,

3223

          class _OutputIterator2, class _Predicate>

3224

pair<_OutputIterator1, _OutputIterator2>

3225

partition_copy(_InputIterator __first, _InputIterator __last,

3226

               _OutputIterator1 __out_true, _OutputIterator2 __out_false,

3227

               _Predicate __pred)

3228

3229

    for (; __first != __last; ++__first)

3230

3231

        if (__pred(*__first))

3232

3233

            *__out_true = *__first;

3234

            ++__out_true;

3235

3236

        else

3237

3238

            *__out_false = *__first;

3239

            ++__out_false;

3240

3241

3242

    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);

3243

3244

3245

// partition_point

3246

3247

template<class _ForwardIterator, class _Predicate>

3248

_ForwardIterator

3249

partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)

3250

3251

    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;

3252

    difference_type __len = _VSTD::distance(__first, __last);

3253

    while (__len != 0)

3254

3255

        difference_type __l2 = __len / 2;

3256

        _ForwardIterator __m = __first;

3257

        _VSTD::advance(__m, __l2);

3258

        if (__pred(*__m))

3259

3260

            __first = ++__m;

3261

            __len -= __l2 + 1;

3262

3263

        else

3264

            __len = __l2;

3265

3266

    return __first;

3267

3268

3269

// stable_partition

3270

3271

template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>

3272

_ForwardIterator

3273

__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,

3274

                   _Distance __len, _Pair __p, forward_iterator_tag __fit)

3275

3276

    // *__first is known to be false

3277

    // __len >= 1

3278

    if (__len == 1)

3279

        return __first;

3280

    if (__len == 2)

3281

3282

        _ForwardIterator __m = __first;

3283

        if (__pred(*++__m))

3284

3285

            swap(*__first, *__m);

3286

            return __m;

3287

3288

        return __first;

3289

3290

    if (__len <= __p.second)

3291

    {   // The buffer is big enough to use

3292

        typedef typename iterator_traits<_ForwardIterator>::value_type value_type;

3293

        __destruct_n __d(0);

3294

        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);

3295

        // Move the falses into the temporary buffer, and the trues to the front of the line

3296

        // Update __first to always point to the end of the trues

3297

        value_type* __t = __p.first;

3298

        ::new(__t) value_type(_VSTD::move(*__first));

3299

        __d.__incr((value_type*)0);

3300

        ++__t;

3301

        _ForwardIterator __i = __first;

3302

        while (++__i != __last)

3303

3304

            if (__pred(*__i))

3305

3306

                *__first = _VSTD::move(*__i);

3307

                ++__first;

3308

3309

            else

3310

3311

                ::new(__t) value_type(_VSTD::move(*__i));

3312

                __d.__incr((value_type*)0);

3313

                ++__t;

3314

3315

3316

        // All trues now at start of range, all falses in buffer

3317

        // Move falses back into range, but don't mess up __first which points to first false

3318

        __i = __first;

3319

        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)

3320

            *__i = _VSTD::move(*__t2);

3321

        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer

3322

        return __first;

3323

3324

    // Else not enough buffer, do in place

3325

    // __len >= 3

3326

    _ForwardIterator __m = __first;

3327

    _Distance __len2 = __len / 2;  // __len2 >= 2

3328

    _VSTD::advance(__m, __len2);

3329

    // recurse on [__first, __m), *__first know to be false

3330

    // F?????????????????

3331

    // f       m         l

3332

    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;

3333

    _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);

3334

    // TTTFFFFF??????????

3335

    // f  ff   m         l

3336

    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true

3337

    _ForwardIterator __m1 = __m;

3338

    _ForwardIterator __second_false = __last;

3339

    _Distance __len_half = __len - __len2;

3340

    while (__pred(*__m1))

3341

3342

        if (++__m1 == __last)

3343

            goto __second_half_done;

3344

        --__len_half;

3345

3346

    // TTTFFFFFTTTF??????

3347

    // f  ff   m  m1     l

3348

    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);

3349

__second_half_done:

3350

    // TTTFFFFFTTTTTFFFFF

3351

    // f  ff   m    sf   l

3352

    return _VSTD::rotate(__first_false, __m, __second_false);

3353

    // TTTTTTTTFFFFFFFFFF

3354

    //         |

3355

3356

3357

struct __return_temporary_buffer

3358

3359

    template <class _Tp>

3360

    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}

3361

};

3362

3363

template <class _Predicate, class _ForwardIterator>

3364

_ForwardIterator

3365

__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,

3366

                   forward_iterator_tag)

3367

3368

    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment

3369

    // Either prove all true and return __first or point to first false

3370

    while (true)

3371

3372

        if (__first == __last)

3373

            return __first;

3374

        if (!__pred(*__first))

3375

            break;

3376

        ++__first;

3377

3378

    // We now have a reduced range [__first, __last)

3379

    // *__first is known to be false

3380

    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;

3381

    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;

3382

    difference_type __len = _VSTD::distance(__first, __last);

3383

    pair<value_type*, ptrdiff_t> __p(0, 0);

3384

    unique_ptr<value_type, __return_temporary_buffer> __h;

3385

    if (__len >= __alloc_limit)

3386

3387

        __p = _VSTD::get_temporary_buffer<value_type>(__len);

3388

        __h.reset(__p.first);

3389

3390

    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>

3391

                             (__first, __last, __pred, __len, __p, forward_iterator_tag());

3392

3393

3394

template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>

3395

_BidirectionalIterator

3396

__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,

3397

                   _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)

3398

3399

    // *__first is known to be false

3400

    // *__last is known to be true

3401

    // __len >= 2

3402

    if (__len == 2)

3403

3404

        swap(*__first, *__last);

3405

        return __last;

3406

3407

    if (__len == 3)

3408

3409

        _BidirectionalIterator __m = __first;

3410

        if (__pred(*++__m))

3411

3412

            swap(*__first, *__m);

3413

            swap(*__m, *__last);

3414

            return __last;

3415

3416

        swap(*__m, *__last);

3417

        swap(*__first, *__m);

3418

        return __m;

3419

3420

    if (__len <= __p.second)

3421

    {   // The buffer is big enough to use

3422

        typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;

3423

        __destruct_n __d(0);

3424

        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);

3425

        // Move the falses into the temporary buffer, and the trues to the front of the line

3426

        // Update __first to always point to the end of the trues

3427

        value_type* __t = __p.first;

3428

        ::new(__t) value_type(_VSTD::move(*__first));

3429

        __d.__incr((value_type*)0);

3430

        ++__t;

3431

        _BidirectionalIterator __i = __first;

3432

        while (++__i != __last)

3433

3434

            if (__pred(*__i))

3435

3436

                *__first = _VSTD::move(*__i);

3437

                ++__first;

3438

3439

            else

3440

3441

                ::new(__t) value_type(_VSTD::move(*__i));

3442

                __d.__incr((value_type*)0);

3443

                ++__t;

3444

3445

3446

        // move *__last, known to be true

3447

        *__first = _VSTD::move(*__i);

3448

        __i = ++__first;

3449

        // All trues now at start of range, all falses in buffer

3450

        // Move falses back into range, but don't mess up __first which points to first false

3451

        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)

3452

            *__i = _VSTD::move(*__t2);

3453

        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer

3454

        return __first;

3455

3456

    // Else not enough buffer, do in place

3457

    // __len >= 4

3458

    _BidirectionalIterator __m = __first;

3459

    _Distance __len2 = __len / 2;  // __len2 >= 2

3460

    _VSTD::advance(__m, __len2);

3461

    // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false

3462

    // F????????????????T

3463

    // f       m        l

3464

    _BidirectionalIterator __m1 = __m;

3465

    _BidirectionalIterator __first_false = __first;

3466

    _Distance __len_half = __len2;

3467

    while (!__pred(*--__m1))

3468

3469

        if (__m1 == __first)

3470

            goto __first_half_done;

3471

        --__len_half;

3472

3473

    // F???TFFF?????????T

3474

    // f   m1  m        l

3475

    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;

3476

    __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);

3477

__first_half_done:

3478

    // TTTFFFFF?????????T

3479

    // f  ff   m        l

3480

    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true

3481

    __m1 = __m;

3482

    _BidirectionalIterator __second_false = __last;

3483

    ++__second_false;

3484

    __len_half = __len - __len2;

3485

    while (__pred(*__m1))

3486

3487

        if (++__m1 == __last)

3488

            goto __second_half_done;

3489

        --__len_half;

3490

3491

    // TTTFFFFFTTTF?????T

3492

    // f  ff   m  m1    l

3493

    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);

3494

__second_half_done:

3495

    // TTTFFFFFTTTTTFFFFF

3496

    // f  ff   m    sf  l

3497

    return _VSTD::rotate(__first_false, __m, __second_false);

3498

    // TTTTTTTTFFFFFFFFFF

3499

    //         |

3500

3501

3502

template <class _Predicate, class _BidirectionalIterator>

3503

_BidirectionalIterator

3504

__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,

3505

                   bidirectional_iterator_tag)

3506

3507

    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;

3508

    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;

3509

    const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment

3510

    // Either prove all true and return __first or point to first false

3511

    while (true)

3512

3513

        if (__first == __last)

3514

            return __first;

3515

        if (!__pred(*__first))

3516

            break;

3517

        ++__first;

3518

3519

    // __first points to first false, everything prior to __first is already set.

3520

    // Either prove [__first, __last) is all false and return __first, or point __last to last true

3521

do

3522

3523

        if (__first == --__last)

3524

            return __first;

3525

    } while (!__pred(*__last));

3526

    // We now have a reduced range [__first, __last]

3527

    // *__first is known to be false

3528

    // *__last is known to be true

3529

    // __len >= 2

3530

    difference_type __len = _VSTD::distance(__first, __last) + 1;

3531

    pair<value_type*, ptrdiff_t> __p(0, 0);

3532

    unique_ptr<value_type, __return_temporary_buffer> __h;

3533

    if (__len >= __alloc_limit)

3534

3535

        __p = _VSTD::get_temporary_buffer<value_type>(__len);

3536

        __h.reset(__p.first);

3537

3538

    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>

3539

                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());

3540

3541

3542

template <class _ForwardIterator, class _Predicate>

3543

inline _LIBCPP_INLINE_VISIBILITY

3544

_ForwardIterator

3545

stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)

3546

3547

    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>

3548

                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());

3549

3550

3551

// is_sorted_until

3552

3553

template <class _ForwardIterator, class _Compare>

3554

_ForwardIterator

3555

is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

3556

3557

    if (__first != __last)

3558

3559

        _ForwardIterator __i = __first;

3560

        while (++__i != __last)

3561

3562

            if (__comp(*__i, *__first))

3563

                return __i;

3564

            __first = __i;

3565

3566

3567

    return __last;

3568

3569

3570

template<class _ForwardIterator>

3571

inline _LIBCPP_INLINE_VISIBILITY

3572

_ForwardIterator

3573

is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)

3574

3575

    return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());

3576

3577

3578

// is_sorted

3579

3580

template <class _ForwardIterator, class _Compare>

3581

inline _LIBCPP_INLINE_VISIBILITY

3582

bool

3583

is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)

3584

3585

    return _VSTD::is_sorted_until(__first, __last, __comp) == __last;

3586

3587

3588

template<class _ForwardIterator>

3589

inline _LIBCPP_INLINE_VISIBILITY

3590

bool

3591

is_sorted(_ForwardIterator __first, _ForwardIterator __last)

3592

3593

    return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());

3594

3595

3596

// sort

3597

3598

// stable, 2-3 compares, 0-2 swaps

3599

3600

template <class _Compare, class _ForwardIterator>

3601

unsigned

3602

__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)

3603

3604

    unsigned __r = 0;

3605

    if (!__c(*__y, *__x))          // if x <= y

3606

3607

        if (!__c(*__z, *__y))      // if y <= z

3608

            return __r;            // x <= y && y <= z

3609

                                   // x <= y && y > z

3610

        swap(*__y, *__z);          // x <= z && y < z

3611

        __r = 1;

3612

        if (__c(*__y, *__x))       // if x > y

3613

3614

            swap(*__x, *__y);      // x < y && y <= z

3615

            __r = 2;

3616

3617

        return __r;                // x <= y && y < z

3618

3619

    if (__c(*__z, *__y))           // x > y, if y > z

3620

3621

        swap(*__x, *__z);          // x < y && y < z

3622

        __r = 1;

3623

        return __r;

3624

3625

    swap(*__x, *__y);              // x > y && y <= z

3626

    __r = 1;                       // x < y && x <= z

3627

    if (__c(*__z, *__y))           // if y > z

3628

3629

        swap(*__y, *__z);          // x <= y && y < z

3630

        __r = 2;

3631

3632

    return __r;

3633

}                                  // x <= y && y <= z

3634

3635

// stable, 3-6 compares, 0-5 swaps

3636

3637

template <class _Compare, class _ForwardIterator>

3638

unsigned

3639

__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,

3640

            _ForwardIterator __x4, _Compare __c)

3641

3642

    unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);

3643

    if (__c(*__x4, *__x3))

3644

3645

        swap(*__x3, *__x4);

3646

        ++__r;

3647

        if (__c(*__x3, *__x2))

3648

3649

            swap(*__x2, *__x3);

3650

            ++__r;

3651

            if (__c(*__x2, *__x1))

3652

3653

                swap(*__x1, *__x2);

3654

                ++__r;

    return __r;

3659

3660

3661

// stable, 4-10 compares, 0-9 swaps

3662

3663

template <class _Compare, class _ForwardIterator>

3664

unsigned

3665

__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,

3666

            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)

3667

3668

    unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);

3669

    if (__c(*__x5, *__x4))

3670

3671

        swap(*__x4, *__x5);

3672

        ++__r;

3673

        if (__c(*__x4, *__x3))

3674

3675

            swap(*__x3, *__x4);

3676

            ++__r;

3677

            if (__c(*__x3, *__x2))

3678

3679

                swap(*__x2, *__x3);

3680

                ++__r;

3681

                if (__c(*__x2, *__x1))

3682

3683

                    swap(*__x1, *__x2);

3684

                    ++__r;

    return __r;

3690

3691

3692

// Assumes size > 0

3693

template <class _Compare, class _BirdirectionalIterator>

3694

void

3695

__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)

3696

3697

    _BirdirectionalIterator __lm1 = __last;

3698

    for (--__lm1; __first != __lm1; ++__first)

3699

3700

        _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,

3701

                                                        typename add_lvalue_reference<_Compare>::type>

3702

                                                       (__first, __last, __comp);

3703

        if (__i != __first)

3704

            swap(*__first, *__i);

template <class _Compare, class _BirdirectionalIterator>

3709

void

3710

__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)

3711

3712

    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;

3713

    if (__first != __last)

3714

3715

        _BirdirectionalIterator __i = __first;

3716

        for (++__i; __i != __last; ++__i)

3717

3718

            _BirdirectionalIterator __j = __i;

3719

            value_type __t(_VSTD::move(*__j));

3720

            for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)

3721

                *__j = _VSTD::move(*__k);

3722

            *__j = _VSTD::move(__t);

template <class _Compare, class _RandomAccessIterator>

3728

void

3729

__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

3730

3731

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

3732

    _RandomAccessIterator __j = __first+2;

3733

    __sort3<_Compare>(__first, __first+1, __j, __comp);

3734

    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)

3735

3736

        if (__comp(*__i, *__j))

3737

3738

            value_type __t(_VSTD::move(*__i));

3739

            _RandomAccessIterator __k = __j;

3740

            __j = __i;

3741

do

3742

3743

                *__j = _VSTD::move(*__k);

3744

                __j = __k;

3745

            } while (__j != __first && __comp(__t, *--__k));

3746

            *__j = _VSTD::move(__t);

3747

3748

        __j = __i;

template <class _Compare, class _RandomAccessIterator>

3753

bool

3754

__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

3755

3756

    switch (__last - __first)

3757

3758

    case 0:

3759

    case 1:

3760

        return true;

3761

    case 2:

3762

        if (__comp(*--__last, *__first))

3763

            swap(*__first, *__last);

3764

        return true;

3765

    case 3:

3766

        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);

3767

        return true;

3768

    case 4:

3769

        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);

3770

        return true;

3771

    case 5:

3772

        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);

3773

        return true;

3774

3775

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

3776

    _RandomAccessIterator __j = __first+2;

3777

    __sort3<_Compare>(__first, __first+1, __j, __comp);

3778

    const unsigned __limit = 8;

3779

    unsigned __count = 0;

3780

    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)

3781

3782

        if (__comp(*__i, *__j))

3783

3784

            value_type __t(_VSTD::move(*__i));

3785

            _RandomAccessIterator __k = __j;

3786

            __j = __i;

3787

do

3788

3789

                *__j = _VSTD::move(*__k);

3790

                __j = __k;

3791

            } while (__j != __first && __comp(__t, *--__k));

3792

            *__j = _VSTD::move(__t);

3793

            if (++__count == __limit)

3794

                return ++__i == __last;

3795

3796

        __j = __i;

3797

3798

    return true;

3799

3800

3801

template <class _Compare, class _BirdirectionalIterator>

3802

void

3803

__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,

3804

                      typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)

3805

3806

    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;

3807

    if (__first1 != __last1)

3808

3809

        __destruct_n __d(0);

3810

        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);

3811

        value_type* __last2 = __first2;

3812

        ::new(__last2) value_type(_VSTD::move(*__first1));

3813

        __d.__incr((value_type*)0);

3814

        for (++__last2; ++__first1 != __last1; ++__last2)

3815

3816

            value_type* __j2 = __last2;

3817

            value_type* __i2 = __j2;

3818

            if (__comp(*__first1, *--__i2))

3819

3820

                ::new(__j2) value_type(_VSTD::move(*__i2));

3821

                __d.__incr((value_type*)0);

3822

                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)

3823

                    *__j2 = _VSTD::move(*__i2);

3824

                *__j2 = _VSTD::move(*__first1);

3825

3826

            else

3827

3828

                ::new(__j2) value_type(_VSTD::move(*__first1));

3829

                __d.__incr((value_type*)0);

3830

3831

3832

        __h.release();

template <class _Compare, class _RandomAccessIterator>

3837

void

3838

__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

3839

3840

    // _Compare is known to be a reference type

3841

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

3842

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

3843

    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&

3844

                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;

3845

    while (true)

3846

3847

    __restart:

3848

        difference_type __len = __last - __first;

3849

        switch (__len)

3850

3851

        case 0:

3852

        case 1:

3853

            return;

3854

        case 2:

3855

            if (__comp(*--__last, *__first))

3856

                swap(*__first, *__last);

3857

            return;

3858

        case 3:

3859

            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);

3860

            return;

3861

        case 4:

3862

            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);

3863

            return;

3864

        case 5:

3865

            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);

3866

            return;

3867

3868

        if (__len <= __limit)

3869

3870

            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);

3871

            return;

3872

3873

        // __len > 5

3874

        _RandomAccessIterator __m = __first;

3875

        _RandomAccessIterator __lm1 = __last;

3876

        --__lm1;

3877

        unsigned __n_swaps;

3878

3879

        difference_type __delta;

3880

        if (__len >= 1000)

3881

3882

            __delta = __len/2;

3883

            __m += __delta;

3884

            __delta /= 2;

3885

            __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);

3886

3887

        else

3888

3889

            __delta = __len/2;

3890

            __m += __delta;

3891

            __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);

3892

3893

3894

        // *__m is median

3895

        // partition [__first, __m) < *__m and *__m <= [__m, __last)

3896

        // (this inhibits tossing elements equivalent to __m around unnecessarily)

3897

        _RandomAccessIterator __i = __first;

3898

        _RandomAccessIterator __j = __lm1;

3899

        // j points beyond range to be tested, *__m is known to be <= *__lm1

3900

        // The search going up is known to be guarded but the search coming down isn't.

3901

        // Prime the downward search with a guard.

3902

        if (!__comp(*__i, *__m))  // if *__first == *__m

3903

3904

            // *__first == *__m, *__first doesn't go in first part

3905

            // manually guard downward moving __j against __i

3906

            while (true)

3907

3908

                if (__i == --__j)

3909

3910

                    // *__first == *__m, *__m <= all other elements

3911

                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)

3912

                    ++__i;  // __first + 1

3913

                    __j = __last;

3914

                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)

3915

3916

                        while (true)

3917

3918

                            if (__i == __j)

3919

                                return;  // [__first, __last) all equivalent elements

3920

                            if (__comp(*__first, *__i))

3921

3922

                                swap(*__i, *__j);

3923

                                ++__n_swaps;

3924

                                ++__i;

3925

                                break;

3926

3927

                            ++__i;

3928

3929

3930

                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1

3931

                    if (__i == __j)

3932

                        return;

3933

                    while (true)

3934

3935

                        while (!__comp(*__first, *__i))

3936

                            ++__i;

3937

                        while (__comp(*__first, *--__j))

3938

3939

                        if (__i >= __j)

3940

                            break;

3941

                        swap(*__i, *__j);

3942

                        ++__n_swaps;

3943

                        ++__i;

3944

3945

                    // [__first, __i) == *__first and *__first < [__i, __last)

3946

                    // The first part is sorted, sort the secod part

3947

                    // _VSTD::__sort<_Compare>(__i, __last, __comp);

3948

                    __first = __i;

3949

                    goto __restart;

3950

3951

                if (__comp(*__j, *__m))

3952

3953

                    swap(*__i, *__j);

3954

                    ++__n_swaps;

3955

                    break;  // found guard for downward moving __j, now use unguarded partition

        // It is known that *__i < *__m

3960

        ++__i;

3961

        // j points beyond range to be tested, *__m is known to be <= *__lm1

3962

        // if not yet partitioned...

3963

        if (__i < __j)

3964

3965

            // known that *(__i - 1) < *__m

3966

            // known that __i <= __m

3967

            while (true)

3968

3969

                // __m still guards upward moving __i

3970

                while (__comp(*__i, *__m))

3971

                    ++__i;

3972

                // It is now known that a guard exists for downward moving __j

3973

                while (!__comp(*--__j, *__m))

3974

3975

                if (__i > __j)

3976

                    break;

3977

                swap(*__i, *__j);

3978

                ++__n_swaps;

3979

                // It is known that __m != __j

3980

                // If __m just moved, follow it

3981

                if (__m == __i)

3982

                    __m = __j;

3983

                ++__i;

3984

3985

3986

        // [__first, __i) < *__m and *__m <= [__i, __last)

3987

        if (__i != __m && __comp(*__m, *__i))

3988

3989

            swap(*__i, *__m);

3990

            ++__n_swaps;

3991

3992

        // [__first, __i) < *__i and *__i <= [__i+1, __last)

3993

        // If we were given a perfect partition, see if insertion sort is quick...

3994

        if (__n_swaps == 0)

3995

3996

            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);

3997

            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))

3998

3999

                if (__fs)

4000

                    return;

4001

                __last = __i;

4002

                continue;

4003

4004

            else

4005

4006

                if (__fs)

4007

4008

                    __first = ++__i;

4009

                    continue;

        // sort smaller range with recursive call and larger with tail recursion elimination

4014

        if (__i - __first < __last - __i)

4015

4016

            _VSTD::__sort<_Compare>(__first, __i, __comp);

4017

            // _VSTD::__sort<_Compare>(__i+1, __last, __comp);

4018

            __first = ++__i;

4019

4020

        else

4021

4022

            _VSTD::__sort<_Compare>(__i+1, __last, __comp);

4023

            // _VSTD::__sort<_Compare>(__first, __i, __comp);

4024

            __last = __i;

// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare

4030

template <class _RandomAccessIterator, class _Compare>

4031

inline _LIBCPP_INLINE_VISIBILITY

4032

void

4033

sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4034

4035

#ifdef _LIBCPP_DEBUG

4036

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4037

    __debug_less<_Compare> __c(__comp);

4038

    __sort<_Comp_ref>(__first, __last, __c);

4039

#else  // _LIBCPP_DEBUG

4040

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4041

    __sort<_Comp_ref>(__first, __last, __comp);

4042

#endif  // _LIBCPP_DEBUG

4043

4044

4045

template <class _RandomAccessIterator>

4046

inline _LIBCPP_INLINE_VISIBILITY

4047

void

4048

sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

4049

4050

    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4051

4052

4053

template <class _Tp>

4054

inline _LIBCPP_INLINE_VISIBILITY

4055

void

4056

sort(_Tp** __first, _Tp** __last)

4057

4058

    _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());

4059

4060

4061

template <class _Tp>

4062

inline _LIBCPP_INLINE_VISIBILITY

4063

void

4064

sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)

4065

4066

    _VSTD::sort(__first.base(), __last.base());

4067

4068

4069

template <class _Tp, class _Compare>

4070

inline _LIBCPP_INLINE_VISIBILITY

4071

void

4072

sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)

4073

4074

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4075

    _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);

4076

4077

4078

#ifdef _LIBCPP_MSVC

4079

#pragma warning( push )

4080

#pragma warning( disable: 4231)

4081

#endif // _LIBCPP_MSVC

4082

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))

4083

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))

4084

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))

4085

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))

4086

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))

4087

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))

4088

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))

4089

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))

4090

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))

4091

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))

4092

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))

4093

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))

4094

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))

4095

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))

4096

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))

4097

4098

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))

4099

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))

4100

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))

4101

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))

4102

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))

4103

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))

4104

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))

4105

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))

4106

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))

4107

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))

4108

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))

4109

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))

4110

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))

4111

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))

4112

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))

4113

4114

_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))

4115

#ifdef _LIBCPP_MSVC

4116

#pragma warning( pop )

4117

#endif  // _LIBCPP_MSVC

4118

4119

// lower_bound

4120

4121

template <class _Compare, class _ForwardIterator, class _Tp>

4122

_ForwardIterator

4123

__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4124

4125

    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;

4126

    difference_type __len = _VSTD::distance(__first, __last);

4127

    while (__len != 0)

4128

4129

        difference_type __l2 = __len / 2;

4130

        _ForwardIterator __m = __first;

4131

        _VSTD::advance(__m, __l2);

4132

        if (__comp(*__m, __value_))

4133

4134

            __first = ++__m;

4135

            __len -= __l2 + 1;

4136

4137

        else

4138

            __len = __l2;

4139

4140

    return __first;

4141

4142

4143

template <class _ForwardIterator, class _Tp, class _Compare>

4144

inline _LIBCPP_INLINE_VISIBILITY

4145

_ForwardIterator

4146

lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4147

4148

#ifdef _LIBCPP_DEBUG

4149

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4150

    __debug_less<_Compare> __c(__comp);

4151

    return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);

4152

#else  // _LIBCPP_DEBUG

4153

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4154

    return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);

4155

#endif  // _LIBCPP_DEBUG

4156

4157

4158

template <class _ForwardIterator, class _Tp>

4159

inline _LIBCPP_INLINE_VISIBILITY

4160

_ForwardIterator

4161

lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

4162

4163

    return _VSTD::lower_bound(__first, __last, __value_,

4164

                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());

4165

4166

4167

// upper_bound

4168

4169

template <class _Compare, class _ForwardIterator, class _Tp>

4170

_ForwardIterator

4171

__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4172

4173

    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;

4174

    difference_type __len = _VSTD::distance(__first, __last);

4175

    while (__len != 0)

4176

4177

        difference_type __l2 = __len / 2;

4178

        _ForwardIterator __m = __first;

4179

        _VSTD::advance(__m, __l2);

4180

        if (__comp(__value_, *__m))

4181

            __len = __l2;

4182

        else

4183

4184

            __first = ++__m;

4185

            __len -= __l2 + 1;

4186

4187

4188

    return __first;

4189

4190

4191

template <class _ForwardIterator, class _Tp, class _Compare>

4192

inline _LIBCPP_INLINE_VISIBILITY

4193

_ForwardIterator

4194

upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4195

4196

#ifdef _LIBCPP_DEBUG

4197

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4198

    __debug_less<_Compare> __c(__comp);

4199

    return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);

4200

#else  // _LIBCPP_DEBUG

4201

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4202

    return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);

4203

#endif  // _LIBCPP_DEBUG

4204

4205

4206

template <class _ForwardIterator, class _Tp>

4207

inline _LIBCPP_INLINE_VISIBILITY

4208

_ForwardIterator

4209

upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

4210

4211

    return _VSTD::upper_bound(__first, __last, __value_,

4212

                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());

4213

4214

4215

// equal_range

4216

4217

template <class _Compare, class _ForwardIterator, class _Tp>

4218

pair<_ForwardIterator, _ForwardIterator>

4219

__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4220

4221

    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;

4222

    difference_type __len = _VSTD::distance(__first, __last);

4223

    while (__len != 0)

4224

4225

        difference_type __l2 = __len / 2;

4226

        _ForwardIterator __m = __first;

4227

        _VSTD::advance(__m, __l2);

4228

        if (__comp(*__m, __value_))

4229

4230

            __first = ++__m;

4231

            __len -= __l2 + 1;

4232

4233

        else if (__comp(__value_, *__m))

4234

4235

            __last = __m;

4236

            __len = __l2;

4237

4238

        else

4239

4240

            _ForwardIterator __mp1 = __m;

4241

            return pair<_ForwardIterator, _ForwardIterator>

4242

4243

                      __lower_bound<_Compare>(__first, __m, __value_, __comp),

4244

                      __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)

4245

);

4246

4247

4248

    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);

4249

4250

4251

template <class _ForwardIterator, class _Tp, class _Compare>

4252

inline _LIBCPP_INLINE_VISIBILITY

4253

pair<_ForwardIterator, _ForwardIterator>

4254

equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4255

4256

#ifdef _LIBCPP_DEBUG

4257

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4258

    __debug_less<_Compare> __c(__comp);

4259

    return __equal_range<_Comp_ref>(__first, __last, __value_, __c);

4260

#else  // _LIBCPP_DEBUG

4261

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4262

    return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);

4263

#endif  // _LIBCPP_DEBUG

4264

4265

4266

template <class _ForwardIterator, class _Tp>

4267

inline _LIBCPP_INLINE_VISIBILITY

4268

pair<_ForwardIterator, _ForwardIterator>

4269

equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

4270

4271

    return _VSTD::equal_range(__first, __last, __value_,

4272

                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());

4273

4274

4275

// binary_search

4276

4277

template <class _Compare, class _ForwardIterator, class _Tp>

4278

inline _LIBCPP_INLINE_VISIBILITY

4279

bool

4280

__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4281

4282

    __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);

4283

    return __first != __last && !__comp(__value_, *__first);

4284

4285

4286

template <class _ForwardIterator, class _Tp, class _Compare>

4287

inline _LIBCPP_INLINE_VISIBILITY

4288

bool

4289

binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)

4290

4291

#ifdef _LIBCPP_DEBUG

4292

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4293

    __debug_less<_Compare> __c(__comp);

4294

    return __binary_search<_Comp_ref>(__first, __last, __value_, __c);

4295

#else  // _LIBCPP_DEBUG

4296

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4297

    return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);

4298

#endif  // _LIBCPP_DEBUG

4299

4300

4301

template <class _ForwardIterator, class _Tp>

4302

inline _LIBCPP_INLINE_VISIBILITY

4303

bool

4304

binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)

4305

4306

    return _VSTD::binary_search(__first, __last, __value_,

4307

                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());

4308

4309

4310

// merge

4311

4312

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

4313

_OutputIterator

4314

__merge(_InputIterator1 __first1, _InputIterator1 __last1,

4315

        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

4316

4317

    for (; __first1 != __last1; ++__result)

4318

4319

        if (__first2 == __last2)

4320

            return _VSTD::copy(__first1, __last1, __result);

4321

        if (__comp(*__first2, *__first1))

4322

4323

            *__result = *__first2;

4324

            ++__first2;

4325

4326

        else

4327

4328

            *__result = *__first1;

4329

            ++__first1;

4330

4331

4332

    return _VSTD::copy(__first2, __last2, __result);

4333

4334

4335

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>

4336

inline _LIBCPP_INLINE_VISIBILITY

4337

_OutputIterator

4338

merge(_InputIterator1 __first1, _InputIterator1 __last1,

4339

      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

4340

4341

#ifdef _LIBCPP_DEBUG

4342

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4343

    __debug_less<_Compare> __c(__comp);

4344

    return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);

4345

#else  // _LIBCPP_DEBUG

4346

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4347

    return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);

4348

#endif  // _LIBCPP_DEBUG

4349

4350

4351

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>

4352

inline _LIBCPP_INLINE_VISIBILITY

4353

_OutputIterator

4354

merge(_InputIterator1 __first1, _InputIterator1 __last1,

4355

      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)

4356

4357

    typedef typename iterator_traits<_InputIterator1>::value_type __v1;

4358

    typedef typename iterator_traits<_InputIterator2>::value_type __v2;

4359

    return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());

4360

4361

4362

// inplace_merge

4363

4364

template <class _Compare, class _InputIterator1, class _InputIterator2,

4365

          class _OutputIterator>

4366

void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,

4367

                          _InputIterator2 __first2, _InputIterator2 __last2,

4368

                          _OutputIterator __result, _Compare __comp)

4369

4370

    for (; __first1 != __last1; ++__result)

4371

4372

        if (__first2 == __last2)

4373

4374

            _VSTD::move(__first1, __last1, __result);

4375

            return;

4376

4377

4378

        if (__comp(*__first2, *__first1))

4379

4380

            *__result = _VSTD::move(*__first2);

4381

            ++__first2;

4382

4383

        else

4384

4385

            *__result = _VSTD::move(*__first1);

4386

            ++__first1;

4387

4388

4389

    // __first2 through __last2 are already in the right spot.

4390

4391

4392

template <class _Compare, class _BidirectionalIterator>

4393

void

4394

__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,

4395

                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,

4396

                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,

4397

                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)

4398

4399

    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;

4400

    __destruct_n __d(0);

4401

    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);

4402

    if (__len1 <= __len2)

4403

4404

        value_type* __p = __buff;

4405

        for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)

4406

            ::new(__p) value_type(_VSTD::move(*__i));

4407

        __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);

4408

4409

    else

4410

4411

        value_type* __p = __buff;

4412

        for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)

4413

            ::new(__p) value_type(_VSTD::move(*__i));

4414

        typedef reverse_iterator<_BidirectionalIterator> _RBi;

4415

        typedef reverse_iterator<value_type*> _Rv;

4416

        __half_inplace_merge(_Rv(__p), _Rv(__buff),

4417

                             _RBi(__middle), _RBi(__first),

4418

                             _RBi(__last), __negate<_Compare>(__comp));

template <class _Compare, class _BidirectionalIterator>

4423

void

4424

__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,

4425

                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,

4426

                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,

4427

                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)

4428

4429

    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;

4430

    while (true)

4431

4432

        // if __middle == __last, we're done

4433

        if (__len2 == 0)

4434

            return;

4435

        if (__len1 <= __buff_size || __len2 <= __buff_size)

4436

            return __buffered_inplace_merge<_Compare>

4437

                   (__first, __middle, __last, __comp, __len1, __len2, __buff);

4438

        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0

4439

        for (; true; ++__first, (void) --__len1)

4440

4441

            if (__len1 == 0)

4442

                return;

4443

            if (__comp(*__middle, *__first))

4444

                break;

4445

4446

        // __first < __middle < __last

4447

        // *__first > *__middle

4448

        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that

4449

        //     all elements in:

4450

        //         [__first, __m1)  <= [__middle, __m2)

4451

        //         [__middle, __m2) <  [__m1, __middle)

4452

        //         [__m1, __middle) <= [__m2, __last)

4453

        //     and __m1 or __m2 is in the middle of its range

4454

        _BidirectionalIterator __m1;  // "median" of [__first, __middle)

4455

        _BidirectionalIterator __m2;  // "median" of [__middle, __last)

4456

        difference_type __len11;      // distance(__first, __m1)

4457

        difference_type __len21;      // distance(__middle, __m2)

4458

        // binary search smaller range

4459

        if (__len1 < __len2)

4460

        {   // __len >= 1, __len2 >= 2

4461

            __len21 = __len2 / 2;

4462

            __m2 = __middle;

4463

            _VSTD::advance(__m2, __len21);

4464

            __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);

4465

            __len11 = _VSTD::distance(__first, __m1);

4466

4467

        else

4468

4469

            if (__len1 == 1)

4470

            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1

4471

                // It is known *__first > *__middle

4472

                swap(*__first, *__middle);

4473

                return;

4474

4475

            // __len1 >= 2, __len2 >= 1

4476

            __len11 = __len1 / 2;

4477

            __m1 = __first;

4478

            _VSTD::advance(__m1, __len11);

4479

            __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);

4480

            __len21 = _VSTD::distance(__middle, __m2);

4481

4482

        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)

4483

        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)

4484

        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)

4485

        // swap middle two partitions

4486

        __middle = _VSTD::rotate(__m1, __middle, __m2);

4487

        // __len12 and __len21 now have swapped meanings

4488

        // merge smaller range with recurisve call and larger with tail recursion elimination

4489

        if (__len11 + __len21 < __len12 + __len22)

4490

4491

            __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);

4492

//          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);

4493

            __first = __middle;

4494

            __middle = __m2;

4495

            __len1 = __len12;

4496

            __len2 = __len22;

4497

4498

        else

4499

4500

            __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);

4501

//          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);

4502

            __last = __middle;

4503

            __middle = __m1;

4504

            __len1 = __len11;

4505

            __len2 = __len21;

template <class _BidirectionalIterator, class _Compare>

4511

inline _LIBCPP_INLINE_VISIBILITY

4512

void

4513

inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,

4514

              _Compare __comp)

4515

4516

    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;

4517

    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;

4518

    difference_type __len1 = _VSTD::distance(__first, __middle);

4519

    difference_type __len2 = _VSTD::distance(__middle, __last);

4520

    difference_type __buf_size = _VSTD::min(__len1, __len2);

4521

    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);

4522

    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);

4523

4524

#ifdef _LIBCPP_DEBUG

4525

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4526

    __debug_less<_Compare> __c(__comp);

4527

    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,

4528

                                            __buf.first, __buf.second);

4529

#else  // _LIBCPP_DEBUG

4530

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4531

    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,

4532

                                            __buf.first, __buf.second);

4533

#endif  // _LIBCPP_DEBUG

4534

4535

4536

template <class _BidirectionalIterator>

4537

inline _LIBCPP_INLINE_VISIBILITY

4538

void

4539

inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)

4540

4541

    _VSTD::inplace_merge(__first, __middle, __last,

4542

                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());

4543

4544

4545

// stable_sort

4546

4547

template <class _Compare, class _InputIterator1, class _InputIterator2>

4548

void

4549

__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,

4550

        _InputIterator2 __first2, _InputIterator2 __last2,

4551

        typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)

4552

4553

    typedef typename iterator_traits<_InputIterator1>::value_type value_type;

4554

    __destruct_n __d(0);

4555

    unique_ptr<value_type, __destruct_n&> __h(__result, __d);

4556

    for (; true; ++__result)

4557

4558

        if (__first1 == __last1)

4559

4560

            for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))

4561

                ::new (__result) value_type(_VSTD::move(*__first2));

4562

            __h.release();

4563

            return;

4564

4565

        if (__first2 == __last2)

4566

4567

            for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))

4568

                ::new (__result) value_type(_VSTD::move(*__first1));

4569

            __h.release();

4570

            return;

4571

4572

        if (__comp(*__first2, *__first1))

4573

4574

            ::new (__result) value_type(_VSTD::move(*__first2));

4575

            __d.__incr((value_type*)0);

4576

            ++__first2;

4577

4578

        else

4579

4580

            ::new (__result) value_type(_VSTD::move(*__first1));

4581

            __d.__incr((value_type*)0);

4582

            ++__first1;

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

4588

void

4589

__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,

4590

        _InputIterator2 __first2, _InputIterator2 __last2,

4591

        _OutputIterator __result, _Compare __comp)

4592

4593

    for (; __first1 != __last1; ++__result)

4594

4595

        if (__first2 == __last2)

4596

4597

            for (; __first1 != __last1; ++__first1, ++__result)

4598

                *__result = _VSTD::move(*__first1);

4599

            return;

4600

4601

        if (__comp(*__first2, *__first1))

4602

4603

            *__result = _VSTD::move(*__first2);

4604

            ++__first2;

4605

4606

        else

4607

4608

            *__result = _VSTD::move(*__first1);

4609

            ++__first1;

4610

4611

4612

    for (; __first2 != __last2; ++__first2, ++__result)

4613

        *__result = _VSTD::move(*__first2);

4614

4615

4616

template <class _Compare, class _RandomAccessIterator>

4617

void

4618

__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,

4619

              typename iterator_traits<_RandomAccessIterator>::difference_type __len,

4620

              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);

4621

4622

template <class _Compare, class _RandomAccessIterator>

4623

void

4624

__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,

4625

                   typename iterator_traits<_RandomAccessIterator>::difference_type __len,

4626

                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)

4627

4628

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

4629

    switch (__len)

4630

4631

    case 0:

4632

        return;

4633

    case 1:

4634

        ::new(__first2) value_type(_VSTD::move(*__first1));

4635

        return;

4636

    case 2:

4637

       __destruct_n __d(0);

4638

        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);

4639

         if (__comp(*--__last1, *__first1))

4640

4641

            ::new(__first2) value_type(_VSTD::move(*__last1));

4642

            __d.__incr((value_type*)0);

4643

            ++__first2;

4644

            ::new(__first2) value_type(_VSTD::move(*__first1));

4645

4646

        else

4647

4648

            ::new(__first2) value_type(_VSTD::move(*__first1));

4649

            __d.__incr((value_type*)0);

4650

            ++__first2;

4651

            ::new(__first2) value_type(_VSTD::move(*__last1));

4652

4653

        __h2.release();

4654

        return;

4655

4656

    if (__len <= 8)

4657

4658

        __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);

4659

        return;

4660

4661

    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;

4662

    _RandomAccessIterator __m = __first1 + __l2;

4663

    __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);

4664

    __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);

4665

    __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);

4666

4667

4668

template <class _Tp>

4669

struct __stable_sort_switch

4670

4671

    static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;

4672

};

4673

4674

template <class _Compare, class _RandomAccessIterator>

4675

void

4676

__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,

4677

              typename iterator_traits<_RandomAccessIterator>::difference_type __len,

4678

              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)

4679

4680

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

4681

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

4682

    switch (__len)

4683

4684

    case 0:

4685

    case 1:

4686

        return;

4687

    case 2:

4688

        if (__comp(*--__last, *__first))

4689

            swap(*__first, *__last);

4690

        return;

4691

4692

    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))

4693

4694

        __insertion_sort<_Compare>(__first, __last, __comp);

4695

        return;

4696

4697

    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;

4698

    _RandomAccessIterator __m = __first + __l2;

4699

    if (__len <= __buff_size)

4700

4701

        __destruct_n __d(0);

4702

        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);

4703

        __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);

4704

        __d.__set(__l2, (value_type*)0);

4705

        __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);

4706

        __d.__set(__len, (value_type*)0);

4707

        __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);

4708

//         __merge<_Compare>(move_iterator<value_type*>(__buff),

4709

//                           move_iterator<value_type*>(__buff + __l2),

4710

//                           move_iterator<_RandomAccessIterator>(__buff + __l2),

4711

//                           move_iterator<_RandomAccessIterator>(__buff + __len),

4712

//                           __first, __comp);

4713

        return;

4714

4715

    __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);

4716

    __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);

4717

    __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);

4718

4719

4720

template <class _RandomAccessIterator, class _Compare>

4721

inline _LIBCPP_INLINE_VISIBILITY

4722

void

4723

stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4724

4725

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

4726

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

4727

    difference_type __len = __last - __first;

4728

    pair<value_type*, ptrdiff_t> __buf(0, 0);

4729

    unique_ptr<value_type, __return_temporary_buffer> __h;

4730

    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))

4731

4732

        __buf = _VSTD::get_temporary_buffer<value_type>(__len);

4733

        __h.reset(__buf.first);

4734

4735

#ifdef _LIBCPP_DEBUG

4736

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4737

    __debug_less<_Compare> __c(__comp);

4738

    __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);

4739

#else  // _LIBCPP_DEBUG

4740

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4741

    __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);

4742

#endif  // _LIBCPP_DEBUG

4743

4744

4745

template <class _RandomAccessIterator>

4746

inline _LIBCPP_INLINE_VISIBILITY

4747

void

4748

stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

4749

4750

    _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4751

4752

4753

// is_heap_until

4754

4755

template <class _RandomAccessIterator, class _Compare>

4756

_RandomAccessIterator

4757

is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4758

4759

    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;

4760

    difference_type __len = __last - __first;

4761

    difference_type __p = 0;

4762

    difference_type __c = 1;

4763

    _RandomAccessIterator __pp = __first;

4764

    while (__c < __len)

4765

4766

        _RandomAccessIterator __cp = __first + __c;

4767

        if (__comp(*__pp, *__cp))

4768

            return __cp;

4769

        ++__c;

4770

        ++__cp;

4771

        if (__c == __len)

4772

            return __last;

4773

        if (__comp(*__pp, *__cp))

4774

            return __cp;

4775

        ++__p;

4776

        ++__pp;

4777

        __c = 2 * __p + 1;

4778

4779

    return __last;

4780

4781

4782

template<class _RandomAccessIterator>

4783

inline _LIBCPP_INLINE_VISIBILITY

4784

_RandomAccessIterator

4785

is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)

4786

4787

    return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4788

4789

4790

// is_heap

4791

4792

template <class _RandomAccessIterator, class _Compare>

4793

inline _LIBCPP_INLINE_VISIBILITY

4794

bool

4795

is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4796

4797

    return _VSTD::is_heap_until(__first, __last, __comp) == __last;

4798

4799

4800

template<class _RandomAccessIterator>

4801

inline _LIBCPP_INLINE_VISIBILITY

4802

bool

4803

is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

4804

4805

    return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4806

4807

4808

// push_heap

4809

4810

template <class _Compare, class _RandomAccessIterator>

4811

void

4812

__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,

4813

          typename iterator_traits<_RandomAccessIterator>::difference_type __len)

4814

4815

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

4816

    if (__len > 1)

4817

4818

        __len = (__len - 2) / 2;

4819

        _RandomAccessIterator __ptr = __first + __len;

4820

        if (__comp(*__ptr, *--__last))

4821

4822

            value_type __t(_VSTD::move(*__last));

4823

do

4824

4825

                *__last = _VSTD::move(*__ptr);

4826

                __last = __ptr;

4827

                if (__len == 0)

4828

                    break;

4829

                __len = (__len - 1) / 2;

4830

                __ptr = __first + __len;

4831

            } while (__comp(*__ptr, __t));

4832

            *__last = _VSTD::move(__t);

template <class _RandomAccessIterator, class _Compare>

4838

inline _LIBCPP_INLINE_VISIBILITY

4839

void

4840

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4841

4842

#ifdef _LIBCPP_DEBUG

4843

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4844

    __debug_less<_Compare> __c(__comp);

4845

    __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);

4846

#else  // _LIBCPP_DEBUG

4847

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4848

    __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);

4849

#endif  // _LIBCPP_DEBUG

4850

4851

4852

template <class _RandomAccessIterator>

4853

inline _LIBCPP_INLINE_VISIBILITY

4854

void

4855

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

4856

4857

    _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4858

4859

4860

// pop_heap

4861

4862

template <class _Compare, class _RandomAccessIterator>

4863

void

4864

__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,

4865

            typename iterator_traits<_RandomAccessIterator>::difference_type __len,

4866

            _RandomAccessIterator __start)

4867

4868

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

4869

    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;

4870

    // left-child of __start is at 2 * __start + 1

4871

    // right-child of __start is at 2 * __start + 2

4872

    difference_type __child = __start - __first;

4873

4874

    if (__len < 2 || (__len - 2) / 2 < __child)

4875

        return;

4876

4877

    __child = 2 * __child + 1;

4878

    _RandomAccessIterator __child_i = __first + __child;

4879

4880

    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {

4881

        // right-child exists and is greater than left-child

4882

        ++__child_i;

4883

        ++__child;

4884

4885

4886

    // check if we are in heap-order

4887

    if (__comp(*__child_i, *__start))

4888

        // we are, __start is larger than it's largest child

4889

        return;

4890

4891

    value_type __top(_VSTD::move(*__start));

4892

do

4893

4894

        // we are not in heap-order, swap the parent with it's largest child

4895

        *__start = _VSTD::move(*__child_i);

4896

        __start = __child_i;

4897

4898

        if ((__len - 2) / 2 < __child)

4899

            break;

4900

4901

        // recompute the child based off of the updated parent

4902

        __child = 2 * __child + 1;

4903

        __child_i = __first + __child;

4904

4905

        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {

4906

            // right-child exists and is greater than left-child

4907

            ++__child_i;

4908

            ++__child;

4909

4910

4911

        // check if we are in heap-order

4912

    } while (!__comp(*__child_i, __top));

4913

    *__start = _VSTD::move(__top);

4914

4915

4916

template <class _Compare, class _RandomAccessIterator>

4917

inline _LIBCPP_INLINE_VISIBILITY

4918

void

4919

__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,

4920

           typename iterator_traits<_RandomAccessIterator>::difference_type __len)

4921

4922

    if (__len > 1)

4923

4924

        swap(*__first, *--__last);

4925

        __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);

template <class _RandomAccessIterator, class _Compare>

4930

inline _LIBCPP_INLINE_VISIBILITY

4931

void

4932

pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4933

4934

#ifdef _LIBCPP_DEBUG

4935

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4936

    __debug_less<_Compare> __c(__comp);

4937

    __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);

4938

#else  // _LIBCPP_DEBUG

4939

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4940

    __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);

4941

#endif  // _LIBCPP_DEBUG

4942

4943

4944

template <class _RandomAccessIterator>

4945

inline _LIBCPP_INLINE_VISIBILITY

4946

void

4947

pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

4948

4949

    _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4950

4951

4952

// make_heap

4953

4954

template <class _Compare, class _RandomAccessIterator>

4955

void

4956

__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4957

4958

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

4959

    difference_type __n = __last - __first;

4960

    if (__n > 1)

4961

4962

        // start from the first parent, there is no need to consider children

4963

        for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)

4964

4965

            __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);

template <class _RandomAccessIterator, class _Compare>

4971

inline _LIBCPP_INLINE_VISIBILITY

4972

void

4973

make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4974

4975

#ifdef _LIBCPP_DEBUG

4976

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

4977

    __debug_less<_Compare> __c(__comp);

4978

    __make_heap<_Comp_ref>(__first, __last, __c);

4979

#else  // _LIBCPP_DEBUG

4980

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

4981

    __make_heap<_Comp_ref>(__first, __last, __comp);

4982

#endif  // _LIBCPP_DEBUG

4983

4984

4985

template <class _RandomAccessIterator>

4986

inline _LIBCPP_INLINE_VISIBILITY

4987

void

4988

make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

4989

4990

    _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

4991

4992

4993

// sort_heap

4994

4995

template <class _Compare, class _RandomAccessIterator>

4996

void

4997

__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

4998

4999

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

5000

    for (difference_type __n = __last - __first; __n > 1; --__last, --__n)

5001

        __pop_heap<_Compare>(__first, __last, __comp, __n);

5002

5003

5004

template <class _RandomAccessIterator, class _Compare>

5005

inline _LIBCPP_INLINE_VISIBILITY

5006

void

5007

sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

5008

5009

#ifdef _LIBCPP_DEBUG

5010

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5011

    __debug_less<_Compare> __c(__comp);

5012

    __sort_heap<_Comp_ref>(__first, __last, __c);

5013

#else  // _LIBCPP_DEBUG

5014

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5015

    __sort_heap<_Comp_ref>(__first, __last, __comp);

5016

#endif  // _LIBCPP_DEBUG

5017

5018

5019

template <class _RandomAccessIterator>

5020

inline _LIBCPP_INLINE_VISIBILITY

5021

void

5022

sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

5023

5024

    _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

5025

5026

5027

// partial_sort

5028

5029

template <class _Compare, class _RandomAccessIterator>

5030

void

5031

__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,

5032

             _Compare __comp)

5033

5034

    __make_heap<_Compare>(__first, __middle, __comp);

5035

    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;

5036

    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)

5037

5038

        if (__comp(*__i, *__first))

5039

5040

            swap(*__i, *__first);

5041

            __sift_down<_Compare>(__first, __middle, __comp, __len, __first);

5042

5043

5044

    __sort_heap<_Compare>(__first, __middle, __comp);

5045

5046

5047

template <class _RandomAccessIterator, class _Compare>

5048

inline _LIBCPP_INLINE_VISIBILITY

5049

void

5050

partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,

5051

             _Compare __comp)

5052

5053

#ifdef _LIBCPP_DEBUG

5054

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5055

    __debug_less<_Compare> __c(__comp);

5056

    __partial_sort<_Comp_ref>(__first, __middle, __last, __c);

5057

#else  // _LIBCPP_DEBUG

5058

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5059

    __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);

5060

#endif  // _LIBCPP_DEBUG

5061

5062

5063

template <class _RandomAccessIterator>

5064

inline _LIBCPP_INLINE_VISIBILITY

5065

void

5066

partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)

5067

5068

    _VSTD::partial_sort(__first, __middle, __last,

5069

                       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

5070

5071

5072

// partial_sort_copy

5073

5074

template <class _Compare, class _InputIterator, class _RandomAccessIterator>

5075

_RandomAccessIterator

5076

__partial_sort_copy(_InputIterator __first, _InputIterator __last,

5077

                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)

5078

5079

    _RandomAccessIterator __r = __result_first;

5080

    if (__r != __result_last)

5081

5082

        for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)

5083

            *__r = *__first;

5084

        __make_heap<_Compare>(__result_first, __r, __comp);

5085

        typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;

5086

        for (; __first != __last; ++__first)

5087

            if (__comp(*__first, *__result_first))

5088

5089

                *__result_first = *__first;

5090

                __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);

5091

5092

        __sort_heap<_Compare>(__result_first, __r, __comp);

5093

5094

    return __r;

5095

5096

5097

template <class _InputIterator, class _RandomAccessIterator, class _Compare>

5098

inline _LIBCPP_INLINE_VISIBILITY

5099

_RandomAccessIterator

5100

partial_sort_copy(_InputIterator __first, _InputIterator __last,

5101

                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)

5102

5103

#ifdef _LIBCPP_DEBUG

5104

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5105

    __debug_less<_Compare> __c(__comp);

5106

    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);

5107

#else  // _LIBCPP_DEBUG

5108

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5109

    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);

5110

#endif  // _LIBCPP_DEBUG

5111

5112

5113

template <class _InputIterator, class _RandomAccessIterator>

5114

inline _LIBCPP_INLINE_VISIBILITY

5115

_RandomAccessIterator

5116

partial_sort_copy(_InputIterator __first, _InputIterator __last,

5117

                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)

5118

5119

    return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,

5120

                                   __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

5121

5122

5123

// nth_element

5124

5125

template <class _Compare, class _RandomAccessIterator>

5126

void

5127

__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)

5128

5129

    // _Compare is known to be a reference type

5130

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;

5131

    const difference_type __limit = 7;

5132

    while (true)

5133

5134

    __restart:

5135

        if (__nth == __last)

5136

            return;

5137

        difference_type __len = __last - __first;

5138

        switch (__len)

5139

5140

        case 0:

5141

        case 1:

5142

            return;

5143

        case 2:

5144

            if (__comp(*--__last, *__first))

5145

                swap(*__first, *__last);

5146

            return;

5147

        case 3:

5148

5149

            _RandomAccessIterator __m = __first;

5150

            _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);

5151

            return;

5152

5153

5154

        if (__len <= __limit)

5155

5156

            __selection_sort<_Compare>(__first, __last, __comp);

5157

            return;

5158

5159

        // __len > __limit >= 3

5160

        _RandomAccessIterator __m = __first + __len/2;

5161

        _RandomAccessIterator __lm1 = __last;

5162

        unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);

5163

        // *__m is median

5164

        // partition [__first, __m) < *__m and *__m <= [__m, __last)

5165

        // (this inhibits tossing elements equivalent to __m around unnecessarily)

5166

        _RandomAccessIterator __i = __first;

5167

        _RandomAccessIterator __j = __lm1;

5168

        // j points beyond range to be tested, *__lm1 is known to be <= *__m

5169

        // The search going up is known to be guarded but the search coming down isn't.

5170

        // Prime the downward search with a guard.

5171

        if (!__comp(*__i, *__m))  // if *__first == *__m

5172

5173

            // *__first == *__m, *__first doesn't go in first part

5174

            // manually guard downward moving __j against __i

5175

            while (true)

5176

5177

                if (__i == --__j)

5178

5179

                    // *__first == *__m, *__m <= all other elements

5180

                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)

5181

                    ++__i;  // __first + 1

5182

                    __j = __last;

5183

                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)

5184

5185

                        while (true)

5186

5187

                            if (__i == __j)

5188

                                return;  // [__first, __last) all equivalent elements

5189

                            if (__comp(*__first, *__i))

5190

5191

                                swap(*__i, *__j);

5192

                                ++__n_swaps;

5193

                                ++__i;

5194

                                break;

5195

5196

                            ++__i;

5197

5198

5199

                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1

5200

                    if (__i == __j)

5201

                        return;

5202

                    while (true)

5203

5204

                        while (!__comp(*__first, *__i))

5205

                            ++__i;

5206

                        while (__comp(*__first, *--__j))

5207

5208

                        if (__i >= __j)

5209

                            break;

5210

                        swap(*__i, *__j);

5211

                        ++__n_swaps;

5212

                        ++__i;

5213

5214

                    // [__first, __i) == *__first and *__first < [__i, __last)

5215

                    // The first part is sorted,

5216

                    if (__nth < __i)

5217

                        return;

5218

                    // __nth_element the secod part

5219

                    // __nth_element<_Compare>(__i, __nth, __last, __comp);

5220

                    __first = __i;

5221

                    goto __restart;

5222

5223

                if (__comp(*__j, *__m))

5224

5225

                    swap(*__i, *__j);

5226

                    ++__n_swaps;

5227

                    break;  // found guard for downward moving __j, now use unguarded partition

        ++__i;

5232

        // j points beyond range to be tested, *__lm1 is known to be <= *__m

5233

        // if not yet partitioned...

5234

        if (__i < __j)

5235

5236

            // known that *(__i - 1) < *__m

5237

            while (true)

5238

5239

                // __m still guards upward moving __i

5240

                while (__comp(*__i, *__m))

5241

                    ++__i;

5242

                // It is now known that a guard exists for downward moving __j

5243

                while (!__comp(*--__j, *__m))

5244

5245

                if (__i >= __j)

5246

                    break;

5247

                swap(*__i, *__j);

5248

                ++__n_swaps;

5249

                // It is known that __m != __j

5250

                // If __m just moved, follow it

5251

                if (__m == __i)

5252

                    __m = __j;

5253

                ++__i;

5254

5255

5256

        // [__first, __i) < *__m and *__m <= [__i, __last)

5257

        if (__i != __m && __comp(*__m, *__i))

5258

5259

            swap(*__i, *__m);

5260

            ++__n_swaps;

5261

5262

        // [__first, __i) < *__i and *__i <= [__i+1, __last)

5263

        if (__nth == __i)

5264

            return;

5265

        if (__n_swaps == 0)

5266

5267

            // We were given a perfectly partitioned sequence.  Coincidence?

5268

            if (__nth < __i)

5269

5270

                // Check for [__first, __i) already sorted

5271

                __j = __m = __first;

5272

                while (++__j != __i)

5273

5274

                    if (__comp(*__j, *__m))

5275

                        // not yet sorted, so sort

5276

                        goto not_sorted;

5277

                    __m = __j;

5278

5279

                // [__first, __i) sorted

5280

                return;

5281

5282

            else

5283

5284

                // Check for [__i, __last) already sorted

5285

                __j = __m = __i;

5286

                while (++__j != __last)

5287

5288

                    if (__comp(*__j, *__m))

5289

                        // not yet sorted, so sort

5290

                        goto not_sorted;

5291

                    __m = __j;

5292

5293

                // [__i, __last) sorted

5294

                return;

5295

5296

5297

not_sorted:

5298

        // __nth_element on range containing __nth

5299

        if (__nth < __i)

5300

5301

            // __nth_element<_Compare>(__first, __nth, __i, __comp);

5302

            __last = __i;

5303

5304

        else

5305

5306

            // __nth_element<_Compare>(__i+1, __nth, __last, __comp);

5307

            __first = ++__i;

template <class _RandomAccessIterator, class _Compare>

5313

inline _LIBCPP_INLINE_VISIBILITY

5314

void

5315

nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)

5316

5317

#ifdef _LIBCPP_DEBUG

5318

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5319

    __debug_less<_Compare> __c(__comp);

5320

    __nth_element<_Comp_ref>(__first, __nth, __last, __c);

5321

#else  // _LIBCPP_DEBUG

5322

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5323

    __nth_element<_Comp_ref>(__first, __nth, __last, __comp);

5324

#endif  // _LIBCPP_DEBUG

5325

5326

5327

template <class _RandomAccessIterator>

5328

inline _LIBCPP_INLINE_VISIBILITY

5329

void

5330

nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)

5331

5332

    _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());

5333

5334

5335

// includes

5336

5337

template <class _Compare, class _InputIterator1, class _InputIterator2>

5338

bool

5339

__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,

5340

           _Compare __comp)

5341

5342

    for (; __first2 != __last2; ++__first1)

5343

5344

        if (__first1 == __last1 || __comp(*__first2, *__first1))

5345

            return false;

5346

        if (!__comp(*__first1, *__first2))

5347

            ++__first2;

5348

5349

    return true;

5350

5351

5352

template <class _InputIterator1, class _InputIterator2, class _Compare>

5353

inline _LIBCPP_INLINE_VISIBILITY

5354

bool

5355

includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,

5356

         _Compare __comp)

5357

5358

#ifdef _LIBCPP_DEBUG

5359

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5360

    __debug_less<_Compare> __c(__comp);

5361

    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);

5362

#else  // _LIBCPP_DEBUG

5363

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5364

    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);

5365

#endif  // _LIBCPP_DEBUG

5366

5367

5368

template <class _InputIterator1, class _InputIterator2>

5369

inline _LIBCPP_INLINE_VISIBILITY

5370

bool

5371

includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)

5372

5373

    return _VSTD::includes(__first1, __last1, __first2, __last2,

5374

                          __less<typename iterator_traits<_InputIterator1>::value_type,

5375

                                 typename iterator_traits<_InputIterator2>::value_type>());

5376

5377

5378

// set_union

5379

5380

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

5381

_OutputIterator

5382

__set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5383

            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5384

5385

    for (; __first1 != __last1; ++__result)

5386

5387

        if (__first2 == __last2)

5388

            return _VSTD::copy(__first1, __last1, __result);

5389

        if (__comp(*__first2, *__first1))

5390

5391

            *__result = *__first2;

5392

            ++__first2;

5393

5394

        else

5395

5396

            *__result = *__first1;

5397

            if (!__comp(*__first1, *__first2))

5398

                ++__first2;

5399

            ++__first1;

5400

5401

5402

    return _VSTD::copy(__first2, __last2, __result);

5403

5404

5405

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>

5406

inline _LIBCPP_INLINE_VISIBILITY

5407

_OutputIterator

5408

set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5409

          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5410

5411

#ifdef _LIBCPP_DEBUG

5412

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5413

    __debug_less<_Compare> __c(__comp);

5414

    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);

5415

#else  // _LIBCPP_DEBUG

5416

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5417

    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);

5418

#endif  // _LIBCPP_DEBUG

5419

5420

5421

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>

5422

inline _LIBCPP_INLINE_VISIBILITY

5423

_OutputIterator

5424

set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5425

          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)

5426

5427

    return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,

5428

                          __less<typename iterator_traits<_InputIterator1>::value_type,

5429

                                 typename iterator_traits<_InputIterator2>::value_type>());

5430

5431

5432

// set_intersection

5433

5434

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

5435

_OutputIterator

5436

__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5437

                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5438

5439

    while (__first1 != __last1 && __first2 != __last2)

5440

5441

        if (__comp(*__first1, *__first2))

5442

            ++__first1;

5443

        else

5444

5445

            if (!__comp(*__first2, *__first1))

5446

5447

                *__result = *__first1;

5448

                ++__result;

5449

                ++__first1;

5450

5451

            ++__first2;

5452

5453

5454

    return __result;

5455

5456

5457

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>

5458

inline _LIBCPP_INLINE_VISIBILITY

5459

_OutputIterator

5460

set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5461

                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5462

5463

#ifdef _LIBCPP_DEBUG

5464

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5465

    __debug_less<_Compare> __c(__comp);

5466

    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);

5467

#else  // _LIBCPP_DEBUG

5468

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5469

    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);

5470

#endif  // _LIBCPP_DEBUG

5471

5472

5473

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>

5474

inline _LIBCPP_INLINE_VISIBILITY

5475

_OutputIterator

5476

set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5477

                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)

5478

5479

    return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,

5480

                                  __less<typename iterator_traits<_InputIterator1>::value_type,

5481

                                         typename iterator_traits<_InputIterator2>::value_type>());

5482

5483

5484

// set_difference

5485

5486

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

5487

_OutputIterator

5488

__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5489

                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5490

5491

    while (__first1 != __last1)

5492

5493

        if (__first2 == __last2)

5494

            return _VSTD::copy(__first1, __last1, __result);

5495

        if (__comp(*__first1, *__first2))

5496

5497

            *__result = *__first1;

5498

            ++__result;

5499

            ++__first1;

5500

5501

        else

5502

5503

            if (!__comp(*__first2, *__first1))

5504

                ++__first1;

5505

            ++__first2;

5506

5507

5508

    return __result;

5509

5510

5511

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>

5512

inline _LIBCPP_INLINE_VISIBILITY

5513

_OutputIterator

5514

set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5515

               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5516

5517

#ifdef _LIBCPP_DEBUG

5518

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5519

    __debug_less<_Compare> __c(__comp);

5520

    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);

5521

#else  // _LIBCPP_DEBUG

5522

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5523

    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);

5524

#endif  // _LIBCPP_DEBUG

5525

5526

5527

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>

5528

inline _LIBCPP_INLINE_VISIBILITY

5529

_OutputIterator

5530

set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5531

               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)

5532

5533

    return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,

5534

                                __less<typename iterator_traits<_InputIterator1>::value_type,

5535

                                       typename iterator_traits<_InputIterator2>::value_type>());

5536

5537

5538

// set_symmetric_difference

5539

5540

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

5541

_OutputIterator

5542

__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5543

                           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5544

5545

    while (__first1 != __last1)

5546

5547

        if (__first2 == __last2)

5548

            return _VSTD::copy(__first1, __last1, __result);

5549

        if (__comp(*__first1, *__first2))

5550

5551

            *__result = *__first1;

5552

            ++__result;

5553

            ++__first1;

5554

5555

        else

5556

5557

            if (__comp(*__first2, *__first1))

5558

5559

                *__result = *__first2;

5560

                ++__result;

5561

5562

            else

5563

                ++__first1;

5564

            ++__first2;

5565

5566

5567

    return _VSTD::copy(__first2, __last2, __result);

5568

5569

5570

template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>

5571

inline _LIBCPP_INLINE_VISIBILITY

5572

_OutputIterator

5573

set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5574

                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

5575

5576

#ifdef _LIBCPP_DEBUG

5577

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5578

    __debug_less<_Compare> __c(__comp);

5579

    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);

5580

#else  // _LIBCPP_DEBUG

5581

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5582

    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);

5583

#endif  // _LIBCPP_DEBUG

5584

5585

5586

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>

5587

inline _LIBCPP_INLINE_VISIBILITY

5588

_OutputIterator

5589

set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5590

                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)

5591

5592

    return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,

5593

                                          __less<typename iterator_traits<_InputIterator1>::value_type,

5594

                                                 typename iterator_traits<_InputIterator2>::value_type>());

5595

5596

5597

// lexicographical_compare

5598

5599

template <class _Compare, class _InputIterator1, class _InputIterator2>

5600

bool

5601

__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,

5602

                          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)

5603

5604

    for (; __first2 != __last2; ++__first1, (void) ++__first2)

5605

5606

        if (__first1 == __last1 || __comp(*__first1, *__first2))

5607

            return true;

5608

        if (__comp(*__first2, *__first1))

5609

            return false;

5610

5611

    return false;

5612

5613

5614

template <class _InputIterator1, class _InputIterator2, class _Compare>

5615

inline _LIBCPP_INLINE_VISIBILITY

5616

bool

5617

lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,

5618

                        _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)

5619

5620

#ifdef _LIBCPP_DEBUG

5621

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5622

    __debug_less<_Compare> __c(__comp);

5623

    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);

5624

#else  // _LIBCPP_DEBUG

5625

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5626

    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);

5627

#endif  // _LIBCPP_DEBUG

5628

5629

5630

template <class _InputIterator1, class _InputIterator2>

5631

inline _LIBCPP_INLINE_VISIBILITY

5632

bool

5633

lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,

5634

                        _InputIterator2 __first2, _InputIterator2 __last2)

5635

5636

    return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,

5637

                                         __less<typename iterator_traits<_InputIterator1>::value_type,

5638

                                                typename iterator_traits<_InputIterator2>::value_type>());

5639

5640

5641

// next_permutation

5642

5643

template <class _Compare, class _BidirectionalIterator>

5644

bool

5645

__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)

5646

5647

    _BidirectionalIterator __i = __last;

5648

    if (__first == __last || __first == --__i)

5649

        return false;

5650

    while (true)

5651

5652

        _BidirectionalIterator __ip1 = __i;

5653

        if (__comp(*--__i, *__ip1))

5654

5655

            _BidirectionalIterator __j = __last;

5656

            while (!__comp(*__i, *--__j))

5657

5658

            swap(*__i, *__j);

5659

            _VSTD::reverse(__ip1, __last);

5660

            return true;

5661

5662

        if (__i == __first)

5663

5664

            _VSTD::reverse(__first, __last);

5665

            return false;

template <class _BidirectionalIterator, class _Compare>

5671

inline _LIBCPP_INLINE_VISIBILITY

5672

bool

5673

next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)

5674

5675

#ifdef _LIBCPP_DEBUG

5676

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5677

    __debug_less<_Compare> __c(__comp);

5678

    return __next_permutation<_Comp_ref>(__first, __last, __c);

5679

#else  // _LIBCPP_DEBUG

5680

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5681

    return __next_permutation<_Comp_ref>(__first, __last, __comp);

5682

#endif  // _LIBCPP_DEBUG

5683

5684

5685

template <class _BidirectionalIterator>

5686

inline _LIBCPP_INLINE_VISIBILITY

5687

bool

5688

next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)

5689

5690

    return _VSTD::next_permutation(__first, __last,

5691

                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());

5692

5693

5694

// prev_permutation

5695

5696

template <class _Compare, class _BidirectionalIterator>

5697

bool

5698

__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)

5699

5700

    _BidirectionalIterator __i = __last;

5701

    if (__first == __last || __first == --__i)

5702

        return false;

5703

    while (true)

5704

5705

        _BidirectionalIterator __ip1 = __i;

5706

        if (__comp(*__ip1, *--__i))

5707

5708

            _BidirectionalIterator __j = __last;

5709

            while (!__comp(*--__j, *__i))

5710

5711

            swap(*__i, *__j);

5712

            _VSTD::reverse(__ip1, __last);

5713

            return true;

5714

5715

        if (__i == __first)

5716

5717

            _VSTD::reverse(__first, __last);

5718

            return false;

template <class _BidirectionalIterator, class _Compare>

5724

inline _LIBCPP_INLINE_VISIBILITY

5725

bool

5726

prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)

5727

5728

#ifdef _LIBCPP_DEBUG

5729

    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;

5730

    __debug_less<_Compare> __c(__comp);

5731

    return __prev_permutation<_Comp_ref>(__first, __last, __c);

5732

#else  // _LIBCPP_DEBUG

5733

    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;

5734

    return __prev_permutation<_Comp_ref>(__first, __last, __comp);

5735

#endif  // _LIBCPP_DEBUG

5736

5737

5738

template <class _BidirectionalIterator>

5739

inline _LIBCPP_INLINE_VISIBILITY

5740

bool

5741

prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)

5742

5743

    return _VSTD::prev_permutation(__first, __last,

5744

                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());

5745

5746

5747

template <class _Tp>

5748

inline _LIBCPP_INLINE_VISIBILITY

5749

typename enable_if

5750

5751

    is_integral<_Tp>::value,

5752

_Tp

5753

>::type

5754

__rotate_left(_Tp __t, _Tp __n = 1)

5755

5756

    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);

5757

    __n &= __bits;

5758

    return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));

5759

5760

5761

template <class _Tp>

5762

inline _LIBCPP_INLINE_VISIBILITY

5763

typename enable_if

5764

5765

    is_integral<_Tp>::value,

5766

_Tp

5767

>::type

5768

__rotate_right(_Tp __t, _Tp __n = 1)

5769

5770

    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);

5771

    __n &= __bits;

5772

    return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));

5773

5774

5775

_LIBCPP_END_NAMESPACE_STD

5776

5777

#endif  // _LIBCPP_ALGORITHM

Project

General

Profile

LCOM1920-T02G10

root / lab4 / .minix-src / include / c++ / algorithm