Commit graph

14 commits

Author SHA1 Message Date
Bruno BELANYI d550642296 Fix edge-case in identifying 'end' upper-bound
All checks were successful
ci/woodpecker/push/check Pipeline was successful
Just my luck, this was found immediately in the CI, right when I
uploaded the project thinking I was done.

Thankfully the fix is easy and (in hindsight) quite obvious.
2024-08-24 21:02:23 +01:00
Bruno BELANYI 3305b13936 Fix Meson install 2024-08-24 21:01:31 +01:00
Bruno BELANYI 08f2364c50 Make implementation follow assignment rules
From what I could find, the rules of the assignment seem to be:

1. Restrict oneself to at most *one* O(log(N)) call, and otherwise use
   constant time operations on the map.
2. Don't use more operations than strictly necessary on `K` and `V`.
3. Prefer simplicity to performance.

I think my solution would fare well under those constraints.
2024-08-24 21:01:31 +01:00
Bruno BELANYI c41d1b2922 Add randomized test
This was especially helpful for my previous attempt at a solution, which
did was more complicated.

The original rules for this assignment are quite silly, I don't think
they really optimize anything, and make understanding the actual
algorithm more difficult than it should be.
2024-08-24 20:32:14 +01:00
Bruno BELANYI 749cb335e3 Make test failure more verbose
Outputting the state of the map and this history of operations makes
debugging easier.
2024-08-24 20:32:14 +01:00
Bruno BELANYI 4d59126f10 Add initial tests
Those were the ones I used for the initial implementation.
2024-08-24 20:32:14 +01:00
Bruno BELANYI 4ab8dd37ff Add implementation 2024-08-24 20:32:14 +01:00
Bruno BELANYI 65e0d4991f Test against fake 'Model' implementation
This removes most of the redundant `for` loops that would appear in
hand-written unit tests, and could potentially open the door to
fuzz-testing/property-test the implementation for a more in-depth
test-suite.
2024-08-24 20:32:02 +01:00
Bruno BELANYI 73c2b21b94 Explicitly test for canonicity
This will come in handy later, with more complex test cases.
2024-08-24 20:32:02 +01:00
Bruno BELANYI 6bc72fdc25 Introduce 'IntervalMapTest' fixture 2024-08-24 20:32:02 +01:00
Bruno BELANYI c8183d99a6 Handle empty range insertion 2024-08-24 20:32:02 +01:00
Bruno BELANYI 5292c22e2c Add test for minimal 'interval_map' type interface
Add `KeyInterface` (respectively `ValueInterface`). Those classes
provide the minimum documented interface for `K` (respectively `V`) in
`interval_map<K, V>`.
2024-08-24 20:32:02 +01:00
Bruno BELANYI 3c0ddf3021 Add given code 2024-08-24 20:32:02 +01:00
Bruno BELANYI c4d81c4e81 Bootstrap project 2024-08-24 20:32:02 +01:00