Common Lisp Package: JP-UTILS

README:

FUNCTION

Public

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

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

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