~ubuntu-branches/ubuntu/maverick/aptitude/maverick

« back to all changes in this revision

Viewing changes to src/generic/util/immset.h

• browse files at revision 55
• compare with another revision
• download diff
• download tarball
• view history from revision 55

Show diffs side-by-side

added

removed

src/generic/util/immset.h

1

1

// immset.h                                     -*-c++-*-

2

2

//

3

 

//   Copyright (C) 2005-2006, 2008-2009 Daniel Burrows

 

3

//   Copyright (C) 2005-2006, 2008-2010 Daniel Burrows

4

4

//

5

5

//   This program is free software; you can redistribute it and/or

6

6

//   modify it under the terms of the GNU General Public License as

26

26

 

27

27

#include <vector>

28

28

 

 

29

#include <boost/compressed_pair.hpp>

 

30

 

29

31

#include "compare3.h"

30

32

 

31

33

/** \brief A class to represent immutable sets

49

51

 

50

52

namespace imm

51

53

{

 

54

  /** \brief A class used in metaprogramming for imm::set.

 

55

   */

 

56

  class nil_t {};

 

57

 

 

58

  template<typename Val, typename AccumVal, typename AccumOps, int w>

 

59

  class wtree_node;

 

60

 

 

61

  /** \brief Helper function used below to accumulate information up

 

62

   *  the tree.

 

63

   *

 

64

   *  \tparam AccumOps The class carrying information about how to

 

65

   *  accumulate values up the tree; if this is nil_t, then this

 

66

   *  function is a NOP.

 

67

   *

 

68

   *  \todo Isn't there a better way of getting this behavior?  I

 

69

   *  tried partially specializing a private member function, but ran

 

70

   *  into syntactic trouble.

 

71

   */

 

72

  template<typename Val, typename AccumVal, typename AccumOps, int w>

 

73

  class doAccumulate

 

74

  {

 

75

  public:

 

76

    static AccumVal

 

77

    call(const Val &val,

 

78

         const wtree_node<Val, AccumVal, AccumOps, w> &left,

 

79

         const wtree_node<Val, AccumVal, AccumOps, w> &right,

 

80

         const AccumOps &accumOps);

 

81

  };

 

82

 

52

83

  /** A generic node in a weighted tree as described in "Implementing

53

84

   *  Sets Efficiently In A Functional Language".  The tree invariant

54

85

   *  is that the tree is not "too unbalanced"; in this case, that no

61

92

   *

62

93

   *  The weighted-tree data structure is reasonably efficient and

63

94

   *  much more straightforward to implement correctly.

 

95

   *

 

96

   *

 

97

   *  In addition to the above notes, this class can be used to

 

98

   *  iteratively maintain the result of accumulating an associative

 

99

   *  and commutative operation across the set.

 

100

   *

 

101

   *  \tparam Val  The type of value stored in this set.

 

102

   *

 

103

   *  \tparam AccumVal The type of value being accumulated at each

 

104

   *  node, or nil_t for no accumulation.

 

105

   *

 

106

   *  \tparam AccumOps If AccumVal is non-nil, this is the type used to

 

107

   *  compute accumulated values.  Must be a class type supporting

 

108

   *  three operations: empty(), project(Val) and merge(AccumVal,

 

109

   *  AccumVal), where empty() produces an AccumVal corresponding to

 

110

   *  an empty set, project() computes the AccumVal associated with a

 

111

   *  single value, and merge() combines two AccumVals.  merge() must

 

112

   *  be associative and commutative.

 

113

   *

 

114

   *  \tparam the weighting value of the tree; must be at least 3.75.

64

115

   */

65

 

  template<typename Val, const int w = 4>

 

116

  template<typename Val, typename AccumVal = nil_t, typename AccumOps = nil_t, const int w = 4>

66

117

  class wtree_node

67

118

  {

68

119

    // Type hack to let us dump trees containing pairs without

92

143

      /** Left and right children (may be \b null). */

93

144

      wtree_node left, right;

94

145

 

95

 

      /** The size of the subtree rooted at this node. */

96

 

      size_type size;

 

146

      /** The size of the subtree rooted at this node, paired with any

 

147

       *  accumulated information specified by the user.

 

148

       *

 

149

       *  Using compressed_pair allows us to avoid allocating space if

 

150

       *  the accumulated value is empty, without having to contain an

 

151

       *  implementation of empty member elision.

 

152

       */

 

153

      boost::compressed_pair<size_type, AccumVal> sizeAndAccumVal;

97

154

 

98

155

      /** The reference-count of this node. */

99

156

      mutable int refcount;

100

157

 

101

158

      /** The enclosed value. */

102

159

      Val val;

 

160

 

103

161

    public:

104

162

      impl(const Val &_val,

105

 

           const wtree_node &_left, const wtree_node &_right)

106

 

        :left(_left), right(_right), size(_left.size()+_right.size()+1),

 

163

           const wtree_node &_left, const wtree_node &_right,

 

164

           const AccumOps &ops)

 

165

        :left(_left), right(_right),

 

166

         sizeAndAccumVal(_left.size() + _right.size() + 1,

 

167

                         doAccumulate<Val, AccumVal, AccumOps, w>::call(_val, _left, _right, ops)),

107

168

         refcount(1), val(_val)

108

169

      {

109

170

      }

110

171

 

 

172

      impl *clone(const AccumOps &ops) const

 

173

      {

 

174

        return new impl(val, left.clone(ops), right.clone(ops), ops);

 

175

      }

 

176

 

111

177

      /** \return the left child. */

112

178

      const wtree_node &getLeftChild() const

113

179

      {

122

188

 

123

189

      size_type getSize() const

124

190

      {

125

 

        return size;

 

191

        return sizeAndAccumVal.first();

126

192

      }

127

193

 

128

194

      const Val &getVal() const

145

211

        if(refcount == 0)

146

212

          delete this;

147

213

      }

 

214

 

 

215

 

 

216

      const AccumVal &getAccumVal() const { return sizeAndAccumVal.second(); }

148

217

    };

149

218

 

150

219

    const impl *realNode;

153

222

    typedef unsigned int size_type;

154

223

 

155

224

    wtree_node(const Val &val,

156

 

               const wtree_node &left, const wtree_node &right)

157

 

      :realNode(new impl(val, left, right))

 

225

               const wtree_node &left, const wtree_node &right,

 

226

               const AccumOps &accumOps)

 

227

      :realNode(new impl(val, left, right, accumOps))

158

228

    {

159

229

    }

160

230

 

161

 

    wtree_node(const Val &val)

162

 

      :realNode(new impl(val, wtree_node(), wtree_node()))

 

231

    wtree_node(const Val &val,

 

232

               const AccumOps &accumOps)

 

233

      :realNode(new impl(val, wtree_node(), wtree_node(),

 

234

                         accumOps))

163

235

    {

164

236

    }

165

237

 

247

319

      return realNode->getVal();

248

320

    }

249

321

 

 

322

    /** \return the accumulated value of this node.

 

323

     *

 

324

     *  Only allowed if AccumVal is non-nil and isValid() is truea.

 

325

     */

 

326

    const AccumVal &getAccumVal() const

 

327

    {

 

328

      return realNode->getAccumVal();

 

329

    }

 

330

 

250

331

    // Tree management routines:

251

332

 

252

333

    /** Perform a 'left rotate' operation on this node.  Requires

253

334

     *  that the right child is not \b null.

254

335

     */

255

 

    wtree_node left_rotate_single() const

 

336

    wtree_node left_rotate_single(const AccumOps &accumOps) const

256

337

    {

257

338

      wtree_node right = getRight(), left = getLeft();

258

339

      wtree_node right_left = right.getLeft(), right_right = right.getRight();

259

340

 

260

341

      return wtree_node(right.getVal(),

261

 

                        wtree_node(getVal(), left, right_left),

262

 

                        right_right);

 

342

                        wtree_node(getVal(), left, right_left, accumOps),

 

343

                        right_right,

 

344

                        accumOps);

263

345

    }

264

346

 

265

347

    /** Perform a 'right rotate' operation on this node.  Requires

266

348

     *  that the left child is not \b null.

267

349

     */

268

 

    wtree_node right_rotate_single() const

 

350

    wtree_node right_rotate_single(const AccumOps &accumOps) const

269

351

    {

270

352

      wtree_node right = getRight(), left = getLeft();

271

353

      wtree_node left_left = left.getLeft(), left_right = left.getRight();

272

354

 

273

355

      return wtree_node(left.getVal(),

274

356

                        left_left,

275

 

                        wtree_node(getVal(), left_right, right));

 

357

                        wtree_node(getVal(), left_right, right, accumOps),

 

358

                        accumOps);

276

359

    }

277

360

 

278

361

    /** Perform a 'double left rotate' operation on this node.

279

362

     *  Requires that the right child not be \b null and that

280

363

     *  its left child is also not \b null.

281

364

     */

282

 

    wtree_node left_rotate_double() const

 

365

    wtree_node left_rotate_double(const AccumOps &accumOps) const

283

366

    {

284

367

      wtree_node right = getRight(), left = getLeft();

285

368

      wtree_node right_right = right.getRight(), right_left = right.getLeft();

287

370

      wtree_node right_left_right = right_left.getRight();

288

371

 

289

372

      return wtree_node(right_left.getVal(),

290

 

                        wtree_node(getVal(), left, right_left_left),

 

373

                        wtree_node(getVal(), left, right_left_left, accumOps),

291

374

                        wtree_node(right.getVal(), right_left_right,

292

 

                                   right_right));

 

375

                                   right_right, accumOps),

 

376

                        accumOps);

293

377

    }

294

378

 

295

379

    /** Perform a 'double right rotate' operation on this node.

296

380

     *  Requires that the left child not be \b null and that

297

381

     *  its right child is also not \b null.

298

382

     */

299

 

    wtree_node right_rotate_double() const

 

383

    wtree_node right_rotate_double(const AccumOps &accumOps) const

300

384

    {

301

385

      wtree_node right = getRight(), left = getLeft();

302

386

      wtree_node left_right = left.getRight(), left_left = left.getLeft();

304

388

      wtree_node left_right_right = left_right.getRight();

305

389

 

306

390

      return wtree_node(left_right.getVal(),

307

 

                        wtree_node(left.getVal(), left_left, left_right_left),

308

 

                        wtree_node(getVal(), left_right_right, right));

 

391

                        wtree_node(left.getVal(), left_left, left_right_left,

 

392

                                   accumOps),

 

393

                        wtree_node(getVal(), left_right_right, right,

 

394

                                   accumOps),

 

395

                        accumOps);

309

396

    }

310

397

 

311

398

 

316

403

     *  element (think inserting or deleting a single element).

317

404

     *  Equivalent to T' in the paper.

318

405

     */ 

319

 

    wtree_node rebalance() const

 

406

    wtree_node rebalance(const AccumOps &accumOps) const

320

407

    {

321

408

      wtree_node left = getLeft(), right = getRight();

322

409

      size_type left_size = left.size();

334

421

          // double rotation is guaranteed sufficient.

335

422

          wtree_node right_left = right.getLeft(), right_right = right.getRight();

336

423

          if(right_left.size() < right_right.size())

337

 

            return left_rotate_single();

 

424

            return left_rotate_single(accumOps);

338

425

          else

339

 

            return left_rotate_double();

 

426

            return left_rotate_double(accumOps);

340

427

        }

341

428

      else if(right_size * w < left_size)

342

429

        {

343

430

          // Dual of above.

344

431

          wtree_node left_left = left.getLeft(), left_right = left.getRight();

345

432

          if(left_right.size() < left_left.size())

346

 

            return right_rotate_single();

 

433

            return right_rotate_single(accumOps);

347

434

          else

348

 

            return right_rotate_double();

 

435

            return right_rotate_double(accumOps);

349

436

        }

350

437

      else

351

438

        // Nothing to do; the tree is already balanced.

402

489

    /** Return a new tree that does not share its structure with any

403

490

     *  other tree.

404

491

     */

405

 

    wtree_node clone() const

 

492

    wtree_node clone(const AccumOps &ops) const

406

493

    {

407

494

      if(empty())

408

495

        return wtree_node();

409

496

      else

410

 

        return wtree_node(getVal(), getLeft().clone(), getRight().clone());

411

 

    }

412

 

  };

 

497

        return wtree_node(realNode->clone(ops));

 

498

    }

 

499

  };

 

500

 

 

501

  template<typename Val, typename AccumVal, typename AccumOps, int w>

 

502

  inline AccumVal

 

503

  doAccumulate<Val, AccumVal, AccumOps, w>::call(const Val &val,

 

504

                                                 const wtree_node<Val, AccumVal, AccumOps, w> &left,

 

505

                                                 const wtree_node<Val, AccumVal, AccumOps, w> &right,

 

506

                                                 const AccumOps &accumOps)

 

507

  {

 

508

    if(left.isValid() && right.isValid())

 

509

      {

 

510

        const AccumVal valAndRight =

 

511

          accumOps.merge(accumOps.project(val),

 

512

                         right.getAccumVal());

 

513

        return accumOps.merge(left.getAccumVal(),

 

514

                              valAndRight);

 

515

      }

 

516

    else if(left.isValid())

 

517

      return accumOps.merge(left.getAccumVal(),

 

518

                            accumOps.project(val));

 

519

    else if(right.isValid())

 

520

      return accumOps.merge(accumOps.project(val),

 

521

                            right.getAccumVal());

 

522

    else

 

523

      return accumOps.project(val);

 

524

  }

 

525

 

 

526

  template<typename Val, typename AccumVal, int w>

 

527

  class doAccumulate<Val, AccumVal, nil_t, w>

 

528

  {

 

529

  public:

 

530

    static inline AccumVal

 

531

    call(const Val &val,

 

532

         const wtree_node<Val, AccumVal, nil_t, w> &left,

 

533

         const wtree_node<Val, AccumVal, nil_t, w> &right,

 

534

         const nil_t &accumOps)

 

535

    {

 

536

      return AccumVal();

 

537

    }

 

538

  };

 

539

 

413

540

 

414

541

  /** An entire weighted tree.

 

542

   *

 

543

   *  \tparam AccumVal if non-nil, a value of this type will be

 

544

   *  computed that represents the combination of all the values in

 

545

   *  the tree under AccumOps.

 

546

   *

 

547

   *  \tparam AccumOps A class type that allows values to be combined;

 

548

   *  documented under wtree_node.

415

549

   */

416

 

  template<typename Val, typename Compare = aptitude::util::compare3_f<Val>, int w = 4 >

 

550

  template<typename Val, typename Compare = aptitude::util::compare3_f<Val>,

 

551

           typename AccumVal = nil_t, typename AccumOps = nil_t, int w = 4 >

417

552

  class set

418

553

  {

419

554

  public:

420

555

    typedef Val value_type;

421

 

    typedef wtree_node<Val, w> node;

 

556

    typedef wtree_node<Val, AccumVal, AccumOps, w> node;

422

557

    typedef typename node::size_type size_type;

423

558

 

424

 

    Compare value_compare;

425

 

 

426

559

    /** An iterator over a wtree.  Note that the lack of parent

427

560

     *  pointers (necessary to allow full memory sharing) forces the

428

561

     *  iterator class to allocate!  I don't recommend using iterators

513

646

      }

514

647

    };

515

648

  private:

516

 

    /** Root of the tree. */

517

 

    node root;

 

649

    // Save space by throwing out empty comparison operators and

 

650

    // accumulation operators.

 

651

    class contents

 

652

    {

 

653

      boost::compressed_pair<Compare, boost::compressed_pair<AccumOps, node> >

 

654

      rootAndParameters;

 

655

 

 

656

    public:

 

657

      contents(const node &root,

 

658

               const Compare &value_compare,

 

659

               const AccumOps &accumOps)

 

660

        : rootAndParameters(value_compare,

 

661

                            boost::compressed_pair<AccumOps, node>(accumOps, root))

 

662

      {

 

663

      }

 

664

 

 

665

      const Compare &get_value_compare() const { return rootAndParameters.first(); }

 

666

      const AccumOps &get_accumOps() const { return rootAndParameters.second().first(); }

 

667

      const node &get_root() const { return rootAndParameters.second().second(); }

 

668

      void set_root(const node &n) { rootAndParameters.second().second() = n; }

 

669

    };

 

670

 

 

671

    contents impl;

518

672

 

519

673

    /** Returns a balanced tree constructed by adding x to n.

520

674

     *

524

678

    node add(const node &n, const Val &x, bool &added_anything) const

525

679

    {

526

680

      if(n.empty())

527

 

        return node(x, node(), node());

 

681

        return node(x, node(), node(), impl.get_accumOps());

528

682

      else

529

683

        {

530

 

          int cmp = value_compare(x, n.getVal());

 

684

          int cmp = impl.get_value_compare()(x, n.getVal());

531

685

 

532

686

          if(cmp < 0)

533

687

            return node(n.getVal(),

534

688

                        add(n.getLeft(), x, added_anything),

535

 

                        n.getRight()).rebalance();

 

689

                        n.getRight(),

 

690

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

536

691

          else if(cmp > 0)

537

692

            return node(n.getVal(),

538

693

                        n.getLeft(),

539

 

                        add(n.getRight(), x, added_anything)).rebalance();

 

694

                        add(n.getRight(), x, added_anything),

 

695

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

540

696

          else

541

697

            {

542

698

              added_anything = false;

554

710

    node addUpdate(const node &n, const Val &x, bool &added_new_entry) const

555

711

    {

556

712

      if(n.empty())

557

 

        return node(x, node(), node());

 

713

        return node(x, node(), node(), impl.get_accumOps());

558

714

      else

559

715

        {

560

 

          int cmp = value_compare(x, n.getVal());

 

716

          int cmp = impl.get_value_compare()(x, n.getVal());

561

717

 

562

718

          if(cmp < 0)

563

719

            return node(n.getVal(),

564

720

                        addUpdate(n.getLeft(), x, added_new_entry),

565

 

                        n.getRight()).rebalance();

 

721

                        n.getRight(),

 

722

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

566

723

          else if(cmp > 0)

567

724

            return node(n.getVal(),

568

725

                        n.getLeft(),

569

 

                        addUpdate(n.getRight(), x, added_new_entry)).rebalance();

 

726

                        addUpdate(n.getRight(), x, added_new_entry),

 

727

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

570

728

          else

571

729

            {

572

730

              added_new_entry = false;

573

 

              return node(x, n.getLeft(), n.getRight());

 

731

              return node(x, n.getLeft(), n.getRight(), impl.get_accumOps());

574

732

            }

575

733

        }

576

734

    }

579

737

     *  simultaneously constructing a new (balanced) node that doesn't

580

738

     *  contain the minimum.

581

739

     */

582

 

    static std::pair<node, Val> find_and_remove_min(const node &n)

 

740

    static std::pair<node, Val> find_and_remove_min(const node &n,

 

741

                                                    const AccumOps &accumOps)

583

742

    {

584

743

      if(n.getLeft().isValid())

585

744

      {

586

 

        std::pair<node, Val> tmp = find_and_remove_min(n.getLeft());

 

745

        std::pair<node, Val> tmp = find_and_remove_min(n.getLeft(), accumOps);

587

746

          return std::pair<node, Val>(node(n.getVal(),

588

 

                                           tmp.first, n.getRight()).rebalance(),

 

747

                                           tmp.first, n.getRight(),

 

748

                                           accumOps).rebalance(accumOps),

589

749

                                      tmp.second);

590

750

      }

591

751

      else

597

757

    /** Join together two trees; every element of l must be less than

598

758

     *  every element of r.

599

759

     */

600

 

    static node splice_trees(const node &l, const node &r)

 

760

    static node splice_trees(const node &l, const node &r,

 

761

                             const AccumOps &accumOps)

601

762

    {

602

763

      if(r.empty())

603

764

        return l;

604

765

      else if(l.empty())

605

766

        return r;

606

767

 

607

 

      std::pair<node, Val> tmp = find_and_remove_min(r);

608

 

      return node(tmp.second, l, tmp.first);

 

768

      std::pair<node, Val> tmp = find_and_remove_min(r, accumOps);

 

769

      return node(tmp.second, l, tmp.first, accumOps);

609

770

    }

610

771

 

611

772

    /** \return \b true if there exist elements x1 and x2 in n1 and n2

626

787

        return false;

627

788

      else

628

789

        {

629

 

          int cmp = value_compare(n1.getVal(), n2.getVal());

 

790

          int cmp = impl.get_value_compare()(n1.getVal(), n2.getVal());

630

791

 

631

792

          if(cmp < 0)

632

793

            return

659

820

        return false;

660

821

      else

661

822

        {

662

 

          int cmp = value_compare(n1.getVal(), n2.getVal());

 

823

          int cmp = impl.get_value_compare()(n1.getVal(), n2.getVal());

663

824

 

664

825

          if(cmp < 0)

665

826

            {

666

827

              // Strip the left subtree of n2.

667

828

              node n2repl = n2.getLeft().empty()

668

 

                ? n2 : node(n2.getVal(), node(), n2.getRight());

 

829

                ? n2 : node(n2.getVal(), node(), n2.getRight(),

 

830

                            impl.get_accumOps());

669

831

 

670

832

              return node_contains(n1, n2.getLeft(), f) &&

671

833

                node_contains(n1.getRight(), n2repl, f);

674

836

            {

675

837

              // Strip the right subtree of n2.

676

838

              node n2repl = n2.getRight().empty()

677

 

                ? n2 : node(n2.getVal(), n2.getLeft(), node());

 

839

                ? n2 : node(n2.getVal(), n2.getLeft(), node(),

 

840

                            impl.get_accumOps());

678

841

 

679

842

              return node_contains(n1, n2.getRight(), f) &&

680

843

                node_contains(n1.getLeft(), n2repl, f);

695

858

        return n;

696

859

      else

697

860

        {

698

 

          const int cmp = value_compare(x, n.getVal());

 

861

          const int cmp = impl.get_value_compare()(x, n.getVal());

699

862

 

700

863

          if(cmp < 0)

701

864

            return node(n.getVal(),

702

865

                        remove(n.getLeft(), x, removed_anything),

703

 

                        n.getRight()).rebalance();

 

866

                        n.getRight(),

 

867

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

704

868

          else if(cmp > 0)

705

869

            return node(n.getVal(),

706

870

                        n.getLeft(),

707

 

                        remove(n.getRight(), x, removed_anything)).rebalance();

 

871

                        remove(n.getRight(), x, removed_anything),

 

872

                        impl.get_accumOps()).rebalance(impl.get_accumOps());

708

873

          else // found an equivalent node:

709

874

            {

710

875

              removed_anything = true;

711

 

              return splice_trees(n.getLeft(), n.getRight());

 

876

              return splice_trees(n.getLeft(), n.getRight(), impl.get_accumOps());

712

877

            }

713

878

        }

714

879

    }

715

880

 

716

 

    set(const node &n, const Compare &_value_compare)

717

 

      :value_compare(_value_compare), root(n)

 

881

    set(const node &n, const Compare &value_compare, const AccumOps &accumOps)

 

882

      : impl(n, value_compare, accumOps)

718

883

    {

719

884

    }

720

885

 

729

894

    };

730

895

  public:

731

896

    /** Construct an empty tree. */

732

 

    set(const Compare &_value_compare = Compare())

733

 

      : value_compare(_value_compare)

 

897

    set(const Compare &value_compare = Compare(),

 

898

        const AccumOps &accumOps = AccumOps())

 

899

      : impl(node(), value_compare, accumOps)

734

900

    {

735

901

    }

736

902

 

738

904

    template<typename Op>

739

905

    bool for_each(const Op &o) const

740

906

    {

741

 

      return root.for_each(o);

 

907

      return impl.get_root().for_each(o);

742

908

    }

743

909

 

744

910

    /** Insert an element into a tree, returning a new tree.  This is

748

914

     */

749

915

    static set add(const set &old, const Val &x, bool &added_anything)

750

916

    {

751

 

      return set(old.add(old.root, x, added_anything), old.value_compare);

 

917

      return set(old.add(old.impl.get_root(), x, added_anything),

 

918

                 old.impl.get_value_compare(),

 

919

                 old.impl.get_accumOps());

752

920

    }

753

921

 

754

922

    static set add(const set &old, const Val &x)

760

928

    /** Like add, but updates existing equivalent elements. */

761

929

    static set addUpdate(const set &old, const Val &x, bool &added_new_entry)

762

930

    {

763

 

      return set(old.addUpdate(old.root, x, added_new_entry), old.value_compare);

 

931

      return set(old.addUpdate(old.impl.get_root(), x, added_new_entry),

 

932

                 old.impl.get_value_compare(),

 

933

                 old.impl.get_accumOps());

764

934

    }

765

935

 

766

936

    static set addUpdate(const set &old, const Val &x)

773

943

    static set remove(const set &old, const Val &x, bool &removed_anything)

774

944

    {

775

945

      removed_anything = false;

776

 

      return set(old.remove(old.root, x, removed_anything), old.value_compare);

 

946

      return set(old.remove(old.impl.get_root(), x, removed_anything),

 

947

                 old.impl.get_value_compare(),

 

948

                 old.impl.get_accumOps());

777

949

    }

778

950

 

779

951

    static set remove(const set &old, const Val &x)

789

961

    template<typename F>

790

962

    bool intersects(const set &other, const F &f) const

791

963

    {

792

 

      return nodes_intersect(root, other.root, f);

 

964

      return nodes_intersect(impl.get_root(), other.impl.get_root(), f);

793

965

    }

794

966

 

795

967

    /** \return \b true if this set intersects the given set. */

796

968

    bool intersects(const set &other) const

797

969

    {

798

 

      return nodes_intersect(root, other.root, universal_relation<Val>());

 

970

      return nodes_intersect(impl.get_root(), other.impl.get_root(), universal_relation<Val>());

799

971

    }

800

972

 

801

973

    /** \return \b true if each element of other is related by f to an

805

977

    template<typename F>

806

978

    bool contains(const set &other, const F &f) const

807

979

    {

808

 

      return node_contains(root, other.root, f);

 

980

      return node_contains(impl.get_root(), other.impl.get_root(), f);

809

981

    }

810

982

 

811

983

    /** \return \b true if each element in other has an equivalent

813

985

     */

814

986

    bool contains(const set &other) const

815

987

    {

816

 

      return node_contains(root, other.root, universal_relation<Val>());

 

988

      return node_contains(impl.get_root(), other.impl.get_root(), universal_relation<Val>());

817

989

    }

818

990

 

819

991

    /** Do an "in-place" update of this set, by replacing the root

824

996

    bool insert(const Val &x)

825

997

    {

826

998

      bool rval = true;

827

 

      root = add(root, x, rval);

 

999

      impl.set_root(add(impl.get_root(), x, rval));

828

1000

      return rval;

829

1001

    }

830

1002

 

832

1004

    bool insertUpdate(const Val &x)

833

1005

    {

834

1006

      bool rval = true;

835

 

      root = addUpdate(root, x, rval);

 

1007

      impl.set_root(addUpdate(impl.get_root(), x, rval));

836

1008

      return rval;

837

1009

    }

838

1010

 

843

1015

    bool erase(const Val &x)

844

1016

    {

845

1017

      bool rval = false;

846

 

      root = remove(root, x, rval);

 

1018

      impl.set_root(remove(impl.get_root(), x, rval));

847

1019

      return rval;

848

1020

    }

849

1021

 

852

1024

     */

853

1025

    node find_node(const Val &x) const

854

1026

    {

855

 

      node rval = root;

 

1027

      node rval = impl.get_root();

856

1028

 

857

1029

      while(rval.isValid())

858

1030

      {

859

 

        int cmp = value_compare(x, rval.getVal());

 

1031

        int cmp = impl.get_value_compare()(x, rval.getVal());

860

1032

 

861

1033

        if(cmp < 0)

862

1034

          rval = rval.getLeft();

869

1041

      return rval;

870

1042

    }

871

1043

 

 

1044

    /** \return the accumulated value for the entire set. */

 

1045

    AccumVal getAccumVal() const

 

1046

    {

 

1047

      if(impl.get_root().isValid())

 

1048

        return impl.get_root().getAccumVal();

 

1049

      else

 

1050

        return impl.get_accumOps().empty();

 

1051

    }

 

1052

 

872

1053

    /** \return \b true if this set contains the given value. */

873

1054

    bool contains(const Val &x) const

874

1055

    {

877

1058

 

878

1059

    const_iterator begin() const

879

1060

    {

880

 

      return const_iterator(root);

 

1061

      return const_iterator(impl.get_root());

881

1062

    }

882

1063

 

883

1064

    const_iterator end() const

887

1068

 

888

1069

    node get_root() const

889

1070

    {

890

 

      return root;

 

1071

      return impl.get_root();

891

1072

    }

892

1073

 

893

1074

    node get_minimum() const

894

1075

    {

895

 

      if(!root.isValid())

896

 

        return root;

 

1076

      if(!impl.get_root().isValid())

 

1077

        return impl.get_root();

897

1078

 

898

 

      node rval = root;

 

1079

      node rval = impl.get_root();

899

1080

      while(rval.getLeft().isValid())

900

1081

        rval = rval.getLeft();

901

1082

 

904

1085

 

905

1086

    size_type size() const

906

1087

    {

907

 

      return root.size();

 

1088

      return impl.get_root().size();

908

1089

    }

909

1090

 

910

1091

    int empty() const

911

1092

    {

912

 

      return root.empty();

 

1093

      return impl.get_root().empty();

913

1094

    }

914

1095

 

915

1096

    void dump(std::ostream &out) const

916

1097

    {

917

 

      root.dump(out);

 

1098

      impl.get_root().dump(out);

918

1099

    }

919

1100

 

920

1101

    /** Return a new set that does not share memory with the original

923

1104

     */

924

1105

    set clone() const

925

1106

    {

926

 

      return set(root.clone(), value_compare);

 

1107

      return set(impl.get_root().clone(impl.get_accumOps()),

 

1108

                 impl.get_value_compare(),

 

1109

                 impl.get_accumOps());

927

1110

    }

928

1111

  };

929

1112

 

954

1137

  /** \brief Write a set to a stream as a set (values are written with

955

1138

   *  operator<<).

956

1139

   */

957

 

  template<typename Val, typename Compare, int w>

958

 

  std::ostream &operator<<(std::ostream &out, const set<Val, Compare, w> &s)

 

1140

  template<typename Val, typename Compare, typename AccumVal, typename AccumOps, int w>

 

1141

  std::ostream &operator<<(std::ostream &out, const set<Val, Compare, AccumVal, AccumOps, w> &s)

959

1142

  {

960

1143

    out.put('{');

961

1144

    set_write_action<Val> act(out);

975

1158

     *  ensuring that this is the case. (i.e., if the comparator has

976

1159

     *  associated data, it should be identical in the two sets)

977

1160

     */

978

 

    template<typename Val, typename Compare, int w>

979

 

    class compare3_f<imm::set<Val, Compare, w> >

 

1161

    template<typename Val, typename Compare, typename AccumVal, typename AccumOps, int w>

 

1162

    class compare3_f<imm::set<Val, Compare, AccumVal, AccumOps, w> >

980

1163

    {

981

1164

    public:

982

 

      int operator()(const imm::set<Val, Compare, w> &s1,

983

 

                     const imm::set<Val, Compare, w> &s2) const

 

1165

      int operator()(const imm::set<Val, Compare, AccumVal, AccumOps, w> &s1,

 

1166

                     const imm::set<Val, Compare, AccumVal, AccumOps, w> &s2) const

984

1167

      {

985

1168

        return aptitude::util::lexicographical_compare3(s1.begin(), s1.end(),

986

1169

                                                        s2.begin(), s2.end());

991

1174

 

992

1175

namespace imm

993

1176

{

994

 

  template<typename Val, typename Compare, int w>

995

 

  inline bool operator<(const set<Val, Compare, w> &s1,

996

 

                        const set<Val, Compare, w> &s2)

 

1177

  template<typename Val, typename Compare, typename AccumVal, typename AccumOps, int w>

 

1178

  inline bool operator<(const set<Val, Compare, AccumVal, AccumOps, w> &s1,

 

1179

                        const set<Val, Compare, AccumVal, AccumOps, w> &s2)

997

1180

  {

998

1181

    return aptitude::util::compare3(s1, s2) < 0;

999

1182

  }

1000

1183

 

1001

1184

  /** Compare two sets for equality, with the same caveat as operator<. */

1002

 

  template<typename Val, typename Compare, int w>

1003

 

  inline bool operator==(const set<Val, Compare, w> &s1,

1004

 

                         const set<Val, Compare, w> &s2)

 

1185

  template<typename Val, typename Compare, typename AccumVal, typename AccumOps, int w>

 

1186

  inline bool operator==(const set<Val, Compare, AccumVal, AccumOps, w> &s1,

 

1187

                         const set<Val, Compare, AccumVal, AccumOps, w> &s2)

1005

1188

  {

1006

 

    typename set<Val, Compare, w>::const_iterator

 

1189

    typename set<Val, Compare, AccumVal, AccumOps, w>::const_iterator

1007

1190

      i1 = s1.begin(), i2 = s2.begin();

1008

1191

 

1009

1192

    while(i1 != s1.end() && i2 != s2.end())

1039

1222

    }

1040

1223

  };

1041

1224

 

1042

 

  template<typename Key, typename Val, typename Compare = aptitude::util::compare3_f<Key> >

 

1225

  template<typename Key, typename Val, typename Compare = aptitude::util::compare3_f<Key>,

 

1226

           typename AccumVal = nil_t,

 

1227

           typename AccumOps = nil_t>

1043

1228

  class map

1044

1229

  {

1045

1230

  public:

1046

1231

    typedef std::pair<Key, Val> binding_type;

1047

 

    typedef set<binding_type, key_compare<Key, Val, Compare> > mapping_type;

 

1232

    typedef set<binding_type, key_compare<Key, Val, Compare>, AccumVal, AccumOps> mapping_type;

1048

1233

    typedef typename mapping_type::const_iterator const_iterator;

1049

1234

    typedef typename mapping_type::size_type size_type;

1050

1235

    typedef typename mapping_type::node node;

1060

1245

    }

1061

1246

 

1062

1247

    /** Construct an empty map */

1063

 

    map(const Compare &value_compare = Compare())

1064

 

      :contents(mapping_type(key_compare<Key, Val, Compare>(value_compare)))

 

1248

    map(const Compare &value_compare = Compare(),

 

1249

        const AccumOps &accumOps = AccumOps())

 

1250

      :contents(mapping_type(key_compare<Key, Val, Compare>(value_compare),

 

1251

                             accumOps))

1065

1252

    {

1066

1253

    }

1067

1254

 

1108

1295

      return contents.find_node(binding_type(k, Val()));

1109

1296

    }

1110

1297

 

 

1298

    /** \return the accumulated value of the whole map. */

 

1299

    AccumVal getAccumVal() const

 

1300

    {

 

1301

      return contents.getAccumVal();

 

1302

    }

 

1303

 

1111

1304

    /** \return either the value of the mapping at k, or dflt if k is

1112

1305

     *  unbound.

1113

1306

     */

1251

1444

  /** \brief Write a map to a stream as a map (values are written with

1252

1445

   *  operator<<).

1253

1446

   */

1254

 

  template<typename Key, typename Val, typename Compare>

1255

 

  std::ostream &operator<<(std::ostream &out, const map<Key, Val, Compare> &m)

 

1447

  template<typename Key, typename Val, typename Compare, typename AccumVal, typename AccumOps>

 

1448

  std::ostream &operator<<(std::ostream &out, const map<Key, Val, Compare, AccumVal, AccumOps> &m)

1256

1449

  {

1257

1450

 

1258

1451

    out.put('{');

1274

1467

     *  ensuring that this is the case. (i.e., if the comparator has

1275

1468

     *  associated data, it should be identical in the two sets)

1276

1469

     */

1277

 

    template<typename Key, typename Val, typename Compare>

1278

 

    class compare3_f<imm::map<Key, Val, Compare> >

 

1470

    template<typename Key, typename Val, typename Compare, typename AccumVal, typename AccumOps>

 

1471

    class compare3_f<imm::map<Key, Val, Compare, AccumVal, AccumOps> >

1279

1472

    {

1280

1473

    public:

1281

 

      int operator()(const imm::map<Key, Val, Compare> &m1,

1282

 

                     const imm::map<Key, Val, Compare> &m2) const

 

1474

      int operator()(const imm::map<Key, Val, Compare, AccumVal, AccumOps> &m1,

 

1475

                     const imm::map<Key, Val, Compare, AccumVal, AccumOps> &m2) const

1283

1476

      {

1284

1477

        return compare3(m1.get_bindings(), m2.get_bindings());

1285

1478

      }

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1