~ubuntu-branches/ubuntu/natty/libofx/natty

<div class="qindex"><a class="qindex" href="main.html">Main Page</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a></div>

<a class="el" href="dir_000003.html">libofx-0.8.0</a> / <a class="el" href="dir_000004.html">lib</a></div>

<h1>fx-0.8.0/lib/tree.hh</h1><div class="fragment"><pre class="fragment">00001 /*

00002

00003 $Id: tree.hh,v 1.3 2004/04/09 06:51:45 benoitg Exp $

00004

00005 STL-like templated tree class.

00007

00008 See

00009

00010 http://www.damtp.cam.ac.uk/user/kp229/tree/

00011

00012 for more information and documentation. See the Changelog file for

00013 other credits.

00014

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

00016 it under the terms of the GNU General Public License as published by

00017 the Free Software Foundation; version 2.

00018

00019 This program is distributed in the hope that it will be useful,

00020 but WITHOUT ANY WARRANTY; without even the implied warranty of

00021 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

00022 GNU General Public License for more details.

00023

00024 You should have received a copy of the GNU General Public License

00025 along with this program; if not, write to the Free Software

00026 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

00027

00028 TODO: - 'Move' members are long overdue; will hopefully be incorporated in the

00029 next release.

00030 - Fixed depth iterators do not iterate over the entire range if there

00031 are 'holes' in the tree.

00032 - If a range uses const iter_base& as end iterator, things will

00033 inevitably go wrong, because upcast from iter_base to a non-sibling_iter

00034 is incorrect. This upcast should be removed (and then all illegal uses

00035 as previously in 'equal' will be flagged by the compiler). This requires

00036 new copy constructors though.

00037 - There's a bug in replace(sibling_iterator, ...) when the ranges

00038 sit next to each other. Turned up in append_child(iter,iter)

00039 but has been avoided now.

00040 - "std::operator<" does not work correctly on our iterators, and for some

00041 reason a globally defined template operator< did not get picked up.

00042 Using a comparison class now, but this should be investigated.

00043 */

00044

00045 #ifndef tree_hh_

00046 #define tree_hh_

00047

00048 #include <cassert>

00049 #include <memory>

00050 #include <stdexcept>

00051 #include <iterator>

00052 #include <set>

00053

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

00055 // so here is a copy.

00056

00057 namespace kp {

00058

00059 template <class T1, class T2>

00060 inline void constructor(T1* p, T2& val)

00061 {

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

00063 }

00064

00065 template <class T1>

00066 inline void constructor(T1* p)

00067 {

00068 new ((void *) p) T1;

00069 }

00070

00071 template <class T1>

00072 inline void kp::destructor(T1* p)

00073 {

00074 p->~T1();

00075 }

00076

00077 };

00078

00079 template<class T>

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

00081 public:

00082 tree_node_<T> *parent;

00083 tree_node_<T> *first_child, *last_child;

00084 tree_node_<T> *prev_sibling, *next_sibling;

00085 T data;

00086 };

00087

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

00089 class tree {

00090 protected:

100

00091 typedef tree_node_<T> tree_node;

101

00092 public:

102

00093 typedef T value_type;

103

00094

104

00095 class iterator_base;

105

00096 class pre_order_iterator;

106

00097 class post_order_iterator;

107

00098 class sibling_iterator;

108

00099

109

00100 tree();

110

00101 tree(const T&);

111

00102 tree(const iterator_base&);

112

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

113

00104 ~tree();

114

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

115

00106

116

00107 #ifdef __SGI_STL_PORT

117

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

118

00109 #else

119

00110 class iterator_base {

120

00111 #endif

121

00112 public:

122

00113 typedef T value_type;

123

00114 typedef T* pointer;

124

00115 typedef T& reference;

125

00116 typedef size_t size_type;

126

00117 typedef ptrdiff_t difference_type;

127

00118 typedef std::bidirectional_iterator_tag iterator_category;

128

00119

129

00120 iterator_base();

130

00121 iterator_base(tree_node *);

131

00122

132

00123 T& operator*() const;

133

00124 T* operator->() const;

134

00125

135

00126 void skip_children(); // do not iterate over children of this node

136

00127 unsigned int number_of_children() const;

137

00128

138

00129 sibling_iterator begin() const;

139

00130 sibling_iterator end() const;

140

00131

141

00132 tree_node *node;

142

00133 protected:

143

00134 bool skip_current_children_;

144

00135 };

145

00136

146

00137 class pre_order_iterator : public iterator_base {

147

00138 public:

148

00139 pre_order_iterator();

149

00140 pre_order_iterator(tree_node *);

150

00141 pre_order_iterator(const iterator_base&);

151

00142 pre_order_iterator(const sibling_iterator&);

152

00143

153

00144 bool operator==(const pre_order_iterator&) const;

154

00145 bool operator!=(const pre_order_iterator&) const;

155

00146 pre_order_iterator& operator++();

156

00147 pre_order_iterator& operator--();

157

00148 pre_order_iterator operator++(int);

158

00149 pre_order_iterator operator--(int);

159

00150 pre_order_iterator& operator+=(unsigned int);

160

00151 pre_order_iterator& operator-=(unsigned int);

161

00152 };

162

00153

163

00154 class post_order_iterator : public iterator_base {

164

00155 public:

165

00156 post_order_iterator();

166

00157 post_order_iterator(tree_node *);

167

00158 post_order_iterator(const iterator_base&);

168

00159 post_order_iterator(const sibling_iterator&);

169

00160

170

00161 bool operator==(const post_order_iterator&) const;

171

00162 bool operator!=(const post_order_iterator&) const;

172

00163 post_order_iterator& operator++();

173

00164 post_order_iterator& operator--();

174

00165 post_order_iterator operator++(int);

175

00166 post_order_iterator operator--(int);

176

00167 post_order_iterator& operator+=(unsigned int);

177

00168 post_order_iterator& operator-=(unsigned int);

178

00169

179

00170 void descend_all();

180

00171 };

181

00172

182

00173 typedef pre_order_iterator iterator;

183

00174

184

00175 class fixed_depth_iterator : public iterator_base {

185

00176 public:

186

00177 fixed_depth_iterator();

187

00178 fixed_depth_iterator(tree_node *);

188

00179 fixed_depth_iterator(const iterator_base&);

189

00180 fixed_depth_iterator(const sibling_iterator&);

190

00181 fixed_depth_iterator(const fixed_depth_iterator&);

191

00182

192

00183 bool operator==(const fixed_depth_iterator&) const;

193

00184 bool operator!=(const fixed_depth_iterator&) const;

194

00185 fixed_depth_iterator& operator++();

195

00186 fixed_depth_iterator& operator--();

196

00187 fixed_depth_iterator operator++(int);

197

00188 fixed_depth_iterator operator--(int);

198

00189 fixed_depth_iterator& operator+=(unsigned int);

199

00190 fixed_depth_iterator& operator-=(unsigned int);

200

00191

201

00192 tree_node *first_parent_;

202

00193 private:

203

00194 void set_first_parent_();

204

00195 void find_leftmost_parent_();

205

00196 };

206

00197

207

00198 class sibling_iterator : public iterator_base {

208

00199 public:

209

00200 sibling_iterator();

210

00201 sibling_iterator(tree_node *);

211

00202 sibling_iterator(const sibling_iterator&);

212

00203 sibling_iterator(const iterator_base&);

213

00204

214

00205 bool operator==(const sibling_iterator&) const;

215

00206 bool operator!=(const sibling_iterator&) const;

216

00207 sibling_iterator& operator++();

217

00208 sibling_iterator& operator--();

218

00209 sibling_iterator operator++(int);

219

00210 sibling_iterator operator--(int);

220

00211 sibling_iterator& operator+=(unsigned int);

221

00212 sibling_iterator& operator-=(unsigned int);

222

00213

223

00214 tree_node *range_first() const;

224

00215 tree_node *range_last() const;

225

00216 tree_node *parent_;

226

00217 private:

227

00218 void set_parent_();

228

00219 };

229

00220

230

00221 // begin/end of tree

231

00222 pre_order_iterator begin() const;

232

00223 pre_order_iterator end() const;

233

00224 post_order_iterator begin_post() const;

234

00225 post_order_iterator end_post() const;

235

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

236

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

237

00228 // begin/end of children of node

238

00229 sibling_iterator begin(const iterator_base&) const;

239

00230 sibling_iterator end(const iterator_base&) const;

240

00231

241

00232 template<typename iter> iter parent(iter) const;

242

00233 sibling_iterator previous_sibling(const iterator_base&) const;

243

00234 sibling_iterator next_sibling(const iterator_base&) const;

244

00235

245

00236 void clear();

246

00237 // erase element at position pointed to by iterator, increment iterator

247

00238 template<typename iter> iter erase(iter);

248

00239 // erase all children of the node pointed to by iterator

249

00240 void erase_children(const iterator_base&);

250

00241

251

00242 // insert node as last child of node pointed to by position (first one inserts empty node)

252

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

253

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

254

00245 // the following two append nodes plus their children

255

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

256

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

257

00248

258

00249 // short-hand to insert topmost node in otherwise empty tree

259

00250 pre_order_iterator set_head(const T& x);

260

00251 // insert node as previous sibling of node pointed to by position

261

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

262

00253 // specialisation: insert node as previous sibling of node pointed to by position

263

00254 //pre_order_iterator insert(sibling_iterator position, const T& x);

264

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

265

00256 // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position

266

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

267

00258 // insert node as next sibling of node pointed to by position

268

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

269

00260

270

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

271

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

272

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

273

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

274

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

275

00266 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,

276

00267 sibling_iterator new_begin, sibling_iterator new_end);

277

00268

278

00269 // move all children of node at 'position' to be siblings, returns position

279

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

280

00271 // move nodes in range to be children of 'position'

281

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

282

00273 // ditto, the range being all children of the 'from' node

283

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

284

00275

285

00276 // new style move members, moving nodes plus children to a different

286

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

287

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

288

00279 template<typename iter> iter move_below(iter target, iter source);

289

00280

290

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

291

00282 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,

292

00283 bool duplicate_leaves=false);

293

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

294

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

295

00286 template<class StrictWeakOrdering>

296

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

297

00288 // compare two ranges of nodes (compares nodes as well as tree structure)

298

00289 template<typename iter>

299

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

300

00291 template<typename iter, class BinaryPredicate>

301

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

302

00293 template<typename iter>

303

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

304

00295 template<typename iter, class BinaryPredicate>

305

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

306

00297 // extract a new tree formed by the range of siblings plus all their children

307

00298 tree subtree(sibling_iterator from, sibling_iterator to) const;

308

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

309

00300 // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)

310

00301 void swap(sibling_iterator it);

311

00302 // find a subtree

312

00303 // template<class BinaryPredicate>

313

00304 // iterator find_subtree(sibling_iterator, sibling_iterator, iterator from, iterator to, BinaryPredicate) const;

314

00305

315

00306 // count the total number of nodes

316

00307 int size() const;

317

00308 // check if tree is empty

318

00309 bool empty() const;

319

00310 // compute the depth to the root

320

00311 int depth(const iterator_base&) const;

321

00312 // count the number of children of node at position

322

00313 unsigned int number_of_children(const iterator_base&) const;

323

00314 // count the number of 'next' siblings of node at iterator

324

00315 unsigned int number_of_siblings(const iterator_base&) const;

325

00316 // determine whether node at position is in the subtrees with root in the range

326

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

327

00318 const iterator_base& end) const;

328

00319 // determine whether the iterator is an 'end' iterator and thus not actually

329

00320 // pointing to a node

330

00321 bool is_valid(const iterator_base&) const;

331

00322

332

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

333

00324 unsigned int index(sibling_iterator it) const;

334

00325 // inverse of 'index': return the n-th child of the node at position

335

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

336

00327

337

00328 class iterator_base_less {

338

00329 public:

339

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

340

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

341

00332 {

342

00333 return one.node < two.node;

343

00334 }

344

00335 };

345

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

346

00337 private:

347

00338 tree_node_allocator alloc_;

348

00339 void head_initialise_();

349

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

350

00341 template<class StrictWeakOrdering>

351

00342 class compare_nodes {

352

00343 public:

353

00344 bool operator()(const tree_node*, const tree_node *);

354

00345 };

355

00346 };

356

00347

357

00348 //template <class T, class tree_node_allocator>

358

00349 //class iterator_base_less {

359

00350 // public:

360

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

361

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

362

00353 // {

363

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

364

00355 // return one.node < two.node;

365

00356 // }

366

00357 //};

367

00358

368

00359 //template <class T, class tree_node_allocator>

369

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

370

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

371

00362 // {

372

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

373

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

374

00365 // return false;

375

00366 // }

376

00367

377

00368 template <class T, class tree_node_allocator>

378

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

379

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

380

00371 {

381

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

382

00373 return false;

383

00374 }

384

00375

385

00376

386

00377

387

00378 // Tree

388

00379

389

00380 template <class T, class tree_node_allocator>

390

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

391

00382 {

392

00383 head_initialise_();

393

00384 }

394

00385

395

00386 template <class T, class tree_node_allocator>

396

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

397

00388 {

398

00389 head_initialise_();

399

00390 set_head(x);

400

00391 }

401

00392

402

00393 template <class T, class tree_node_allocator>

403

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

404

00395 {

405

00396 head_initialise_();

406

00397 set_head((*other));

407

00398 replace(begin(), other);

408

00399 }

409

00400

410

00401 template <class T, class tree_node_allocator>

411

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

412

00403 {

413

00404 clear();

414

00405 alloc_.deallocate(head,1);

415

00406 alloc_.deallocate(feet,1);

416

00407 }

417

00408

418

00409 template <class T, class tree_node_allocator>

419

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

420

00411 {

421

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

422

00413 feet = alloc_.allocate(1,0);

423

00414

424

00415 head->parent=0;

425

00416 head->first_child=0;

426

00417 head->last_child=0;

427

00418 head->prev_sibling=0; //head;

428

00419 head->next_sibling=feet; //head;

429

00420

430

00421 feet->parent=0;

431

00422 feet->first_child=0;

432

00423 feet->last_child=0;

433

00424 feet->prev_sibling=head;

434

00425 feet->next_sibling=0;

435

00426 }

436

00427

437

00428 template <class T, class tree_node_allocator>

438

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

439

00430 {

440

00431 copy_(other);

441

00432 }

442

00433

443

00434 template <class T, class tree_node_allocator>

444

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

445

00436 {

446

00437 head_initialise_();

447

00438 copy_(other);

448

00439 }

449

00440

450

00441 template <class T, class tree_node_allocator>

451

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

452

00443 {

453

00444 clear();

454

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

455

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

456

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

457

00448 it.skip_children();

458

00449 ++it;

459

00450 }

460

00451 to=begin();

461

00452 it=other.begin();

462

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

463

00454 to=replace(to, it);

464

00455 to.skip_children();

465

00456 it.skip_children();

466

00457 ++to;

467

00458 ++it;

468

00459 }

469

00460 }

470

00461

471

00462 template <class T, class tree_node_allocator>

472

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

473

00464 {

474

00465 if(head)

475

00466 while(head->next_sibling!=feet)

476

00467 erase(pre_order_iterator(head->next_sibling));

477

00468 }

478

00469

479

00470 template<class T, class tree_node_allocator>

480

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

481

00472 {

482

00473 tree_node *cur=it.node->first_child;

483

00474 tree_node *prev=0;

484

00475

485

00476 while(cur!=0) {

486

00477 prev=cur;

487

00478 cur=cur->next_sibling;

488

00479 erase_children(pre_order_iterator(prev));

489

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

490

00481 alloc_.deallocate(prev,1);

491

00482 }

492

00483 it.node->first_child=0;

493

00484 it.node->last_child=0;

494

00485 }

495

00486

496

00487 template<class T, class tree_node_allocator>

497

00488 template<class iter>

498

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

499

00490 {

500

00491 tree_node *cur=it.node;

501

00492 assert(cur!=head);

502

00493 iter ret=it;

503

00494 ret.skip_children();

504

00495 ++ret;

505

00496 erase_children(it);

506

00497 if(cur->prev_sibling==0) {

507

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

508

00499 }

509

00500 else {

510

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

511

00502 }

512

00503 if(cur->next_sibling==0) {

513

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

514

00505 }

515

00506 else {

516

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

517

00508 }

518

00509

519

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

520

00511 alloc_.deallocate(cur,1);

521

00512 return ret;

522

00513 }

523

00514

524

00515 template <class T, class tree_node_allocator>

525

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

526

00517 {

527

00518 return pre_order_iterator(head->next_sibling);

528

00519 }

529

00520

530

00521 template <class T, class tree_node_allocator>

531

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

532

00523 {

533

00524 return pre_order_iterator(feet);

534

00525 }

535

00526

536

00527 template <class T, class tree_node_allocator>

537

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

538

00529 {

539

00530 tree_node *tmp=head->next_sibling;

540

00531 if(tmp!=feet) {

541

00532 while(tmp->first_child)

542

00533 tmp=tmp->first_child;

543

00534 }

544

00535 return post_order_iterator(tmp);

545

00536 }

546

00537

547

00538 template <class T, class tree_node_allocator>

548

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

549

00540 {

550

00541 return post_order_iterator(feet);

551

00542 }

552

00543

553

00544 template <class T, class tree_node_allocator>

554

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

555

00546 {

556

00547 tree_node *tmp=pos.node;

557

00548 unsigned int curdepth=0;

558

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

559

00550 while(tmp->first_child==0) {

560

00551 tmp=tmp->next_sibling;

561

00552 if(tmp==0)

562

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

563

00554 }

564

00555 tmp=tmp->first_child;

565

00556 ++curdepth;

566

00557 }

567

00558 return tmp;

568

00559 }

569

00560

570

00561 template <class T, class tree_node_allocator>

571

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

572

00563 {

573

00564 assert(1==0); // FIXME: not correct yet

574

00565 tree_node *tmp=pos.node;

575

00566 unsigned int curdepth=1;

576

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

577

00568 while(tmp->first_child==0) {

578

00569 tmp=tmp->next_sibling;

579

00570 if(tmp==0)

580

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

581

00572 }

582

00573 tmp=tmp->first_child;

583

00574 ++curdepth;

584

00575 }

585

00576 return tmp;

586

00577 }

587

00578

588

00579 template <class T, class tree_node_allocator>

589

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

590

00581 {

591

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

592

00583 return end(pos);

593

00584 }

594

00585 return pos.node->first_child;

595

00586 }

596

00587

597

00588 template <class T, class tree_node_allocator>

598

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

599

00590 {

600

00591 sibling_iterator ret(0);

601

00592 ret.parent_=pos.node;

602

00593 return ret;

603

00594 }

604

00595

605

00596 template <class T, class tree_node_allocator>

606

00597 template <typename iter>

607

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

608

00599 {

609

00600 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=0);

610

00601 return iter(<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent);

611

00602 }

612

00603

613

00604 template <class T, class tree_node_allocator>

614

00605 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::previous_sibling(const iterator_base& position) const

615

00606 {

616

00607 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=0);

617

00608 return sibling_iterator(<a class="code" href="messages_8cpp.html#a1">position</a>.node->prev_sibling);

618

00609 }

619

00610

620

00611 template <class T, class tree_node_allocator>

621

00612 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::next_sibling(const iterator_base& position) const

622

00613 {

623

00614 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=0);

624

00615 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling==0)

625

00616 return end(pre_order_iterator(<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent));

626

00617 else

627

00618 return sibling_iterator(<a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling);

628

00619 }

629

00620

630

00621 template <class T, class tree_node_allocator>

631

00622 template <typename iter>

632

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

633

00624 {

634

00625 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=head);

635

00626

636

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

637

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

638

00629 tmp->first_child=0;

639

00630 tmp->last_child=0;

640

00631

641

00632 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

642

00633 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child!=0) {

643

00634 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child->next_sibling=tmp;

644

00635 }

645

00636 else {

646

00637 <a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child=tmp;

647

00638 }

648

00639 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child;

649

00640 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child=tmp;

650

00641 tmp->next_sibling=0;

651

00642 return tmp;

652

00643 }

653

00644

654

00645 template <class T, class tree_node_allocator>

655

00646 template <class iter>

656

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

657

00648 {

658

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

659

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

660

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

661

00652 // the API change.

662

00653 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=head);

663

00654

664

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

665

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

666

00657 tmp->first_child=0;

667

00658 tmp->last_child=0;

668

00659

669

00660 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

670

00661 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child!=0) {

671

00662 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child->next_sibling=tmp;

672

00663 }

673

00664 else {

674

00665 <a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child=tmp;

675

00666 }

676

00667 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child;

677

00668 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child=tmp;

678

00669 tmp->next_sibling=0;

679

00670 return tmp;

680

00671 }

681

00672

682

00673 template <class T, class tree_node_allocator>

683

00674 template <class iter>

684

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

685

00676 {

686

00677 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=head);

687

00678

688

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

689

00680 return replace(aargh, other);

690

00681 }

691

00682

692

00683 template <class T, class tree_node_allocator>

693

00684 template <class iter>

694

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

695

00686 {

696

00687 iter ret=from;

697

00688

698

00689 while(from!=to) {

699

00690 insert_subtree(<a class="code" href="messages_8cpp.html#a1">position</a>.end(), from);

700

00691 ++from;

701

00692 }

702

00693 return ret;

703

00694 }

704

00695

705

00696 template <class T, class tree_node_allocator>

706

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

707

00698 {

708

00699 assert(head->next_sibling==feet);

709

00700 return insert(iterator(feet), x);

710

00701 }

711

00702

712

00703 template <class T, class tree_node_allocator>

713

00704 template <class iter>

714

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

715

00706 {

716

00707 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node==0) {

717

00708 <a class="code" href="messages_8cpp.html#a1">position</a>.node=feet; // Backward compatibility: when calling insert on a null node,

718

00709 // insert before the feet.

719

00710 }

720

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

721

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

722

00713 tmp->first_child=0;

723

00714 tmp->last_child=0;

724

00715

725

00716 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent;

726

00717 tmp->next_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

727

00718 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->prev_sibling;

728

00719 <a class="code" href="messages_8cpp.html#a1">position</a>.node->prev_sibling=tmp;

729

00720

730

00721 if(tmp->prev_sibling==0)

731

00722 tmp->parent->first_child=tmp;

732

00723 else

733

00724 tmp->prev_sibling->next_sibling=tmp;

734

00725 return tmp;

735

00726 }

736

00727

737

00728 template <class T, class tree_node_allocator>

738

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

739

00730 {

740

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

741

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

742

00733 tmp->first_child=0;

743

00734 tmp->last_child=0;

744

00735

745

00736 tmp->next_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

746

00737 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node==0) { // iterator points to end of a subtree

747

00738 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.parent_;

748

00739 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.range_last();

749

00740 tmp->parent->last_child=tmp;

750

00741 }

751

00742 else {

752

00743 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent;

753

00744 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->prev_sibling;

754

00745 <a class="code" href="messages_8cpp.html#a1">position</a>.node->prev_sibling=tmp;

755

00746 }

756

00747

757

00748 if(tmp->prev_sibling==0)

758

00749 tmp->parent->first_child=tmp;

759

00750 else

760

00751 tmp->prev_sibling->next_sibling=tmp;

761

00752 return tmp;

762

00753 }

763

00754

764

00755 template <class T, class tree_node_allocator>

765

00756 template <class iter>

766

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

767

00758 {

768

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

769

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

770

00761 tmp->first_child=0;

771

00762 tmp->last_child=0;

772

00763

773

00764 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent;

774

00765 tmp->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

775

00766 tmp->next_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling;

776

00767 <a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling=tmp;

777

00768

778

00769 if(tmp->next_sibling==0) {

779

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

780

00771 tmp->parent->last_child=tmp;

781

00772 }

782

00773 else {

783

00774 tmp->next_sibling->prev_sibling=tmp;

784

00775 }

785

00776 return tmp;

786

00777 }

787

00778

788

00779 template <class T, class tree_node_allocator>

789

00780 template <class iter>

790

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

791

00782 {

792

00783 // insert dummy

793

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

794

00785 // replace dummy with subtree

795

00786 return replace(it, subtree);

796

00787 }

797

00788

798

00789 // template <class T, class tree_node_allocator>

799

00790 // template <class iter>

800

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

801

00792 // {

802

00793 // // insert dummy

803

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

804

00795 // // replace dummy with subtree

805

00796 // return replace(it, subtree);

806

00797 // }

807

00798

808

00799 template <class T, class tree_node_allocator>

809

00800 template <class iter>

810

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

811

00802 {

812

00803 kp::destructor(&<a class="code" href="messages_8cpp.html#a1">position</a>.node->data);

813

00804 kp::constructor(&<a class="code" href="messages_8cpp.html#a1">position</a>.node->data, x);

814

00805 return position;

815

00806 }

816

00807

817

00808 template <class T, class tree_node_allocator>

818

00809 template <class iter>

819

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

820

00811 {

821

00812 assert(<a class="code" href="messages_8cpp.html#a1">position</a>.node!=head);

822

00813 tree_node *current_from=from.node;

823

00814 tree_node *start_from=from.node;

824

00815 tree_node *current_to =<a class="code" href="messages_8cpp.html#a1">position</a>.node;

825

00816

826

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

827

00818 erase_children(position);

828

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

829

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

830

00821 tmp->first_child=0;

831

00822 tmp->last_child=0;

832

00823 if(current_to->prev_sibling==0) {

833

00824 current_to->parent->first_child=tmp;

834

00825 }

835

00826 else {

836

00827 current_to->prev_sibling->next_sibling=tmp;

837

00828 }

838

00829 tmp->prev_sibling=current_to->prev_sibling;

839

00830 if(current_to->next_sibling==0) {

840

00831 current_to->parent->last_child=tmp;

841

00832 }

842

00833 else {

843

00834 current_to->next_sibling->prev_sibling=tmp;

844

00835 }

845

00836 tmp->next_sibling=current_to->next_sibling;

846

00837 tmp->parent=current_to->parent;

847

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

848

00839 alloc_.deallocate(current_to,1);

849

00840 current_to=tmp;

850

00841

851

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

852

00843 tree_node *last=from.node->next_sibling;

853

00844

854

00845 pre_order_iterator toit=tmp;

855

00846 // copy all children

856

00847 do {

857

00848 assert(current_from!=0);

858

00849 if(current_from->first_child != 0) {

859

00850 current_from=current_from->first_child;

860

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

861

00852 }

862

00853 else {

863

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

864

00855 current_from=current_from->parent;

865

00856 toit=parent(toit);

866

00857 assert(current_from!=0);

867

00858 }

868

00859 current_from=current_from->next_sibling;

869

00860 if(current_from!=last) {

870

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

871

00862 }

872

00863 }

873

00864 } while(current_from!=last);

874

00865

875

00866 return current_to;

876

00867 }

877

00868

878

00869 template <class T, class tree_node_allocator>

879

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

880

00871 sibling_iterator orig_begin,

881

00872 sibling_iterator orig_end,

882

00873 sibling_iterator new_begin,

883

00874 sibling_iterator new_end)

884

00875 {

885

00876 tree_node *orig_first=orig_begin.node;

886

00877 tree_node *new_first=new_begin.node;

887

00878 tree_node *orig_last=orig_first;

888

00879 while((++orig_begin)!=orig_end)

889

00880 orig_last=orig_last->next_sibling;

890

00881 tree_node *new_last=new_first;

891

00882 while((++new_begin)!=new_end)

892

00883 new_last=new_last->next_sibling;

893

00884

894

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

895

00886 bool first=true;

896

00887 pre_order_iterator ret;

897

00888 while(1==1) {

898

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

899

00890 if(first) {

900

00891 ret=tt;

901

00892 first=false;

902

00893 }

903

00894 if(new_first==new_last)

904

00895 break;

905

00896 new_first=new_first->next_sibling;

906

00897 }

907

00898

908

00899 // erase old range of siblings

909

00900 bool last=false;

910

00901 tree_node *next=orig_first;

911

00902 while(1==1) {

912

00903 if(next==orig_last)

913

00904 last=true;

914

00905 next=next->next_sibling;

915

00906 erase((pre_order_iterator)orig_first);

916

00907 if(last)

917

00908 break;

918

00909 orig_first=next;

919

00910 }

920

00911 return ret;

921

00912 }

922

00913

923

00914 template <class T, class tree_node_allocator>

924

00915 template <typename iter>

925

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

926

00917 {

927

00918 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child==0)

928

00919 return position;

929

00920

930

00921 tree_node *tmp=<a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child;

931

00922 while(tmp) {

932

00923 tmp->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node->parent;

933

00924 tmp=tmp->next_sibling;

934

00925 }

935

00926 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling) {

936

00927 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child->next_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling;

937

00928 <a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child;

938

00929 }

939

00930 else {

940

00931 <a class="code" href="messages_8cpp.html#a1">position</a>.node->parent->last_child=<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child;

941

00932 }

942

00933 <a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child;

943

00934 <a class="code" href="messages_8cpp.html#a1">position</a>.node->next_sibling->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

944

00935 <a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child=0;

945

00936 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child=0;

946

00937

947

00938 return position;

948

00939 }

949

00940

950

00941

951

00942 template <class T, class tree_node_allocator>

952

00943 template <typename iter>

953

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

954

00945 {

955

00946 tree_node *first=begin.node;

956

00947 tree_node *last=first;

957

00948 if(begin==end) return begin;

958

00949 // determine last node

959

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

960

00951 last=last->next_sibling;

961

00952 }

962

00953 // move subtree

963

00954 if(first->prev_sibling==0) {

964

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

965

00956 }

966

00957 else {

967

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

968

00959 }

969

00960 if(last->next_sibling==0) {

970

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

971

00962 }

972

00963 else {

973

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

974

00965 }

975

00966 if(<a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child==0) {

976

00967 <a class="code" href="messages_8cpp.html#a1">position</a>.node->first_child=first;

977

00968 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child=last;

978

00969 first->prev_sibling=0;

979

00970 }

980

00971 else {

981

00972 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child->next_sibling=first;

982

00973 first->prev_sibling=<a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child;

983

00974 <a class="code" href="messages_8cpp.html#a1">position</a>.node->last_child=last;

984

00975 }

985

00976 last->next_sibling=0;

986

00977

987

00978 tree_node *pos=first;

988

00979 while(1==1) {

989

00980 pos->parent=<a class="code" href="messages_8cpp.html#a1">position</a>.node;

990

00981 if(pos==last) break;

991

00982 pos=pos->next_sibling;

992

00983 }

993

00984

994

00985 return first;

995

00986 }

996

00987

997

00988 template <class T, class tree_node_allocator>

998

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

999

00990 {

1000

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

1001

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

1002

00993 }

1003

00994

1004

00995 template <class T, class tree_node_allocator>

1005

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

1006

00997 {

1007

00998 tree_node *dst=target.node;

1008

00999 tree_node *src=source.node;

1009

01000 assert(dst);

1010

01001 assert(src);

1011

01002

1012

01003 if(dst==src) return source;

1013

01004

1014

01005 // take src out of the tree

1015

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

1016

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

1017

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

1018

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

1019

01010

1020

01011 // connect it to the new point

1021

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

1022

01013 else dst->parent->first_child=src;

1023

01014 src->prev_sibling=dst->prev_sibling;

1024

01015 dst->prev_sibling=src;

1025

01016 src->next_sibling=dst;

1026

01017 src->parent=dst->parent;

1027

01018 return src;

1028

01019 }

1029

01020

1030

01021 template <class T, class tree_node_allocator>

1031

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

1032

01023 sibling_iterator from1, sibling_iterator from2,

1033

01024 bool duplicate_leaves)

1034

01025 {

1035

01026 sibling_iterator fnd;

1036

01027 while(from1!=from2) {

1037

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

1038

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

1039

01030 if(duplicate_leaves)

1040

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

1041

01032 }

1042

01033 else { // descend further

1043

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

1044

01035 }

1045

01036 }

1046

01037 else { // element missing

1047

01038 insert_subtree(to2, from1);

1048

01039 }

1049

01040 ++from1;

1050

01041 }

1051

01042 }

1052

01043

1053

01044 template <class T, class tree_node_allocator>

1054

01045 template <class StrictWeakOrdering>

1055

01046 bool tree<T, tree_node_allocator>::compare_nodes<StrictWeakOrdering>::operator()(const tree_node *a,

1056

01047 const tree_node *b)

1057

01048 {

1058

01049 static StrictWeakOrdering comp;

1059

01050

1060

01051 return comp(a->data, b->data);

1061

01052 }

1062

01053

1063

01054 template <class T, class tree_node_allocator>

1064

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

1065

01056 {

1066

01057 std::less<T> comp;

1067

01058 sort(from, to, comp, deep);

1068

01059 }

1069

01060

1070

01061 template <class T, class tree_node_allocator>

1071

01062 template <class StrictWeakOrdering>

1072

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

1073

01064 StrictWeakOrdering comp, bool deep)

1074

01065 {

1075

01066 if(from==to) return;

1076

01067 // make list of sorted nodes

1077

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

1078

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

1079

01070 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;

1080

01071 sibling_iterator it=from, it2=to;

1081

01072 while(it != to) {

1082

01073 nodes.insert(it.node);

1083

01074 ++it;

1084

01075 }

1085

01076 // reassemble

1086

01077 --it2;

1087

01078

1088

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

1089

01080 tree_node *prev=from.node->prev_sibling;

1090

01081 tree_node *next=it2.node->next_sibling;

1091

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

1092

01083 if(prev==0) {

1093

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

1094

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

1095

01086 }

1096

01087 else prev->next_sibling=(*nit);

1097

01088

1098

01089 --eit;

1099

01090 while(nit!=eit) {

1100

01091 (*nit)->prev_sibling=prev;

1101

01092 if(prev)

1102

01093 prev->next_sibling=(*nit);

1103

01094 prev=(*nit);

1104

01095 ++nit;

1105

01096 }

1106

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

1107

01098 if(prev)

1108

01099 prev->next_sibling=(*eit);

1109

01100

1110

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

1111

01102 (*eit)->next_sibling=next;

1112

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

1113

01104 if(next==0) {

1114

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

1115

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

1116

01107 }

1117

01108 else next->prev_sibling=(*eit);

1118

01109

1119

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

1120

01111 sibling_iterator bcs(*nodes.begin());

1121

01112 sibling_iterator ecs(*eit);

1122

01113 ++ecs;

1123

01114 while(bcs!=ecs) {

1124

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

1125

01116 ++bcs;

1126

01117 }

1127

01118 }

1128

01119 }

1129

01120

1130

01121 template <class T, class tree_node_allocator>

1131

01122 template <typename iter>

1132

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

1133

01124 {

1134

01125 std::equal_to<T> comp;

1135

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

1136

01127 }

1137

01128

1138

01129 template <class T, class tree_node_allocator>

1139

01130 template <typename iter>

1140

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

1141

01132 {

1142

01133 std::equal_to<T> comp;

1143

01134 return equal_subtree(one_, two_, comp);

1144

01135 }

1145

01136

1146

01137 template <class T, class tree_node_allocator>

1147

01138 template <typename iter, class BinaryPredicate>

1148

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

1149

01140 {

1150

01141 pre_order_iterator one(one_), three(three_);

1151

01142

1152

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

1153

01144 // return false;

1154

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

1155

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

1156

01147 return false;

1157

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

1158

01149 return false;

1159

01150 ++one;

1160

01151 ++three;

1161

01152 }

1162

01153 return true;

1163

01154 }

1164

01155

1165

01156 template <class T, class tree_node_allocator>

1166

01157 template <typename iter, class BinaryPredicate>

1167

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

1168

01159 {

1169

01160 pre_order_iterator one(one_), two(two_);

1170

01161

1171

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

1172

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

1173

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

1174

01165 }

1175

01166

1176

01167 template <class T, class tree_node_allocator>

1177

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

1178

01169 {

1179

01170 tree tmp;

1180

01171 tmp.set_head(value_type());

1181

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

1182

01173 return tmp;

1183

01174 }

1184

01175

1185

01176 template <class T, class tree_node_allocator>

1186

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

1187

01178 {

1188

01179 tmp.set_head(value_type());

1189

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

1190

01181 }

1191

01182

1192

01183 template <class T, class tree_node_allocator>

1193

01184 int tree<T, tree_node_allocator>::size() const

1194

01185 {

1195

01186 int i=0;

1196

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

1197

01188 while(it!=eit) {

1198

01189 ++i;

1199

01190 ++it;

1200

01191 }

1201

01192 return i;

1202

01193 }

1203

01194

1204

01195 template <class T, class tree_node_allocator>

1205

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

1206

01197 {

1207

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

1208

01199 return (it==eit);

1209

01200 }

1210

01201

1211

01202 template <class T, class tree_node_allocator>

1212

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

1213

01204 {

1214

01205 tree_node* pos=it.node;

1215

01206 assert(pos!=0);

1216

01207 int ret=0;

1217

01208 while(pos->parent!=0) {

1218

01209 pos=pos->parent;

1219

01210 ++ret;

1220

01211 }

1221

01212 return ret;

1222

01213 }

1223

01214

1224

01215 template <class T, class tree_node_allocator>

1225

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

1226

01217 {

1227

01218 tree_node *pos=it.node->first_child;

1228

01219 if(pos==0) return 0;

1229

01220

1230

01221 unsigned int ret=1;

1231

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

1232

01223 // ++ret;

1233

01224 // pos=pos->next_sibling;

1234

01225 // }

1235

01226 while((pos=pos->next_sibling))

1236

01227 ++ret;

1237

01228 return ret;

1238

01229 }

1239

01230

1240

01231 template <class T, class tree_node_allocator>

1241

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

1242

01233 {

1243

01234 tree_node *pos=it.node;

1244

01235 unsigned int ret=1;

1245

01236 while(pos->next_sibling && pos->next_sibling!=head) {

1246

01237 ++ret;

1247

01238 pos=pos->next_sibling;

1248

01239 }

1249

01240 return ret;

1250

01241 }

1251

01242

1252

01243 template <class T, class tree_node_allocator>

1253

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

1254

01245 {

1255

01246 tree_node *nxt=it.node->next_sibling;

1256

01247 if(nxt) {

1257

01248 if(it.node->prev_sibling)

1258

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

1259

01250 else

1260

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

1261

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

1262

01253 tree_node *nxtnxt=nxt->next_sibling;

1263

01254 if(nxtnxt)

1264

01255 nxtnxt->prev_sibling=it.node;

1265

01256 else

1266

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

1267

01258 nxt->next_sibling=it.node;

1268

01259 it.node->prev_sibling=nxt;

1269

01260 it.node->next_sibling=nxtnxt;

1270

01261 }

1271

01262 }

1272

01263

1273

01264 // template <class BinaryPredicate>

1274

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

1275

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

1276

01267 // BinaryPredicate fun) const

1277

01268 // {

1278

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

1279

01270 // while(from!=to) {

1280

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

1281

01272 //

1282

01273 // }

1283

01274 // }

1284

01275 // return to;

1285

01276 // }

1286

01277

1287

01278 template <class T, class tree_node_allocator>

1288

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

1289

01280 const iterator_base& end) const

1290

01281 {

1291

01282 // FIXME: this should be optimised.

1292

01283 pre_order_iterator tmp=begin;

1293

01284 while(tmp!=end) {

1294

01285 if(tmp==it) return true;

1295

01286 ++tmp;

1296

01287 }

1297

01288 return false;

1298

01289 }

1299

01290

1300

01291 template <class T, class tree_node_allocator>

1301

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

1302

01293 {

1303

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

1304

01295 else return true;

1305

01296 }

1306

01297

1307

01298 template <class T, class tree_node_allocator>

1308

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

1309

01300 {

1310

01301 unsigned int ind=0;

1311

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

1312

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

1313

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

1314

01305 ++ind;

1315

01306 }

1316

01307 }

1317

01308 else {

1318

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

1319

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

1320

01311 ++ind;

1321

01312 }

1322

01313 }

1323

01314 return ind;

1324

01315 }

1325

01316

1326

01317

1327

01318 template <class T, class tree_node_allocator>

1328

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

1329

01320 {

1330

01321 tree_node *tmp=it.node->first_child;

1331

01322 while(num--) {

1332

01323 assert(tmp!=0);

1333

01324 tmp=tmp->next_sibling;

1334

01325 }

1335

01326 return tmp;

1336

01327 }

1337

01328

1338

01329

1339

01330

1340

01331

1341

01332 // Iterator base

1342

01333

1343

01334 template <class T, class tree_node_allocator>

1344

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

1345

01336 : node(0), skip_current_children_(false)

1346

01337 {

1347

01338 }

1348

01339

1349

01340 template <class T, class tree_node_allocator>

1350

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

1351

01342 : node(tn), skip_current_children_(false)

1352

01343 {

1353

01344 }

1354

01345

1355

01346 template <class T, class tree_node_allocator>

1356

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

1357

01348 {

1358

01349 return node->data;

1359

01350 }

1360

01351

1361

01352 template <class T, class tree_node_allocator>

1362

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

1363

01354 {

1364

01355 return &(node->data);

1365

01356 }

1366

01357

1367

01358 template <class T, class tree_node_allocator>

1368

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

1369

01360 {

1370

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

1371

01362 else return false;

1372

01363 }

1373

01364

1374

01365 template <class T, class tree_node_allocator>

1375

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

1376

01367 {

1377

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

1378

01369 else return false;

1379

01370 }

1380

01371

1381

01372 template <class T, class tree_node_allocator>

1382

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

1383

01374 {

1384

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

1385

01376 else return false;

1386

01377 }

1387

01378

1388

01379 template <class T, class tree_node_allocator>

1389

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

1390

01381 {

1391

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

1392

01383 else return false;

1393

01384 }

1394

01385

1395

01386 template <class T, class tree_node_allocator>

1396

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

1397

01388 {

1398

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

1399

01390 else return false;

1400

01391 }

1401

01392

1402

01393 template <class T, class tree_node_allocator>

1403

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

1404

01395 {

1405

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

1406

01397 else return false;

1407

01398 }

1408

01399

1409

01400 template <class T, class tree_node_allocator>

1410

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

1411

01402 {

1412

01403 sibling_iterator ret(node->first_child);

1413

01404 ret.parent_=this->node;

1414

01405 return ret;

1415

01406 }

1416

01407

1417

01408 template <class T, class tree_node_allocator>

1418

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

1419

01410 {

1420

01411 sibling_iterator ret(0);

1421

01412 ret.parent_=node;

1422

01413 return ret;

1423

01414 }

1424

01415

1425

01416 template <class T, class tree_node_allocator>

1426

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

1427

01418 {

1428

01419 skip_current_children_=true;

1429

01420 }

1430

01421

1431

01422 template <class T, class tree_node_allocator>

1432

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

1433

01424 {

1434

01425 tree_node *pos=node->first_child;

1435

01426 if(pos==0) return 0;

1436

01427

1437

01428 unsigned int ret=1;

1438

01429 while(pos!=node->last_child) {

1439

01430 ++ret;

1440

01431 pos=pos->next_sibling;

1441

01432 }

1442

01433 return ret;

1443

01434 }

1444

01435

1445

01436

1446

01437

1447

01438 // Pre-order iterator

1448

01439

1449

01440 template <class T, class tree_node_allocator>

1450

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

1451

01442 : iterator_base(0)

1452

01443 {

1453

01444 }

1454

01445

1455

01446 template <class T, class tree_node_allocator>

1456

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

1457

01448 : iterator_base(tn)

1458

01449 {

1459

01450 }

1460

01451

1461

01452 template <class T, class tree_node_allocator>

1462

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

1463

01454 : iterator_base(other.node)

1464

01455 {

1465

01456 }

1466

01457

1467

01458 template <class T, class tree_node_allocator>

1468

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

1469

01460 : iterator_base(other.node)

1470

01461 {

1471

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

1472

01463 if(other.range_last()!=0)

1473

01464 this->node=other.range_last();

1474

01465 else

1475

01466 this->node=other.parent_;

1476

01467 this->skip_children();

1477

01468 ++(*this);

1478

01469 }

1479

01470 }

1480

01471

1481

01472 template <class T, class tree_node_allocator>

1482

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

1483

01474 {

1484

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

1485

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

1486

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

1487

01478 }

1488

01479 else {

1489

01480 this->skip_current_children_=false;

1490

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

1491

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

1492

01483 if(this->node==0)

1493

01484 return *this;

1494

01485 }

1495

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

1496

01487 }

1497

01488 return *this;

1498

01489 }

1499

01490

1500

01491 template <class T, class tree_node_allocator>

1501

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

1502

01493 {

1503

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

1504

01495 if(this->node->prev_sibling) {

1505

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

1506

01497 while(this->node->last_child)

1507

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

1508

01499 }

1509

01500 else {

1510

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

1511

01502 if(this->node==0)

1512

01503 return *this;

1513

01504 }

1514

01505 return *this;

1515

01506 }

1516

01507

1517

01508 template <class T, class tree_node_allocator>

1518

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

1519

01510 {

1520

01511 pre_order_iterator copy = *this;

1521

01512 ++(*this);

1522

01513 return copy;

1523

01514 }

1524

01515

1525

01516 template <class T, class tree_node_allocator>

1526

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

1527

01518 {

1528

01519 pre_order_iterator copy = *this;

1529

01520 --(*this);

1530

01521 return copy;

1531

01522 }

1532

01523

1533

01524 template <class T, class tree_node_allocator>

1534

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

1535

01526 {

1536

01527 while(num>0) {

1537

01528 ++(*this);

1538

01529 --num;

1539

01530 }

1540

01531 return (*this);

1541

01532 }

1542

01533

1543

01534 template <class T, class tree_node_allocator>

1544

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

1545

01536 {

1546

01537 while(num>0) {

1547

01538 --(*this);

1548

01539 --num;

1549

01540 }

1550

01541 return (*this);

1551

01542 }

1552

01543

1553

01544

1554

01545

1555

01546 // Post-order iterator

1556

01547

1557

01548 template <class T, class tree_node_allocator>

1558

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

1559

01550 : iterator_base(0)

1560

01551 {

1561

01552 }

1562

01553

1563

01554 template <class T, class tree_node_allocator>

1564

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

1565

01556 : iterator_base(tn)

1566

01557 {

1567

01558 }

1568

01559

1569

01560 template <class T, class tree_node_allocator>

1570

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

1571

01562 : iterator_base(other.node)

1572

01563 {

1573

01564 }

1574

01565

1575

01566 template <class T, class tree_node_allocator>

1576

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

1577

01568 : iterator_base(other.node)

1578

01569 {

1579

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

1580

01571 if(other.range_last()!=0)

1581

01572 this->node=other.range_last();

1582

01573 else

1583

01574 this->node=other.parent_;

1584

01575 this->skip_children();

1585

01576 ++(*this);

1586

01577 }

1587

01578 }

1588

01579

1589

01580 template <class T, class tree_node_allocator>

1590

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

1591

01582 {

1592

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

1593

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

1594

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

1595

01586 else {

1596

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

1597

01588 if(this->skip_current_children_) {

1598

01589 this->skip_current_children_=false;

1599

01590 }

1600

01591 else {

1601

01592 while(this->node->first_child)

1602

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

1603

01594 }

1604

01595 }

1605

01596 return *this;

1606

01597 }

1607

01598

1608

01599 template <class T, class tree_node_allocator>

1609

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

1610

01601 {

1611

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

1612

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

1613

01604 this->skip_current_children_=false;

1614

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

1615

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

1616

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

1617

01608 }

1618

01609 else {

1619

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

1620

01611 }

1621

01612 return *this;

1622

01613 }

1623

01614

1624

01615 template <class T, class tree_node_allocator>

1625

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

1626

01617 {

1627

01618 post_order_iterator copy = *this;

1628

01619 ++(*this);

1629

01620 return copy;

1630

01621 }

1631

01622

1632

01623 template <class T, class tree_node_allocator>

1633

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

1634

01625 {

1635

01626 post_order_iterator copy = *this;

1636

01627 --(*this);

1637

01628 return copy;

1638

01629 }

1639

01630

1640

01631

1641

01632 template <class T, class tree_node_allocator>

1642

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

1643

01634 {

1644

01635 while(num>0) {

1645

01636 ++(*this);

1646

01637 --num;

1647

01638 }

1648

01639 return (*this);

1649

01640 }

1650

01641

1651

01642 template <class T, class tree_node_allocator>

1652

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

1653

01644 {

1654

01645 while(num>0) {

1655

01646 --(*this);

1656

01647 --num;

1657

01648 }

1658

01649 return (*this);

1659

01650 }

1660

01651

1661

01652 template <class T, class tree_node_allocator>

1662

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

1663

01654 {

1664

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

1665

01656 while(this->node->first_child)

1666

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

1667

01658 }

1668

01659

1669

01660

1670

01661 // Fixed depth iterator

1671

01662

1672

01663 template <class T, class tree_node_allocator>

1673

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

1674

01665 : iterator_base()

1675

01666 {

1676

01667 set_first_parent_();

1677

01668 }

1678

01669

1679

01670 template <class T, class tree_node_allocator>

1680

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

1681

01672 : iterator_base(tn)

1682

01673 {

1683

01674 set_first_parent_();

1684

01675 }

1685

01676

1686

01677 template <class T, class tree_node_allocator>

1687

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

1688

01679 : iterator_base(other.node)

1689

01680 {

1690

01681 set_first_parent_();

1691

01682 }

1692

01683

1693

01684 template <class T, class tree_node_allocator>

1694

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

1695

01686 : iterator_base(other.node), first_parent_(other.parent_)

1696

01687 {

1697

01688 find_leftmost_parent_();

1698

01689 }

1699

01690

1700

01691 template <class T, class tree_node_allocator>

1701

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

1702

01693 : iterator_base(other.node), first_parent_(other.first_parent_)

1703

01694 {

1704

01695 }

1705

01696

1706

01697 template <class T, class tree_node_allocator>

1707

01698 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()

1708

01699 {

1709

01700 return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if

1710

01701 // it is ever to work at the 'head' level.

1711

01702 first_parent_=0;

1712

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

1713

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

1714

01705 first_parent_=this->node->parent;

1715

01706 if(first_parent_)

1716

01707 find_leftmost_parent_();

1717

01708 }

1718

01709

1719

01710 template <class T, class tree_node_allocator>

1720

01711 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()

1721

01712 {

1722

01713 return; // FIXME: see 'set_first_parent()'

1723

01714 tree_node *tmppar=first_parent_;

1724

01715 while(tmppar->prev_sibling) {

1725

01716 tmppar=tmppar->prev_sibling;

1726

01717 if(tmppar->first_child)

1727

01718 first_parent_=tmppar;

1728

01719 }

1729

01720 }

1730

01721

1731

01722 template <class T, class tree_node_allocator>

1732

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

1733

01724 {

1734

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

1735

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

1736

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

1737

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

1738

01729 if(this->node->parent==0 && this->node->next_sibling==0) // feet element

1739

01730 this->node=0;

1740

01731 }

1741

01732 else {

1742

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

1743

01734 do {

1744

01735 par=par->next_sibling;

1745

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

1746

01737 this->node=0;

1747

01738 return *this;

1748

01739 }

1749

01740 } while(par->first_child==0);

1750

01741 this->node=par->first_child;

1751

01742 }

1752

01743 return *this;

1753

01744 }

1754

01745

1755

01746 template <class T, class tree_node_allocator>

1756

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

1757

01748 {

1758

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

1759

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

1760

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

1761

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

1762

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

1763

01754 this->node=0;

1764

01755 }

1765

01756 else {

1766

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

1767

01758 do {

1768

01759 par=par->prev_sibling;

1769

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

1770

01761 this->node=0;

1771

01762 return *this;

1772

01763 }

1773

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

1774

01765 this->node=par->last_child;

1775

01766 }

1776

01767 return *this;

1777

01768 }

1778

01769

1779

01770 template <class T, class tree_node_allocator>

1780

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

1781

01772 {

1782

01773 fixed_depth_iterator copy = *this;

1783

01774 ++(*this);

1784

01775 return copy;

1785

01776 }

1786

01777

1787

01778 template <class T, class tree_node_allocator>

1788

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

1789

01780 {

1790

01781 fixed_depth_iterator copy = *this;

1791

01782 --(*this);

1792

01783 return copy;

1793

01784 }

1794

01785

1795

01786 template <class T, class tree_node_allocator>

1796

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

1797

01788 {

1798

01789 while(num>0) {

1799

01790 --(*this);

1800

01791 --(num);

1801

01792 }

1802

01793 return (*this);

1803

01794 }

1804

01795

1805

01796 template <class T, class tree_node_allocator>

1806

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

1807

01798 {

1808

01799 while(num>0) {

1809

01800 ++(*this);

1810

01801 --(num);

1811

01802 }

1812

01803 return *this;

1813

01804 }

1814

01805

1815

01806 // FIXME: add the other members of fixed_depth_iterator.

1816

01807

1817

01808

1818

01809 // Sibling iterator

1819

01810

1820

01811 template <class T, class tree_node_allocator>

1821

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

1822

01813 : iterator_base()

1823

01814 {

1824

01815 set_parent_();

1825

01816 }

1826

01817

1827

01818 template <class T, class tree_node_allocator>

1828

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

1829

01820 : iterator_base(tn)

1830

01821 {

1831

01822 set_parent_();

1832

01823 }

1833

01824

1834

01825 template <class T, class tree_node_allocator>

1835

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

1836

01827 : iterator_base(other.node)

1837

01828 {

1838

01829 set_parent_();

1839

01830 }

1840

01831

1841

01832 template <class T, class tree_node_allocator>

1842

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

1843

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

1844

01835 {

1845

01836 }

1846

01837

1847

01838 template <class T, class tree_node_allocator>

1848

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

1849

01840 {

1850

01841 parent_=0;

1851

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

1852

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

1853

01844 parent_=this->node->parent;

1854

01845 }

1855

01846

1856

01847 template <class T, class tree_node_allocator>

1857

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

1858

01849 {

1859

01850 if(this->node)

1860

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

1861

01852 return *this;

1862

01853 }

1863

01854

1864

01855 template <class T, class tree_node_allocator>

1865

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

1866

01857 {

1867

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

1868

01859 else {

1869

01860 assert(parent_);

1870

01861 this->node=parent_->last_child;

1871

01862 }

1872

01863 return *this;

1873

01864 }

1874

01865

1875

01866 template <class T, class tree_node_allocator>

1876

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

1877

01868 {

1878

01869 sibling_iterator copy = *this;

1879

01870 ++(*this);

1880

01871 return copy;

1881

01872 }

1882

01873

1883

01874 template <class T, class tree_node_allocator>

1884

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

1885

01876 {

1886

01877 sibling_iterator copy = *this;

1887

01878 --(*this);

1888

01879 return copy;

1889

01880 }

1890

01881

1891

01882 template <class T, class tree_node_allocator>

1892

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

1893

01884 {

1894

01885 while(num>0) {

1895

01886 ++(*this);

1896

01887 --num;

1897

01888 }

1898

01889 return (*this);

1899

01890 }

1900

01891

1901

01892 template <class T, class tree_node_allocator>

1902

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

1903

01894 {

1904

01895 while(num>0) {

1905

01896 --(*this);

1906

01897 --num;

1907

01898 }

1908

01899 return (*this);

1909

01900 }

1910

01901

1911

01902 template <class T, class tree_node_allocator>

1912

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

1913

01904 {

1914

01905 tree_node *tmp=parent_->first_child;

1915

01906 return tmp;

1916

01907 }

1917

01908

1918

01909 template <class T, class tree_node_allocator>

1919

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

1920

01911 {

1921

01912 return parent_->last_child;

1922

01913 }

1923

01914

1924

01915

1925

01916 #endif

1926

01917

1927

01918 // Local variables:

1928

01919 // default-tab-width: 3

1929

01920 // End:

1930

</pre></div><hr size="1"><address style="align: right;">Generated on Sun Jul 31 15:38:35 2005 for LibOFX by

1931

1932

1933

</body>

1934

</html>

Older »