/elec/propeller-clock : revision 90

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

Committer: Tim Marston
Date: 2012-05-18 18:29:50 UTC
Revision ID: tim@ed.am-20120518182950-t85bn9a21n72uzm8

text messages are now individually enabled and draw()n automatically

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/util/Bounce.cpp

src/util/Bounce.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/associative_base

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<utility.h>

#include<iterator>

#include<functional>

#include<list>

#ifndef __STD_HEADER_ASSOCIATIVE_BASE

#define __STD_HEADER_ASSOCIATIVE_BASE

#pragma GCC visibility push(default)

namespace std{

* The basic premise here is that most of the code used by map, multimap, set and

* multiset is really common. There are a number of interface additions, and

* considerations about how to address multiple entries with the same key.

* The goal is that the tree/storage code should be here, and managing

* single or multiple counts will be left to subclasses.

* Yes, inheritence for the purpose of code sharing is usually a bad idea.

* However, since our goal is to reduce the total amount of code written

* and the overall binary size, this seems to be the best approach possible.

template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative;

template<class ValueType, class Compare, class Allocator> class _associative_iter;

template<class ValueType, class Compare, class Allocator> class _associative_citer;

template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __single_associative;

template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __multi_associative;

template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __base_associative{

protected:

public:

typedef Key key_type;

typedef ValueType value_type;

typedef Compare key_compare;

typedef Allocator allocator_type;

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 typename Allocator::pointer pointer;

typedef typename Allocator::const_pointer const_pointer;

typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type;

typedef _associative_iter<value_type, Compare, Allocator> iterator;

typedef _associative_citer<value_type, Compare, Allocator> const_iterator;

typedef typename std::reverse_iterator<iterator> reverse_iterator;

typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;

explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))

: c(comp), value_to_key(v_to_k) { }

protected:

__base_associative(const associative_type& x)

: c(x.c), backing(x.backing), value_to_key(x.value_to_key) { }

public:

~__base_associative(){

}

bool empty() const{

return backing.empty();

}

size_type size() const{

return backing.size();

}

size_type max_size() const{

return backing.max_size();

}

iterator begin(){

return iterator(backing.begin());

}

100

101

const_iterator begin() const{

102

return const_iterator(backing.begin());

103

}

104

105

iterator end() {

106

return iterator(backing.end());

107

}

108

109

const_iterator end() const{

110

return const_iterator(backing.end());

111

}

112

113

reverse_iterator rbegin(){

114

return reverse_iterator(end());

115

}

116

117

const_reverse_iterator rbegin() const{

118

return const_reverse_iterator(end());

119

}

120

121

reverse_iterator rend(){

122

return reverse_iterator(begin());

123

}

124

125

const_reverse_iterator rend() const{

126

return const_reverse_iterator(begin());

127

}

128

129

130

iterator lower_bound(const key_type &x);

131

const_iterator lower_bound(const key_type &x) const;

132

iterator upper_bound(const key_type &x);

133

const_iterator upper_bound(const key_type &x) const;

134

135

pair<iterator,iterator> equal_range(const key_type& x){

136

pair<iterator, iterator> retval;

137

retval.first = lower_bound(x);

138

retval.second = retval.first;

139

while(retval.second != end() && !c(x, value_to_key(*retval.second))){

140

++retval.second;

141

}

142

return retval;

143

}

144

pair<const_iterator,const_iterator> equal_range(const key_type& x) const{

145

pair<const_iterator, const_iterator> retval;

146

retval.first = lower_bound(x);

147

retval.second = retval.first;

148

while(retval.second != end() && !c(x, value_to_key(*retval.second))){

149

++retval.second;

150

}

151

return retval;

152

}

153

154

iterator find(const key_type& x){

155

iterator retval = lower_bound(x);

156

if(retval == end()){

157

return retval;

158

}

159

if(c(x, value_to_key(*retval))){

160

return end();

161

}

162

return retval;

163

}

164

const_iterator find(const key_type& x) const{

165

const_iterator retval = lower_bound(x);

166

if(retval == end()){

167

return retval;

168

}

169

if(c(x, value_to_key(*retval))){

170

return end();

171

}

172

return retval;

173

}

174

size_type count(const key_type& x) const{

175

size_type retval(0);

176

const_iterator first = lower_bound(x);

177

while(first != end() && !c(x, value_to_key(*first))){

178

++retval;

179

++first;

180

}

181

return retval;

182

}

183

184

void clear(){

185

backing.clear();

186

}

187

188

void erase(iterator pos){

189

backing.erase(pos.base_iterator());

190

}

191

size_type erase(const key_type& x){

192

size_type count(0);

193

iterator start = lower_bound(x);

194

iterator end = upper_bound(x);

195

while(start != end){

196

start = backing.erase(start.base_iterator());

197

++count;

198

}

199

return count;

200

}

201

void erase(iterator first, iterator last){

202

while(first != last){

203

backing.erase(first.base_iterator());

204

++first;

205

}

206

}

207

208

key_compare key_comp() const{

209

return c;

210

}

211

212

__base_associative &operator=(const __base_associative & x){

213

c = x.c;

214

backing = x.backing;

215

value_to_key = x.value_to_key;

216

return *this;

217

}

218

bool operator==(const __base_associative & x){

219

return x.backing == backing;

220

}

221

bool operator!=(const __base_associative & x){

222

return !(x.backing == backing);

223

}

224

225

protected:

226

void swap(__base_associative & x);

227

228

Compare c;

229

std::list<value_type> backing;

230

231

const key_type (*value_to_key)(const value_type);

232

233

};

234

235

236

237

* Tree iterators for the base associative class

238

239

240

template<class ValueType, class Compare, class Allocator> class _associative_citer

241

: public std::iterator<

242

bidirectional_iterator_tag,

243

ValueType,

244

typename Allocator::difference_type,

245

ValueType*,

246

ValueType&

247

248

{

249

protected:

250

typedef std::list<ValueType> listtype;

251

252

typename listtype::const_iterator base_iter;

253

friend class _associative_iter<ValueType, Compare, Allocator>;

254

public:

255

_associative_citer() { }

256

_associative_citer(const _associative_citer & m)

257

: base_iter(m.base_iter) { }

258

_associative_citer(const typename listtype::const_iterator & m)

259

: base_iter(m) { }

260

~_associative_citer() { }

261

ValueType operator*() const{

262

return *base_iter;

263

}

264

const ValueType * operator->() const{

265

return &(*base_iter);

266

}

267

_associative_citer & operator=(const _associative_citer & m){

268

base_iter = m.base_iter;

269

return *this;

270

}

271

bool operator==(const _associative_citer & m) const{

272

return m.base_iter == base_iter;

273

}

274

bool operator!=(const _associative_citer & m) const{

275

return m.base_iter != base_iter;

276

}

277

_associative_citer & operator++(){

278

++base_iter;

279

return *this;

280

}

281

_associative_citer operator++(int){

282

//The following approach ensures that we only need to

283

//provide code for ++ in one place (above)

284

_associative_citer temp(base_iter);

285

++base_iter;

286

return temp;

287

}

288

_associative_citer & operator--(){

289

--base_iter;

290

return *this;

291

}

292

_associative_citer operator--(int){

293

//The following approach ensures that we only need to

294

//provide code for -- in one place (above)

295

_associative_citer temp(base_iter);

296

--base_iter;

297

return temp;

298

}

299

300

//This is an implementation-defined function designed to make internals work correctly

301

typename listtype::const_iterator base_iterator(){

302

return base_iter;

303

}

304

};

305

306

307

template<class ValueType, class Compare, class Allocator> class _associative_iter

308

: public std::iterator<

309

bidirectional_iterator_tag,

310

ValueType,

311

typename Allocator::difference_type,

312

ValueType*,

313

ValueType&

314

315

{

316

protected:

317

typedef std::list<ValueType> listtype;

318

319

typename listtype::iterator base_iter;

320

typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer;

321

322

public:

323

_associative_iter() { }

324

_associative_iter(const _associative_iter & m)

325

: base_iter(m.base_iter) { }

326

_associative_iter(const typename listtype::iterator & m)

327

: base_iter(m) { }

328

~_associative_iter() { }

329

const ValueType & operator*() const{

330

return *base_iter;

331

}

332

ValueType & operator*(){

333

return *base_iter;

334

}

335

ValueType * operator->(){

336

return &(*base_iter);

337

}

338

const ValueType * operator->() const{

339

return &(*base_iter);

340

}

341

_associative_iter & operator=(const _associative_iter & m){

342

base_iter = m.base_iter;

343

return *this;

344

}

345

bool operator==(const _associative_iter & m) const{

346

return m.base_iter == base_iter;

347

}

348

bool operator==(const __associative_citer & m) const{

349

return m.base_iter == base_iter;

350

}

351

bool operator!=(const _associative_iter & m) const{

352

return m.base_iter != base_iter;

353

}

354

bool operator!=(const __associative_citer & m) const{

355

return m.base_iter != base_iter;

356

}

357

_associative_iter & operator++(){

358

++base_iter;

359

return *this;

360

}

361

_associative_iter operator++(int){

362

//The following approach ensures that we only need to

363

//provide code for ++ in one place (above)

364

_associative_iter temp(base_iter);

365

++base_iter;

366

return temp;

367

}

368

_associative_iter & operator--(){

369

--base_iter;

370

return *this;

371

}

372

_associative_iter operator--(int){

373

//The following approach ensures that we only need to

374

//provide code for -- in one place (above)

375

_associative_iter temp(base_iter);

376

--base_iter;

377

return temp;

378

}

379

operator __associative_citer() const{

380

return __associative_citer(base_iter);

381

}

382

typename listtype::iterator base_iterator(){

383

return base_iter;

384

}

385

const typename listtype::iterator base_iterator() const{

386

return base_iter;

387

}

388

389

};

390

391

392

// The lower_bound code is really crappy linear search. However, it is a dead

393

// simple implementation (easy to audit). It can also be easily replaced.

394

395

396

template <class Key, class ValueType, class Compare, class Allocator>

397

typename __base_associative<Key, ValueType, Compare, Allocator>::iterator

398

__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x)

399

{

400

iterator retval = begin();

401

while(retval != end() && c(value_to_key(*retval), x)){

402

++retval;

403

}

404

return retval;

405

}

406

407

template <class Key, class ValueType, class Compare, class Allocator>

408

typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator

409

__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const

410

{

411

const_iterator retval = begin();

412

while(retval != end() && c(value_to_key(*retval), x)){

413

++retval;

414

}

415

return retval;

416

}

417

418

// Upper bound search is linear from the point of lower_bound. This is likely the best solution

419

// in all but the most pathological of cases.

420

421

template <class Key, class ValueType, class Compare, class Allocator>

422

typename __base_associative<Key, ValueType, Compare, Allocator>::iterator

423

__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x)

424

{

425

iterator retval = lower_bound(x);

426

while(retval != end() && !c(x, value_to_key(*retval))){

427

++retval;

428

}

429

return retval;

430

}

431

432

template <class Key, class ValueType, class Compare, class Allocator>

433

typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator

434

__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const

435

{

436

const_iterator retval = begin();

437

while(retval != end() && !c(x, value_to_key(*retval))){

438

++retval;

439

}

440

return retval;

441

}

442

443

444

template <class Key, class ValueType, class Compare, class Allocator>

445

void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m)

446

{

447

Compare n = c;

448

c = m.c;

449

m.c = n;

450

451

m.backing.swap(backing);

452

}

453

454

455

template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative :

456

public __base_associative<Key, ValueType, Compare, Allocator>

457

{

458

protected:

459

typedef __base_associative<Key, ValueType, Compare, Allocator> base;

460

using base::backing;

461

462

using base::c;

463

464

public:

465

typedef typename base::key_type key_type;

466

typedef typename base::value_type value_type;

467

typedef typename base::key_compare key_compare;

468

typedef typename base::allocator_type allocator_type;

469

typedef typename base::reference reference;

470

typedef typename base::const_reference const_reference;

471

typedef typename base::iterator iterator;

472

typedef typename base::const_iterator const_iterator;

473

typedef typename base::size_type size_type;

474

typedef typename base::difference_type difference_type;

475

typedef typename base::pointer pointer;

476

typedef typename base::const_pointer const_pointer;

477

typedef typename base::reverse_iterator reverse_iterator;

478

typedef typename base::const_reverse_iterator const_reverse_iterator;

479

480

using base::begin;

481

using base::end;

482

using base::rbegin;

483

using base::rend;

484

485

using base::empty;

486

using base::size;

487

using base::max_size;

488

489

using base::find;

490

using base::count;

491

using base::lower_bound;

492

using base::upper_bound;

493

using base::equal_range;

494

495

using base::operator=;

496

using base::operator==;

497

using base::operator!=;

498

499

explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))

500

: base(comp, A, v_to_k) { }

501

502

template <class InputIterator> __single_associative(

503

InputIterator first,

504

InputIterator last,

505

const Compare& comp,

506

const Allocator& A,

507

const key_type (*v_to_k)(const value_type)

508

) : base(comp, A, v_to_k) {

509

insert(first, last);

510

}

511

512

pair<iterator, bool> insert(const value_type& x){

513

pair<iterator, bool> retval;

514

iterator location = lower_bound(value_to_key(x));

515

retval.second = true;

516

//Empty list or need to insert at end

517

if(end() == location){

518

backing.push_back(x);

519

retval.first = --(end());

520

return retval;

521

}

522

//Something in the list

523

if(c(value_to_key(x), value_to_key(*location))){

524

location = backing.insert(location.base_iterator(), x);

525

retval.first = location;

526

}else{

527

retval.second = false;

528

retval.first = location;

529

}

530

return retval;

531

}

532

533

iterator insert(iterator position, const value_type& x){

534

// FIXME - this is cheating and probably should be more efficient since we are

535

// now log(n) to find for inserts

536

return insert(x).first;

537

}

538

539

template <class InputIterator> void insert(InputIterator first, InputIterator last){

540

while(first != last){

541

insert(*first);

542

++first;

543

}

544

}

545

546

};

547

548

549

template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative :

550

public __base_associative<Key, ValueType, Compare, Allocator>

551

{

552

protected:

553

typedef __base_associative<Key, ValueType, Compare, Allocator> base;

554

using base::backing;

555

556

using base::c;

557

558

public:

559

typedef typename base::key_type key_type;

560

typedef typename base::value_type value_type;

561

typedef typename base::key_compare key_compare;

562

typedef typename base::allocator_type allocator_type;

563

typedef typename base::reference reference;

564

typedef typename base::const_reference const_reference;

565

typedef typename base::iterator iterator;

566

typedef typename base::const_iterator const_iterator;

567

typedef typename base::size_type size_type;

568

typedef typename base::difference_type difference_type;

569

typedef typename base::pointer pointer;

570

typedef typename base::const_pointer const_pointer;

571

typedef typename base::reverse_iterator reverse_iterator;

572

typedef typename base::const_reverse_iterator const_reverse_iterator;

573

574

using base::begin;

575

using base::end;

576

using base::rbegin;

577

using base::rend;

578

579

using base::empty;

580

using base::size;

581

using base::max_size;

582

583

using base::find;

584

using base::count;

585

using base::lower_bound;

586

using base::upper_bound;

587

using base::equal_range;

588

589

using base::operator=;

590

using base::operator==;

591

592

593

explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))

594

: base(comp, A, v_to_k) { }

595

596

template <class InputIterator> __multi_associative(

597

InputIterator first,

598

InputIterator last,

599

const Compare& comp,

600

const Allocator& A,

601

const key_type (*v_to_k)(const value_type)

602

) : base(comp, A, v_to_k) {

603

insert(first, last);

604

}

605

606

iterator insert(const value_type& x){

607

iterator location = lower_bound(value_to_key(x));

608

609

if(location == begin()){

610

backing.push_front(x);

611

location = begin();

612

}else{

613

location = backing.insert(location.base_iterator(), x);

614

}

615

return location;

616

}

617

618

iterator insert(iterator position, const value_type& x){

619

// FIXME - this is cheating and probably should be more efficient since we are

620

// now log(n) to find for inserts

621

return insert(x);

622

}

623

624

template <class InputIterator> void insert(InputIterator first, InputIterator last){

625

while(first != last){

626

insert(*first);

627

++first;

628

}

629

}

630

};

631

632

633

634

635

}

636

637

#pragma GCC visibility pop

638

639

#endif //__STD_HEADER_ASSOCIATIVE_BASE

640

Older »