Replay set is my term for a set whose iteration order is the order in which the elements were
first added to it. It’s the same concept as Java’s LinkedHashSet, but I don’t like the term
“linked” here, because it’s a fact about the implementation, not the semantics. Anyway, FSet’s
replay sets don’t use a linked list, but keep the ordering in a seq alongside the set.
Alternatively, you can look at a replay set as a sequence that enforces uniqueness: an element can be added only once.
Replay maps are very similar; like LinkedHashMap, they remember the order in which keys
were first added. They also use a seq for this purpose.
Of course, FSet’s implementation is functional and persistent. There is one significant downside to
it, though: the less and index operations take O(n) time, as they have to scan
through the seq to find the element or key.
The original implementations of replay sets and maps used WB-trees. By default, the newer and
faster CHAMP sets and maps are now used instead. I have not removed the older classes
wb-replay-set and wb-replay-map, so as not to break existing code, but I’m not
documenting them because I don’t know why you would want to use them; iteration order is not a
concern here, since it’s imposed by the client anyway.