/usr/share/axiom-20170501/src/algebra/SCACHE.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | )abbrev package SCACHE SortedCache
++ Author: Manuel Bronstein
++ Date Created: 31 Oct 1988
++ Date Last Updated: 14 May 1991
++ Description:
++ 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.
SortedCache(S) : SIG == CODE where
S : CachableSet
N ==> NonNegativeInteger
DIFF ==> 1024
SIG ==> with
clearCache : () -> Void
++ clearCache() empties the cache.
cache : () -> List S
++ cache() returns the current cache as a list.
enterInCache : (S, S -> Boolean) -> S
++ enterInCache(x, f) enters x in the cache, calling \spad{f(y)} to
++ determine whether x is equal to y. It returns x with an integer
++ associated with it.
enterInCache : (S, (S, S) -> Integer) -> S
++ enterInCache(x, f) enters x in the cache, calling \spad{f(x, y)} to
++ determine whether \spad{x < y (f(x,y) < 0), x = y (f(x,y) = 0)}, or
++ \spad{x > y (f(x,y) > 0)}.
++ It returns x with an integer associated with it.
CODE ==> add
shiftCache : (List S, N) -> Void
insertInCache: (List S, List S, S, N) -> S
cach := [nil()]$Record(cche:List S)
cache() == cach.cche
shiftCache(l, n) ==
for x in l repeat setPosition(x, n + position x)
void
clearCache() ==
for x in cache repeat setPosition(x, 0)
cach.cche := nil()
void
enterInCache(x:S, equal?:S -> Boolean) ==
scan := cache()
while not null scan repeat
equal?(y := first scan) =>
setPosition(x, position y)
return y
scan := rest scan
setPosition(x, 1 + #cache())
cach.cche := concat(cache(), x)
x
enterInCache(x:S, triage:(S, S) -> Integer) ==
scan := cache()
pos:N:= 0
for i in 1..#scan repeat
zero?(n := triage(x, y := first scan)) =>
setPosition(x, position y)
return y
n<0 => return insertInCache(first(cache(),(i-1)::N),scan,x,pos)
scan := rest scan
pos := position y
setPosition(x, pos + DIFF)
cach.cche := concat(cache(), x)
x
insertInCache(before, after, x, pos) ==
if ((pos+1) = position first after) then shiftCache(after, DIFF)
setPosition(x, pos + (((position first after) - pos)::N quo 2))
cach.cche := concat(before, concat(x, after))
x
|