SortedCache S

kl.spad line 14 [edit on github]

• S: CachableSet

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: (S, (S, S) -> Integer) -> Union(S, failed)

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: () -> Void

clearCache() empties the cache.

enterInCache: (S, (S, S) -> Integer) -> S

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.

enterInCache: (S, S -> Boolean) -> S

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.

linearSearch: (S, S -> Boolean) -> Union(S, failed)

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.