# FUNCTION

# Public

# BINARY-SEARCH (THE-ELEMENT VECTOR &KEY (TEST= #'EQL) (TEST< #'<) (GET-ELEMENT #'AREF) (START 0) (END (1- (LENGTH VECTOR))) (NOT-FOUND NIL))

Performs a binary search for an element el on a (sorted) array vec.
Return values:
- The index where the element was found
- Either t (if el was found) or nil (if el was not found) You can ask
the function to return something else on failure.
Named parameters:
- get-element is the function used to retrieve an element of the vector.
The default is aref. This should be a FUNCTION, and not a symbol!
- start and end are the start and end indices within the array. If
they are not supplied, 0 and the last index will be used.
- test= and test-before are the tests to be used for equality and for
determining precedence between elements. These should be FUNCTIONS,
and not symbols!
- not-found is the element to be returned when the element is not found.
If not-found is set to 't', then, in case of failure, the function will
return (i NIL), where i is the index where the element *should* be (or
where it could be inserted).
So, by default you can test the return inside an (if (binary-search) ...),
since it returns either NIL or the position.

# COUNTING-SORT

Counting sort. Only works for arrays of fixnums.
data is the array. The elements in the array must range from
zero to k. Optional parameters start and end can be used to specify
a subrange of the array to be sorted, but then the new array will
have zeroes in all other places (this will be fixed later).
This function returns the new array and the counting array, which
tells where each each key starts in the new array.

# COUNTING-SORT-G

Generalized counting sort: it will sort data structures, provided that there
is a way to identify elements with fixnum keys.
Parameters:
===========
- data is the structure to be sorted.
- sorted-data is the new sorted structure, that needs to be previously allocated
(and be similar to data)
- k is the maximum key value. CAUTION: this function will allocate an array
of size k, so if it is too large, it may not work.
- start and end define the slice of the keys that will be sorted.
- The key function identifies array elements given a fixnum. By default
tihs is aref;
- The copy-element wihch will be used to copy elements among different posisions
needs to have four arguments:
+ new: the new data structure
+ new-i: the index in the new data structure
+ old: the old data structure
+ old-i: the index in the old data structure
So, given those, this function should copy an element from position old-i on
structure old to position new-i on structure new.
Return value and result:
========================
This function will return the counting array, which shows where in the new structure
each key begins:
(let ((new-data (make-array 12 :element-type 'fixnum)))
(counting-sort-g #(0 2 4 6 0 2 4 6 1 3 5 7) new-data 8 0 11))
=> #(0 2 3 5 6 8 9 11)
new-data #(0 0 1 2 2 3 4 4 5 6 6 7)
count vector: #(0 2 3 5 6 8 9 11)
Looking at the count vector, we see that the elements with key '0' start
at position '0' in the new structure; the elements with key '1' start
at position '2'; elements with key '2' start at '3', etc, and elements
with key '7' start at the last position, '11'.
Example:
========
;;; A structure contains two arrays:
(defstruct (two-arrays (conc-name ta))
array-one
array-two)
;;; Now we sort it, using the first array as the key array, and the second as
;;; the data array.
(counting-sort-g two-arrays
two-arrays-new
100
10
110
:key #'(lambda (data i) (aref (ta-array-one data) i))
:copy-element #'(lambda (new new-i old old-i)
(setf (aref (ta-array-one new) new-i) (aref (ta-array-one old) old-i)
(aref (ta-array-two new) new-i) (aref (ta-array-two old) old-i))
Efficiency:
===========
If k is not large, this is much faster than Lisp's built-in sort function, because it
does not rely on element comparison. cl:sort takes O(n lg n) time, counting-sort-g takes
O(n + k) time. On the other hand, it requires O(n + k) additional memory: besides the
argument sorted-data, which is provided by you, this function will also allocate an array
of size k.
For details, see:
- Cormen, Leiserson, Rivest and Stein: 'Introduction to algorithms'
- Berman and Paul, 'Algorithms: sequential, parallel, and distributed'
- Wikipedia:
+ http://en.wikipedia.org/wiki/Sorting_algorithm
+ http://en.wikipedia.org/wiki/Counting_sort
Because it is generic and works on any data structure, this function can be ten times
slower than the counting-sort function in this package, which works on arrays of fixnums
only.

# GENERATE-RANDOM-ARRAY (SIZE RANGE-START RANGE-END)

Generates an array of fixnums of size n, ranging from 0 to k

# HASH-TABLE-KEYS (HASH)

Returns a list with the keys of a hash table.

# ROBUST-ADJUST-ARRAY (ARRAY SIZE &KEY (ELEMENT-TYPE NIL))

Adjusts the size of an array, setting it to the new one. Also works around
an issue with Allegro Common Lisp: in ACL, when you call adjust-array on a non-adjustable
array, the resulting array is not necessarily of the same type. It is not a SIMPLE-ARRAY
anymore. Dependig on how you try to fix it, you may end up with an array whose
element-type is T. So, this is a method for resizing an array and keeping the same array
type.
Yes, we want SIMPLE-ARRAYs because access is faster. But we also want to adjust them, even
if adjusting is slow.

# SORTEDP (SEQ &KEY (TEST #'<))

Determines if a sequence is sorted. Will return (t size)
on success (where size is the size of the sequence) or
nil size), where size is the size of the largest sorted subsequence,
from the beginning to the right.
For example:
(sortedp '(10 20 30 40 1 100)) ==> (NIL, 4)
(sortedp #(10 20 30 40 50 100)) ==> (T, 6)
See that the size of the sorted sequence is always at least one, except
for empty sequences, which are always sorted:
(sortedp ()) ==> (T, 0)

# SUBST-ALL (SUBST-LIST TREE)

Performs several substitutions on a tree (similar to what subst does).
subst-list is a list of substitutions. For example:
(subst-all '((a 1) (b 2) (c 3))
'(x y a (z b (u v c))))
=> (X Y 1 (Z 2 (U V 3)))

# Undocumented

# FORMAT-SYMBOL (STRING &REST ARGS)

# FORMAT-UNINTERNED-SYMBOL (STRING &REST ARGS)

# Private

# COPY-CLOCK (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

# ELAPSED-TIME

Returns the time elapsed since the stopwatch started,
while it was running (pauses are excluded).
If the clock was currently running, the time until now
is computed. Otherwise, time until the most recenr stop
is computed.

# RESET-CLOCK

Completely resets the stopwatch.

# SEQUENCE-FIRST (SEQ)

Returns the first element of a sequence.

# START-CLOCK

Sets the start time of the stopwatch to 'now',
but does NOT reset the elapsed time.

# STOP-CLOCK

Pauses the stopwatch and updates the elapsed-time.

# Undocumented

# CLOCK-ELAPSED-TIME (STRUCTURE)

# SETFCLOCK-ELAPSED-TIME (NEW-VALUE STRUCTURE)

# CLOCK-RUNNING (STRUCTURE)

# SETFCLOCK-RUNNING (NEW-VALUE STRUCTURE)

# CLOCK-START-TIME (STRUCTURE)

# SETFCLOCK-START-TIME (NEW-VALUE STRUCTURE)

# HASH-TABLE-KEYS-AS-ARRAY (HASH)

# MAKE-CLOCK (&KEY ((START-TIME DUM688) 0) ((ELAPSED-TIME DUM689) 0) ((RUNNING DUM690) NIL))

# MACRO

# Public

# DO-SEQUENCE ((IDX SEQ) &REST BODY)

Runs across a sequence (syntatic sugar).

# FAST-BINARY-SEARCH (THE-ELEMENT VECTOR &KEY (ELEMENT-TYPE T) (TEST= 'EQL) (TEST< '<) (GET-ELEMENT 'AREF) (START 0) (END NIL) (NOT-FOUND NIL))

This is binary search with type declarations. It's similar to the binary-search function.

# GET-BINARY-SEARCH (&KEY (ELEMENT-TYPE T) (TEST= 'EQL) (TEST< '<) (GET-ELEMENT 'AREF) (NOT-FOUND 'NIL))

This function returns a function (with type declarations) that will perform binary search.

# WITH-GENSYMS ((&REST NAMES) &BODY BODY)

Expands into code that binds all names to symbols generated by (gensym).