~crack-team/crack-lang/trunk : revision 1419

8

#

9

# Generic array implementation

10

11

import crack.lang cmp, free, IndexError, InvalidArgumentError, AssertionError, Formatter;

12

import crack.io cout, Writer, FStr, StandardFormatter;

13

11

import crack.algorithm QuickSort;

12

import crack.io cout, FStr, StandardFormatter, Writer;

13

import crack.lang cmp, free, AssertionError, Formatter, IndexError,

14

InvalidArgumentError;

14

15

16

# we use poormac here because the standard macro mechanism depends on this

16

17

# module.

19

20

void _bind(Object obj) { obj.oper bind(); }

20

21

void _release(Object obj) { obj.oper release(); }

21

22

bool _isObject(Object obj) { return true; }

22

bool _isNull(Object obj) {

23

return (obj is null);

24

}

23

bool _isNull(Object obj) { return (obj is null); }

25

24

26

25

@define _nobind 1

27

26

void _bind($1 i) { }

48

47

@_nobind byteptr

49

48

50

49

## An Array is a sequence backed by a low-level array. It supports the

51

## bracket operators and adding items at the end.

50

## bracket operators, iteration, and insertion and append of new elements.

51

##

52

## Array supports negative indexes. a[-1] is the last item in the array 'a'.

52

53

class Array[Elem] {

53

54

55

@define _setItem 1

55

56

if ($1 >= __size)

56

57

throw IndexError(FStr() I`Index out of range in Array.oper []= \

57

(index = $index, size = $__size)`);

58

(index = $index, size = $__size)`

59

);

58

60

59

61

tmp := __rep[$1];

60

62

__rep[$1] = elem;

61

63

_bind(elem);

62

64

_release(tmp);

63

65

return elem;

64

65

66

$$

66

67

68

@define _getItem 1

68

69

if ($1 >= __size) {

69

70

uint _i = $1;

70

71

throw IndexError(FStr() I`Index out of range in Array.oper [] \

71

(index = $_i, size = $__size)`);

72

(index = $_i, size = $__size)`

73

);

72

74

}

73

75

74

76

return __rep[$1];

83

85

# the unsigned case) if we want to report the index correctly.

84

86

if (i >= __size)

85

87

throw IndexError(FStr() I`Index out of range in Array.oper \

86

[]= (index = $index, size = $__size)`);

88

[]= (index = $index, size = $__size)`

89

);

87

90

88

91

} else {

89

92

i = uint(index);

93

96

array[Elem] __rep;

94

97

uint __cap, __size;

95

98

96

@final

97

Elem oper []=(int index, Elem elem) {

99

## Sets the element at the specified index. There must already be an

100

## element at the index.

101

@final Elem oper []=(int index, Elem elem) {

98

102

@_fixIntIndex

99

103

@_setItem i

100

104

}

101

105

102

@final

103

Elem oper []=(uint index, Elem elem) { @_setItem index }

104

105

@final

106

uint count() { return __size; }

107

108

@static bool elemIsNull(Elem e) { return _isNull(e); }

109

110

@final

111

Elem oper [](int index) {

106

## Sets the element at the specified index. There must already be an

107

## element at the index.

108

@final Elem oper []=(uint index, Elem elem) { @_setItem index }

109

110

## Returns the number of elements in the array.

111

@final uint count() { return __size; }

112

113

## Returns the element at the specified index.

114

@final Elem oper [](int index) {

112

115

@_fixIntIndex

113

116

@_getItem i

114

117

}

115

118

116

@final

117

Elem oper [](uint index) {

119

## Returns the element at the specified index.

120

@final Elem oper [](uint index) {

118

121

@_getItem index

119

122

}

120

123

121

@final

122

Elem last() {

124

## Returns the last element in the array.

125

@final Elem last() {

123

126

if (!__size)

124

127

throw IndexError('last() called on an empty array.');

125

128

return __rep[__size - 1];

126

129

}

127

130

128

## convert negative indexes.

129

@final

130

int __adjust(int index) {

131

## Converts a negative (end-relative) index to a positive one.

132

@final int __adjust(int index) {

131

133

if (index < 0)

132

134

index = __size + index;

133

135

return index;

164

166

return 0;

165

167

}

166

168

169

## The iterator class.

167

170

class ArrayIter {

168

171

Array __arr;

169

172

uint __index;

170

173

bool __first = true;

171

174

172

175

oper init(Array arr) : __arr = arr {}

173

176

177

## Returns the element referenced by the iterator.

174

178

Elem elem() {

175

179

return __arr[__index];

176

180

}

177

181

178

@final

179

bool next() {

182

## Forwards the iterator to the next element, returns true if it is

183

## still valid, false if it has fallen off the end.

184

@final bool next() {

180

185

cnt := __arr.count();

181

186

if (__index < cnt) {

182

187

__index = __index + 1;

186

191

}

187

192

}

188

193

189

@final

190

bool nx() {

191

if (__first) {

192

__first = false;

193

return __index < __arr.count();

194

} else {

195

return next();

196

}

197

}

198

194

## Returns the index of the element currently referenced by the

195

## iterator.

199

196

@final uint _getIndex() { return __index; }

200

197

198

## Returns true if the iterator is valid.

201

199

bool isTrue() {

202

200

return __index < __arr.count();

203

201

}

204

202

}

205

203

204

## Constructs an array given its initial capacity.

206

205

oper init(uint initCapacity) :

207

206

__rep = array[Elem](initCapacity),

208

207

__cap = initCapacity,

209

208

__size = 0 {

210

209

}

211

210

211

## Constructs an array with the default initial capacity (currently 16).

212

oper init() :

213

__rep = array[Elem](16),

214

__cap = 16,

215

__size = 0 {

216

}

217

218

oper init(array[Elem] rep, uint cap, uint size, bool takeOwnership):

218

## Constructs and array from an existing low-level representation ('rep')

219

## of the specified size. If 'takeOwnership' is true, takes ownership of

220

## the representation, otherwise makes a copy.

221

oper init(array[Elem] rep, uint cap, uint size, bool takeOwnership) :

219

222

__rep = rep,

220

223

__cap(cap),

221

224

__size(size) {

231

234

}

232

235

}

233

236

234

array[Elem] data() {

237

## Returns the underlying array representation.

238

## @unsafe

239

@final array[Elem] data() {

235

240

return __rep;

236

241

}

237

242

248

253

249

254

## Increase the capacity of the array (doesn't increase the size).

250

255

## newCapacity must be greater than the existing capacity.

251

void grow(uint newCapacity) {

256

@final void grow(uint newCapacity) {

252

257

uint newCap = newCapacity;

253

258

if (newCap < __cap)

254

259

throw InvalidArgumentError('Array.grow() - decreasing capacity');

264

269

__cap = newCap;

265

270

}

266

271

272

## Returns a copy of the array.

267

273

Array clone() {

268

274

newRep := array[Elem](__cap);

269

275

274

280

return Array(newRep, __cap, __size, true);

275

281

}

276

282

277

@final

278

void append(Elem elem) {

283

## Append the element to the array.

284

@final void append(Elem elem) {

279

285

if (__size == __cap)

280

286

grow(__cap * 2);

281

287

__rep[__size++] = elem;

299

305

__size += other.__size;

300

306

}

301

307

302

Elem pop() {

308

## Remove the last element from the array and return it.

309

@final Elem pop() {

303

310

if (__size) {

304

311

result := __rep[__size - 1];

305

312

_release(__rep[--__size]);

309

316

}

310

317

}

311

318

312

void sort() {

319

## Sort the array (using quicksort).

320

@final void sort() {

313

321

QuickSort[Array].sort(this);

314

322

}

315

323

316

void sort(function[int, Elem, Elem] cmp) {

324

## Sort the array with the given comparison function.

325

@final void sort(function[int, Elem, Elem] cmp) {

317

326

QuickSort[Array].sort(this, cmp);

318

327

}

319

328

320

Array sorted() {

329

## Returns a sorted copy of the array.

330

@final Array sorted() {

321

331

Array newArray = this.clone();

322

332

QuickSort[Array].sort(newArray);

323

333

return newArray;

324

334

}

325

335

326

Array sorted(function[int, Elem, Elem] cmp) {

336

## Returns a copy of the array sorted with the given comparison function.

337

@final Array sorted(function[int, Elem, Elem] cmp) {

327

338

Array newArray = this.clone();

328

339

QuickSort[Array].sort(newArray, cmp);

329

340

return newArray;

330

341

}

331

342

332

bool contains(Elem e) {

333

for (uint i = 0; i < __size; i++){

343

## Returns true if the array contains the specified element.

344

@final bool contains(Elem e) {

345

for (uint i = 0; i < __size; i++) {

334

346

if (cmp(e, __rep[i]) == 0)

335

347

return true;

336

348

}

337

349

return false;

338

350

}

339

351

340

void map(function[Elem, Elem] f){

352

## Applies the function 'f' to every element of the array.

353

## 'for i < this.count(), this[i] = f(this[i])'

354

@final void map(function[Elem, Elem] f) {

341

355

Elem newElem;

342

356

for (uint i = 0; i < __size; i++){

343

357

newElem = f(__rep[i]);

346

360

}

347

361

}

348

362

349

Array mapped(function[Elem, Elem] f){

363

## Returns a copy of the array with f applied to all elements (see map()).

364

@final Array mapped(function[Elem, Elem] f){

350

365

newRep := array[Elem](__cap);

351

366

Array newArray = Array(newRep, __cap, __size, true);

352

367

Elem newElem;

369

384

return val;

370

385

}

371

386

387

## Do a reduce on tha array. 'for elem in array, result = f(result, elem)'

372

388

@final Elem reduce(function[Elem, Elem, Elem] f, Elem initialValue) {

373

389

return __reduce(f, initialValue, 0);

374

390

}

375

391

376

@final

377

Elem reduce(function[Elem, Elem, Elem] f){

392

## Do a reduce on tha array. 'for elem in array, result = f(result, elem)'

393

## Uses the first element as an initial value.

394

@final Elem reduce(function[Elem, Elem, Elem] f) {

378

395

if (__size == 0) throw AssertionError(I"reduce of zero-length Array \

379

396

is undefined");

380

397

return __reduce(f, __rep[0], 1);

381

398

}

382

399

383

400

## Remove all elements from the array where f(elem) returns false.

384

void filter(function[bool, Elem] f) {

401

@final void filter(function[bool, Elem] f) {

385

402

uint ns = 0;

386

403

for (uint i = 0; i < __size; i++) {

387

404

if (f(__rep[i]))

397

414

__size = ns;

398

415

}

399

416

400

Array filtered(function[bool, Elem] f) {

417

## Returns a copy of the array with all elements where f(elem) returns

418

## false removed.

419

@final Array filtered(function[bool, Elem] f) {

401

420

retval := Array();

402

421

for (uint i = 0; i < __size; i++)

403

422

if (f(__rep[i])) retval.append(__rep[i]);

404

423

return retval;

405

424

}

406

425

407

void _setSize(uint newSize){

426

## Sets the new size of the array.

427

@final void _setSize(uint newSize) {

408

428

if (newSize > __cap)

409

429

throw IndexError('Index out of range in Array.setSize');

410

430

__size = newSize;

411

431

}

412

432

433

## Returns an iterator over the array.

413

434

@final ArrayIter iter() {

414

435

return ArrayIter(this);

415

436

}

416

437

417

uint capacity() {

438

## returns the capacity of the array.

439

@final uint capacity() {

418

440

return __cap;

419

441

}

420

442

431

453

fmt `]`;

432

454

}

433

455

434

Array _subarray(uint pos, uint len) {

456

@final Array _subarray(uint pos, uint len) {

435

457

if (pos > __size || pos + len > __size)

436

458

throw IndexError(FStr() I`Sub-array index out of range \

437

459

(pos = $pos, len = $len, size = $__size`

450

472

return Array(newRep, newCap, len, true);

451

473

}

452

474

453

454

Array subarray(int pos, uint len) {

475

476

## Returns a subset of the array of length 'len' beginning at 'pos'.

477

@final Array subarray(int pos, uint len) {

455

478

# adjust a negative position

456

479

if (pos < 0) {

457

480

pos = int(__size) + pos;

466

489

return _subarray(uint(pos), len);

467

490

}

468

491

469

Array subarray(uint pos, uint len) {

492

## Returns a subset of the array of length 'len' beginning at 'pos'.

493

@final Array subarray(uint pos, uint len) {

470

494

return _subarray(pos, len);

471

495

}

472

496

473

Array subarray(int pos) {

497

498

## Returns a subset of the array beginning at 'pos' and extending to the

499

## end of the array.

500

@final Array subarray(int pos) {

474

501

# adjust a negative position

475

502

if (pos < 0)

476

503

pos = int(__size) + pos;

478

505

return _subarray(uint(pos), __size - uint(pos));

479

506

}

480

507

481

Array subarray(uint pos) {

508

## Returns a subset of the array beginning at 'pos' and extending to the

509

## end of the array.

510

@final Array subarray(uint pos) {

482

511

return _subarray(pos, __size - pos);

483

512

}

484

513

485

Array slice(int start, int end) {

514

## Returns a slice of the array beginning at the start index and ending at

515

## the element before the end index.

516

@final Array slice(int start, int end) {

486

517

# adjust negative offsets

487

518

if (start < 0) {

488

519

start = int(__size) + start;

511

542

return _subarray(uint(start), uint(end - start));

512

543

}

513

544

514

Array slice(uint start, uint end) {

545

## Returns a slice of the array beginning at the start index and ending at

546

## the element before the end index.

547

@final Array slice(uint start, uint end) {

515

548

# bounds checking

516

549

if (end < start)

517

550

throw IndexError('Start of slice is after end.');

519

552

return _subarray(start, end - start);

520

553

}

521

554

522

523

Array slice(int start) {

555

## Returns a slice of the array beginning at the start index and ending at

556

## the end of the array.

557

@final Array slice(int start) {

524

558

# adjust negative offsets

525

559

if (start < 0)

526

560

start = int(__size) + start;

565

599

--__size;

566

600

}

567

601

602

## Delete all elements in the array, setting the size to 0.

568

603

@final void clear() {

569

604

if (!__size) return;

570

605

for (uintz i = 0; i < __size; ++i) {

575

610

__size = 0;

576

611

}

577

612

578

void insert(int index, Elem elem) {

613

## Insert the element at the specified index (elements after the index are

614

## shifted up one slot).

615

@final void insert(int index, Elem elem) {

579

616

index = __adjust(index);

580

617

if (uint(index) > __size)

581

618

throw IndexError('Index out of range in Array.insert()');

593

630

++__size;

594

631

}

595

632

596

void insert(ArrayIter i, Elem elem) {

633

## Insert the element at the position of the iterator.

634

@final void insert(ArrayIter i, Elem elem) {

597

635

insert(i._getIndex(), elem);

598

636

}

599

637