BeginPackage["CSM`Collect`", "CSM`Classes`"]

collection::usage = "collection is the abstract base class
	of all collections."
indexedCollection::usage = "indexedCollection is the abstract
	base class of all indexed collections."
array::usage = "new[array, size, elem] creates an array of
	given size with elements initialized to elem."
list::usage = "new[list] creates a new empty list."
set::usage = "new[set] creates a new empty set."
interval::usage = "new[interval, from, to, step] creates the
	interval {from, to, step}."
dictionary::usage = "new[dictionary, hsize] creates a new
	dictionary with a hashtable of size hsize."

includes::usage = "includes[coll, elem] is True,
	if coll contains elem."
includesKey::usage = "includes[indcoll, key] is True,
	if indcoll contains an element with given key."
fold::usage = "fold[coll, start, binop] folds binop over coll
	with starting value start."
size::usage = "size[coll] gives the number of elements of coll."
isEmpty::usage = "isEmpty[coll] returns True,
	if coll has no elements."
select::usage = "select[coll, crit] returns a list of those
	elements of coll that satisfy crit."
do::usage = "do[coll, f] iterates f over all elements of coll."
binaryDo::usage = "binaryDo[indcoll, f2] call f2 with all
	keys and values of indcoll."
at::usage = "at[indcoll, key] returns the value stored under key."
atPut::usage = "atPut[indcoll, key, val] stores val under
	key in indcoll."
add::usage = "add[list|set, val] adds val to the list or set."

Begin["`Private`"]

Class[ collection, Object,
    {},
    {{fold,     Function[{v0, g},
                    Module[{v = v0}, do[self, (v = g[v, #])&]; v] ]},
     {size,     Function[{}, fold[self, 0, #1+1&] ]},
     {isEmpty,  Function[{}, size[self] == 0 ]},
     {includes, Function[{elem},
                    Catch[ do[self, If[#===elem, Throw[True]]&]; False ] ]},
     {select,   Function[{pred},
                    fold[self, new[list], (If[pred[#2], add[#1, #2]]; #1)&] ]}
    }
]

indexedCollection::nsk = "Key `1` is not in `2`."

Class[ indexedCollection, collection,
    {},
    {{do,          Function[{f}, binaryDo[self, f[#2]&]]},
     {includesKey, Function[{key},
                       Catch[atIfAbsent[self, key, Throw[False]&]; True] ]},
     {at,          Function[{key},
                       atIfAbsent[self, key,
                         Message[indexedCollection::nsk, key, self]&]
                   ]}
    }
]

array::nsk = "Array index `1` is not in the range (1...`2`)."

Class[ array, indexedCollection,
    {ar},
    {{binaryDo,   Function[{f},
                    do[ new[interval, 1, size[self], 1], f[#, at[self, #]]& ] ]},
     {atIfAbsent, Function[{key, proc}, 
                    If[ boundCheck[self, key], ar[[key]], proc[] ] ]},
     {atPut,      Function[{key, val},
                    If[ boundCheck[self, key],
                        ar[[key]] = val,
                        Message[array::nsk, key, size[self]] ];
                    self ]},
     {size,       Function[{}, Length[ar] ]},
     {boundCheck, Function[{i}, TrueQ[1 <= i <= size[self]] ]},
     {new,        Function[{size, v0}, new[super]; ar = Table[v0, {size}] ]}
    }
]

Class[ link, indexedCollection,
    {key, val, next},
    {{new, (new[super]; {key, val, next} = {##})&},
     {notNil, self =!= nullLink&},
     {binaryDo, Function[ {f},
	     If[notNil[self], f[key, val]; binaryDo[next, f]] ]},
     {atIfAbsent, Function[{k, proc},
	        Which[ !notNil[self], proc[],
	               key===k, val,
	               True,    atIfAbsent[next, k, proc] ]
	          ]},
     {atPut, Function[{k, v},
	        Which[ !notNil[self], new[link, k, v, nullLink],
	               key===k, val=v; self,
	               True,    next=atPut[next, k, v]; self ]
	     ]}
    }
]

nullLink = new[link, 0, 0, nullLink]

Class[ list, collection,
    {head},
    {{do,   Function[{f}, do[head, f]]},
     {add,  Function[{elem}, head = new[link, 0, elem, head]; self]},
     {new,  Function[{}, new[super]; head=nullLink]}
    }
]

Class[ set, list,
    {},
    {{add,  Function[{elem}, If[!includes[self, elem], add[super, elem]]; self ]}
    }
]

Class[ interval, collection,
    {lower, upper, step},
    {{do,  Function[{f}, Do[ f[i], {i, lower, upper, step}]]},
     {new, Function[{l, u, s}, new[super]; {lower, upper, step}={l, u, s}]}
    }
]

Class[ dictionary, indexedCollection,
    {linktable},
    {{binaryDo,   Function[{f}, do[linktable, binaryDo[#, f]&] ]},
     {atIfAbsent, Function[{key, proc},
                    atIfAbsent[ at[linktable, bin[self, key]], key, proc ] ]},
     {atPut,      Function[{key, val}, With[{slot = bin[self, key]},
                    atPut[ linktable, slot, atPut[at[linktable, slot], key, val] ];
                    self ]]},
     {new,        Function[{n}, new[super]; linktable = new[array, n, nullLink] ]},
     {bin,        Function[ {key}, Mod[Hash[key], size[linktable]] + 1 ]}
    }
]

End[]

EndPackage[]
