kl.spad line 14 [edit on github]
A sorted cache of a cachable set S is a dynamic structure that keeps the elements of S sorted and assigns an integer to each element of S once it is in the cache. This way, equality and ordering on S are tested directly on the integers associated with the elements of S, once they have been entered in the cache.
binarySearch(x, f) searches x in the cache, calling f(x, y) to determine order. It returns y from cache if f(x, y) is 0 or "failed" if no such y exists.
clearCache() empties the cache.
enterInCache(x, f) enters x in the cache, calling f(y) to determine whether x is equal to y. It returns x with an integer associated with it.
enterInCache(x, f) enters x in the cache, calling f(x, y) to determine whether x < y (f(x, y) < 0), x = y (f(x, y) = 0), or x > y (f(x, y) > 0). It returns x with an integer associated with it.
linearSearch(x, f) searches x in the cache, calling f(y) to determine whether x is equal to y. It returns y from cache if f(y) is true or "failed" if no such y exists.