/elec/propeller-clock : revision 4

To get this branch, use:

bzr branch
http://bzr.ed.am/elec/propeller-clock

« back to all changes in this revision

Viewing changes to src/utility/list

Committer: Dan
Date: 2011-11-03 00:18:13 UTC
Revision ID: dan@waxworlds.org-20111103001813-gwefcqb2m5mk1ye2

Added Notes

files removed:
.bzrignore

arduino.mk

electronics-information

pcb.psd

project

project/propeller-clock.pro

project/propeller-clock.sch

src/analogue_clock_mode.cc

src/analogue_clock_mode.h

src/button.cc

src/button.h

src/config.h

src/drawer.cc

src/drawer.h

src/major_mode.h

src/minor_mode.cc

src/minor_mode.h

src/mode_switcher.cc

src/mode_switcher.h

src/propeller-clock.ino

src/test_mode.cc

src/test_mode.h

src/time.cc

src/time.h

src/util

src/util/Bounce.cpp

src/util/Bounce.h

src/util/DS1307.cpp

src/util/DS1307.h

src/utility

src/utility/Jamfile

src/utility/Makefile

src/utility/README.md

src/utility/StandardCplusplus.h

src/utility/algorithm

src/utility/algorithm.cpp

src/utility/associative_base

src/utility/associative_base.cpp

src/utility/basic_definitions

src/utility/bitset

src/utility/bitset.cpp

src/utility/cassert

src/utility/cctype

src/utility/cerrno

src/utility/cfloat

src/utility/char_traits

src/utility/char_traits.cpp

src/utility/climits

src/utility/clocale

src/utility/cmath

src/utility/complex

src/utility/complex.cpp

src/utility/csetjmp

src/utility/csignal

src/utility/cstdarg

src/utility/cstddef

src/utility/cstdio

src/utility/cstdlib

src/utility/cstring

src/utility/ctime

src/utility/cwchar

src/utility/cwctype

src/utility/del_op.cpp

src/utility/del_opnt.cpp

src/utility/del_opv.cpp

src/utility/del_opvnt.cpp

src/utility/deque

src/utility/deque.cpp

src/utility/eh_alloc.cpp

src/utility/eh_globals.cpp

src/utility/exception

src/utility/exception.cpp

src/utility/fstream

src/utility/fstream.cpp

src/utility/func_exception

src/utility/func_exception.cpp

src/utility/functional

src/utility/iomanip

src/utility/iomanip.cpp

src/utility/ios

src/utility/ios.cpp

src/utility/iosfwd

src/utility/iostream

src/utility/iostream.cpp

src/utility/istream

src/utility/istream.cpp

src/utility/istream_helpers

src/utility/iterator

src/utility/iterator.cpp

src/utility/iterator_base

src/utility/limits

src/utility/limits.cpp

src/utility/list

src/utility/list.cpp

src/utility/locale

src/utility/locale.cpp

src/utility/map

src/utility/map.cpp

src/utility/memory

src/utility/new

src/utility/new_handler.cpp

src/utility/new_op.cpp

src/utility/new_opnt.cpp

src/utility/new_opv.cpp

src/utility/new_opvnt.cpp

src/utility/numeric

src/utility/numeric.cpp

src/utility/ostream

src/utility/ostream.cpp

src/utility/ostream_helpers

src/utility/queue

src/utility/queue.cpp

src/utility/serstream

src/utility/set

src/utility/set.cpp

src/utility/sstream

src/utility/sstream.cpp

src/utility/stack

src/utility/stack.cpp

src/utility/stdexcept

src/utility/stdexcept.cpp

src/utility/streambuf

src/utility/streambuf.cpp

src/utility/string

src/utility/string.cpp

src/utility/string_iostream

src/utility/support

src/utility/support.cpp

src/utility/system_configuration.h

src/utility/type_traits

src/utility/typeinfo

src/utility/typeinfo.cpp

src/utility/uartbuf

src/utility/unwind-cxx.h

src/utility/utility.cpp

src/utility/utility.h

src/utility/valarray

src/utility/valarray.cpp

src/utility/vector

src/utility/vector.cpp

test

test/fan-test

test/fan-test/Makefile

test/fan-test/fan-test.ino

test/led-test

test/led-test/Makefile

test/led-test/led-test.ino

test/phantom-button-presses

test/phantom-button-presses/Makefile

test/phantom-button-presses/main.ino

files renamed:
src/Makefile@ => Makefile

notes => Notes.rtf

Show diffs side-by-side

added added

removed removed

src/utility/list

This file is part of the uClibc++ Library.

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

modify it under the terms of the GNU Lesser General Public

License as published by the Free Software Foundation; either

version 2.1 of the License, or (at your option) any later version.

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

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public

License along with this library; if not, write to the Free Software

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

#include <memory>

#include <iterator>

#include <algorithm>

#ifndef __STD_HEADER_LIST

#define __STD_HEADER_LIST 1

#pragma GCC visibility push(default)

namespace std{

template <class T, class Allocator = allocator<T> > class _UCXXEXPORT list {

public:

typedef typename Allocator::reference reference;

typedef typename Allocator::const_reference const_reference;

typedef typename Allocator::size_type size_type;

typedef typename Allocator::difference_type difference_type;

typedef T value_type;

typedef Allocator allocator_type;

typedef typename Allocator::pointer pointer;

typedef typename Allocator::const_pointer const_pointer;

protected:

class node;

class iter_list;

node * list_start;

node * list_end;

size_type elements;

Allocator a;

public:

typedef iter_list iterator;

typedef iter_list const_iterator;

typedef std::reverse_iterator<iterator> reverse_iterator;

typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

explicit list(const Allocator& = Allocator());

explicit list(size_type n, const T& value = T(), const Allocator& = Allocator());

template <class InputIterator> list(InputIterator first, InputIterator last,

const Allocator& al= Allocator());

list(const list<T,Allocator>& x);

~list();

list<T,Allocator>& operator=(const list<T,Allocator>& x){

if(&x == this){

return *this;

}

clear();

iterator i = x.begin();

while(i != x.end()){

push_back(*i);

++i;

}

return *this;

}

template <class InputIterator> void assign(InputIterator first, InputIterator last);

template <class Size, class U> void assign(Size n, const U& u = U());

allocator_type get_allocator() const;

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

bool empty() const;

size_type size() const;

size_type max_size() const;

void resize(size_type sz, T c = T());

reference front();

const_reference front() const;

reference back();

const_reference back() const;

100

101

void push_front(const T& x);

102

void pop_front();

103

void push_back(const T& x);

104

void pop_back();

105

iterator insert(iterator position, const T& x = T());

106

void insert(iterator position, size_type n, const T& x);

107

template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last);

108

iterator erase(iterator position);

109

iterator erase(iterator position, iterator last);

110

void swap(list<T,Allocator>&);

111

void clear();

112

113

void splice(iterator position, list<T,Allocator>& x);

114

void splice(iterator position, list<T,Allocator>& x, iterator i);

115

void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);

116

void remove(const T& value);

117

template <class Predicate> void remove_if(Predicate pred);

118

void unique();

119

template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);

120

void merge(list<T,Allocator>& x);

121

template <class Compare> void merge(list<T,Allocator>& x, Compare comp);

122

void sort();

123

template <class Compare> void sort(Compare comp);

124

void reverse();

125

protected:

126

void swap_nodes(node * x, node * y);

127

};

128

129

130

//Implementations of List

131

132

//List node

133

template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::node{

134

public:

135

node * previous;

136

node * next;

137

T * val;

138

139

node(): previous(0), next(0), val(0){ }

140

node(const T & t ): previous(0), next(0), val(0) {

141

val = new T(t);

142

//FIXME use allocator somehow but only call constructor once

143

}

144

node(const T & t, node * p, node * n): previous(p), next(n), val(0) {

145

val = new T(t);

146

}

147

~node(){ }

148

};

149

150

//List iterator

151

template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::iter_list

152

: public std::iterator<

153

bidirectional_iterator_tag,

154

155

typename Allocator::difference_type,

156

typename Allocator::pointer,

157

typename Allocator::reference

158

159

{

160

private:

161

node * current;

162

public:

163

iter_list():current(0) { }

164

iter_list( typename list<T, Allocator>::node * n): current(n) { }

165

iter_list(const list<T, Allocator>::iter_list & l): current(l.current) { }

166

~iter_list(){ }

167

168

iter_list & operator=(const list<T, Allocator>::iter_list & right ){

169

current = right.current;

170

return *this;

171

}

172

173

T & operator*(){

174

return *(current->val);

175

}

176

T * operator->(){

177

return current->val;

178

}

179

const T & operator*() const{

180

return *current->val;

181

}

182

const T * operator->() const{

183

return current->val;

184

}

185

186

bool operator==(const list<T, Allocator>::iter_list & right) const {

187

return (current == right.current);

188

}

189

190

bool operator!=(const list<T, Allocator>::iter_list & right) const {

191

return (current != right.current);

192

}

193

194

iter_list & operator++(){

195

current = current->next;

196

return *this;

197

}

198

199

iter_list operator++(int){

200

iter_list temp(current);

201

current = current->next;

202

return temp;

203

}

204

iter_list & operator--(){

205

current = current->previous;

206

return *this;

207

}

208

209

iter_list operator--(int){

210

iter_list temp(current);

211

current = current->previous;

212

return temp;

213

}

214

node * link_struct(){

215

return current;

216

}

217

iter_list & operator+=(unsigned int n){

218

for(unsigned int i = 0; i < n; ++i){

219

current = current->next;

220

}

221

return *this;

222

}

223

iter_list & operator-=(unsigned int n){

224

for(unsigned int i = 0; i < n; ++i){

225

current = current->previous;

226

}

227

return *this;

228

}

229

};

230

231

232

template<class T, class Allocator> list<T, Allocator>::list(const Allocator& al)

233

:list_start(0), list_end(0), elements(0), a(al)

234

{

235

//End node

236

list_start = new node();

237

list_end = list_start;

238

return;

239

}

240

241

template<class T, class Allocator> list<T, Allocator>::list

242

(typename Allocator::size_type n, const T& value, const Allocator& al)

243

:list_start(0), list_end(0), elements(0), a(al)

244

{

245

//End node

246

list_start = new node();

247

list_end = list_start;

248

249

for(typename Allocator::size_type i = 0; i < n ; ++i){

250

push_back(value);

251

}

252

}

253

254

template<class T, class Allocator> template <class InputIterator>

255

list<T, Allocator>::list

256

(InputIterator first, InputIterator last, const Allocator& al)

257

: list_start(0), list_end(0), elements(0), a(al)

258

{

259

list_start = new node();

260

list_end = list_start;

261

while(first != last){

262

push_back(*first);

263

++first;

264

}

265

}

266

267

template<class T, class Allocator> list<T, Allocator>::list(const list<T,Allocator>& x)

268

: list_start(0), list_end(0), elements(0), a(x.a)

269

{

270

list_start = new node();

271

list_end = list_start;

272

273

iterator i = x.begin();

274

while(i != x.end()){

275

push_back( *i);

276

++i;

277

}

278

}

279

280

template<class T, class Allocator> list<T, Allocator>::~list(){

281

while(elements > 0){

282

pop_front();

283

}

284

delete list_start->val;

285

#if UCLIBCXX_DEBUG

286

list_start->val = 0;

287

#endif

288

delete list_start;

289

#if UCLIBCXX_DEBUG

290

list_start = 0;

291

list_end = 0;

292

#endif

293

}

294

295

296

template<class T, class Allocator> void list<T, Allocator>::swap_nodes(node * x, node * y){

297

T * v = x->val;

298

x->val = y->val;

299

y->val = v;

300

}

301

302

template<class T, class Allocator> typename list<T, Allocator>::iterator

303

list<T, Allocator>::begin()

304

{

305

return iterator(list_start);

306

}

307

308

309

template<class T, class Allocator> typename list<T, Allocator>::const_iterator

310

list<T, Allocator>::begin() const

311

{

312

return const_iterator(list_start);

313

}

314

315

316

template<class T, class Allocator> typename list<T, Allocator>::iterator

317

list<T, Allocator>::end()

318

{

319

return iterator(list_end);

320

}

321

322

template<class T, class Allocator> typename list<T, Allocator>::const_iterator

323

list<T, Allocator>::end() const

324

{

325

return const_iterator(list_end);

326

}

327

328

template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator

329

list<T, Allocator>::rbegin()

330

{

331

return reverse_iterator(end());

332

}

333

334

template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator

335

list<T, Allocator>::rbegin() const

336

{

337

return const_reverse_iterator(end());

338

}

339

340

template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator

341

list<T, Allocator>::rend()

342

{

343

return reverse_iterator(begin());

344

}

345

346

template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator

347

list<T, Allocator>::rend() const

348

{

349

return const_reverse_iterator(begin());

350

}

351

352

template<class T, class Allocator> bool list<T, Allocator>::empty() const{

353

return (elements == 0);

354

}

355

template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::size() const{

356

return elements;

357

}

358

template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::max_size() const{

359

return ((size_type)(-1)) / (sizeof(T) + sizeof(node));

360

}

361

template<class T, class Allocator> void list<T, Allocator>::resize(typename Allocator::size_type sz, T c){

362

// if(sz > elements){

363

for(typename Allocator::size_type i = elements; i < sz; ++i){

364

push_back(c);

365

}

366

// }

367

// if(sz < elements){

368

for(typename Allocator::size_type i = elements; i > sz; --i){

369

pop_back();

370

}

371

// }

372

}

373

374

template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::front(){

375

return *(list_start->val);

376

}

377

template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::front() const{

378

return *(list_start->val);

379

}

380

template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::back(){

381

return *(list_end->previous->val);

382

}

383

template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::back() const{

384

return *(list_end->previous->val);

385

}

386

387

388

template<class T, class Allocator> void list<T, Allocator>::push_front(const T& x){

389

node * temp = new node(x);

390

list_start->previous = temp;

391

temp->previous = 0;

392

temp->next = list_start;

393

list_start = temp;

394

++elements;

395

}

396

397

template<class T, class Allocator> void list<T, Allocator>::pop_front(){

398

if(elements > 0){

399

list_start = list_start->next;

400

delete list_start->previous->val;

401

#if UCLIBCXX_DEBUG

402

list_start->previous->val = 0;

403

list_start->previous->next = 0;

404

list_start->previous->previous = 0;

405

#endif

406

delete list_start->previous;

407

list_start->previous = 0;

408

--elements;

409

}

410

}

411

412

template<class T, class Allocator> void list<T, Allocator>::push_back(const T& x){

413

if(elements == 0){

414

//The list is completely empty

415

list_start = new node(x);

416

list_end->previous = list_start;

417

list_start->previous = 0;

418

list_start->next = list_end;

419

elements = 1;

420

}else{

421

node * temp = new node(x);

422

temp->previous = list_end->previous;

423

temp->next = list_end;

424

list_end->previous->next = temp;

425

list_end->previous = temp;

426

++elements;

427

}

428

}

429

430

template<class T, class Allocator> void list<T, Allocator>::pop_back(){

431

if(elements > 0){

432

node * temp = list_end->previous;

433

if(temp == list_start){

434

list_end->previous = 0;

435

list_start = list_end;

436

}else{

437

temp->previous->next = temp->next;

438

list_end->previous = temp->previous;

439

}

440

delete temp->val;

441

#if UCLIBCXX_DEBUG

442

temp->val = 0;

443

temp->next = 0;

444

temp->previous = 0;

445

#endif

446

delete temp;

447

#if UCLIBCXX_DEBUG

448

temp = 0;

449

#endif

450

--elements;

451

}

452

}

453

454

455

template<class T, class Allocator> typename list<T, Allocator>::iterator

456

list<T, Allocator>::insert(iterator position, const T& x)

457

{

458

node * temp = new node(x);

459

460

temp->previous = position.link_struct()->previous;

461

temp->next = position.link_struct();

462

463

if(temp->previous == 0){

464

list_start = temp;

465

}else{

466

position.link_struct()->previous->next = temp;

467

}

468

469

position.link_struct()->previous = temp;

470

471

++elements;

472

--position;

473

return position;

474

}

475

476

template<class T, class Allocator> void list<T, Allocator>::insert(iterator position, size_type n, const T& x){

477

for(typename list<T, Allocator>::size_type i = 0; i < n; ++i){

478

position = insert(position, x);

479

}

480

}

481

482

template<class T, class Allocator> template <class InputIterator> void

483

list<T, Allocator>::insert(iterator position, InputIterator first, InputIterator last)

484

{

485

while(first !=last){

486

insert(position, *first);

487

++first;

488

}

489

}

490

template<class T, class Allocator> typename list<T, Allocator>::iterator

491

list<T, Allocator>::erase(iterator position)

492

{

493

if(position != end() ){

494

node * temp = position.link_struct();

495

if(temp == list_start){

496

++position;

497

temp->next->previous = 0;

498

list_start = temp->next;

499

}else{

500

--position;

501

temp->next->previous = temp->previous;

502

temp->previous->next = temp->next;

503

++position;

504

}

505

delete temp->val;

506

#if UCLIBCXX_DEBUG

507

temp->next = 0;

508

temp->previous = 0;

509

temp->val = 0;

510

#endif

511

delete temp;

512

#if UCLIBCXX_DEBUG

513

temp = 0;

514

#endif

515

--elements;

516

}

517

return position;

518

}

519

template<class T, class Allocator> typename list<T, Allocator>::iterator

520

list<T, Allocator>::erase(iterator position, iterator last)

521

{

522

iterator temp = position;

523

while(position !=last){

524

position = erase(position);

525

}

526

return position;

527

}

528

template<class T, class Allocator> void list<T, Allocator>::swap(list<T,Allocator>& l){

529

node * temp;

530

size_type tempel;

531

532

temp = list_start;

533

list_start = l.list_start;

534

l.list_start = temp;

535

536

temp = list_end;

537

list_end = l.list_end;

538

l.list_end = temp;

539

540

tempel = elements;

541

elements = l.elements;

542

l.elements = tempel;

543

}

544

template<class T, class Allocator> void list<T, Allocator>::clear(){

545

while(elements > 0){

546

pop_front();

547

}

548

}

549

550

template<class T, class Allocator>

551

void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x)

552

{

553

554

//Can't add non-existant elements

555

if(x.elements == 0){

556

return;

557

}

558

559

elements += x.elements;

560

x.elements = 0;

561

562

563

//Chaining to the begining

564

if(position == begin()){

565

x.list_end->previous->next = list_start;

566

list_start->previous = x.list_end->previous;

567

568

list_start = x.list_start;

569

570

x.list_start = x.list_end;

571

x.list_end->previous = 0;

572

573

return;

574

}

575

576

//Link everything we need

577

x.list_start->previous = position.link_struct()->previous;

578

position.link_struct()->previous->next = x.list_start;

579

580

position.link_struct()->previous = x.list_end->previous;

581

x.list_end->previous->next = position.link_struct();

582

583

//Clean up the other list

584

585

x.list_start = x.list_end;

586

x.list_end->previous=0;

587

588

}

589

590

template<class T, class Allocator>

591

void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x, iterator i)

592

{

593

//Invalid conditions

594

if( x.elements == 0 || i == position || position.link_struct() == i.link_struct()->next ){

595

return;

596

}

597

598

599

//Do we need to adjust the begining pointer?

600

if(i == x.begin()){

601

x.list_start = x.list_start->next;

602

x.list_start->previous = 0;

603

}

604

605

606

//Insert at begining special case

607

if(position == begin()){

608

609

i.link_struct()->previous->next = i.link_struct()->next;

610

i.link_struct()->next->previous = i.link_struct()->previous;

611

612

i.link_struct()->previous = 0;

613

i.link_struct()->next = position.link_struct();

614

position.link_struct()->previous = i.link_struct();

615

616

list_start = i.link_struct();

617

618

--x.elements;

619

++elements;

620

return;

621

}

622

623

if( i.link_struct()->previous != 0){

624

i.link_struct()->previous->next = i.link_struct()->next;

625

i.link_struct()->next->previous = i.link_struct()->previous;

626

}else{

627

i.link_struct()->next->previous = 0;

628

x.list_start = i.link_struct()->next;

629

}

630

631

i.link_struct()->previous = position.link_struct()->previous;

632

position.link_struct()->previous->next = i.link_struct();

633

634

i.link_struct()->next = position.link_struct();

635

position.link_struct()->previous = i.link_struct();

636

637

--x.elements;

638

++elements;

639

}

640

641

template<class T, class Allocator>

642

void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x,

643

iterator first, iterator last)

644

{

645

if(x.elements == 0){

646

return;

647

}

648

649

iterator temp;

650

while(first != last){

651

temp = first;

652

++first;

653

splice(position, x, temp);

654

}

655

}

656

657

658

template<class T, class Allocator> void list<T, Allocator>::remove(const T& value){

659

iterator temp = begin();

660

while( temp != end() ){

661

if(*temp == value){

662

temp = erase(temp);

663

}else{

664

++temp;

665

}

666

}

667

}

668

669

670

template<class T, class Allocator> template <class Predicate> void list<T, Allocator>::remove_if(Predicate pred){

671

iterator temp = begin();

672

while( temp != end() ){

673

if( pred(*temp) ){

674

temp = erase(temp);

675

}else{

676

++temp;

677

}

678

}

679

}

680

681

682

template<class T, class Allocator> void list<T, Allocator>::unique(){

683

equal_to<typename iterator_traits<iterator>::value_type> p;

684

unique(p);

685

}

686

687

template<class T, class Allocator> template <class BinaryPredicate>

688

void list<T, Allocator>::unique(BinaryPredicate binary_pred)

689

{

690

iterator temp1 = begin();

691

iterator temp2;

692

++temp1;

693

while( temp1 != end() ){

694

temp2 = temp1;

695

--temp2;

696

if( binary_pred(*temp1, *temp2) ){

697

erase(temp1);

698

temp1 = temp2;

699

}

700

++temp1;

701

}

702

}

703

704

template<class T, class Allocator> void list<T, Allocator>::merge(list<T,Allocator>& x){

705

less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;

706

merge(x, c);

707

}

708

709

template<class T, class Allocator> template <class Compare>

710

void list<T, Allocator>::merge(list<T,Allocator>& x, Compare comp)

711

{

712

iterator source = x.begin();

713

iterator temp;

714

iterator dest = begin();

715

716

while(source != x.end()){

717

while( dest != end() && comp (*dest, *source) ){

718

++dest;

719

}

720

++elements;

721

--x.elements;

722

723

temp = source;

724

++temp;

725

726

if(dest == begin()){

727

dest.link_struct()->previous = source.link_struct();

728

source.link_struct()->next = dest.link_struct();

729

source.link_struct()->previous = 0;

730

list_start = source.link_struct();

731

}else{

732

source.link_struct()->previous = dest.link_struct()->previous;

733

dest.link_struct()->previous->next = source.link_struct();

734

source.link_struct()->next = dest.link_struct();

735

dest.link_struct()->previous = source.link_struct();

736

}

737

source = temp;

738

}

739

740

//Fix up x;

741

x.list_start = x.list_end;

742

x.list_start->previous = 0;

743

}

744

745

template<class T, class Allocator> void list<T, Allocator>::sort(){

746

less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;

747

sort(c);

748

}

749

750

template<class T, class Allocator> template <class Compare>

751

void list<T, Allocator>::sort(Compare comp)

752

{

753

typename list<T, Allocator>::iterator i, j, k;

754

755

//FIXME - bubble sort

756

757

if(elements == 0){

758

return;

759

}

760

761

i = end();

762

--i;

763

while(i != begin()){

764

j = begin();

765

k = j;

766

++k;

767

while(j != i){

768

if( comp(*k, *j) ){

769

swap_nodes(k.link_struct(), j.link_struct());

770

}

771

++j;

772

++k;

773

}

774

--i;

775

}

776

}

777

778

779

template<class T, class Allocator> void list<T, Allocator>::reverse(){

780

if(elements == 0){

781

return;

782

}

783

784

node * current;

785

node * following;

786

node * temp;

787

788

//Need to move the list_end element to the begining

789

790

temp = list_end;

791

list_end = temp->previous;

792

list_end->next = 0;

793

794

list_start->previous = temp;

795

temp->previous = 0;

796

temp->next = list_start;

797

list_start = temp;

798

799

current = list_start;

800

801

while( current != list_end ){

802

following = current->next;

803

804

//Swap the values pointed to/at with the current node

805

temp = current->next;

806

current->next = current->previous;

807

current->previous = temp;

808

809

current = following;

810

}

811

812

//Swap pointers on the end node

813

temp = list_end->next;

814

list_end->next = list_end->previous;

815

list_end->previous = temp;

816

817

818

//Swap the fixed pointers

819

temp = list_start;

820

list_start = list_end;

821

list_end = temp;

822

823

}

824

825

template <class T, class Allocator>

826

bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y){

827

if(x.size() != y.size()){

828

return false;

829

}

830

typename list<T,Allocator>::const_iterator i = x.begin();

831

typename list<T,Allocator>::const_iterator j = y.begin();

832

833

while(i != x.end()){

834

if( *i != *j){

835

return false;

836

}

837

++i;

838

++j;

839

}

840

return true;

841

}

842

843

template <class T, class Allocator>

844

bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y){

845

typename list<T,Allocator>::const_iterator i = x.begin();

846

typename list<T,Allocator>::const_iterator j = y.begin();

847

while(i != x.end() && j != y.end()){

848

if( *i < *j){

849

return true;

850

}

851

if(*j < *i){

852

return false;

853

}

854

++i;

855

++j;

856

}

857

return (i == x.end() && j != y.end());

858

}

859

860

template <class T, class Allocator>

861

bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y){

862

return !(x == y);

863

}

864

865

template <class T, class Allocator>

866

bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y){

867

typename list<T,Allocator>::const_iterator i = x.begin();

868

typename list<T,Allocator>::const_iterator j = y.begin();

869

while(i != x.end() && j != y.end()){

870

if( *i > *j){

871

return true;

872

}

873

if( *j > *i){

874

return false;

875

}

876

++i;

877

++j;

878

}

879

return (i != x.end() && j == y.end());

880

}

881

882

template <class T, class Allocator>

883

bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y){

884

typename list<T,Allocator>::const_iterator i = x.begin();

885

typename list<T,Allocator>::const_iterator j = y.begin();

886

while(i != x.end() && j != y.end()){

887

if( *i >= *j){

888

return true;

889

}

890

if(*j >= *i){

891

return false;

892

}

893

++i;

894

++j;

895

}

896

return (i != x.end() && j == y.end());

897

}

898

899

template <class T, class Allocator>

900

bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y){

901

typename list<T,Allocator>::const_iterator i = x.begin();

902

typename list<T,Allocator>::const_iterator j = y.begin();

903

while(i != x.end() && j != y.end()){

904

if( *i <= *j){

905

return true;

906

}

907

if(*j <= *i){

908

return false;

909

}

910

++i;

911

++j;

912

}

913

return (i == x.end());

914

}

915

916

template <class T, class Allocator>

917

void swap(list<T,Allocator>& x, list<T,Allocator>& y){

918

x.swap(y);

919

}

920

921

}

922

923

#pragma GCC visibility pop

924

925

#endif

926

927

Older »