data_structures: d359966ed8de src/ost.c

view src/ost.c @ 12:d359966ed8de

Added trie

author	Eris Caffee <discordia@eldalin.com>
date	Mon, 01 Oct 2012 15:50:30 -0500
parents
children

line source

1 // Implemented as a red-black tree

3 #include <stdio.h>

4 #include <stdlib.h>

6 #include "ost.h"

8 enum ost_color { RED, BLACK };

10 struct ost_node

11 {

12 enum ost_color color;

13 unsigned int size;

14 struct ost_node * parent;

15 struct ost_node * left;

16 struct ost_node * right;

17 void * data;

18 };

20 struct ost

21 {

22 struct ost_node nil_node;

23 struct ost_node * nil;

24 struct ost_node * root;

25 size_t size;

26 bool (*le)(void * a, void * b);

27 bool (*eq)(void * a, void * b);

28 };

30 struct ost_iterator

31 {

32 struct ost * ost;

33 struct ost_node * curr;

34 };

36 void * ost_data_search (struct ost * ost, struct ost_node * node, void * data);

37 void * ost_node_minimum (struct ost * ost, struct ost_node * node);

38 void * ost_node_maximum (struct ost * ost, struct ost_node * node);

40 void ost_data_walk_inorder (struct ost * ost, struct ost_node * node, void (*op)(void * data));

41 void ost_data_walk_preorder (struct ost * ost, struct ost_node * node, void (*op)(void * data));

42 void ost_data_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(void * data));

43 void ost_node_walk_postorder (struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n));

45 void ost_node_free (struct ost_node * node);

47 struct ost_node * ost_node_search (struct ost * ost, struct ost_node * node, void * data);

49 struct ost_node * ost_transplant (struct ost * ost, struct ost_node * a, struct ost_node * b);

50 void ost_rotate_left (struct ost * ost, struct ost_node * node);

51 void ost_rotate_right (struct ost * ost, struct ost_node * node);

52 void ost_insert_fixup (struct ost * ost, struct ost_node * node);

53 void ost_remove_fixup (struct ost * ost, struct ost_node * node);

55 void ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth);

57 ////////////////////////////////////////////////////////////////////////////////

58 struct ost *

59 ost_new(bool (*le)(void * a, void * b),

60 bool (*eq)(void * a, void * b))

61 {

62 if ( (NULL == le) || (NULL == eq) )

63 return NULL;

65 struct ost * ost = malloc(sizeof(struct ost));

66 if (NULL == ost)

67 return NULL;

69 ost->nil_node = (struct ost_node) { BLACK, 0, &ost->nil_node, &ost->nil_node, &ost->nil_node, NULL };

70 ost->nil = &(ost->nil_node);

71 ost->root = ost->nil;

72 ost->size = 0;

73 ost->le = le;

74 ost->eq = eq;

75 return ost;

76 }

79 ////////////////////////////////////////////////////////////////////////////////

80 void

81 ost_delete(struct ost * ost)

82 {

83 if (NULL == ost) return;

84 if (0 < ost->size)

85 {

86 // Walk the tree and delete the nodes.

87 // This may cause memory leaks, so hopefully the user has already

88 // emptied the tree.

89 ost_node_walk_postorder(ost, ost->root, ost_node_free);

90 }

91 free(ost);

92 }

94 ////////////////////////////////////////////////////////////////////////////////

95 void

96 ost_node_free(struct ost_node * node)

97 {

98 free(node);

99 }

100

101 ////////////////////////////////////////////////////////////////////////////////

102 void *

103 ost_insert(struct ost * ost, void * data)

104 {

105 if ( (NULL == ost) || (NULL == data) )

106 return NULL;

107

108 struct ost_node * new = malloc(sizeof(struct ost_node));

109 if (NULL == new)

110 return NULL;

111 new->left = new->right = new->parent = ost->nil;

112 new->color = RED;

113 new->size = 1;

114 new->data = data;

115

116 if (ost->nil == ost->root)

117 {

118 ost->root = new;

119 new->color = BLACK;

120 new->parent = ost->nil;

121 ost->size = 1;

122 return new->data;

123 }

124

125 struct ost_node * p = ost->nil;

126 struct ost_node * c = ost->root;

127

128 while (ost->nil != c)

129 {

130 c->size++;

131 p = c;

132 if (ost->le(new->data, c->data))

133 c = c->left;

134 else

135 c = c->right;

136 }

137 new->parent = p;

138 if (ost->le(new->data, p->data))

139 p->left = new;

140 else

141 p->right = new;

142

143 ost_insert_fixup(ost, new);

144

145 ost->size++;

146 return new->data;

147 }

148

149 ////////////////////////////////////////////////////////////////////////////////

150 void

151 ost_insert_fixup(struct ost * ost, struct ost_node * node)

152 {

153 if ( (NULL == ost) || (NULL == node) )

154 return;

155

156 while (RED == node->parent->color)

157 {

158 if (node->parent == node->parent->parent->left)

159 {

160 struct ost_node * y = node->parent->parent->right;

161 if (RED == y->color)

162 {

163 node->parent->color = BLACK;

164 y->color = BLACK;

165 node->parent->parent->color = RED;

166 node = node->parent->parent;

167 }

168 else

169 {

170 if (node == node->parent->right)

171 {

172 node = node->parent;

173 ost_rotate_left(ost, node);

174 }

175 node->parent->color = BLACK;

176 node->parent->parent->color = RED;

177 ost_rotate_right(ost, node->parent->parent);

178 }

179 }

180 else

181 {

182 struct ost_node * y = node->parent->parent->left;

183 if (RED == y->color)

184 {

185 node->parent->color = BLACK;

186 y->color = BLACK;

187 node->parent->parent->color = RED;

188 node = node->parent->parent;

189 }

190 else

191 {

192 if (node == node->parent->left)

193 {

194 node = node->parent;

195 ost_rotate_right(ost, node);

196 }

197 node->parent->color = BLACK;

198 node->parent->parent->color = RED;

199 ost_rotate_left(ost, node->parent->parent);

200 }

201 }

202 }

203 ost->root->color = BLACK;

204 }

205

206 ////////////////////////////////////////////////////////////////////////////////

207 void

208 ost_walk_inorder(struct ost * ost, void (*op)(void * data))

209 {

210 if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) )

211 return;

212

213 ost_data_walk_inorder(ost, ost->root, op);

214 }

215

216 ////////////////////////////////////////////////////////////////////////////////

217 void

218 ost_walk_postorder(struct ost * ost, void (*op)(void * data))

219 {

220 if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) )

221 return;

222

223 ost_data_walk_postorder(ost, ost->root, op);

224 }

225

226 ////////////////////////////////////////////////////////////////////////////////

227 void

228 ost_walk_preorder(struct ost * ost, void (*op)(void * data))

229 {

230 if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == op) )

231 return;

232

233 ost_data_walk_preorder(ost, ost->root, op);

234 }

235

236 ////////////////////////////////////////////////////////////////////////////////

237 void

238 ost_data_walk_inorder(struct ost * ost, struct ost_node * node, void (*op)(void * data))

239 {

240 if (ost->nil != node)

241 {

242 ost_data_walk_inorder(ost, node->left, op);

243 op(node->data);

244 ost_data_walk_inorder(ost, node->right, op);

245 }

246 }

247

248 ////////////////////////////////////////////////////////////////////////////////

249 void

250 ost_data_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(void * data))

251 {

252 if (ost->nil != node)

253 {

254 ost_data_walk_postorder(ost, node->left, op);

255 ost_data_walk_postorder(ost, node->right, op);

256 op(node->data);

257 }

258 }

259

260 ////////////////////////////////////////////////////////////////////////////////

261 void

262 ost_data_walk_preorder(struct ost * ost, struct ost_node * node, void (*op)(void * data))

263 {

264 if (ost->nil != node)

265 {

266 op(node->data);

267 ost_data_walk_preorder(ost, node->left, op);

268 ost_data_walk_preorder(ost, node->right, op);

269 }

270 }

271

272 ////////////////////////////////////////////////////////////////////////////////

273 void

274 ost_node_walk_postorder(struct ost * ost, struct ost_node * node, void (*op)(struct ost_node * n))

275 {

276 if (ost->nil != node)

277 {

278 ost_node_walk_postorder(ost, node->left, op);

279 ost_node_walk_postorder(ost, node->right, op);

280 op(node);

281 }

282 }

283

284 ////////////////////////////////////////////////////////////////////////////////

285 void *

286 ost_search(struct ost * ost, void * data)

287 {

288 if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) )

289 return NULL;

290

291 return ost_data_search(ost, ost->root, data);

292 }

293

294 ////////////////////////////////////////////////////////////////////////////////

295 // Recursive

296 void *

297 ost_data_search(struct ost * ost, struct ost_node * node, void * data)

298 {

299 if (ost->nil == node)

300 return NULL;

301

302 if (ost->eq(data, node->data))

303 return node->data;

304

305 if (ost->le(data, node->data))

306 return ost_data_search(ost, node->left, data);

307 else

308 return ost_data_search(ost, node->right, data);

309 }

310

311 ////////////////////////////////////////////////////////////////////////////////

312 // Iterative

313 void *

314 ost_search_iterative(struct ost * ost, void * data)

315 {

316 if ( (NULL == ost) || (ost->nil == ost->root) || (NULL == data) )

317 return NULL;

318

319 struct ost_node * node = ost->root;

320 while (1)

321 {

322 if (ost->nil == node)

323 return NULL;

324

325 if (ost->eq(data, node->data))

326 return node->data;

327

328 if (ost->le(data, node->data))

329 node = node->left;

330 else

331 node = node->right;

332 }

333 }

334

335 ////////////////////////////////////////////////////////////////////////////////

336 void *

337 ost_minimum(struct ost * ost)

338 {

339 if (NULL == ost)

340 return NULL;

341

342 return ost_node_minimum(ost, ost->root);

343 }

344

345 ////////////////////////////////////////////////////////////////////////////////

346 void *

347 ost_node_minimum(struct ost * ost, struct ost_node * node)

348 {

349 while ( (ost->nil != node) && (ost->nil != node->left) )

350 node = node->left;

351 if (ost->nil == node)

352 return NULL;

353 return node->data;

354 }

355

356 ////////////////////////////////////////////////////////////////////////////////

357 void *

358 ost_maximum(struct ost * ost)

359 {

360 if (NULL == ost)

361 return NULL;

362

363 return ost_node_maximum(ost, ost->root);

364 }

365

366 ////////////////////////////////////////////////////////////////////////////////

367 void *

368 ost_node_maximum(struct ost * ost, struct ost_node * node)

369 {

370 while ( (ost->nil != node) && (ost->nil != node->right) )

371 node = node->right;

372 if (ost->nil == node)

373 return NULL;

374 return node->data;

375 }

376

377 ////////////////////////////////////////////////////////////////////////////////

378 struct ost_iterator *

379 ost_begin(struct ost * ost)

380 {

381 if ( (NULL == ost) || (ost->nil == ost->root) )

382 return NULL;

383

384 struct ost_node * min = ost->root;

385 while (ost->nil != min->left)

386 min = min->left;

387

388 struct ost_iterator * it = malloc(sizeof(struct ost_iterator));

389 if (NULL == it)

390 return NULL;

391

392 it->ost = ost;

393 it->curr = min;

394 return it;

395 }

396

397 ////////////////////////////////////////////////////////////////////////////////

398 struct ost_iterator *

399 ost_end(struct ost * ost)

400 {

401 if ( (NULL == ost) || (ost->nil == ost->root) )

402 return NULL;

403

404 struct ost_node * max = ost->root;

405 while (ost->nil != max->right)

406 max = max->right;

407

408 struct ost_iterator * it = malloc(sizeof(struct ost_iterator));

409 if (NULL == it)

410 return NULL;

411

412 it->ost = ost;

413 it->curr = max;

414 return it;

415 }

416

417 ////////////////////////////////////////////////////////////////////////////////

418 struct ost_iterator *

419 ost_next(struct ost_iterator * it)

420 {

421 if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) )

422 return NULL;

423

424 if (it->ost->nil == it->curr->right)

425 {

426 struct ost_node * p = it->curr;

427 it->curr = it->curr->parent;

428 while ( (it->ost->nil != it->curr) && (p == it->curr->right) )

429 {

430 p = it->curr;

431 it->curr = it->curr->parent;

432 }

433

434 if (it->curr == it->ost->nil)

435 return NULL;

436 }

437 else

438 {

439 struct ost_node * min = it->curr->right;

440 while (it->ost->nil != min->left)

441 min = min->left;

442 it->curr = min;

443 }

444 return it;

445 }

446

447 ////////////////////////////////////////////////////////////////////////////////

448 struct ost_iterator *

449 ost_prev(struct ost_iterator * it)

450 {

451 if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) )

452 return NULL;

453

454 if (it->ost->nil == it->curr->left)

455 {

456 struct ost_node * p = it->curr;

457 it->curr = it->curr->parent;

458 while ( (it->ost->nil != it->curr) && (p == it->curr->left) )

459 {

460 p = it->curr;

461 it->curr = it->curr->parent;

462 }

463

464 if (it->curr == it->ost->nil)

465 return NULL;

466 }

467 else

468 {

469 struct ost_node * max = it->curr->left;

470 while (it->ost->nil != max->right)

471 max = max->right;

472 it->curr = max;

473 }

474 return it;

475 }

476

477 ////////////////////////////////////////////////////////////////////////////////

478 void *

479 ost_value(struct ost_iterator * it)

480 {

481 if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) )

482 return NULL;

483

484 return it->curr->data;

485 }

486

487 ////////////////////////////////////////////////////////////////////////////////

488 void *

489 ost_find(struct ost_iterator * it, void * data)

490 {

491 if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->ost->root) || (NULL == data) )

492 return NULL;

493

494 return ost_node_search(it->ost, it->ost->root, data);

495 }

496

497 ////////////////////////////////////////////////////////////////////////////////

498 // Recursive

499 struct ost_node *

500 ost_node_search(struct ost * ost, struct ost_node * node, void * data)

501 {

502 if (ost->nil == node)

503 return NULL;

504

505 if (ost->eq(data, node->data))

506 return node;

507

508 if (ost->le(data, node->data))

509 return ost_node_search(ost, node->left, data);

510 else

511 return ost_node_search(ost, node->right, data);

512 }

513

514 ////////////////////////////////////////////////////////////////////////////////

515 struct ost_node *

516 ost_transplant(struct ost * ost, struct ost_node * a, struct ost_node * b)

517 {

518 if ( (NULL == a) || (NULL == b) )

519 return NULL;

520

521 if (ost->nil == a->parent)

522 ost->root = b;

523 else if (a == a->parent->left)

524 a->parent->left = b;

525 else

526 a->parent->right = b;

527

528 b->parent = a->parent;

529

530 return a;

531 }

532

533 ////////////////////////////////////////////////////////////////////////////////

534 void *

535 ost_remove(struct ost_iterator * it)

536 {

537 if ( (NULL == it) || (NULL == it->ost) || (it->ost->nil == it->curr) )

538 return NULL;

539

540 // Get successor and save it

541 struct ost_iterator succ;

542 succ.curr = it->curr;

543 succ.ost = it->ost;

544 ost_next(&succ);

545

546 struct ost_node * x;

547 struct ost_node * y = it->curr;

548 enum ost_color original_color = y->color;

549

550 if (it->ost->nil == it->curr->left)

551 {

552 x = it->curr->right;

553 ost_transplant(it->ost, it->curr, it->curr->right);

554 }

555 else if (it->ost->nil == it->curr->right)

556 {

557 x = it->curr->left;

558 ost_transplant(it->ost, it->curr, it->curr->left);

559 }

560 else

561 {

562 y = ost_node_minimum(it->ost, it->curr->right);

563 original_color = y->color;

564 x = y->right;

565 if (it->curr == y->parent)

566 x->parent = y;

567 else

568 {

569 ost_transplant(it->ost, y, y->right);

570 y->right = it->curr->right;

571 y->right->parent = y;

572 }

573 ost_transplant(it->ost, it->curr, y);

574 y->left = it->curr->left;

575 y->left->parent = y;

576 y->color = it->curr->color;

577 }

578

579 if (BLACK == original_color)

580 ost_remove_fixup(it->ost, x);

581

582 void * data = it->curr->data;

583 free(it->curr);

584

585 // Update it to point to saved successor

586 it->curr = succ.curr;

587 it->ost->size--;

588

589 return data;

590 }

591

592 ////////////////////////////////////////////////////////////////////////////////

593 void

594 ost_remove_fixup(struct ost * ost, struct ost_node * node)

595 {

596 while ( (ost->root != node) && (BLACK == node->color) )

597 {

598 if (node == node->parent->left)

599 {

600 struct ost_node * w = node->parent->right;

601 if (RED == w->color)

602 {

603 w->color = BLACK;

604 node->parent->color = RED;

605 ost_rotate_left(ost, node->parent);

606 w = node->parent->right;

607 }

608 if ( (BLACK == w->left->color) && (BLACK == w->right->color) )

609 {

610 w->left->color = RED;

611 node = node->parent;

612 }

613 else

614 {

615 if (BLACK == w->right->color)

616 {

617 w->left->color = BLACK;

618 w->color = RED;

619 ost_rotate_right(ost, w);

620 w = node->parent->right;

621 }

622 w->color = node->parent->color;

623 node->parent->color = BLACK;

624 w->right->color = BLACK;

625 ost_rotate_left(ost, node->parent);

626 node = ost->root;

627 }

628 }

629 else

630 {

631 struct ost_node * w = node->parent->left;

632 if (RED == w->color)

633 {

634 w->color = BLACK;

635 node->parent->color = RED;

636 ost_rotate_right(ost, node->parent);

637 w = node->parent->left;

638 }

639 if ( (BLACK == w->right->color) && (BLACK == w->left->color) )

640 {

641 w->right->color = RED;

642 node = node->parent;

643 }

644 else

645 {

646 if (BLACK == w->left->color)

647 {

648 w->right->color = BLACK;

649 w->color = RED;

650 ost_rotate_left(ost, w);

651 w = node->parent->left;

652 }

653 w->color = node->parent->color;

654 node->parent->color = BLACK;

655 w->left->color = BLACK;

656 ost_rotate_right(ost, node->parent);

657 node = ost->root;

658 }

659 }

660 }

661 node->color = BLACK;

662 }

663

664 ////////////////////////////////////////////////////////////////////////////////

665 void

666 ost_rotate_left(struct ost * ost, struct ost_node * node)

667 {

668 if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->right) )

669 return;

670

671 struct ost_node * y = node->right;

672

673 node->right = y->left;

674 if (ost->nil != y->left)

675 y->left->parent = node;

676

677 y->parent = node->parent;

678 if (ost->nil == node->parent)

679 ost->root = y;

680 else if (node == node->parent->left)

681 node->parent->left = y;

682 else

683 node->parent->right = y;

684

685 y->left = node;

686 node->parent = y;

687

688 y->size = node->size;

689 node->size = node->left->size + node->right->size + 1;

690 }

691

692 ////////////////////////////////////////////////////////////////////////////////

693 void

694 ost_rotate_right(struct ost * ost, struct ost_node * node)

695 {

696 if ( (NULL == ost) || (ost->nil == node) || (ost->nil == node->left) )

697 return;

698

699 struct ost_node * y = node->left;

700

701 node->left = y->right;

702 if (ost->nil != y->right)

703 y->right->parent = node;

704

705 y->parent = node->parent;

706 if (ost->nil == node->parent)

707 ost->root = y;

708 else if (node == node->parent->right)

709 node->parent->right = y;

710 else

711 node->parent->left = y;

712

713 y->right = node;

714 node->parent = y;

715

716 y->size = node->size;

717 node->size = node->left->size + node->right->size + 1;

718 }

719

720 ////////////////////////////////////////////////////////////////////////////////

721 unsigned int ost_black_depth(struct ost * ost)

722 {

723 if ( (NULL == ost) || (NULL == ost->root) )

724 return 0;

725

726 struct ost_node * node = ost->root;

727 unsigned int black_depth = 0;

728

729 while (ost->nil != node)

730 {

731 if (BLACK == node->color)

732 black_depth++;

733 node = node->left;

734 }

735

736 return black_depth;

737 }

738

739 ////////////////////////////////////////////////////////////////////////////////

740 void

741 ost_dump(struct ost * ost, void (*print_val)(void *) )

742 {

743 if ( (NULL == ost) || (ost->nil == ost->root) )

744 return;

745 ost_node_dump_preorder(ost, ost->root, print_val, 0);

746 }

747

748 ////////////////////////////////////////////////////////////////////////////////

749 void

750 ost_node_dump_preorder(struct ost * ost, struct ost_node * node, void (*print_val)(void *), int depth)

751 {

752 for (int i=0; i < depth; i++)

753 printf("\t");

754 printf("%-8s", (BLACK == node->color ? "black" : "red"));

755 print_val(node->data);

756 printf("\n");

757 if (ost->nil != node->left)

758 ost_node_dump_preorder(ost, node->left, print_val, depth+1);

759 if (ost->nil != node->right)

760 ost_node_dump_preorder(ost, node->right, print_val, depth+1);

761 }

762

763 ////////////////////////////////////////////////////////////////////////////////

764 struct ost_iterator *

765 ost_select(struct ost * ost, unsigned int i)

766 {

767 if ( (NULL == ost) || (ost->nil == ost->root) )

768 return NULL;

769

770 struct ost_iterator * it = malloc(sizeof(struct ost_iterator));

771 if (NULL == it)

772 return NULL;

773

774 it->ost = ost;

775 it->curr = ost->root;

776 return ost_select_subtree(it, i);

777 }

778

779 ////////////////////////////////////////////////////////////////////////////////

780 struct ost_iterator *

781 ost_select_subtree(struct ost_iterator * it, unsigned int i)

782 {

783 if ( (NULL == it) || (NULL == it->ost) )

784 return NULL;

785

786 unsigned int r = it->curr->left->size + 1;

787 if (i == r)

788 return it;

789 else

790 {

791 if (i < r)

792 {

793 it->curr = it->curr->left;

794 return ost_select_subtree(it, i);

795 }

796 else

797 {

798 it->curr = it->curr->right;

799 return ost_select_subtree(it, i - r);

800 }

801 }

802 return it;

803 }

804

805 ////////////////////////////////////////////////////////////////////////////////

806 unsigned int

807 ost_rank(struct ost_iterator * it)

808 {

809 if ( (NULL == it) || (NULL == it->ost) )

810 return 0;

811

812 unsigned int r = it->curr->left->size + 1;

813 struct ost_node * y = it->curr;

814 while (y != it->ost->root)

815 {

816 if (y == y->parent->right)

817 r += y->parent->left->size + 1;

818 y = y->parent;

819 }

820 return r;

821 }

822

823 ////////////////////////////////////////////////////////////////////////////////

824 unsigned int

825 ost_size (struct ost * ost)

826 {

827 if (NULL == ost)

828 return 0;

829 return ost->size;

830 }

831

Mercurial > data_structures

view src/ost.c @ 12:d359966ed8de