Skip to content

Latest commit

 

History

History
36 lines (24 loc) · 1.74 KB

README.md

File metadata and controls

36 lines (24 loc) · 1.74 KB
Raw

License: MIT Build Status

ftreap

Order statistic tree based on Treap data structure and powerful Implicit Treap for interval operations. Compact ObjectPascal generic class TTreapNode and generic class TImplicitTreapNode. See Wiki for more info.

Motivation

Why another treap implementation? The story begins from the SPOJ problem ALLIN1. All accepted solutions was in C/C++ and one in D-DMD. I asked myself - why not Pascal? My first attempt was based on records (mode DELPHI) - time 2.28s. After reading Michalis Kamburelis excellent Modern Object Pascal Introduction for Programmers I started ftreap. So, here we are.

Benchmarks

Here some testing results on IDEONE.

Method \ Number of keys 100000 200000 400000 800000 1600000
Insert 0.08s 0.19s 0.42s 1.06s 2.58s

FTREAP vs FCL-STL gset.

Built With

  • Lazarus - The professional Free Pascal RAD IDE.
  • PasDoc - Documentation tool for ObjectPascal (Free Pascal, Lazarus, Delphi).

License

This project is licensed under the MIT License - see the LICENSE file for details.