[ANN] First release of oma

Community
1

Hello,

It is my pleasure to announce the first release of Oma. This library offers an implementation of the
order maintenance data structure described in this paper.

  opam update
  opam install oma

Here is its documentation.

Happy hacking!

16 Likes
2

I have just published a new release of oma with the following fixes and changes:

  • New functions invalidate_open_interval and invalidate_semi_open_interval.

  • Fix a serious bug in Unsafe.first and Unsafe.last, which would incorrectly return None when the region contains only one point.

  • Fix a serious bug in Unsafe.iter, which would systematically omit the last point of the region.

4 Likes
3

Would it be possible to have an efficient rank operation?
Given set s, I want to know the rank of x, with x in s.

Also, is it possible to access efficiently the element at a given rank?

4

IIUC, in this data structure the cells carry no data, so this question does not really apply here.
The idea is maybe to use them as identifiers, eg:
type t = { data : string; id : Oma.point }

Of course it should be easy to modify oma to get something like type 'a point.

BTW, it was interesting for me to realise that I used a strategy similar to oma in the Chain module (which does carry data). Except that I didn’t optimize the renumbering process, which is a nontrivial task of course.

1 Like
5

Could you please explain the rank?

6

Hello, and sorry for my late reply. No, oma does not allow efficient conversions between a point and its integer rank (in either direction). As far as I can see, the data structure fundamentally does not support such conversions. If necessary, you can implement these conversions in an inefficient way (that is, in linear time) using the iteration functions in the submodule Oma.Unsafe.

1 Like