/elec/propeller-clock : revision 91

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/deque

Committer: Tim Marston
Date: 2012-05-23 23:02:50 UTC
Revision ID: tim@ed.am-20120523230250-3pls2u6zt3av0uam

fixed text glitch; extended all modes; added screen flip super-long press;
added button unpress debounde; moved interim button press ignoration to
settings mode; fixed left-over led issue; finished for demo!

files added:
src/TODO

src/common.cc

src/common.h

src/modes

src/modes/digital_clock_mode.cc

src/modes/digital_clock_mode.h

src/modes/info_mode.cc

src/modes/info_mode.h

src/modes/major_mode.cc

src/modes/major_mode.h

src/modes/mode.cc

src/modes/mode.h

src/modes/settings_major_mode.cc

src/modes/settings_major_mode.h

src/modes/switcher_major_mode.cc

src/modes/switcher_major_mode.h

src/nvram.h

src/text.cc

src/text.h

src/text_renderer.cc

src/text_renderer.h

src/util/PString.cpp

src/util/PString.h

test/rtc-test

test/rtc-test/Makefile

test/rtc-test/rtc-ds1307.ino

test/rtc-test/util

test/rtc-test/util/DS1307.cpp

test/rtc-test/util/DS1307.h

files removed:
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/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

files renamed:
src/analogue_clock_mode.cc => src/modes/analogue_clock_mode.cc

src/analogue_clock_mode.h => src/modes/analogue_clock_mode.h

src/test_mode.cc => src/modes/test_pattern_mode.cc

src/test_mode.h => src/modes/test_pattern_mode.h

src/propeller-clock.ino => src/propeller-clock.cc

files modified:
.bzrignore

arduino.mk

electronics-information

notes

project/propeller-clock.sch

src/Makefile

src/button.cc

src/button.h

src/config.h

src/time.cc

src/time.h

Show diffs side-by-side

added added

removed removed

src/utility/deque

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 <stdexcept>

#pragma GCC visibility push(default)

#ifndef __STD_HEADER_DEQUE

#define __STD_HEADER_DEQUE

namespace std{

template <class T, class Allocator = allocator<T> > class deque;

template <class T, class Allocator> bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

template <class T, class Allocator> void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);

template <class T, class Allocator> class _UCXXEXPORT deque {

public:

friend bool operator==<>(const deque<T, Allocator>& x, const deque<T, Allocator>& y);

friend class deque_iter;

friend class deque_citer;

class deque_iter;

class deque_citer;

typedef typename Allocator::reference reference;

typedef typename Allocator::const_reference const_reference;

typedef deque_iter iterator;

typedef deque_citer const_iterator;

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;

typedef std::reverse_iterator<iterator> reverse_iterator;

typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

explicit deque(const Allocator& al = Allocator());

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

template <class InputIterator> deque(InputIterator first, InputIterator last, const Allocator& = Allocator());

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

~deque();

deque<T,Allocator>& operator=(const deque<T,Allocator>& x);

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;

size_type size() const;

size_type max_size() const;

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

bool empty() const;

reference operator[](size_type n);

const_reference operator[](size_type n) const;

reference at(size_type n);

const_reference at(size_type n) const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

void push_front(const T& x);

void push_back(const T& x);

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

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

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

100

void pop_front();

101

void pop_back();

102

103

iterator erase(iterator position);

104

iterator erase(iterator first, iterator last);

105

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

106

void clear();

107

108

protected:

109

void reserve(size_type n);

110

inline size_type array_element(size_type deque_element) const{

111

if(deque_element < (data_size - first_element)){

112

return first_element + deque_element;

113

}

114

return deque_element - (data_size - first_element);

115

}

116

inline size_type first_subtract(size_type sub_size) const{

117

if(sub_size > first_element){

118

return (data_size - first_element) - sub_size;

119

}

120

return first_element - sub_size;

121

}

122

123

T * data;

124

size_type data_size; //Physical size of array

125

size_type elements; //Elements in array

126

size_type first_element; //Element number of array 0..n

127

size_type last_element; //Element number of array 0..n

128

Allocator a;

129

130

};

131

132

133

template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_iter

134

: public std::iterator<

135

random_access_iterator_tag,

136

137

typename Allocator::difference_type,

138

typename Allocator::pointer,

139

typename Allocator::reference

140

141

{

142

friend class deque<T, Allocator>;

143

protected:

144

deque<T, Allocator> * container;

145

typename Allocator::size_type element;

146

147

public:

148

deque_iter() : container(0), element(0) { }

149

deque_iter(const deque_iter & d) : container (d.container), element(d.element) { }

150

deque_iter(deque<T, Allocator> * c, typename Allocator::size_type e)

151

: container(c), element(e)

152

{

153

return;

154

}

155

~deque_iter() { }

156

deque_iter & operator=(const deque_iter & d){

157

container = d.container;

158

element = d.element;

159

return *this;

160

}

161

T & operator*(){

162

return container->data[container->array_element(element)];

163

}

164

T * operator->(){

165

return container->data + container->array_element(element);

166

}

167

const T & operator*() const{

168

return container->data[container->array_element(element)];

169

}

170

const T * operator->() const{

171

return container->data + container->array_element(element);

172

}

173

bool operator==(const deque_iter & d) const{

174

if(container == d.container && element == d.element){

175

return true;

176

}

177

return false;

178

}

179

bool operator==(const deque_citer & d) const{

180

if(container == d.container && element == d.element){

181

return true;

182

}

183

return false;

184

}

185

bool operator!=(const deque_iter & d) const{

186

if(container != d.container || element != d.element){

187

return true;

188

}

189

return false;

190

}

191

bool operator!=(const deque_citer & d) const{

192

if(container != d.container || element != d.element){

193

return true;

194

}

195

return false;

196

}

197

bool operator<(const deque_iter & d) const{

198

if(element < d.element){

199

return true;

200

}

201

return false;

202

}

203

bool operator<(const deque_citer & d) const{

204

if(element < d.element){

205

return true;

206

}

207

return false;

208

}

209

bool operator<=(const deque_iter & d) const{

210

if(element <= d.element){

211

return true;

212

}

213

return false;

214

}

215

bool operator<=(const deque_citer & d) const{

216

if(element <= d.element){

217

return true;

218

}

219

return false;

220

}

221

bool operator>(const deque_iter & d) const{

222

if(element > d.element){

223

return true;

224

}

225

return false;

226

}

227

bool operator>(const deque_citer & d) const{

228

if(element > d.element){

229

return true;

230

}

231

return false;

232

}

233

bool operator>=(const deque_iter & d) const{

234

if(element >= d.element){

235

return true;

236

}

237

return false;

238

}

239

bool operator>=(const deque_citer & d) const{

240

if(element >= d.element){

241

return true;

242

}

243

return false;

244

}

245

deque_iter & operator++(){

246

++element;

247

return *this;

248

}

249

deque_iter operator++(int){

250

deque_iter temp(container, element);

251

++element;

252

return temp;

253

}

254

deque_iter operator+(typename Allocator::size_type n){

255

deque_iter temp(container, element + n);

256

return temp;

257

}

258

deque_iter & operator+=(typename Allocator::size_type n){

259

element += n;

260

return *this;

261

}

262

deque_iter & operator--(){

263

--element;

264

return *this;

265

}

266

deque_iter operator--(int){

267

deque_iter temp(container, element);

268

--element;

269

return temp;

270

}

271

deque_iter operator-(typename Allocator::size_type n){

272

deque_iter temp(container, element - n);

273

return temp;

274

}

275

deque_iter & operator-=(typename Allocator::size_type n){

276

element -= n;

277

return *this;

278

}

279

typename Allocator::size_type operator-(const deque_iter & d){

280

return element - d.element;

281

}

282

283

};

284

285

template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_citer

286

: public std::iterator<

287

random_access_iterator_tag,

288

289

typename Allocator::difference_type,

290

typename Allocator::const_pointer,

291

typename Allocator::const_reference

292

293

{

294

friend class deque<T, Allocator>;

295

protected:

296

const deque<T, Allocator> * container;

297

typename Allocator::size_type element;

298

299

public:

300

deque_citer() : container(0), element(0) { }

301

deque_citer(const deque_citer & d) : container (d.container), element(d.element) { }

302

deque_citer(const deque_iter & d) : container (d.container), element(d.element) { }

303

deque_citer(const deque<T, Allocator> * c, typename Allocator::size_type e)

304

: container(c), element(e)

305

{

306

return;

307

}

308

~deque_citer() { }

309

deque_citer & operator=(const deque_iter & d){

310

container = d.container;

311

element = d.element;

312

return *this;

313

}

314

const T & operator*() const{

315

return container->data[container->array_element(element)];

316

}

317

const T * operator->() const{

318

return container->data + container->array_element(element);

319

}

320

bool operator==(const deque_citer & d) const{

321

if(container == d.container && element == d.element){

322

return true;

323

}

324

return false;

325

}

326

bool operator==(const deque_iter & d) const{

327

if(container == d.container && element == d.element){

328

return true;

329

}

330

return false;

331

}

332

bool operator!=(const deque_citer & d) const{

333

if(container != d.container || element != d.element){

334

return true;

335

}

336

return false;

337

}

338

bool operator!=(const deque_iter & d) const{

339

if(container != d.container || element != d.element){

340

return true;

341

}

342

return false;

343

}

344

bool operator<(const deque_citer & d) const{

345

if(element < d.element){

346

return true;

347

}

348

return false;

349

}

350

bool operator<(const deque_iter & d) const{

351

if(element < d.element){

352

return true;

353

}

354

return false;

355

}

356

bool operator<=(const deque_citer & d) const{

357

if(element <= d.element){

358

return true;

359

}

360

return false;

361

}

362

bool operator<=(const deque_iter & d) const{

363

if(element <= d.element){

364

return true;

365

}

366

return false;

367

}

368

bool operator>(const deque_citer & d) const{

369

if(element > d.element){

370

return true;

371

}

372

return false;

373

}

374

bool operator>(const deque_iter & d) const{

375

if(element > d.element){

376

return true;

377

}

378

return false;

379

}

380

bool operator>=(const deque_citer & d){

381

if(element >= d.element){

382

return true;

383

}

384

return false;

385

}

386

bool operator>=(const deque_iter & d){

387

if(element >= d.element){

388

return true;

389

}

390

return false;

391

}

392

deque_citer & operator++(){

393

++element;

394

return *this;

395

}

396

deque_citer operator++(int){

397

deque_citer temp(container, element);

398

++element;

399

return temp;

400

}

401

deque_citer operator+(typename Allocator::size_type n){

402

deque_citer temp(container, element + n);

403

return temp;

404

}

405

deque_citer & operator+=(typename Allocator::size_type n){

406

element += n;

407

return *this;

408

}

409

deque_citer & operator--(){

410

--element;

411

return *this;

412

}

413

deque_citer operator--(int){

414

deque_citer temp(container, element);

415

--element;

416

return temp;

417

}

418

deque_citer operator-(typename Allocator::size_type n){

419

deque_citer temp(container, element - n);

420

return temp;

421

}

422

deque_citer & operator-=(typename Allocator::size_type n){

423

element -= n;

424

return *this;

425

}

426

typename Allocator::size_type operator-(const deque_citer & d){

427

return element - d.element;

428

}

429

430

};

431

432

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

433

: data(0),

434

data_size(0), elements(0), first_element(0), last_element(0), a(al)

435

{

436

data_size = __UCLIBCXX_STL_BUFFER_SIZE__;

437

data = a.allocate(data_size);

438

first_element = data_size /2;

439

last_element = first_element;

440

}

441

442

443

template<class T, class Allocator> deque<T, Allocator>::deque(

444

size_type n, const T& value, const Allocator& al)

445

: data(0),

446

elements(n), first_element(0), last_element(0), a(al)

447

{

448

data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;

449

data = a.allocate(data_size);

450

first_element = (data_size - elements) / 2;

451

last_element = first_element;

452

453

for(n=first_element ; n < last_element; ++n ){

454

a.construct(data+n, value);

455

}

456

}

457

458

459

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

460

deque<T, Allocator>::deque(InputIterator first, InputIterator last, const Allocator& al)

461

: data(0),

462

data_size(0), elements(0), first_element(0), last_element(0), a(al)

463

{

464

data_size = __UCLIBCXX_STL_BUFFER_SIZE__;

465

data = a.allocate(data_size);

466

first_element = data_size / 4; //Note sure how big, but let's add a little space...

467

last_element = first_element;

468

while(first != last){

469

push_back(*first);

470

++first;

471

}

472

}

473

474

475

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

476

: data(0),

477

elements(0), first_element(0), last_element(0), a(x.a)

478

{

479

data_size = x.elements + __UCLIBCXX_STL_BUFFER_SIZE__;

480

data = a.allocate(data_size);

481

first_element = (data_size - x.elements) / 2;

482

last_element = first_element;

483

for(size_type i=0; i < x.elements; ++i){

484

push_back(x[i]);

485

}

486

}

487

488

489

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

490

clear();

491

a.deallocate(data, data_size);

492

}

493

494

template<class T, class Allocator> deque<T,Allocator>& deque<T, Allocator>::

495

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

496

{

497

if(&x == this){

498

return *this;

499

}

500

resize(x.elements);

501

for(size_t i = 0; i < elements; ++i){

502

data[array_element(i)] = x[i];

503

}

504

return *this;

505

}

506

507

508

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

509

deque<T, Allocator>::assign(InputIterator first, InputIterator last)

510

{

511

clear();

512

while(first !=last){

513

push_back(*first);

514

++first;

515

}

516

}

517

518

519

template<class T, class Allocator> template <class Size, class U> void

520

deque<T, Allocator>::assign(Size n, const U& u)

521

{

522

if(&u == this){

523

return;

524

}

525

clear();

526

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

527

push_back(u);

528

}

529

}

530

531

532

template<class T, class Allocator> typename deque<T, Allocator>::allocator_type

533

deque<T, Allocator>::get_allocator() const

534

{

535

return a;

536

}

537

538

template<class T, class Allocator> typename

539

deque<T, Allocator>::iterator deque<T, Allocator>::begin()

540

{

541

return deque_iter(this, 0);

542

}

543

544

545

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

546

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

547

{

548

return deque_citer(this, 0);

549

}

550

551

template<class T, class Allocator> typename

552

deque<T, Allocator>::iterator deque<T, Allocator>::end()

553

{

554

return deque_iter(this, elements);

555

}

556

557

template<class T, class Allocator> typename

558

deque<T, Allocator>::const_iterator deque<T, Allocator>::end() const

559

{

560

return deque_citer(this, elements);

561

}

562

563

template<class T, class Allocator> typename

564

deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rbegin()

565

{

566

return reverse_iterator(end());

567

}

568

569

template<class T, class Allocator> typename

570

deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rbegin() const

571

{

572

return const_reverse_iterator(end());

573

}

574

575

template<class T, class Allocator> typename

576

deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rend()

577

{

578

return reverse_iterator(begin());

579

}

580

581

template<class T, class Allocator> typename

582

deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rend() const

583

{

584

return const_reverse_iterator(begin());

585

}

586

587

template<class T, class Allocator> typename

588

deque<T, Allocator>::size_type deque<T, Allocator>::size() const

589

{

590

return elements;

591

}

592

593

template<class T, class Allocator> typename

594

deque<T, Allocator>::size_type deque<T, Allocator>::max_size() const

595

{

596

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

597

}

598

599

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

600

reserve(sz);

601

while(sz > size()){

602

push_back(c);

603

}

604

while(sz < size()){

605

pop_back();

606

}

607

}

608

609

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

610

return (elements == 0);

611

}

612

613

template<class T, class Allocator> typename

614

deque<T, Allocator>::reference deque<T, Allocator>::operator[](size_type n)

615

{

616

return data[array_element(n)];

617

}

618

619

template<class T, class Allocator> typename

620

deque<T, Allocator>::const_reference deque<T, Allocator>::operator[](size_type n) const

621

{

622

return data[array_element(n)];

623

}

624

625

template<class T, class Allocator> typename

626

deque<T, Allocator>::reference deque<T, Allocator>::at(size_type n)

627

{

628

if(n > elements){

629

__throw_out_of_range("Out of deque range");

630

}

631

return data[array_element(n)];

632

}

633

634

template<class T, class Allocator> typename

635

deque<T, Allocator>::const_reference deque<T, Allocator>::at(size_type n) const

636

{

637

if(n > elements){

638

__throw_out_of_range("Out of deque range");

639

}

640

return data[array_element(n)];

641

}

642

643

template<class T, class Allocator> typename

644

deque<T, Allocator>::reference deque<T, Allocator>::front()

645

{

646

return data[first_element];

647

}

648

649

template<class T, class Allocator> typename

650

deque<T, Allocator>::const_reference deque<T, Allocator>::front() const

651

{

652

return data[first_element];

653

}

654

655

template<class T, class Allocator> typename

656

deque<T, Allocator>::reference deque<T, Allocator>::back()

657

{

658

return data[array_element(elements-1)];

659

}

660

661

template<class T, class Allocator> typename

662

deque<T, Allocator>::const_reference deque<T, Allocator>::back() const

663

{

664

return data[array_element(elements-1)];

665

}

666

667

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

668

reserve(elements + 1);

669

first_element = first_subtract(1);

670

a.construct(data + first_element, x);

671

++elements;

672

}

673

674

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

675

reserve(elements + 1);

676

a.construct(data + last_element, x);

677

++elements;

678

last_element = array_element(elements);

679

}

680

681

template<class T, class Allocator> typename

682

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

683

{

684

reserve(elements+1);

685

if(position.element > (elements/2)){

686

//Push all elements back 1

687

push_back(x);

688

for(size_type i = elements-1; i > position.element; --i){

689

at(i) = at(i-1);

690

}

691

}else{

692

//Push all elements forward 1

693

push_front(x);

694

for(size_type i = 0; i < position.element; ++i){

695

at(i) = at(i+1);

696

}

697

}

698

at(position.element) = x;

699

return deque_iter(this, position.element);

700

}

701

702

template<class T, class Allocator> void deque<T, Allocator>::

703

insert(typename deque<T, Allocator>::iterator position, size_type n, const T& x)

704

{

705

reserve(elements + n);

706

for(size_t i =0; i < n; ++i){

707

position = insert(position, x);

708

}

709

}

710

711

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

712

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

713

{

714

while(first != last){

715

position = insert(position, *first);

716

++first;

717

}

718

}

719

720

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

721

if(elements == 0){

722

__throw_out_of_range("deque pop_front");

723

}

724

a.destroy(data + first_element);

725

first_element = array_element(1);

726

--elements;

727

}

728

729

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

730

last_element = array_element(elements - 1);

731

a.destroy(data + last_element);

732

--elements;

733

}

734

735

template<class T, class Allocator> typename

736

deque<T, Allocator>::iterator deque<T, Allocator>::erase(typename deque<T, Allocator>::iterator position)

737

{

738

if(position.element > (elements /2)){

739

for(size_type i = position.element; i < elements - 1; ++i){

740

at(i) = at(i+1);

741

}

742

pop_back();

743

}else{

744

for(size_type i = position.element; i > 0; --i){

745

at(i) = at(i-1);

746

}

747

pop_front();

748

}

749

return deque_iter(this, position.element);

750

}

751

752

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

753

deque<T, Allocator>::

754

erase(typename deque<T, Allocator>::iterator first, typename deque<T, Allocator>::iterator last)

755

{

756

//Shift backwards

757

size_type num_move = last.element - first.element;

758

if( first.element > (elements - last.element) ){

759

for(size_type i = last.element; i < elements ; ++i){

760

at(i-num_move) = at(i);

761

}

762

for(size_type i = 0; i < num_move ; ++i){

763

pop_back();

764

}

765

}else{

766

for(size_type i = 0; i < first.element ; ++i){

767

at(last.element - i - 1) = at(first.element - i - 1);

768

}

769

for(size_type i = 0; i < num_move ; ++i){

770

pop_front();

771

}

772

}

773

return deque_iter(this, first.element);

774

}

775

776

template<class T, class Allocator> void deque<T, Allocator>::swap(deque<T,Allocator>& x)

777

{

778

T * temp_data;

779

typename deque<T,Allocator>::size_type temp_size;

780

781

//Swap data pointers

782

temp_data = x.data;

783

x.data = data;

784

data = temp_data;

785

786

//Swap array sizes

787

temp_size = x.data_size;

788

x.data_size = data_size;

789

data_size = temp_size;

790

791

//Swap num array elements

792

temp_size = x.elements;

793

x.elements = elements;

794

elements = temp_size;

795

796

//Swap first_pointer

797

temp_size = x.first_element;

798

x.first_element = first_element;

799

first_element = temp_size;

800

801

//Swap last_pointer

802

temp_size = x.last_element;

803

x.last_element = last_element;

804

last_element = temp_size;

805

}

806

807

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

808

{

809

while(elements > 0 ){

810

pop_back();

811

}

812

}

813

814

815

template<class T, class Allocator> void deque<T, Allocator>::reserve(typename deque<T, Allocator>::size_type n)

816

{

817

if(data_size >= n){

818

return;

819

}

820

821

size_type size_temp;

822

size_type first_temp;

823

T * data_temp;

824

size_temp = n + __UCLIBCXX_STL_BUFFER_SIZE__; //Reserve extra 'cause we can

825

data_temp = a.allocate(size_temp);

826

827

first_temp = (size_temp - elements) / 2;

828

for(size_type i = 0; i < elements; ++i){

829

a.construct(data_temp + first_temp + i, data[array_element(i)]);

830

a.destroy(data + array_element(i));

831

}

832

833

//Now shuffle pointers

834

a.deallocate(data, data_size);

835

data = data_temp;

836

data_size = size_temp;

837

first_element = first_temp;

838

last_element = first_element + elements;

839

}

840

841

842

template <class T, class Allocator> _UCXXEXPORT

843

bool

844

operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y)

845

{

846

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

847

return false;

848

}

849

for(typename deque<T,Allocator>::size_type i = 0; i < x.elements; ++i){

850

if(x[i] < y[i] || y[i] < x[i]){

851

return false;

852

}

853

}

854

return true;

855

}

856

857

template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

858

template <class T, class Allocator> _UCXXEXPORT

859

bool

860

operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y)

861

{

862

if(x == y){

863

return false;

864

}

865

return true;

866

}

867

template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

868

template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

869

template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

870

template <class T, class Allocator> _UCXXEXPORT void swap(deque<T,Allocator>& x, deque<T,Allocator>& y){

871

x.swap(y);

872

}

873

874

875

876

}

877

878

#pragma GCC visibility pop

879

880

#endif

881

882

883

884

Older »