I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.
One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.
Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so). More precisely, the operations I will need to perform are as follows:
- Remove an element from the antichain;
- Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.
I can also bound every element by two integers, so that if I know that $i_1 < a < i_2$ and $i_3 < b < i_4$, then knowing $i_2 < i_3$ instantly gives me $a < b$. Of course, $i_2 \not< i_3$ does not mean $a \not < b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.