~ubuntu-branches/debian/sid/3depict/sid : revision 1

1

2

// STL-like templated tree class.

3

//

4

5

// Distributed under the GNU General Public License version 3,

6

// (eventually to be changed to the Boost Software License).

7

8

/** The tree.hh library for C++ provides an STL-like container class

9

for n-ary trees, templated over the data stored at the

10

nodes. Various types of iterators are provided (post-order,

11

pre-order, and others). Where possible the access methods are

12

compatible with the STL or alternative algorithms are

13

available.

14

*/

15

16

17

#ifndef tree_hh_

18

#define tree_hh_

19

20

#include <cassert>

21

#include <memory>

22

#include <stdexcept>

23

#include <iterator>

24

#include <set>

25

#include <queue>

26

#include <algorithm>

27

28

// HP-style construct/destroy have gone from the standard,

29

// so here is a copy.

30

31

namespace kp {

32

33

template <class T1, class T2>

34

void constructor(T1* p, T2& val)

35

{

36

new ((void *) p) T1(val);

37

}

38

39

template <class T1>

40

void constructor(T1* p)

41

{

42

new ((void *) p) T1;

43

}

44

45

template <class T1>

46

void destructor(T1* p)

47

{

48

p->~T1();

49

}

50

51

}

52

53

/// A node in the tree, combining links to other nodes as well as the actual data.

54

template<class T>

55

class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.

56

public:

57

tree_node_<T> *parent;

58

tree_node_<T> *first_child, *last_child;

59

tree_node_<T> *prev_sibling, *next_sibling;

60

T data;

61

}; // __attribute__((packed));

62

63

template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >

64

class tree {

65

protected:

66

typedef tree_node_<T> tree_node;

67

public:

68

/// Value of the data stored at a node.

69

typedef T value_type;

70

71

class iterator_base;

72

class pre_order_iterator;

73

class post_order_iterator;

74

class sibling_iterator;

75

class leaf_iterator;

76

77

tree();

78

tree(const T&);

79

tree(const iterator_base&);

80

tree(const tree<T, tree_node_allocator>&);

81

~tree();

82

void operator=(const tree<T, tree_node_allocator>&);

83

84

/// Base class for iterators, only pointers stored, no traversal logic.

85

#ifdef __SGI_STL_PORT

86

class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {

87

#else

88

class iterator_base {

89

#endif

90

public:

91

typedef T value_type;

92

typedef T* pointer;

93

typedef T& reference;

94

typedef size_t size_type;

95

typedef ptrdiff_t difference_type;

96

typedef std::bidirectional_iterator_tag iterator_category;

97

98

iterator_base();

99

iterator_base(tree_node *);

100

101

T& operator*() const;

102

T* operator->() const;

103

104

/// When called, the next increment/decrement skips children of this node.

105

void skip_children();

106

void skip_children(bool skip);

107

/// Number of children of the node pointed to by the iterator.

108

unsigned int number_of_children() const;

109

110

sibling_iterator begin() const;

111

sibling_iterator end() const;

112

113

tree_node *node;

114

protected:

115

bool skip_current_children_;

116

};

117

118

/// Depth-first iterator, first accessing the node, then its children.

119

class pre_order_iterator : public iterator_base {

120

public:

121

pre_order_iterator();

122

pre_order_iterator(tree_node *);

123

pre_order_iterator(const iterator_base&);

124

pre_order_iterator(const sibling_iterator&);

125

126

bool operator==(const pre_order_iterator&) const;

127

bool operator!=(const pre_order_iterator&) const;

128

pre_order_iterator& operator++();

129

pre_order_iterator& operator--();

130

pre_order_iterator operator++(int);

131

pre_order_iterator operator--(int);

132

pre_order_iterator& operator+=(unsigned int);

133

pre_order_iterator& operator-=(unsigned int);

134

};

135

136

/// Depth-first iterator, first accessing the children, then the node itself.

137

class post_order_iterator : public iterator_base {

138

public:

139

post_order_iterator();

140

post_order_iterator(tree_node *);

141

post_order_iterator(const iterator_base&);

142

post_order_iterator(const sibling_iterator&);

143

144

bool operator==(const post_order_iterator&) const;

145

bool operator!=(const post_order_iterator&) const;

146

post_order_iterator& operator++();

147

post_order_iterator& operator--();

148

post_order_iterator operator++(int);

149

post_order_iterator operator--(int);

150

post_order_iterator& operator+=(unsigned int);

151

post_order_iterator& operator-=(unsigned int);

152

153

/// Set iterator to the first child as deep as possible down the tree.

154

void descend_all();

155

};

156

157

/// Breadth-first iterator, using a queue

158

class breadth_first_queued_iterator : public iterator_base {

159

public:

160

breadth_first_queued_iterator();

161

breadth_first_queued_iterator(tree_node *);

162

breadth_first_queued_iterator(const iterator_base&);

163

164

bool operator==(const breadth_first_queued_iterator&) const;

165

bool operator!=(const breadth_first_queued_iterator&) const;

166

breadth_first_queued_iterator& operator++();

167

breadth_first_queued_iterator operator++(int);

168

breadth_first_queued_iterator& operator+=(unsigned int);

169

170

private:

171

std::queue<tree_node *> traversal_queue;

172

};

173

174

/// The default iterator types throughout the tree class.

175

typedef pre_order_iterator iterator;

176

typedef breadth_first_queued_iterator breadth_first_iterator;

177

178

/// Iterator which traverses only the nodes at a given depth from the root.

179

class fixed_depth_iterator : public iterator_base {

180

public:

181

fixed_depth_iterator();

182

fixed_depth_iterator(tree_node *);

183

fixed_depth_iterator(const iterator_base&);

184

fixed_depth_iterator(const sibling_iterator&);

185

fixed_depth_iterator(const fixed_depth_iterator&);

186

187

bool operator==(const fixed_depth_iterator&) const;

188

bool operator!=(const fixed_depth_iterator&) const;

189

fixed_depth_iterator& operator++();

190

fixed_depth_iterator& operator--();

191

fixed_depth_iterator operator++(int);

192

fixed_depth_iterator operator--(int);

193

fixed_depth_iterator& operator+=(unsigned int);

194

fixed_depth_iterator& operator-=(unsigned int);

195

196

tree_node *top_node;

197

};

198

199

/// Iterator which traverses only the nodes which are siblings of each other.

200

class sibling_iterator : public iterator_base {

201

public:

202

sibling_iterator();

203

sibling_iterator(tree_node *);

204

sibling_iterator(const sibling_iterator&);

205

sibling_iterator(const iterator_base&);

206

207

bool operator==(const sibling_iterator&) const;

208

bool operator!=(const sibling_iterator&) const;

209

sibling_iterator& operator++();

210

sibling_iterator& operator--();

211

sibling_iterator operator++(int);

212

sibling_iterator operator--(int);

213

sibling_iterator& operator+=(unsigned int);

214

sibling_iterator& operator-=(unsigned int);

215

216

tree_node *range_first() const;

217

tree_node *range_last() const;

218

tree_node *parent_;

219

private:

220

void set_parent_();

221

};

222

223

/// Iterator which traverses only the leaves.

224

class leaf_iterator : public iterator_base {

225

public:

226

leaf_iterator();

227

leaf_iterator(tree_node *, tree_node *top=0);

228

leaf_iterator(const sibling_iterator&);

229

leaf_iterator(const iterator_base&);

230

231

bool operator==(const leaf_iterator&) const;

232

bool operator!=(const leaf_iterator&) const;

233

leaf_iterator& operator++();

234

leaf_iterator& operator--();

235

leaf_iterator operator++(int);

236

leaf_iterator operator--(int);

237

leaf_iterator& operator+=(unsigned int);

238

leaf_iterator& operator-=(unsigned int);

239

private:

240

tree_node *top_node;

241

};

242

243

/// Return iterator to the beginning of the tree.

244

inline pre_order_iterator begin() const;

245

/// Return iterator to the end of the tree.

246

inline pre_order_iterator end() const;

247

/// Return post-order iterator to the beginning of the tree.

248

post_order_iterator begin_post() const;

249

/// Return post-order end iterator of the tree.

250

post_order_iterator end_post() const;

251

/// Return fixed-depth iterator to the first node at a given depth from the given iterator.

252

fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;

253

/// Return fixed-depth end iterator.

254

fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;

255

/// Return breadth-first iterator to the first node at a given depth.

256

breadth_first_queued_iterator begin_breadth_first() const;

257

/// Return breadth-first end iterator.

258

breadth_first_queued_iterator end_breadth_first() const;

259

/// Return sibling iterator to the first child of given node.

260

sibling_iterator begin(const iterator_base&) const;

261

/// Return sibling end iterator for children of given node.

262

sibling_iterator end(const iterator_base&) const;

263

/// Return leaf iterator to the first leaf of the tree.

264

leaf_iterator begin_leaf() const;

265

/// Return leaf end iterator for entire tree.

266

leaf_iterator end_leaf() const;

267

/// Return leaf iterator to the first leaf of the subtree at the given node.

268

leaf_iterator begin_leaf(const iterator_base& top) const;

269

/// Return leaf end iterator for the subtree at the given node.

270

leaf_iterator end_leaf(const iterator_base& top) const;

271

272

/// Return iterator to the parent of a node.

273

template<typename iter> static iter parent(iter);

274

/// Return iterator to the previous sibling of a node.

275

template<typename iter> iter previous_sibling(iter) const;

276

/// Return iterator to the next sibling of a node.

277

template<typename iter> iter next_sibling(iter) const;

278

/// Return iterator to the next node at a given depth.

279

template<typename iter> iter next_at_same_depth(iter) const;

280

281

/// Erase all nodes of the tree.

282

void clear();

283

/// Erase element at position pointed to by iterator, return incremented iterator.

284

template<typename iter> iter erase(iter);

285

/// Erase all children of the node pointed to by iterator.

286

void erase_children(const iterator_base&);

287

288

/// Insert empty node as last/first child of node pointed to by position.

289

template<typename iter> iter append_child(iter position);

290

template<typename iter> iter prepend_child(iter position);

291

/// Insert node as last/first child of node pointed to by position.

292

template<typename iter> iter append_child(iter position, const T& x);

293

template<typename iter> iter prepend_child(iter position, const T& x);

294

/// Append the node (plus its children) at other_position as last/first child of position.

295

template<typename iter> iter append_child(iter position, iter other_position);

296

template<typename iter> iter prepend_child(iter position, iter other_position);

297

/// Append the nodes in the from-to range (plus their children) as last/first children of position.

298

template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);

299

template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);

300

301

/// Short-hand to insert topmost node in otherwise empty tree.

302

pre_order_iterator set_head(const T& x);

303

/// Insert node as previous sibling of node pointed to by position.

304

template<typename iter> iter insert(iter position, const T& x);

305

/// Specialisation of previous member.

306

sibling_iterator insert(sibling_iterator position, const T& x);

307

/// Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.

308

template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);

309

/// Insert node as next sibling of node pointed to by position.

310

template<typename iter> iter insert_after(iter position, const T& x);

311

/// Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.

312

template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);

313

314

/// Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.

315

template<typename iter> iter replace(iter position, const T& x);

316

/// Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

317

template<typename iter> iter replace(iter position, const iterator_base& from);

318

/// Replace string of siblings (plus their children) with copy of a new string (with children); see above

319

sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,

320

sibling_iterator new_begin, sibling_iterator new_end);

321

322

/// Move all children of node at 'position' to be siblings, returns position.

323

template<typename iter> iter flatten(iter position);

324

/// Move nodes in range to be children of 'position'.

325

template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);

326

/// Move all child nodes of 'from' to be children of 'position'.

327

template<typename iter> iter reparent(iter position, iter from);

328

329

/// Replace node with a new node, making the old node a child of the new node.

330

template<typename iter> iter wrap(iter position, const T& x);

331

332

/// Move 'source' node (plus its children) to become the next sibling of 'target'.

333

template<typename iter> iter move_after(iter target, iter source);

334

/// Move 'source' node (plus its children) to become the previous sibling of 'target'.

335

template<typename iter> iter move_before(iter target, iter source);

336

sibling_iterator move_before(sibling_iterator target, sibling_iterator source);

337

/// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').

338

template<typename iter> iter move_ontop(iter target, iter source);

339

340

/// Merge with other tree, creating new branches and leaves only if they are not already present.

341

void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,

342

bool duplicate_leaves=false);

343

/// Sort (std::sort only moves values of nodes, this one moves children as well).

344

void sort(sibling_iterator from, sibling_iterator to, bool deep=false);

345

template<class StrictWeakOrdering>

346

void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);

347

/// Compare two ranges of nodes (compares nodes as well as tree structure).

348

template<typename iter>

349

bool equal(const iter& one, const iter& two, const iter& three) const;

350

template<typename iter, class BinaryPredicate>

351

bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;

352

template<typename iter>

353

bool equal_subtree(const iter& one, const iter& two) const;

354

template<typename iter, class BinaryPredicate>

355

bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;

356

/// Extract a new tree formed by the range of siblings plus all their children.

357

tree subtree(sibling_iterator from, sibling_iterator to) const;

358

void subtree(tree&, sibling_iterator from, sibling_iterator to) const;

359

/// Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).

360

void swap(sibling_iterator it);

361

/// Exchange two nodes (plus subtrees)

362

void swap(iterator, iterator);

363

364

/// Count the total number of nodes.

365

size_t size() const;

366

/// Count the total number of nodes below the indicated node (plus one).

367

size_t size(const iterator_base&) const;

368

/// Check if tree is empty.

369

bool empty() const;

370

/// Compute the depth to the root or to a fixed other iterator.

371

static int depth(const iterator_base&);

372

static int depth(const iterator_base&, const iterator_base&);

373

/// Determine the maximal depth of the tree. An empty tree has max_depth=-1.

374

int max_depth() const;

375

/// Determine the maximal depth of the tree with top node at the given position.

376

int max_depth(const iterator_base&) const;

377

/// Count the number of children of node at position.

378

static unsigned int number_of_children(const iterator_base&);

379

/// Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.

380

unsigned int number_of_siblings(const iterator_base&) const;

381

/// Determine whether node at position is in the subtrees with root in the range.

382

bool is_in_subtree(const iterator_base& position, const iterator_base& begin,

383

const iterator_base& end) const;

384

/// Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.

385

bool is_valid(const iterator_base&) const;

386

387

/// Determine the index of a node in the range of siblings to which it belongs.

388

unsigned int index(sibling_iterator it) const;

389

/// Inverse of 'index': return the n-th child of the node at position.

390

static sibling_iterator child(const iterator_base& position, unsigned int);

391

/// Return iterator to the sibling indicated by index

392

sibling_iterator sibling(const iterator_base& position, unsigned int);

393

394

/// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)

395

class iterator_base_less {

396

public:

397

bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,

398

const typename tree<T, tree_node_allocator>::iterator_base& two) const

399

{

400

return one.node < two.node;

401

}

402

};

403

tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid

404

private:

405

tree_node_allocator alloc_;

406

void head_initialise_();

407

void copy_(const tree<T, tree_node_allocator>& other);

408

409

/// Comparator class for two nodes of a tree (used for sorting and searching).

410

template<class StrictWeakOrdering>

411

class compare_nodes {

412

public:

413

compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};

414

415

bool operator()(const tree_node *a, const tree_node *b)

416

{

417

return comp_(a->data, b->data);

418

}

419

private:

420

StrictWeakOrdering comp_;

421

};

422

};

423

424

//template <class T, class tree_node_allocator>

425

//class iterator_base_less {

426

// public:

427

// bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,

428

// const typename tree<T, tree_node_allocator>::iterator_base& two) const

429

// {

430

// txtout << "operatorclass<" << one.node < two.node << std::endl;

431

// return one.node < two.node;

432

// }

433

//};

434

435

// template <class T, class tree_node_allocator>

436

// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,

437

// const typename tree<T, tree_node_allocator>::iterator& two)

438

// {

439

// txtout << "operator< " << one.node < two.node << std::endl;

440

// if(one.node < two.node) return true;

441

// return false;

442

// }

443

//

444

// template <class T, class tree_node_allocator>

445

// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,

446

// const typename tree<T, tree_node_allocator>::iterator& two)

447

// {

448

// txtout << "operator== " << one.node == two.node << std::endl;

449

// if(one.node == two.node) return true;

450

// return false;

451

// }

452

//

453

// template <class T, class tree_node_allocator>

454

// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,

455

// const typename tree<T, tree_node_allocator>::iterator_base& two)

456

// {

457

// txtout << "operator> " << one.node < two.node << std::endl;

458

// if(one.node > two.node) return true;

459

// return false;

460

// }

461

462

463

464

// Tree

465

466

template <class T, class tree_node_allocator>

467

tree<T, tree_node_allocator>::tree()

468

{

469

head_initialise_();

470

}

471

472

template <class T, class tree_node_allocator>

473

tree<T, tree_node_allocator>::tree(const T& x)

474

{

475

head_initialise_();

476

set_head(x);

477

}

478

479

template <class T, class tree_node_allocator>

480

tree<T, tree_node_allocator>::tree(const iterator_base& other)

481

{

482

head_initialise_();

483

set_head((*other));

484

replace(begin(), other);

485

}

486

487

template <class T, class tree_node_allocator>

488

tree<T, tree_node_allocator>::~tree()

489

{

490

clear();

491

alloc_.deallocate(head,1);

492

alloc_.deallocate(feet,1);

493

}

494

495

template <class T, class tree_node_allocator>

496

void tree<T, tree_node_allocator>::head_initialise_()

497

{

498

head = alloc_.allocate(1,0); // MSVC does not have default second argument

499

feet = alloc_.allocate(1,0);

500

501

head->parent=0;

502

head->first_child=0;

503

head->last_child=0;

504

head->prev_sibling=0; //head;

505

head->next_sibling=feet; //head;

506

507

feet->parent=0;

508

feet->first_child=0;

509

feet->last_child=0;

510

feet->prev_sibling=head;

511

feet->next_sibling=0;

512

}

513

514

template <class T, class tree_node_allocator>

515

void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)

516

{

517

copy_(other);

518

}

519

520

template <class T, class tree_node_allocator>

521

tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)

522

{

523

head_initialise_();

524

copy_(other);

525

}

526

527

template <class T, class tree_node_allocator>

528

void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)

529

{

530

clear();

531

pre_order_iterator it=other.begin(), to=begin();

532

while(it!=other.end()) {

533

to=insert(to, (*it));

534

it.skip_children();

535

++it;

536

}

537

to=begin();

538

it=other.begin();

539

while(it!=other.end()) {

540

to=replace(to, it);

541

to.skip_children();

542

it.skip_children();

543

++to;

544

++it;

545

}

546

}

547

548

template <class T, class tree_node_allocator>

549

void tree<T, tree_node_allocator>::clear()

550

{

551

if(head)

552

while(head->next_sibling!=feet)

553

erase(pre_order_iterator(head->next_sibling));

554

}

555

556

template<class T, class tree_node_allocator>

557

void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)

558

{

559

// std::cout << "erase_children " << it.node << std::endl;

560

if(it.node==0) return;

561

562

tree_node *cur=it.node->first_child;

563

tree_node *prev=0;

564

565

while(cur!=0) {

566

prev=cur;

567

cur=cur->next_sibling;

568

erase_children(pre_order_iterator(prev));

569

kp::destructor(&prev->data);

570

alloc_.deallocate(prev,1);

571

}

572

it.node->first_child=0;

573

it.node->last_child=0;

574

// std::cout << "exit" << std::endl;

575

}

576

577

template<class T, class tree_node_allocator>

578

template<class iter>

579

iter tree<T, tree_node_allocator>::erase(iter it)

580

{

581

tree_node *cur=it.node;

582

assert(cur!=head);

583

iter ret=it;

584

ret.skip_children();

585

++ret;

586

erase_children(it);

587

if(cur->prev_sibling==0) {

588

cur->parent->first_child=cur->next_sibling;

589

}

590

else {

591

cur->prev_sibling->next_sibling=cur->next_sibling;

592

}

593

if(cur->next_sibling==0) {

594

cur->parent->last_child=cur->prev_sibling;

595

}

596

else {

597

cur->next_sibling->prev_sibling=cur->prev_sibling;

598

}

599

600

kp::destructor(&cur->data);

601

alloc_.deallocate(cur,1);

602

return ret;

603

}

604

605

template <class T, class tree_node_allocator>

606

typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const

607

{

608

return pre_order_iterator(head->next_sibling);

609

}

610

611

template <class T, class tree_node_allocator>

612

typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const

613

{

614

return pre_order_iterator(feet);

615

}

616

617

template <class T, class tree_node_allocator>

618

typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const

619

{

620

return breadth_first_queued_iterator(head->next_sibling);

621

}

622

623

template <class T, class tree_node_allocator>

624

typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const

625

{

626

return breadth_first_queued_iterator();

627

}

628

629

template <class T, class tree_node_allocator>

630

typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const

631

{

632

tree_node *tmp=head->next_sibling;

633

if(tmp!=feet) {

634

while(tmp->first_child)

635

tmp=tmp->first_child;

636

}

637

return post_order_iterator(tmp);

638

}

639

640

template <class T, class tree_node_allocator>

641

typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const

642

{

643

return post_order_iterator(feet);

644

}

645

646

template <class T, class tree_node_allocator>

647

typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const

648

{

649

typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;

650

ret.top_node=pos.node;

651

652

tree_node *tmp=pos.node;

653

unsigned int curdepth=0;

654

while(curdepth<dp) { // go down one level

655

while(tmp->first_child==0) {

656

if(tmp->next_sibling==0) {

657

// try to walk up and then right again

658

do {

659

if(tmp==ret.top_node)

660

throw std::range_error("tree: begin_fixed out of range");

661

tmp=tmp->parent;

662

if(tmp==0)

663

throw std::range_error("tree: begin_fixed out of range");

664

--curdepth;

665

} while(tmp->next_sibling==0);

666

}

667

tmp=tmp->next_sibling;

668

}

669

tmp=tmp->first_child;

670

++curdepth;

671

}

672

673

ret.node=tmp;

674

return ret;

675

}

676

677

template <class T, class tree_node_allocator>

678

typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const

679

{

680

assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround

681

tree_node *tmp=pos.node;

682

unsigned int curdepth=1;

683

while(curdepth<dp) { // go down one level

684

while(tmp->first_child==0) {

685

tmp=tmp->next_sibling;

686

if(tmp==0)

687

throw std::range_error("tree: end_fixed out of range");

688

}

689

tmp=tmp->first_child;

690

++curdepth;

691

}

692

return tmp;

693

}

694

695

template <class T, class tree_node_allocator>

696

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const

697

{

698

assert(pos.node!=0);

699

if(pos.node->first_child==0) {

700

return end(pos);

701

}

702

return pos.node->first_child;

703

}

704

705

template <class T, class tree_node_allocator>

706

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const

707

{

708

sibling_iterator ret(0);

709

ret.parent_=pos.node;

710

return ret;

711

}

712

713

template <class T, class tree_node_allocator>

714

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const

715

{

716

tree_node *tmp=head->next_sibling;

717

if(tmp!=feet) {

718

while(tmp->first_child)

719

tmp=tmp->first_child;

720

}

721

return leaf_iterator(tmp);

722

}

723

724

template <class T, class tree_node_allocator>

725

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const

726

{

727

return leaf_iterator(feet);

728

}

729

730

template <class T, class tree_node_allocator>

731

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf(const iterator_base& top) const

732

{

733

tree_node *tmp=top.node;

734

while(tmp->first_child)

735

tmp=tmp->first_child;

736

return leaf_iterator(tmp, top.node);

737

}

738

739

template <class T, class tree_node_allocator>

740

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf(const iterator_base& top) const

741

{

742

return leaf_iterator(top.node, top.node);

743

}

744

745

template <class T, class tree_node_allocator>

746

template <typename iter>

747

iter tree<T, tree_node_allocator>::parent(iter position)

748

{

749

assert(position.node!=0);

750

return iter(position.node->parent);

751

}

752

753

template <class T, class tree_node_allocator>

754

template <typename iter>

755

iter tree<T, tree_node_allocator>::previous_sibling(iter position) const

756

{

757

assert(position.node!=0);

758

iter ret(position);

759

ret.node=position.node->prev_sibling;

760

return ret;

761

}

762

763

template <class T, class tree_node_allocator>

764

template <typename iter>

765

iter tree<T, tree_node_allocator>::next_sibling(iter position) const

766

{

767

assert(position.node!=0);

768

iter ret(position);

769

ret.node=position.node->next_sibling;

770

return ret;

771

}

772

773

template <class T, class tree_node_allocator>

774

template <typename iter>

775

iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const

776

{

777

// We make use of a temporary fixed_depth iterator to implement this.

778

779

typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp(position.node);

780

781

++tmp;

782

return iter(tmp);

783

784

// assert(position.node!=0);

785

// iter ret(position);

786

//

787

// if(position.node->next_sibling) {

788

// ret.node=position.node->next_sibling;

789

// }

790

// else {

791

// int relative_depth=0;

792

// upper:

793

// do {

794

// ret.node=ret.node->parent;

795

// if(ret.node==0) return ret;

796

// --relative_depth;

797

// } while(ret.node->next_sibling==0);

798

// lower:

799

// ret.node=ret.node->next_sibling;

800

// while(ret.node->first_child==0) {

801

// if(ret.node->next_sibling==0)

802

// goto upper;

803

// ret.node=ret.node->next_sibling;

804

// if(ret.node==0) return ret;

805

// }

806

// while(relative_depth<0 && ret.node->first_child!=0) {

807

// ret.node=ret.node->first_child;

808

// ++relative_depth;

809

// }

810

// if(relative_depth<0) {

811

// if(ret.node->next_sibling==0) goto upper;

812

// else goto lower;

813

// }

814

// }

815

// return ret;

816

}

817

818

template <class T, class tree_node_allocator>

819

template <typename iter>

820

iter tree<T, tree_node_allocator>::append_child(iter position)

821

{

822

assert(position.node!=head);

823

assert(position.node);

824

825

tree_node *tmp=alloc_.allocate(1,0);

826

kp::constructor(&tmp->data);

827

tmp->first_child=0;

828

tmp->last_child=0;

829

830

tmp->parent=position.node;

831

if(position.node->last_child!=0) {

832

position.node->last_child->next_sibling=tmp;

833

}

834

else {

835

position.node->first_child=tmp;

836

}

837

tmp->prev_sibling=position.node->last_child;

838

position.node->last_child=tmp;

839

tmp->next_sibling=0;

840

return tmp;

841

}

842

843

template <class T, class tree_node_allocator>

844

template <typename iter>

845

iter tree<T, tree_node_allocator>::prepend_child(iter position)

846

{

847

assert(position.node!=head);

848

assert(position.node);

849

850

tree_node *tmp=alloc_.allocate(1,0);

851

kp::constructor(&tmp->data);

852

tmp->first_child=0;

853

tmp->last_child=0;

854

855

tmp->parent=position.node;

856

if(position.node->first_child!=0) {

857

position.node->first_child->prev_sibling=tmp;

858

}

859

else {

860

position.node->last_child=tmp;

861

}

862

tmp->next_sibling=position.node->first_child;

863

position.node->prev_child=tmp;

864

tmp->prev_sibling=0;

865

return tmp;

866

}

867

868

template <class T, class tree_node_allocator>

869

template <class iter>

870

iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)

871

{

872

// If your program fails here you probably used 'append_child' to add the top

873

// node to an empty tree. From version 1.45 the top element should be added

874

// using 'insert'. See the documentation for further information, and sorry about

875

// the API change.

876

assert(position.node!=head);

877

assert(position.node);

878

879

tree_node* tmp = alloc_.allocate(1,0);

880

kp::constructor(&tmp->data, x);

881

tmp->first_child=0;

882

tmp->last_child=0;

883

884

tmp->parent=position.node;

885

if(position.node->last_child!=0) {

886

position.node->last_child->next_sibling=tmp;

887

}

888

else {

889

position.node->first_child=tmp;

890

}

891

tmp->prev_sibling=position.node->last_child;

892

position.node->last_child=tmp;

893

tmp->next_sibling=0;

894

return tmp;

895

}

896

897

template <class T, class tree_node_allocator>

898

template <class iter>

899

iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)

900

{

901

assert(position.node!=head);

902

assert(position.node);

903

904

tree_node* tmp = alloc_.allocate(1,0);

905

kp::constructor(&tmp->data, x);

906

tmp->first_child=0;

907

tmp->last_child=0;

908

909

tmp->parent=position.node;

910

if(position.node->first_child!=0) {

911

position.node->first_child->prev_sibling=tmp;

912

}

913

else {

914

position.node->last_child=tmp;

915

}

916

tmp->next_sibling=position.node->first_child;

917

position.node->first_child=tmp;

918

tmp->prev_sibling=0;

919

return tmp;

920

}

921

922

template <class T, class tree_node_allocator>

923

template <class iter>

924

iter tree<T, tree_node_allocator>::append_child(iter position, iter other)

925

{

926

assert(position.node!=head);

927

assert(position.node);

928

929

sibling_iterator aargh=append_child(position, value_type());

930

return replace(aargh, other);

931

}

932

933

template <class T, class tree_node_allocator>

934

template <class iter>

935

iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)

936

{

937

assert(position.node!=head);

938

assert(position.node);

939

940

sibling_iterator aargh=prepend_child(position, value_type());

941

return replace(aargh, other);

942

}

943

944

template <class T, class tree_node_allocator>

945

template <class iter>

946

iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)

947

{

948

assert(position.node!=head);

949

assert(position.node);

950

951

iter ret=from;

952

953

while(from!=to) {

954

insert_subtree(position.end(), from);

955

++from;

956

}

957

return ret;

958

}

959

960

template <class T, class tree_node_allocator>

961

template <class iter>

962

iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)

963

{

964

assert(position.node!=head);

965

assert(position.node);

966

967

iter ret=from;

968

969

while(from!=to) {

970

insert_subtree(position.begin(), from);

971

++from;

972

}

973

return ret;

974

}

975

976

template <class T, class tree_node_allocator>

977

typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)

978

{

979

assert(head->next_sibling==feet);

980

return insert(iterator(feet), x);

981

}

982

983

template <class T, class tree_node_allocator>

984

template <class iter>

985

iter tree<T, tree_node_allocator>::insert(iter position, const T& x)

986

{

987

if(position.node==0) {

988

position.node=feet; // Backward compatibility: when calling insert on a null node,

989

// insert before the feet.

990

}

991

tree_node* tmp = alloc_.allocate(1,0);

992

kp::constructor(&tmp->data, x);

993

tmp->first_child=0;

994

tmp->last_child=0;

995

996

tmp->parent=position.node->parent;

997

tmp->next_sibling=position.node;

998

tmp->prev_sibling=position.node->prev_sibling;

999

position.node->prev_sibling=tmp;

1000

1001

if(tmp->prev_sibling==0) {

1002

if(tmp->parent) // when inserting nodes at the head, there is no parent

1003

tmp->parent->first_child=tmp;

1004

}

1005

else

1006

tmp->prev_sibling->next_sibling=tmp;

1007

return tmp;

1008

}

1009

1010

template <class T, class tree_node_allocator>

1011

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)

1012

{

1013

tree_node* tmp = alloc_.allocate(1,0);

1014

kp::constructor(&tmp->data, x);

1015

tmp->first_child=0;

1016

tmp->last_child=0;

1017

1018

tmp->next_sibling=position.node;

1019

if(position.node==0) { // iterator points to end of a subtree

1020

tmp->parent=position.parent_;

1021

tmp->prev_sibling=position.range_last();

1022

tmp->parent->last_child=tmp;

1023

}

1024

else {

1025

tmp->parent=position.node->parent;

1026

tmp->prev_sibling=position.node->prev_sibling;

1027

position.node->prev_sibling=tmp;

1028

}

1029

1030

if(tmp->prev_sibling==0) {

1031

if(tmp->parent) // when inserting nodes at the head, there is no parent

1032

tmp->parent->first_child=tmp;

1033

}

1034

else

1035

tmp->prev_sibling->next_sibling=tmp;

1036

return tmp;

1037

}

1038

1039

template <class T, class tree_node_allocator>

1040

template <class iter>

1041

iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)

1042

{

1043

tree_node* tmp = alloc_.allocate(1,0);

1044

kp::constructor(&tmp->data, x);

1045

tmp->first_child=0;

1046

tmp->last_child=0;

1047

1048

tmp->parent=position.node->parent;

1049

tmp->prev_sibling=position.node;

1050

tmp->next_sibling=position.node->next_sibling;

1051

position.node->next_sibling=tmp;

1052

1053

if(tmp->next_sibling==0) {

1054

if(tmp->parent) // when inserting nodes at the head, there is no parent

1055

tmp->parent->last_child=tmp;

1056

}

1057

else {

1058

tmp->next_sibling->prev_sibling=tmp;

1059

}

1060

return tmp;

1061

}

1062

1063

template <class T, class tree_node_allocator>

1064

template <class iter>

1065

iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)

1066

{

1067

// insert dummy

1068

iter it=insert(position, value_type());

1069

// replace dummy with subtree

1070

return replace(it, subtree);

1071

}

1072

1073

template <class T, class tree_node_allocator>

1074

template <class iter>

1075

iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)

1076

{

1077

// insert dummy

1078

iter it=insert_after(position, value_type());

1079

// replace dummy with subtree

1080

return replace(it, subtree);

1081

}

1082

1083

// template <class T, class tree_node_allocator>

1084

// template <class iter>

1085

// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)

1086

// {

1087

// // insert dummy

1088

// iter it(insert(position, value_type()));

1089

// // replace dummy with subtree

1090

// return replace(it, subtree);

1091

// }

1092

1093

template <class T, class tree_node_allocator>

1094

template <class iter>

1095

iter tree<T, tree_node_allocator>::replace(iter position, const T& x)

1096

{

1097

kp::destructor(&position.node->data);

1098

kp::constructor(&position.node->data, x);

1099

return position;

1100

}

1101

1102

template <class T, class tree_node_allocator>

1103

template <class iter>

1104

iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)

1105

{

1106

assert(position.node!=head);

1107

tree_node *current_from=from.node;

1108

tree_node *start_from=from.node;

1109

tree_node *current_to =position.node;

1110

1111

// replace the node at position with head of the replacement tree at from

1112

// std::cout << "warning!" << position.node << std::endl;

1113

erase_children(position);

1114

// std::cout << "no warning!" << std::endl;

1115

tree_node* tmp = alloc_.allocate(1,0);

1116

kp::constructor(&tmp->data, (*from));

1117

tmp->first_child=0;

1118

tmp->last_child=0;

1119

if(current_to->prev_sibling==0) {

1120

if(current_to->parent!=0)

1121

current_to->parent->first_child=tmp;

1122

}

1123

else {

1124

current_to->prev_sibling->next_sibling=tmp;

1125

}

1126

tmp->prev_sibling=current_to->prev_sibling;

1127

if(current_to->next_sibling==0) {

1128

if(current_to->parent!=0)

1129

current_to->parent->last_child=tmp;

1130

}

1131

else {

1132

current_to->next_sibling->prev_sibling=tmp;

1133

}

1134

tmp->next_sibling=current_to->next_sibling;

1135

tmp->parent=current_to->parent;

1136

kp::destructor(&current_to->data);

1137

alloc_.deallocate(current_to,1);

1138

current_to=tmp;

1139

1140

// only at this stage can we fix 'last'

1141

tree_node *last=from.node->next_sibling;

1142

1143

pre_order_iterator toit=tmp;

1144

// copy all children

1145

do {

1146

assert(current_from!=0);

1147

if(current_from->first_child != 0) {

1148

current_from=current_from->first_child;

1149

toit=append_child(toit, current_from->data);

1150

}

1151

else {

1152

while(current_from->next_sibling==0 && current_from!=start_from) {

1153

current_from=current_from->parent;

1154

toit=parent(toit);

1155

assert(current_from!=0);

1156

}

1157

current_from=current_from->next_sibling;

1158

if(current_from!=last) {

1159

toit=append_child(parent(toit), current_from->data);

1160

}

1161

}

1162

} while(current_from!=last);

1163

1164

return current_to;

1165

}

1166

1167

template <class T, class tree_node_allocator>

1168

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(

1169

sibling_iterator orig_begin,

1170

sibling_iterator orig_end,

1171

sibling_iterator new_begin,

1172

sibling_iterator new_end)

1173

{

1174

tree_node *orig_first=orig_begin.node;

1175

tree_node *new_first=new_begin.node;

1176

tree_node *orig_last=orig_first;

1177

while((++orig_begin)!=orig_end)

1178

orig_last=orig_last->next_sibling;

1179

tree_node *new_last=new_first;

1180

while((++new_begin)!=new_end)

1181

new_last=new_last->next_sibling;

1182

1183

// insert all siblings in new_first..new_last before orig_first

1184

bool first=true;

1185

pre_order_iterator ret;

1186

while(1==1) {

1187

pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));

1188

if(first) {

1189

ret=tt;

1190

first=false;

1191

}

1192

if(new_first==new_last)

1193

break;

1194

new_first=new_first->next_sibling;

1195

}

1196

1197

// erase old range of siblings

1198

bool last=false;

1199

tree_node *next=orig_first;

1200

while(1==1) {

1201

if(next==orig_last)

1202

last=true;

1203

next=next->next_sibling;

1204

erase((pre_order_iterator)orig_first);

1205

if(last)

1206

break;

1207

orig_first=next;

1208

}

1209

return ret;

1210

}

1211

1212

template <class T, class tree_node_allocator>

1213

template <typename iter>

1214

iter tree<T, tree_node_allocator>::flatten(iter position)

1215

{

1216

if(position.node->first_child==0)

1217

return position;

1218

1219

tree_node *tmp=position.node->first_child;

1220

while(tmp) {

1221

tmp->parent=position.node->parent;

1222

tmp=tmp->next_sibling;

1223

}

1224

if(position.node->next_sibling) {

1225

position.node->last_child->next_sibling=position.node->next_sibling;

1226

position.node->next_sibling->prev_sibling=position.node->last_child;

1227

}

1228

else {

1229

position.node->parent->last_child=position.node->last_child;

1230

}

1231

position.node->next_sibling=position.node->first_child;

1232

position.node->next_sibling->prev_sibling=position.node;

1233

position.node->first_child=0;

1234

position.node->last_child=0;

1235

1236

return position;

1237

}

1238

1239

1240

template <class T, class tree_node_allocator>

1241

template <typename iter>

1242

iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)

1243

{

1244

tree_node *first=begin.node;

1245

tree_node *last=first;

1246

1247

assert(first!=position.node);

1248

1249

if(begin==end) return begin;

1250

// determine last node

1251

while((++begin)!=end) {

1252

last=last->next_sibling;

1253

}

1254

// move subtree

1255

if(first->prev_sibling==0) {

1256

first->parent->first_child=last->next_sibling;

1257

}

1258

else {

1259

first->prev_sibling->next_sibling=last->next_sibling;

1260

}

1261

if(last->next_sibling==0) {

1262

last->parent->last_child=first->prev_sibling;

1263

}

1264

else {

1265

last->next_sibling->prev_sibling=first->prev_sibling;

1266

}

1267

if(position.node->first_child==0) {

1268

position.node->first_child=first;

1269

position.node->last_child=last;

1270

first->prev_sibling=0;

1271

}

1272

else {

1273

position.node->last_child->next_sibling=first;

1274

first->prev_sibling=position.node->last_child;

1275

position.node->last_child=last;

1276

}

1277

last->next_sibling=0;

1278

1279

tree_node *pos=first;

1280

for(;;) {

1281

pos->parent=position.node;

1282

if(pos==last) break;

1283

pos=pos->next_sibling;

1284

}

1285

1286

return first;

1287

}

1288

1289

template <class T, class tree_node_allocator>

1290

template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)

1291

{

1292

if(from.node->first_child==0) return position;

1293

return reparent(position, from.node->first_child, end(from));

1294

}

1295

1296

template <class T, class tree_node_allocator>

1297

template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)

1298

{

1299

assert(position.node!=0);

1300

sibling_iterator fr=position, to=position;

1301

++to;

1302

iter ret = insert(position, x);

1303

reparent(ret, fr, to);

1304

return ret;

1305

}

1306

1307

template <class T, class tree_node_allocator>

1308

template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)

1309

{

1310

tree_node *dst=target.node;

1311

tree_node *src=source.node;

1312

assert(dst);

1313

assert(src);

1314

1315

if(dst==src) return source;

1316

if(dst->next_sibling)

1317

if(dst->next_sibling==src) // already in the right spot

1318

return source;

1319

1320

// take src out of the tree

1321

if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;

1322

else src->parent->first_child=src->next_sibling;

1323

if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;

1324

else src->parent->last_child=src->prev_sibling;

1325

1326

// connect it to the new point

1327

if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;

1328

else dst->parent->last_child=src;

1329

src->next_sibling=dst->next_sibling;

1330

dst->next_sibling=src;

1331

src->prev_sibling=dst;

1332

src->parent=dst->parent;

1333

return src;

1334

}

1335

1336

template <class T, class tree_node_allocator>

1337

template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)

1338

{

1339

tree_node *dst=target.node;

1340

tree_node *src=source.node;

1341

assert(dst);

1342

assert(src);

1343

1344

if(dst==src) return source;

1345

if(dst->prev_sibling)

1346

if(dst->prev_sibling==src) // already in the right spot

1347

return source;

1348

1349

// take src out of the tree

1350

if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;

1351

else src->parent->first_child=src->next_sibling;

1352

if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;

1353

else src->parent->last_child=src->prev_sibling;

1354

1355

// connect it to the new point

1356

if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;

1357

else dst->parent->first_child=src;

1358

src->prev_sibling=dst->prev_sibling;

1359

dst->prev_sibling=src;

1360

src->next_sibling=dst;

1361

src->parent=dst->parent;

1362

return src;

1363

}

1364

1365

// specialisation for sibling_iterators

1366

template <class T, class tree_node_allocator>

1367

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target,

1368

sibling_iterator source)

1369

{

1370

tree_node *dst=target.node;

1371

tree_node *src=source.node;

1372

tree_node *dst_prev_sibling;

1373

if(dst==0) { // must then be an end iterator

1374

dst_prev_sibling=target.parent_->last_child;

1375

assert(dst_prev_sibling);

1376

}

1377

else dst_prev_sibling=dst->prev_sibling;

1378

assert(src);

1379

1380

if(dst==src) return source;

1381

if(dst_prev_sibling)

1382

if(dst_prev_sibling==src) // already in the right spot

1383

return source;

1384

1385

// take src out of the tree

1386

if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;

1387

else src->parent->first_child=src->next_sibling;

1388

if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;

1389

else src->parent->last_child=src->prev_sibling;

1390

1391

// connect it to the new point

1392

if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;

1393

else target.parent_->first_child=src;

1394

src->prev_sibling=dst_prev_sibling;

1395

if(dst) {

1396

dst->prev_sibling=src;

1397

src->parent=dst->parent;

1398

}

1399

src->next_sibling=dst;

1400

return src;

1401

}

1402

1403

template <class T, class tree_node_allocator>

1404

template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)

1405

{

1406

tree_node *dst=target.node;

1407

tree_node *src=source.node;

1408

assert(dst);

1409

assert(src);

1410

1411

if(dst==src) return source;

1412

1413

// remember connection points

1414

tree_node *b_prev_sibling=dst->prev_sibling;

1415

tree_node *b_next_sibling=dst->next_sibling;

1416

tree_node *b_parent=dst->parent;

1417

1418

// remove target

1419

erase(target);

1420

1421

// take src out of the tree

1422

if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;

1423

else src->parent->first_child=src->next_sibling;

1424

if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;

1425

else src->parent->last_child=src->prev_sibling;

1426

1427

// connect it to the new point

1428

if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;

1429

else b_parent->first_child=src;

1430

if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;

1431

else b_parent->last_child=src;

1432

src->prev_sibling=b_prev_sibling;

1433

src->next_sibling=b_next_sibling;

1434

src->parent=b_parent;

1435

return src;

1436

}

1437

1438

template <class T, class tree_node_allocator>

1439

void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,

1440

sibling_iterator from1, sibling_iterator from2,

1441

bool duplicate_leaves)

1442

{

1443

sibling_iterator fnd;

1444

while(from1!=from2) {

1445

if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found

1446

if(from1.begin()==from1.end()) { // full depth reached

1447

if(duplicate_leaves)

1448

append_child(parent(to1), (*from1));

1449

}

1450

else { // descend further

1451

merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);

1452

}

1453

}

1454

else { // element missing

1455

insert_subtree(to2, from1);

1456

}

1457

++from1;

1458

}

1459

}

1460

1461

1462

template <class T, class tree_node_allocator>

1463

void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)

1464

{

1465

std::less<T> comp;

1466

sort(from, to, comp, deep);

1467

}

1468

1469

template <class T, class tree_node_allocator>

1470

template <class StrictWeakOrdering>

1471

void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,

1472

StrictWeakOrdering comp, bool deep)

1473

{

1474

if(from==to) return;

1475

// make list of sorted nodes

1476

// CHECK: if multiset stores equivalent nodes in the order in which they

1477

// are inserted, then this routine should be called 'stable_sort'.

1478

std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);

1479

sibling_iterator it=from, it2=to;

1480

while(it != to) {

1481

nodes.insert(it.node);

1482

++it;

1483

}

1484

// reassemble

1485

--it2;

1486

1487

// prev and next are the nodes before and after the sorted range

1488

tree_node *prev=from.node->prev_sibling;

1489

tree_node *next=it2.node->next_sibling;

1490

typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();

1491

if(prev==0) {

1492

if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent

1493

(*nit)->parent->first_child=(*nit);

1494

}

1495

else prev->next_sibling=(*nit);

1496

1497

--eit;

1498

while(nit!=eit) {

1499

(*nit)->prev_sibling=prev;

1500

if(prev)

1501

prev->next_sibling=(*nit);

1502

prev=(*nit);

1503

++nit;

1504

}

1505

// prev now points to the last-but-one node in the sorted range

1506

if(prev)

1507

prev->next_sibling=(*eit);

1508

1509

// eit points to the last node in the sorted range.

1510

(*eit)->next_sibling=next;

1511

(*eit)->prev_sibling=prev; // missed in the loop above

1512

if(next==0) {

1513

if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent

1514

(*eit)->parent->last_child=(*eit);

1515

}

1516

else next->prev_sibling=(*eit);

1517

1518

if(deep) { // sort the children of each node too

1519

sibling_iterator bcs(*nodes.begin());

1520

sibling_iterator ecs(*eit);

1521

++ecs;

1522

while(bcs!=ecs) {

1523

sort(begin(bcs), end(bcs), comp, deep);

1524

++bcs;

1525

}

1526

}

1527

}

1528

1529

template <class T, class tree_node_allocator>

1530

template <typename iter>

1531

bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const

1532

{

1533

std::equal_to<T> comp;

1534

return equal(one_, two, three_, comp);

1535

}

1536

1537

template <class T, class tree_node_allocator>

1538

template <typename iter>

1539

bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const

1540

{

1541

std::equal_to<T> comp;

1542

return equal_subtree(one_, two_, comp);

1543

}

1544

1545

template <class T, class tree_node_allocator>

1546

template <typename iter, class BinaryPredicate>

1547

bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const

1548

{

1549

pre_order_iterator one(one_), three(three_);

1550

1551

// if(one==two && is_valid(three) && three.number_of_children()!=0)

1552

// return false;

1553

while(one!=two && is_valid(three)) {

1554

if(!fun(*one,*three))

1555

return false;

1556

if(one.number_of_children()!=three.number_of_children())

1557

return false;

1558

++one;

1559

++three;

1560

}

1561

return true;

1562

}

1563

1564

template <class T, class tree_node_allocator>

1565

template <typename iter, class BinaryPredicate>

1566

bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const

1567

{

1568

pre_order_iterator one(one_), two(two_);

1569

1570

if(!fun(*one,*two)) return false;

1571

if(number_of_children(one)!=number_of_children(two)) return false;

1572

return equal(begin(one),end(one),begin(two),fun);

1573

}

1574

1575

template <class T, class tree_node_allocator>

1576

tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const

1577

{

1578

tree tmp;

1579

tmp.set_head(value_type());

1580

tmp.replace(tmp.begin(), tmp.end(), from, to);

1581

return tmp;

1582

}

1583

1584

template <class T, class tree_node_allocator>

1585

void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const

1586

{

1587

tmp.set_head(value_type());

1588

tmp.replace(tmp.begin(), tmp.end(), from, to);

1589

}

1590

1591

template <class T, class tree_node_allocator>

1592

size_t tree<T, tree_node_allocator>::size() const

1593

{

1594

size_t i=0;

1595

pre_order_iterator it=begin(), eit=end();

1596

while(it!=eit) {

1597

++i;

1598

++it;

1599

}

1600

return i;

1601

}

1602

1603

template <class T, class tree_node_allocator>

1604

size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const

1605

{

1606

size_t i=0;

1607

pre_order_iterator it=top, eit=top;

1608

eit.skip_children();

1609

++eit;

1610

while(it!=eit) {

1611

++i;

1612

++it;

1613

}

1614

return i;

1615

}

1616

1617

template <class T, class tree_node_allocator>

1618

bool tree<T, tree_node_allocator>::empty() const

1619

{

1620

pre_order_iterator it=begin(), eit=end();

1621

return (it==eit);

1622

}

1623

1624

template <class T, class tree_node_allocator>

1625

int tree<T, tree_node_allocator>::depth(const iterator_base& it)

1626

{

1627

tree_node* pos=it.node;

1628

assert(pos!=0);

1629

int ret=0;

1630

while(pos->parent!=0) {

1631

pos=pos->parent;

1632

++ret;

1633

}

1634

return ret;

1635

}

1636

1637

template <class T, class tree_node_allocator>

1638

int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root)

1639

{

1640

tree_node* pos=it.node;

1641

assert(pos!=0);

1642

int ret=0;

1643

while(pos->parent!=0 && pos!=root.node) {

1644

pos=pos->parent;

1645

++ret;

1646

}

1647

return ret;

1648

}

1649

1650

template <class T, class tree_node_allocator>

1651

int tree<T, tree_node_allocator>::max_depth() const

1652

{

1653

int maxd=-1;

1654

for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)

1655

maxd=std::max(maxd, max_depth(it));

1656

1657

return maxd;

1658

}

1659

1660

1661

template <class T, class tree_node_allocator>

1662

int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const

1663

{

1664

tree_node *tmp=pos.node;

1665

1666

if(tmp==0 || tmp==head || tmp==feet) return -1;

1667

1668

int curdepth=0, maxdepth=0;

1669

while(true) { // try to walk the bottom of the tree

1670

while(tmp->first_child==0) {

1671

if(tmp==pos.node) return maxdepth;

1672

if(tmp->next_sibling==0) {

1673

// try to walk up and then right again

1674

do {

1675

tmp=tmp->parent;

1676

if(tmp==0) return maxdepth;

1677

--curdepth;

1678

} while(tmp->next_sibling==0);

1679

}

1680

if(tmp==pos.node) return maxdepth;

1681

tmp=tmp->next_sibling;

1682

}

1683

tmp=tmp->first_child;

1684

++curdepth;

1685

maxdepth=std::max(curdepth, maxdepth);

1686

}

1687

}

1688

1689

template <class T, class tree_node_allocator>

1690

unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)

1691

{

1692

tree_node *pos=it.node->first_child;

1693

if(pos==0) return 0;

1694

1695

unsigned int ret=1;

1696

// while(pos!=it.node->last_child) {

1697

// ++ret;

1698

// pos=pos->next_sibling;

1699

// }

1700

while((pos=pos->next_sibling))

1701

++ret;

1702

return ret;

1703

}

1704

1705

template <class T, class tree_node_allocator>

1706

unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const

1707

{

1708

tree_node *pos=it.node;

1709

unsigned int ret=0;

1710

// count forward

1711

while(pos->next_sibling &&

1712

pos->next_sibling!=head &&

1713

pos->next_sibling!=feet) {

1714

++ret;

1715

pos=pos->next_sibling;

1716

}

1717

// count backward

1718

pos=it.node;

1719

while(pos->prev_sibling &&

1720

pos->prev_sibling!=head &&

1721

pos->prev_sibling!=feet) {

1722

++ret;

1723

pos=pos->prev_sibling;

1724

}

1725

1726

return ret;

1727

}

1728

1729

template <class T, class tree_node_allocator>

1730

void tree<T, tree_node_allocator>::swap(sibling_iterator it)

1731

{

1732

tree_node *nxt=it.node->next_sibling;

1733

if(nxt) {

1734

if(it.node->prev_sibling)

1735

it.node->prev_sibling->next_sibling=nxt;

1736

else

1737

it.node->parent->first_child=nxt;

1738

nxt->prev_sibling=it.node->prev_sibling;

1739

tree_node *nxtnxt=nxt->next_sibling;

1740

if(nxtnxt)

1741

nxtnxt->prev_sibling=it.node;

1742

else

1743

it.node->parent->last_child=it.node;

1744

nxt->next_sibling=it.node;

1745

it.node->prev_sibling=nxt;

1746

it.node->next_sibling=nxtnxt;

1747

}

1748

}

1749

1750

template <class T, class tree_node_allocator>

1751

void tree<T, tree_node_allocator>::swap(iterator one, iterator two)

1752

{

1753

// if one and two are adjacent siblings, use the sibling swap

1754

if(one.node->next_sibling==two.node) swap(one);

1755

else if(two.node->next_sibling==one.node) swap(two);

1756

else {

1757

tree_node *nxt1=one.node->next_sibling;

1758

tree_node *nxt2=two.node->next_sibling;

1759

tree_node *pre1=one.node->prev_sibling;

1760

tree_node *pre2=two.node->prev_sibling;

1761

tree_node *par1=one.node->parent;

1762

tree_node *par2=two.node->parent;

1763

1764

// reconnect

1765

one.node->parent=par2;

1766

one.node->next_sibling=nxt2;

1767

if(nxt2) nxt2->prev_sibling=one.node;

1768

else par2->last_child=one.node;

1769

one.node->prev_sibling=pre2;

1770

if(pre2) pre2->next_sibling=one.node;

1771

else par2->first_child=one.node;

1772

1773

two.node->parent=par1;

1774

two.node->next_sibling=nxt1;

1775

if(nxt1) nxt1->prev_sibling=two.node;

1776

else par1->last_child=two.node;

1777

two.node->prev_sibling=pre1;

1778

if(pre1) pre1->next_sibling=two.node;

1779

else par1->first_child=two.node;

1780

}

1781

}

1782

1783

// template <class BinaryPredicate>

1784

// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(

1785

// sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,

1786

// BinaryPredicate fun) const

1787

// {

1788

// assert(1==0); // this routine is not finished yet.

1789

// while(from!=to) {

1790

// if(fun(*subfrom, *from)) {

1791

//

1792

// }

1793

// }

1794

// return to;

1795

// }

1796

1797

template <class T, class tree_node_allocator>

1798

bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,

1799

const iterator_base& end) const

1800

{

1801

// FIXME: this should be optimised.

1802

pre_order_iterator tmp=begin;

1803

while(tmp!=end) {

1804

if(tmp==it) return true;

1805

++tmp;

1806

}

1807

return false;

1808

}

1809

1810

template <class T, class tree_node_allocator>

1811

bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const

1812

{

1813

if(it.node==0 || it.node==feet || it.node==head) return false;

1814

else return true;

1815

}

1816

1817

template <class T, class tree_node_allocator>

1818

unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const

1819

{

1820

unsigned int ind=0;

1821

if(it.node->parent==0) {

1822

while(it.node->prev_sibling!=head) {

1823

it.node=it.node->prev_sibling;

1824

++ind;

1825

}

1826

}

1827

else {

1828

while(it.node->prev_sibling!=0) {

1829

it.node=it.node->prev_sibling;

1830

++ind;

1831

}

1832

}

1833

return ind;

1834

}

1835

1836

template <class T, class tree_node_allocator>

1837

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling(const iterator_base& it, unsigned int num)

1838

{

1839

tree_node *tmp;

1840

if(it.node->parent==0) {

1841

tmp=head->next_sibling;

1842

while(num) {

1843

tmp = tmp->next_sibling;

1844

--num;

1845

}

1846

}

1847

else {

1848

tmp=it.node->parent->first_child;

1849

while(num) {

1850

assert(tmp!=0);

1851

tmp = tmp->next_sibling;

1852

--num;

1853

}

1854

}

1855

return tmp;

1856

}

1857

1858

1859

template <class T, class tree_node_allocator>

1860

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num)

1861

{

1862

tree_node *tmp=it.node->first_child;

1863

while(num--) {

1864

assert(tmp!=0);

1865

tmp=tmp->next_sibling;

1866

}

1867

return tmp;

1868

}

1869

1870

1871

1872

1873

// Iterator base

1874

1875

template <class T, class tree_node_allocator>

1876

tree<T, tree_node_allocator>::iterator_base::iterator_base()

1877

: node(0), skip_current_children_(false)

1878

{

1879

}

1880

1881

template <class T, class tree_node_allocator>

1882

tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)

1883

: node(tn), skip_current_children_(false)

1884

{

1885

}

1886

1887

template <class T, class tree_node_allocator>

1888

T& tree<T, tree_node_allocator>::iterator_base::operator*() const

1889

{

1890

return node->data;

1891

}

1892

1893

template <class T, class tree_node_allocator>

1894

T* tree<T, tree_node_allocator>::iterator_base::operator->() const

1895

{

1896

return &(node->data);

1897

}

1898

1899

template <class T, class tree_node_allocator>

1900

bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const

1901

{

1902

if(other.node!=this->node) return true;

1903

else return false;

1904

}

1905

1906

template <class T, class tree_node_allocator>

1907

bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const

1908

{

1909

if(other.node==this->node) return true;

1910

else return false;

1911

}

1912

1913

template <class T, class tree_node_allocator>

1914

bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const

1915

{

1916

if(other.node!=this->node) return true;

1917

else return false;

1918

}

1919

1920

template <class T, class tree_node_allocator>

1921

bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const

1922

{

1923

if(other.node==this->node) return true;

1924

else return false;

1925

}

1926

1927

template <class T, class tree_node_allocator>

1928

bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const

1929

{

1930

if(other.node!=this->node) return true;

1931

else return false;

1932

}

1933

1934

template <class T, class tree_node_allocator>

1935

bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const

1936

{

1937

if(other.node==this->node) return true;

1938

else return false;

1939

}

1940

1941

template <class T, class tree_node_allocator>

1942

bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const

1943

{

1944

if(other.node!=this->node) return true;

1945

else return false;

1946

}

1947

1948

template <class T, class tree_node_allocator>

1949

bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const

1950

{

1951

if(other.node==this->node && other.top_node==this->top_node) return true;

1952

else return false;

1953

}

1954

1955

template <class T, class tree_node_allocator>

1956

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const

1957

{

1958

if(node->first_child==0)

1959

return end();

1960

1961

sibling_iterator ret(node->first_child);

1962

ret.parent_=this->node;

1963

return ret;

1964

}

1965

1966

template <class T, class tree_node_allocator>

1967

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const

1968

{

1969

sibling_iterator ret(0);

1970

ret.parent_=node;

1971

return ret;

1972

}

1973

1974

template <class T, class tree_node_allocator>

1975

void tree<T, tree_node_allocator>::iterator_base::skip_children()

1976

{

1977

skip_current_children_=true;

1978

}

1979

1980

template <class T, class tree_node_allocator>

1981

void tree<T, tree_node_allocator>::iterator_base::skip_children(bool skip)

1982

{

1983

skip_current_children_=skip;

1984

}

1985

1986

template <class T, class tree_node_allocator>

1987

unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const

1988

{

1989

tree_node *pos=node->first_child;

1990

if(pos==0) return 0;

1991

1992

unsigned int ret=1;

1993

while(pos!=node->last_child) {

1994

++ret;

1995

pos=pos->next_sibling;

1996

}

1997

return ret;

1998

}

1999

2000

2001

2002

// Pre-order iterator

2003

2004

template <class T, class tree_node_allocator>

2005

tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()

2006

: iterator_base(0)

2007

{

2008

}

2009

2010

template <class T, class tree_node_allocator>

2011

tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)

2012

: iterator_base(tn)

2013

{

2014

}

2015

2016

template <class T, class tree_node_allocator>

2017

tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)

2018

: iterator_base(other.node)

2019

{

2020

}

2021

2022

template <class T, class tree_node_allocator>

2023

tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)

2024

: iterator_base(other.node)

2025

{

2026

if(this->node==0) {

2027

if(other.range_last()!=0)

2028

this->node=other.range_last();

2029

else

2030

this->node=other.parent_;

2031

this->skip_children();

2032

++(*this);

2033

}

2034

}

2035

2036

template <class T, class tree_node_allocator>

2037

typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()

2038

{

2039

assert(this->node!=0);

2040

if(!this->skip_current_children_ && this->node->first_child != 0) {

2041

this->node=this->node->first_child;

2042

}

2043

else {

2044

this->skip_current_children_=false;

2045

while(this->node->next_sibling==0) {

2046

this->node=this->node->parent;

2047

if(this->node==0)

2048

return *this;

2049

}

2050

this->node=this->node->next_sibling;

2051

}

2052

return *this;

2053

}

2054

2055

template <class T, class tree_node_allocator>

2056

typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()

2057

{

2058

assert(this->node!=0);

2059

if(this->node->prev_sibling) {

2060

this->node=this->node->prev_sibling;

2061

while(this->node->last_child)

2062

this->node=this->node->last_child;

2063

}

2064

else {

2065

this->node=this->node->parent;

2066

if(this->node==0)

2067

return *this;

2068

}

2069

return *this;

2070

}

2071

2072

template <class T, class tree_node_allocator>

2073

typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)

2074

{

2075

pre_order_iterator copy = *this;

2076

++(*this);

2077

return copy;

2078

}

2079

2080

template <class T, class tree_node_allocator>

2081

typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)

2082

{

2083

pre_order_iterator copy = *this;

2084

--(*this);

2085

return copy;

2086

}

2087

2088

template <class T, class tree_node_allocator>

2089

typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)

2090

{

2091

while(num>0) {

2092

++(*this);

2093

--num;

2094

}

2095

return (*this);

2096

}

2097

2098

template <class T, class tree_node_allocator>

2099

typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)

2100

{

2101

while(num>0) {

2102

--(*this);

2103

--num;

2104

}

2105

return (*this);

2106

}

2107

2108

2109

2110

// Post-order iterator

2111

2112

template <class T, class tree_node_allocator>

2113

tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()

2114

: iterator_base(0)

2115

{

2116

}

2117

2118

template <class T, class tree_node_allocator>

2119

tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)

2120

: iterator_base(tn)

2121

{

2122

}

2123

2124

template <class T, class tree_node_allocator>

2125

tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)

2126

: iterator_base(other.node)

2127

{

2128

}

2129

2130

template <class T, class tree_node_allocator>

2131

tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)

2132

: iterator_base(other.node)

2133

{

2134

if(this->node==0) {

2135

if(other.range_last()!=0)

2136

this->node=other.range_last();

2137

else

2138

this->node=other.parent_;

2139

this->skip_children();

2140

++(*this);

2141

}

2142

}

2143

2144

template <class T, class tree_node_allocator>

2145

typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()

2146

{

2147

assert(this->node!=0);

2148

if(this->node->next_sibling==0) {

2149

this->node=this->node->parent;

2150

this->skip_current_children_=false;

2151

}

2152

else {

2153

this->node=this->node->next_sibling;

2154

if(this->skip_current_children_) {

2155

this->skip_current_children_=false;

2156

}

2157

else {

2158

while(this->node->first_child)

2159

this->node=this->node->first_child;

2160

}

2161

}

2162

return *this;

2163

}

2164

2165

template <class T, class tree_node_allocator>

2166

typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()

2167

{

2168

assert(this->node!=0);

2169

if(this->skip_current_children_ || this->node->last_child==0) {

2170

this->skip_current_children_=false;

2171

while(this->node->prev_sibling==0)

2172

this->node=this->node->parent;

2173

this->node=this->node->prev_sibling;

2174

}

2175

else {

2176

this->node=this->node->last_child;

2177

}

2178

return *this;

2179

}

2180

2181

template <class T, class tree_node_allocator>

2182

typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)

2183

{

2184

post_order_iterator copy = *this;

2185

++(*this);

2186

return copy;

2187

}

2188

2189

template <class T, class tree_node_allocator>

2190

typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)

2191

{

2192

post_order_iterator copy = *this;

2193

--(*this);

2194

return copy;

2195

}

2196

2197

2198

template <class T, class tree_node_allocator>

2199

typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)

2200

{

2201

while(num>0) {

2202

++(*this);

2203

--num;

2204

}

2205

return (*this);

2206

}

2207

2208

template <class T, class tree_node_allocator>

2209

typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)

2210

{

2211

while(num>0) {

2212

--(*this);

2213

--num;

2214

}

2215

return (*this);

2216

}

2217

2218

template <class T, class tree_node_allocator>

2219

void tree<T, tree_node_allocator>::post_order_iterator::descend_all()

2220

{

2221

assert(this->node!=0);

2222

while(this->node->first_child)

2223

this->node=this->node->first_child;

2224

}

2225

2226

2227

// Breadth-first iterator

2228

2229

template <class T, class tree_node_allocator>

2230

tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()

2231

: iterator_base()

2232

{

2233

}

2234

2235

template <class T, class tree_node_allocator>

2236

tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)

2237

: iterator_base(tn)

2238

{

2239

traversal_queue.push(tn);

2240

}

2241

2242

template <class T, class tree_node_allocator>

2243

tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)

2244

: iterator_base(other.node)

2245

{

2246

traversal_queue.push(other.node);

2247

}

2248

2249

template <class T, class tree_node_allocator>

2250

bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const

2251

{

2252

if(other.node!=this->node) return true;

2253

else return false;

2254

}

2255

2256

template <class T, class tree_node_allocator>

2257

bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const

2258

{

2259

if(other.node==this->node) return true;

2260

else return false;

2261

}

2262

2263

template <class T, class tree_node_allocator>

2264

typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()

2265

{

2266

assert(this->node!=0);

2267

2268

// Add child nodes and pop current node

2269

sibling_iterator sib=this->begin();

2270

while(sib!=this->end()) {

2271

traversal_queue.push(sib.node);

2272

++sib;

2273

}

2274

traversal_queue.pop();

2275

if(traversal_queue.size()>0)

2276

this->node=traversal_queue.front();

2277

else

2278

this->node=0;

2279

return (*this);

2280

}

2281

2282

template <class T, class tree_node_allocator>

2283

typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)

2284

{

2285

breadth_first_queued_iterator copy = *this;

2286

++(*this);

2287

return copy;

2288

}

2289

2290

template <class T, class tree_node_allocator>

2291

typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)

2292

{

2293

while(num>0) {

2294

++(*this);

2295

--num;

2296

}

2297

return (*this);

2298

}

2299

2300

2301

2302

// Fixed depth iterator

2303

2304

template <class T, class tree_node_allocator>

2305

tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()

2306

: iterator_base()

2307

{

2308

}

2309

2310

template <class T, class tree_node_allocator>

2311

tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)

2312

: iterator_base(tn), top_node(0)

2313

{

2314

}

2315

2316

template <class T, class tree_node_allocator>

2317

tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)

2318

: iterator_base(other.node), top_node(0)

2319

{

2320

}

2321

2322

template <class T, class tree_node_allocator>

2323

tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)

2324

: iterator_base(other.node), top_node(0)

2325

{

2326

}

2327

2328

template <class T, class tree_node_allocator>

2329

tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)

2330

: iterator_base(other.node), top_node(other.top_node)

2331

{

2332

}

2333

2334

template <class T, class tree_node_allocator>

2335

bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const

2336

{

2337

if(other.node==this->node && other.top_node==top_node) return true;

2338

else return false;

2339

}

2340

2341

template <class T, class tree_node_allocator>

2342

bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const

2343

{

2344

if(other.node!=this->node || other.top_node!=top_node) return true;

2345

else return false;

2346

}

2347

2348

template <class T, class tree_node_allocator>

2349

typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()

2350

{

2351

assert(this->node!=0);

2352

2353

if(this->node->next_sibling) {

2354

this->node=this->node->next_sibling;

2355

}

2356

else {

2357

int relative_depth=0;

2358

upper:

2359

do {

2360

if(this->node==this->top_node) {

2361

this->node=0; // FIXME: return a proper fixed_depth end iterator once implemented

2362

return *this;

2363

}

2364

this->node=this->node->parent;

2365

if(this->node==0) return *this;

2366

--relative_depth;

2367

} while(this->node->next_sibling==0);

2368

lower:

2369

this->node=this->node->next_sibling;

2370

while(this->node->first_child==0) {

2371

if(this->node->next_sibling==0)

2372

goto upper;

2373

this->node=this->node->next_sibling;

2374

if(this->node==0) return *this;

2375

}

2376

while(relative_depth<0 && this->node->first_child!=0) {

2377

this->node=this->node->first_child;

2378

++relative_depth;

2379

}

2380

if(relative_depth<0) {

2381

if(this->node->next_sibling==0) goto upper;

2382

else goto lower;

2383

}

2384

}

2385

return *this;

2386

}

2387

2388

template <class T, class tree_node_allocator>

2389

typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()

2390

{

2391

assert(this->node!=0);

2392

2393

if(this->node->prev_sibling) {

2394

this->node=this->node->prev_sibling;

2395

}

2396

else {

2397

int relative_depth=0;

2398

upper:

2399

do {

2400

if(this->node==this->top_node) {

2401

this->node=0;

2402

return *this;

2403

}

2404

this->node=this->node->parent;

2405

if(this->node==0) return *this;

2406

--relative_depth;

2407

} while(this->node->prev_sibling==0);

2408

lower:

2409

this->node=this->node->prev_sibling;

2410

while(this->node->last_child==0) {

2411

if(this->node->prev_sibling==0)

2412

goto upper;

2413

this->node=this->node->prev_sibling;

2414

if(this->node==0) return *this;

2415

}

2416

while(relative_depth<0 && this->node->last_child!=0) {

2417

this->node=this->node->last_child;

2418

++relative_depth;

2419

}

2420

if(relative_depth<0) {

2421

if(this->node->prev_sibling==0) goto upper;

2422

else goto lower;

2423

}

2424

}

2425

return *this;

2426

2427

//

2428

//

2429

// assert(this->node!=0);

2430

// if(this->node->prev_sibling!=0) {

2431

// this->node=this->node->prev_sibling;

2432

// assert(this->node!=0);

2433

// if(this->node->parent==0 && this->node->prev_sibling==0) // head element

2434

// this->node=0;

2435

// }

2436

// else {

2437

// tree_node *par=this->node->parent;

2438

// do {

2439

// par=par->prev_sibling;

2440

// if(par==0) { // FIXME: need to keep track of this!

2441

// this->node=0;

2442

// return *this;

2443

// }

2444

// } while(par->last_child==0);

2445

// this->node=par->last_child;

2446

// }

2447

// return *this;

2448

}

2449

2450

template <class T, class tree_node_allocator>

2451

typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)

2452

{

2453

fixed_depth_iterator copy = *this;

2454

++(*this);

2455

return copy;

2456

}

2457

2458

template <class T, class tree_node_allocator>

2459

typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)

2460

{

2461

fixed_depth_iterator copy = *this;

2462

--(*this);

2463

return copy;

2464

}

2465

2466

template <class T, class tree_node_allocator>

2467

typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)

2468

{

2469

while(num>0) {

2470

--(*this);

2471

--(num);

2472

}

2473

return (*this);

2474

}

2475

2476

template <class T, class tree_node_allocator>

2477

typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)

2478

{

2479

while(num>0) {

2480

++(*this);

2481

--(num);

2482

}

2483

return *this;

2484

}

2485

2486

2487

// Sibling iterator

2488

2489

template <class T, class tree_node_allocator>

2490

tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()

2491

: iterator_base()

2492

{

2493

set_parent_();

2494

}

2495

2496

template <class T, class tree_node_allocator>

2497

tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)

2498

: iterator_base(tn)

2499

{

2500

set_parent_();

2501

}

2502

2503

template <class T, class tree_node_allocator>

2504

tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)

2505

: iterator_base(other.node)

2506

{

2507

set_parent_();

2508

}

2509

2510

template <class T, class tree_node_allocator>

2511

tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)

2512

: iterator_base(other), parent_(other.parent_)

2513

{

2514

}

2515

2516

template <class T, class tree_node_allocator>

2517

void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()

2518

{

2519

parent_=0;

2520

if(this->node==0) return;

2521

if(this->node->parent!=0)

2522

parent_=this->node->parent;

2523

}

2524

2525

template <class T, class tree_node_allocator>

2526

typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()

2527

{

2528

if(this->node)

2529

this->node=this->node->next_sibling;

2530

return *this;

2531

}

2532

2533

template <class T, class tree_node_allocator>

2534

typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()

2535

{

2536

if(this->node) this->node=this->node->prev_sibling;

2537

else {

2538

assert(parent_);

2539

this->node=parent_->last_child;

2540

}

2541

return *this;

2542

}

2543

2544

template <class T, class tree_node_allocator>

2545

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)

2546

{

2547

sibling_iterator copy = *this;

2548

++(*this);

2549

return copy;

2550

}

2551

2552

template <class T, class tree_node_allocator>

2553

typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)

2554

{

2555

sibling_iterator copy = *this;

2556

--(*this);

2557

return copy;

2558

}

2559

2560

template <class T, class tree_node_allocator>

2561

typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)

2562

{

2563

while(num>0) {

2564

++(*this);

2565

--num;

2566

}

2567

return (*this);

2568

}

2569

2570

template <class T, class tree_node_allocator>

2571

typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)

2572

{

2573

while(num>0) {

2574

--(*this);

2575

--num;

2576

}

2577

return (*this);

2578

}

2579

2580

template <class T, class tree_node_allocator>

2581

typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const

2582

{

2583

tree_node *tmp=parent_->first_child;

2584

return tmp;

2585

}

2586

2587

template <class T, class tree_node_allocator>

2588

typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const

2589

{

2590

return parent_->last_child;

2591

}

2592

2593

// Leaf iterator

2594

2595

template <class T, class tree_node_allocator>

2596

tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()

2597

: iterator_base(0), top_node(0)

2598

{

2599

}

2600

2601

template <class T, class tree_node_allocator>

2602

tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)

2603

: iterator_base(tn), top_node(top)

2604

{

2605

}

2606

2607

template <class T, class tree_node_allocator>

2608

tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)

2609

: iterator_base(other.node), top_node(0)

2610

{

2611

}

2612

2613

template <class T, class tree_node_allocator>

2614

tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)

2615

: iterator_base(other.node), top_node(0)

2616

{

2617

if(this->node==0) {

2618

if(other.range_last()!=0)

2619

this->node=other.range_last();

2620

else

2621

this->node=other.parent_;

2622

++(*this);

2623

}

2624

}

2625

2626

template <class T, class tree_node_allocator>

2627

typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()

2628

{

2629

assert(this->node!=0);

2630

if(this->node->first_child!=0) { // current node is no longer leaf (children got added)

2631

while(this->node->first_child)

2632

this->node=this->node->first_child;

2633

}

2634

else {

2635

while(this->node->next_sibling==0) {

2636

if (this->node->parent==0) return *this;

2637

this->node=this->node->parent;

2638

if (top_node != 0 && this->node==top_node) return *this;

2639

}

2640

this->node=this->node->next_sibling;

2641

while(this->node->first_child)

2642

this->node=this->node->first_child;

2643

}

2644

return *this;

2645

}

2646

2647

template <class T, class tree_node_allocator>

2648

typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()

2649

{

2650

assert(this->node!=0);

2651

while (this->node->prev_sibling==0) {

2652

if (this->node->parent==0) return *this;

2653

this->node=this->node->parent;

2654

if (top_node !=0 && this->node==top_node) return *this;

2655

}

2656

this->node=this->node->prev_sibling;

2657

while(this->node->last_child)

2658

this->node=this->node->last_child;

2659

return *this;

2660

}

2661

2662

template <class T, class tree_node_allocator>

2663

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)

2664

{

2665

leaf_iterator copy = *this;

2666

++(*this);

2667

return copy;

2668

}

2669

2670

template <class T, class tree_node_allocator>

2671

typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)

2672

{

2673

leaf_iterator copy = *this;

2674

--(*this);

2675

return copy;

2676

}

2677

2678

2679

template <class T, class tree_node_allocator>

2680

typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)

2681

{

2682

while(num>0) {

2683

++(*this);

2684

--num;

2685

}

2686

return (*this);

2687

}

2688

2689

template <class T, class tree_node_allocator>

2690

typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)

2691

{

2692

while(num>0) {

2693

--(*this);

2694

--num;

2695

}

2696

return (*this);

2697

}

2698

2699

#endif

2700

2701

// Local variables:

2702

// default-tab-width: 3

2703

// End: