IntervalTree.h Source File (original) (raw)

198template <typename PointT, typename ValueT> class IntervalData {

199protected:

202

203private:

207

208public:

211 : Left(Left), Right(Right), Value(Value) {

212 assert(Left <= Right && "'Left' must be less or equal to 'Right'");

213 }

218

219

220

222

223

224

226

227

228

230 return left(Point) && right(Point);

231 }

232};

249 "PointT must be a fundamental type");

251 "ValueT must be a fundamental or pointer type");

252

253public:

258

261

262private:

265

266 class IntervalNode {

267 PointType MiddlePoint;

268 IntervalNode *Left = nullptr;

269 IntervalNode *Right = nullptr;

270 unsigned BucketIntervalsStart = 0;

271 unsigned BucketIntervalsSize = 0;

272

273 public:

274 PointType middle() const { return MiddlePoint; }

275 unsigned start() const { return BucketIntervalsStart; }

276 unsigned size() const { return BucketIntervalsSize; }

277

278 IntervalNode(PointType Point, unsigned Start)

279 : MiddlePoint(Point), BucketIntervalsStart(Start) {}

280

282 };

283

284 Allocator &NodeAllocator;

285 IntervalNode *Root = nullptr;

286 IntervalVector Intervals;

287

288 PointsVector EndPoints;

289

290

291

292

293

294

295

296

297

298 IntervalReferences IntervalsLeft;

299 IntervalReferences IntervalsRight;

300

301

302

304

305

306 void deleteTree(IntervalNode *Node) {

308 deleteTree(Node->Left);

309 deleteTree(Node->Right);

310 Node->~IntervalNode();

311 NodeAllocator.Deallocate(Node);

312 }

313 }

314

315

316 static void printList(raw_ostream &OS, IntervalReferences &IntervalSet,

317 unsigned Start, unsigned Size, bool HexFormat = true) {

318 assert(Start + Size <= IntervalSet.size() &&

319 "Start + Size must be in bounds of the IntervalSet");

320 const char *Format = HexFormat ? "[0x%08x,0x%08x] " : "[%2d,%2d] ";

322 for (unsigned Position = Start; Position < Start + Size; ++Position)

323 OS << format(Format, IntervalSet[Position]->left(),

324 IntervalSet[Position]->right());

325 } else {

326 OS << "[]";

327 }

328 OS << "\n";

329 }

330

331

332 void printNode(raw_ostream &OS, unsigned Level, IntervalNode *Node,

333 bool HexFormat = true) {

334 const char *Format = HexFormat ? "MP:0x%08x " : "MP:%2d ";

336 OS << format("%5d: ", Level);

337 OS.indent(Level * 2);

339 printList(OS, IntervalSet, Node->start(), Node->size(), HexFormat);

340 };

341

342 PrintNodeData("IR", IntervalsRight);

343 PrintNodeData("IL", IntervalsLeft);

344 }

345

346

347 void printTree(raw_ostream &OS, unsigned Level, IntervalNode *Node,

348 bool HexFormat = true) {

349 if (Node) {

350 printNode(OS, Level, Node, HexFormat);

352 printTree(OS, Level, Node->Left, HexFormat);

353 printTree(OS, Level, Node->Right, HexFormat);

354 }

355 }

356

357

358

359

360

361

362

363

364 IntervalNode *createTree(unsigned &IntervalsSize, int PointsBeginIndex,

365 int PointsEndIndex, int ReferencesBeginIndex,

366 int ReferencesSize) {

367

368

369

370

371

372

373

374

375

376

377 if (PointsBeginIndex > PointsEndIndex ||

378 ReferencesBeginIndex >= ReferencesSize)

379 return nullptr;

380

381 int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2;

382 PointType MiddlePoint = EndPoints[MiddleIndex];

383

384 unsigned NewBucketStart = IntervalsSize;

385 unsigned NewBucketSize = 0;

386 int ReferencesRightIndex = ReferencesSize;

387

388 IntervalNode *Root =

389 new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart);

390

391

392

393

394 for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) {

395

396

397 if (References[Index]->contains(MiddlePoint)) {

398 IntervalsLeft[IntervalsSize] = References[Index];

399 IntervalsRight[IntervalsSize] = References[Index];

400 ++IntervalsSize;

401 Root->BucketIntervalsSize = ++NewBucketSize;

402

403 if (Index < --ReferencesRightIndex)

404 std::swap(References[Index], References[ReferencesRightIndex]);

405 if (ReferencesRightIndex < --ReferencesSize)

406 std::swap(References[ReferencesRightIndex],

407 References[ReferencesSize]);

408 continue;

409 }

410

411 if (References[Index]->left() > MiddlePoint) {

412 if (Index < --ReferencesRightIndex)

413 std::swap(References[Index], References[ReferencesRightIndex]);

414 continue;

415 }

417 }

418

419

420 if (NewBucketSize > 1) {

421

422 std::stable_sort(IntervalsLeft.begin() + NewBucketStart,

423 IntervalsLeft.begin() + NewBucketStart + NewBucketSize,

425 return LHS->left() < RHS->left();

426 });

427

428 std::stable_sort(IntervalsRight.begin() + NewBucketStart,

429 IntervalsRight.begin() + NewBucketStart + NewBucketSize,

431 return LHS->right() > RHS->right();

432 });

433 }

434

435 if (PointsBeginIndex <= MiddleIndex - 1) {

436 Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1,

437 ReferencesBeginIndex, ReferencesRightIndex);

438 }

439

440 if (MiddleIndex + 1 <= PointsEndIndex) {

441 Root->Right = createTree(IntervalsSize, MiddleIndex + 1, PointsEndIndex,

442 ReferencesRightIndex, ReferencesSize);

443 }

444

445 return Root;

446 }

447

448public:

449 class find_iterator {

450 public:

456

457 private:

460

461

462

463 IntervalNode *Node = nullptr;

465 unsigned Index = 0;

466

467

468

469

470 void initNode() {

471 Index = 0;

472 while (Node) {

473

474

475 if (Point == Node->middle()) {

476 if (Node->size() == 0) {

477

478 Node = nullptr;

479 }

480 return;

481 }

482

483 if (Point < Node->middle()) {

484

485

486

487 if (Node->size() && (*AscendingBuckets)[Node->start()]->left(Point)) {

488 return;

489 }

490 Node = Node->Left;

491 } else {

492 if (Node->size() &&

493 (*DescendingBuckets)[Node->start()]->right(Point)) {

494 return;

495 }

496 Node = Node->Right;

497 }

498 }

499 }

500

501

502

503

504

505 void nextInterval() {

506

507

508

509 if (++Index < Node->size()) {

510 if (Node->middle() == Point)

511 return;

512 if (Point < Node->middle()) {

513

514 if (!(*AscendingBuckets)[Node->start() + Index]->left(Point)) {

515

516

517 Node = Node->Left;

518 initNode();

519 }

520 } else {

521

522 if (!(*DescendingBuckets)[Node->start() + Index]->right(Point)) {

523

524

525 Node = Node->Right;

526 initNode();

527 }

528 }

529 } else {

530

531 if (Point == Node->middle()) {

532 Node = nullptr;

533 Index = 0;

534 return;

535 }

536

537 Node = Point < Node->middle() ? Node->Left : Node->Right;

538 initNode();

539 }

540 }

541

542 find_iterator() = default;

546 : AscendingBuckets(Left), DescendingBuckets(Right), Node(Node),

547 Point(Point), Index(0) {

548 initNode();

549 }

550

551 const DataType *current() const {

552 return (Point <= Node->middle())

553 ? (*AscendingBuckets)[Node->start() + Index]

554 : (*DescendingBuckets)[Node->start() + Index];

555 }

556

557 public:

559 nextInterval();

560 return *this;

561 }

562

564 find_iterator Iter(*this);

565 nextInterval();

566 return Iter;

567 }

568

569

572

573

582

584 };

585

586private:

588

589public:

591 : NodeAllocator(NodeAllocator) {}

593

594

595 bool empty() const { return Root == nullptr; }

596

597

599 deleteTree(Root);

600 Root = nullptr;

601 Intervals.clear();

602 IntervalsLeft.clear();

603 IntervalsRight.clear();

604 EndPoints.clear();

605 }

606

607

609 assert(empty() && "Invalid insertion. Interval tree already constructed.");

611 }

612

613

614

616 assert( empty () && "Interval tree it is not constructed.");

618 for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter)

620 return IntervalSet;

621 }

622

623

624

625

627 std::stable_sort(IntervalSet.begin(), IntervalSet.end(),

629 return Sort == Sorting::Ascending

630 ? (LHS->right() - LHS->left()) >

631 (RHS->right() - RHS->left())

632 : (LHS->right() - LHS->left()) <

633 (RHS->right() - RHS->left());

634 });

635 }

636

637

638

639

641 printTree(OS, 0, Root, HexFormat);

642 }

643

644

646 assert(empty() && "Interval tree already constructed.");

647

648

653 References.push_back(std::addressof(Data));

654 }

655 std::stable_sort(Points.begin(), Points.end());

658

659 EndPoints.assign(Points.begin(), Points.end());

660

661 IntervalsLeft.resize(Intervals.size());

662 IntervalsRight.resize(Intervals.size());

663

664

665

666

667 unsigned IntervalsSize = 0;

668 Root =

669 createTree(IntervalsSize, 0, EndPoints.size() - 1,

670 0, References.size());

671

672

673 References.clear();

674 }

675

676

677

678

682 : find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point);

683 }

684

685

686 find_iterator find_end() const { return End; }

687};