Algorithms Reference

This section contains reference of all the functions in the CL-DS.ALG package.

Aggregation Functions

Aggregation functions transform range into a singular value, akin to the SQL aggregation functions.

Symbols in the package CL-DATA-STRUCTURES.ALGORITHMS:
ACCUMULATE
Lambda List: (RANGE FN &KEY KEY INITIAL-VALUE AFTER)
Description: Like CL:REDUCE but works on all traversable objects.
See also:
  • CUMULATIVE-ACCUMULATE

RESERVOIR-SAMPLE
Lambda List: (RANGE SAMPLE-SIZE &KEY KEY AFTER)
Description: Draws sample in the form of the vector from the range.
Returns: VECTOR of the size equal to the SAMPLE-SIZE and with the fill pointer up to the sample-size.
Exceptional situations:
  • Will signal TYPE-ERROR if SAMPLE-SIZE is not of the type POSITIVE-FIXNUM.

Notes: This function implements the L algorithm.
COUNT-ELEMENTS
Lambda List: (RANGE &KEY AFTER)
Arguments:
  • RANGE, Input range.

Examples: 
(LET ((DATA #(1 2 3 4 5)))
  (PROVE.TEST:IS (LENGTH DATA)
                 (CL-DATA-STRUCTURES.ALGORITHMS:COUNT-ELEMENTS DATA))
  (PROVE.TEST:IS 3
                 (CL-DATA-STRUCTURES:AT
                  (CL-DATA-STRUCTURES.ALGORITHMS:COUNT-ELEMENTS
                   (CL-DATA-STRUCTURES.ALGORITHMS:GROUP-BY DATA :KEY #'EVENP))
                  NIL)))

Description: Counts the number of elements. Useful mostly in conjunction with a GROUP-BY.
Returns: Integer.
See also:
  • GROUP-BY

EXTREMA
Lambda List: (RANGE FN &KEY KEY VALUE-KEY AFTER)
Arguments:
  • RANGE, Input range.
  • FN, Comparsion function.
  • KEY, Function used to extract values from the elements in the RANGE.
  • VALUE-KEY, Like KEY, but using this instead will preserve the complete element in the result. This argument can be used in combination with KEY, in which case KEY is applied before the VALUE-KEY.

Description: An aggregation function. Finds extrema (both minimum and maximum) in the RANGE, according to the FN comparsion function.
Returns: Dotted pair. The first value is the extremum that would occur as the first element in the sequence sorted according to the FN, second value is an element that would occur as the last.
Exceptional situations: Will signal a TYPE-ERROR if either FN, KEY or VALUE-KEY is not funcallable.
Notes:
  • Shadows SERAPEUM:EXTREMA.

EXTREMUM
Lambda List: (RANGE FN &KEY KEY VALUE-KEY AFTER)
Arguments:
  • RANGE, Input range.
  • FN, Comparsion function.
  • KEY, Function used to extract values from the elements in the RANGE.
  • VALUE-KEY, Like KEY, but using this instead will preserve the complete element in the result. This argument can be used in combination with KEY, in which case KEY is applied before the VALUE-KEY.

Description: An aggregation function. Finds the extremum (the first value that would occur if the whole range was sorted according to the FN). This can be used to find either the maximum or the minimum.
Returns: Single extremum value.
Exceptional situations: Will signal a TYPE-ERROR if either FN, KEY or VALUE-KEY is not funcallable.
Notes:
  • Shadows ALEXANDRIA:EXTREMUM.

TO-VECTOR
Lambda List: (RANGE &KEY KEY ELEMENT-TYPE SIZE AFTER)
Arguments:
  • RANGE, Object to aggregate.
  • KEY, Key function used to extract value to the result vector.
  • ELEMENT-TYPE, :ELEMENT-TYPE for the result vector.
  • SIZE, Initial size of the internal vector. Supplie to minimize memory allocations count.
  • FORCE-COPY, When false, TO-VECTOR called with CL:VECTOR is allowed to return the input.

Description: Collects all elements into a CL:VECTOR.
Returns: CL:VECTOR with the content of the RANGE.
Exceptional situations:
  • Will signal a TYPE-ERROR if KEY is not funcallable.
  • Will signal same conditions as make-array would when ELEMENT-TYPE or SIZE are invalid.

Notes:
  • There is no way to know ahead of time how large vector will be created, and therefore multiple reallocations may be performed during aggregation. A user can supply :SIZE to mitigate that.
  • To avoid copying in the case when RANGE is also a vector, pass NIL as :FORCE-COPY.

TO-LIST
Lambda List: (RANGE &KEY KEY AFTER)
Description: Collects all elements into a CL:LIST.
Returns: CL:LIST with the content of the RANGE.
Exceptional situations:
  • Will signal a TYPE-ERROR if KEY is not funcallable.

TO-HASH-TABLE
Lambda List: (RANGE &KEY KEY TEST SIZE HASH-TABLE-KEY HASH-TABLE-VALUE AFTER)
Arguments:
  • KEY, Key function used to extract value to the result vector.
  • TEST, Test fo the MAKE-HASH-TABLE.
  • SIZE, Size for the MAKE-HASH-TABLE.
  • TABLE, Optional, initial HASH-TABLE.
  • HASH-TABLE-KEY, Function used to extract key for the HASH-TABLE. Defaults to IDENTITY.
  • HASH-TABLE-VALUE, Function used to extract value for the HASH-TABLE. Defaults to IDENTITY.

Description: Collects all elements into a CL:HASH-TABLE.
Returns: CL:HASH-TABLE with the content of the RANGE.
Exceptional situations:
  • Will signal a TYPE-ERROR if either KEY, HASH-TABLE-VALUE, HASH-TABLE-KEY is not funcallable.
  • Will signal a TYPE-ERROR if TABLE is not of type CL:HASH-TABLE.
  • Will signal conditions just like MAKE-HASH-TABLE would if either SIZE or TEST is invalid.

Layer Functions

Layer functions decorate the input range to add a new behavior to it.

Symbols in the package CL-DATA-STRUCTURES.ALGORITHMS:
DISTINCT
Lambda List: (RANGE &KEY KEY TEST HASH-FUNCTION)
Arguments:
  • RANGE, Input range.
  • TEST, Function used to compare elements. Defaults to EQL.
  • HASH-FUNCTION, Function used for hashing. Defaults to #'sxhash.
  • KEY, Key function, used to extract values for test.

Description: Returns forward range that skips elements that were already seen.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations: Will signal a TYPE-ERROR if either TEST, HASH-FUNCTION or KEY is not funcallable.
CUMULATIVE-ACCUMULATE
Lambda List: (RANGE FUNCTION &KEY KEY RESULT INITIAL-VALUE)
Description: Like ACCUMULATE, but produces range with all intermediate accumulation states.
See also:
  • ACCUMULATE

Notes:
  • Can be considered to be lazy version of SERAPEUM:SCAN.

TRANSLATION
Lambda List: (RANGE DICT &KEY KEY)
Description: Substitutes element in the range with one found in the DICT, if present. If not, leaves element unchanged.
Returns: ON-EACH-RANGE subclass.
Exceptional situations:
  • Will signal a TYPE-ERROR if KEY is not funcallable.

ENUMERATE
Lambda List: (RANGE &KEY KEY TEST SIZE NUMBER)
Arguments:
  • KEY, Key function used to extract value to the result vector.
  • NUMBER, Start of the enumeration.
  • TEST, Test fo the MAKE-HASH-TABLE.
  • SIZE, Size for the MAKE-HASH-TABLE.

Description: Gathers unique elements in the RANGE and assigns a number to each (starting with NUMBER, incrementing by 1).
Returns: CL:HASH-TABLE, unique elements used as keys, numbers stored as values.
Exceptional situations:
  • Will signal a TYPE-ERROR if either KEY is not funcallable.
  • Will signal a TYPE-ERROR if TABLE is not of type CL:HASH-TABLE.
  • Will signal a TYPE-ERROR if NUMBER is not of type CL:INTEGER
  • Will signal conditions just like MAKE-HASH-TABLE would if either SIZE or TEST is invalid.

FLATTEN-LISTS
Lambda List: (RANGE &KEY KEY)
Arguments:
  • RANGE, Input range.
  • KEY, Function used to extract lists from elements of the RANGE. Defaults to CL:IDENTITY.

Description: A layer function. Flattens each list in the input range to the atoms.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations: Will signal a TYPE-ERROR if KEY is not funcallable.
See also:
  • MULTIPLEX

Notes:
  • Pretty much the same purpose as for ALEXANDRIA:FLATTEN, but FLATTEN-LISTS is lazy.

GROUP-BY
Lambda List: (RANGE &KEY TEST KEY GROUPS TRANSFORM HAVING)
Arguments:
  • RANGE, Range that is supposed to be groupped.
  • TRANSFORM, This function will be called with each constructed group and the result will be placed in the result range in place of the original group. Defaults to IDENTITY.
  • HAVING, This function will called with each constructed group (before calling TRANSFORM). If true is returned; group is kept in the result range, otherwise group is discarded.
  • KEY, Key function, used to extract value for TEST.
  • GROUPS, HASH-TABLE groups prototype. Passing this will cause :TEST to be discarded. This argument is useful for using non-portable HASH-TABLE extension.
  • TEST, Test for the inner hashtable (either eq, eql or equal).

Examples: 
(LET* ((DATA #(1 2 3 4 5 6 7 8 9 10))
       (SUMS
        (ITERATE:ACCUMULATE
         (CL-DATA-STRUCTURES.ALGORITHMS:GROUP-BY DATA :KEY #'EVENP) #'+)))
  (PROVE.TEST:IS (CL-DATA-STRUCTURES:SIZE SUMS) 2)
  (PROVE.TEST:IS (CL-DATA-STRUCTURES:AT SUMS T) 30)
  (PROVE.TEST:IS (CL-DATA-STRUCTURES:AT SUMS NIL) 25))

Description: Groups RANGE into partitions according to the TEST. This does not change the content of the RANGE, but will force aggregation to be performed on every group independently.
Returns: GROUP-BY-RANGE instance (either forward, bidirectional or random access, based on the class of the RANGE).
Exceptional situations:
  • Will signal a TYPE-ERROR if KEY is not funcallable.
  • Will pass TEST to MAKE-HASH-TABLE and therefore will signal same conditions as MAKE-HASH-TABLE.

SLIDING-WINDOW
Lambda List: (RANGE BATCH-SIZE)
Arguments:
  • RANGE, Input range.
  • WINDOW-SIZE, Size of the sliding window.

Examples: 
(PROGN
 (PROVE.TEST:IS
  (CL-DATA-STRUCTURES.ALGORITHMS:TO-LIST
   (CL-DATA-STRUCTURES.ALGORITHMS:SLIDING-WINDOW '(1 2 3) 3))
  '((1 2 3)) :TEST 'EQUAL)
 (PROVE.TEST:IS
  (CL-DATA-STRUCTURES.ALGORITHMS:TO-LIST
   (CL-DATA-STRUCTURES.ALGORITHMS:SLIDING-WINDOW '(1 2 3 4) 3))
  '((1 2 3) (2 3 4)) :TEST 'EQUAL))

Description: Groups RANE elementwise using sliding window of the the size WINDOW-SIZE.
Exceptional situations:
  • Will signal a TYPE-ERROR if WINDOW-SIZE is not of the type POSITIVE-INTEGER.

Notes:
  • Windows are always of the length of WINDOW-SIZE. If there is not enough elements to form window, range will act as it would be empty.

ONLY-DIFFERENT
Lambda List: (RANGE &KEY TEST INITIAL-VALUE KEY)
Description: A layer function. Creates a range that skips ELEMENT if it is the same as the previous in the range (according to the TEST function).
Returns: A forward range.
ON-EACH
Lambda List: (RANGE FUNCTION &KEY KEY FUNCTOR-CONSTRUCTOR)
Arguments:
  • RANGE, Input range.
  • FUNCTION, Function called on the RANGE content.
  • KEY, Function used to extract content for the FUNCTION. Defaults to the CL:IDENTITY.

Description: Creates a new range by applying the FUNCTION to each element of the RANGE.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations: Will signal a TYPE-ERROR if KEY or FUNCTION is not funcallable.
Notes: Works almost like cl:map-and-friends, but lazily evaluates content.
ONLY
Lambda List: (RANGE PREDICATE &KEY KEY)
Arguments:
  • RANGE, Input range.
  • PREDICATE, Test used to check if element should be skipped.
  • KEY, Key function used to extract a value for predicate.

Description: A layer function. Creates a range that skips elements that PREDICATE (KEY element) => NIL.
Returns: Either forward, bidirectional or random-access range, depending on the RANGE.
Exceptional situations: Will signal a TYPE-ERROR if either PREDICATE or KEY is not funcallable.
ONLY-DIFFERENT
Lambda List: (RANGE &KEY TEST INITIAL-VALUE KEY)
Description: A layer function. Creates a range that skips ELEMENT if it is the same as the previous in the range (according to the TEST function).
Returns: A forward range.
WITHOUT
Lambda List: (RANGE PREDICATE &KEY KEY)
Arguments:
  • RANGE, Input range.
  • PREDICATE, Test used to check if an element should be skipped.
  • KEY, Key function used to extract a value for the predicate.

Description: A layer function. Creates a range that skips elements that PREDICATE (KEY element) => T.
Returns: Either forward, bidirectional or random-access range, depending on the RANGE.
Exceptional situations: Will signal a TYPE-ERROR if either PREDICATE or KEY is not funcallable.
PARTITION-IF
Lambda List: (RANGE TEST &KEY KEY ON-FIRST)
Arguments:
  • RANGE, An input range.
  • TEST, A function of two arguments used to check if elements belong to the same partition.

Examples: 
(LET* ((DATA
        '((1 "w") (1 "o") (1 "r") (1 "d") (2 "a") (2 "s") (3 "l") (3 "a")
          (3 "w")))
       (PARTITIONED
        (CL-DATA-STRUCTURES.ALGORITHMS:PARTITION-IF DATA
                                                    (LAMBDA (PREV NEXT)
                                                      (= (FIRST PREV)
                                                         (FIRST NEXT)))))
       (AGGREGATED
        (CL-DATA-STRUCTURES.ALGORITHMS:TO-VECTOR PARTITIONED :KEY
                                                 (LAMBDA (X)
                                                   (MAP 'STRING
                                                        (ALEXANDRIA:COMPOSE
                                                         #'ALEXANDRIA:FIRST-ELT
                                                         #'SECOND)
                                                        X)))))
  (PROVE.TEST:IS AGGREGATED #("word" "as" "law") :TEST #'EQUALP))

Description: Groups consecutive elements in the range into a partition if TEST called on the previous value in the range and the current value in the range returns non-NIL, creates new partition otherwise. This does not change the content of the RANGE, but it will force aggregation to be performed on every group independently. Order of the groups is preserved in the aggregation result.
Returns: ABSTRACT-PARTITION-IF-PROXY instance.
Notes:
  • Aggregation on the returned range is performed eagerly.
  • Can be considered to be alternative to the GROUP-BY, suitable for the ordered data.

REPEAT
Lambda List: (RANGE TIMES)
Arguments:
  • RANGE, Input range used to construct the result.
  • TIMES, How many times the range will be repeated? Unlimited by default.

Description: A layer function. Constructs new range from the RANGE. The new range is cyclic and will reset to initial position once the end is reached when calling the CONSUME-FRONT function or after calling TRAVERSE. This happens always by default, and can be limited to a number of times by supplying optional TIMES argument. This function can be therefore used to go over the same range multiple times in a aggregation function.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations:
  • Will raise the TYPE-ERROR when TIMES is not of the type (OR NULL POSITIVE-INTEGER).

LATCH
Lambda List: (RANGE LATCH &REST MORE-LATCHES)
Arguments:
  • RANGE, Primary input range.
  • LATCH, Range with boolean values.
  • MORE-LATCHES, Ranges with boolean values.

Examples: 
(PROVE.TEST:IS '(1 4)
               (CL-DATA-STRUCTURES.ALGORITHMS:TO-LIST
                (CL-DATA-STRUCTURES.ALGORITHMS:LATCH
                 (CL-DATA-STRUCTURES:IOTA-RANGE :FROM 0 :TO 5)
                 (LIST NIL T NIL NIL T))))

Description: Combines primary range with multiple latch ranges. The returned range contains elements picked from the primary range, where, on corresponding positions, each of the latch ranges contains a non-nil value.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
RESTRAIN-SIZE
Lambda List: (RANGE SIZE)
Arguments:
  • RANGE, Input range used to construct the result.
  • SIZE, What should be the limit on the new range?

Description: A layer function. Constructs new range from the RANGE. New range contains a limit on how many times consume-front can be called on it before returning (values nil nil), effectively reducing size of the RANGE.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations:
  • Will raise a TYPE-ERROR when the SIZE is not of the type INTEGER.
  • Will raise ARGUMENT-VALUE-OUT-OF-BOUNDS when the SIZE is negative.

Other Functions

Symbols in the package CL-DATA-STRUCTURES.ALGORITHMS:
CARTESIAN
Lambda List: (FUNCTION RANGE &REST MORE-RANGES)
Arguments:
  • FUNCTION, Function used to combine input ranges.
  • RANGE, First input range.
  • MORE-RANGES, All other ranges.

Description: Combines RANGES into a singular range that contains results of FUNCTION application on cartesian combination of all elements in the input RANGES.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations: Will raise a TYPE-ERROR if any of the RANGES is of a wrong type.
CHAIN
Lambda List: (&REST RANGES)
Examples: 
(PROVE.TEST:IS
 (CL-DATA-STRUCTURES.ALGORITHMS:TO-VECTOR
  (CL-DATA-STRUCTURES.ALGORITHMS:CHAIN '(1 2 3) '(4 5 6)))
 #(1 2 3 4 5 6) :TEST #'EQUALP)

Description: Concatenate multiple ranges into one.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations:
  • Raises TYPE-ERROR if any of the input ranges is not (OR CL:SEQUENCE FUNDAMENTAL-FORWARD-RANGE).

CARTESIAN
Lambda List: (FUNCTION RANGE &REST MORE-RANGES)
Arguments:
  • FUNCTION, Function used to combine input ranges.
  • RANGE, First input range.
  • MORE-RANGES, All other ranges.

Description: Combines RANGES into a singular range that contains results of FUNCTION application on cartesian combination of all elements in the input RANGES.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations: Will raise a TYPE-ERROR if any of the RANGES is of a wrong type.
SHUFFLED-RANGE
Lambda List: (FROM TO)
Arguments:
  • FROM, The lowest integer.
  • TO, The highest integer.

Description: Creates a range of shuffled integers from FROM, to TO.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations:
  • Raises TYPE-ERROR if FROM or TO is not an integer.
  • TO must be equal or greater than FROM, otherwise the incompatible-arguments error is signaled.

ZIP
Lambda List: (FUNCTION RANGE &REST RANGES)
Arguments:
  • FUNCTION, Function used to join contents of the RANGES.
  • RANGES, Input.

Examples: 
(PROVE.TEST:IS
 (CL-DATA-STRUCTURES.ALGORITHMS:TO-VECTOR
  (CL-DATA-STRUCTURES.ALGORITHMS:ZIP #'LIST '(1 2 3) '(4 5 6)))
 #((1 4) (2 5) (3 6)) :TEST #'EQUALP)

Description: Combines multiple ranges into a single range by applying FUNCTION elementwise.
Returns: New fundamental-forward-range instance.
Exceptional situations:
  • Raises TYPE-ERROR if any of the input ranges is not (OR CL:SEQUENCE FUNDAMENTAL-FORWARD-RANGE).
  • Will raise TYPE-ERROR if FUNCTION is not FUNCALLABLE.

Notes: Can be considered to be lazy variant of CL:MAP function called on multiple sequences.
SUMMARY
Lambda List: (RANGE &BODY FUNCTIONS)
Arguments:
  • RANGE, Range to aggregate.
  • FORMS, Description of function invocation in the form of the plist. Key is a label used to identify value in the result range, a value is an aggregation function form (function and the function arguments). The range will be inserted as the first argument in the aggregation function call by default, or in the place of any symbol with name '_' if such symbol is present.

Examples: 
(LET ((RESULT
       (CL-DATA-STRUCTURES.ALGORITHMS:SUMMARY (CL-DATA-STRUCTURES:IOTA-RANGE
                                               :TO 250)
         :MIN
         (ITERATE:ACCUMULATE #'MIN)
         :MAX
         (ITERATE:ACCUMULATE #'MAX))))
  (PROVE.TEST:IS (CL-DATA-STRUCTURES:AT RESULT :MIN) 0)
  (PROVE.TEST:IS (CL-DATA-STRUCTURES:AT RESULT :MAX) 249))

Description: The summary is a macro allowing performance of multiple aggregations in one function call.
Returns: Range of results. Use cl-ds:at with label to extract result of each individual aggregation form.
Notes:
  • Currently, this macro does support only the single stage aggregation functions.
  • This macro expands to %SUMMARY call. Programmer may opt to write %SUMMARY call directly despite extra boilerplate required.
  • Particularly useful when the iteration over the range requires considerable time alone and therefore repeating it should be avoided for efficiency sake.

SHUFFLED-RANGE
Lambda List: (FROM TO)
Arguments:
  • FROM, The lowest integer.
  • TO, The highest integer.

Description: Creates a range of shuffled integers from FROM, to TO.
Returns: FUNDAMENTAL-FORWARD-RANGE instance.
Exceptional situations:
  • Raises TYPE-ERROR if FROM or TO is not an integer.
  • TO must be equal or greater than FROM, otherwise the incompatible-arguments error is signaled.

Variables

Symbols in the package CL-DATA-STRUCTURES.ALGORITHMS:
*CURRENT-KEY*
Description: KEY for the current group when aggregating by the GROUP-BY or PARTITION-IF function.