# 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.