The track-best Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The track-best Reference Manual

This is the track-best Reference Manual, version 0.1.20130509, generated automatically by Declt version 2.3 "Robert April" on Tue Jan 09 15:53:29 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Track-Best Library

Track-Best is a Common Lisp library used to track the N best of some series of items. One creates a tracker and then adds scored items to it. The tracker keeps the N best items and returns them at the end.

The main entry point is the function WITH-TRACK-BEST macro.

(with-track-best (keyword-args)
   ...body...)

The body can call (track item score &optional tracker) as often as desired. In the end, the with-track-best will return two values: the list of best items and the list of their scores.

The keyword-args can be any of the following:

Example: Finding the longest matching substring in two strings

Given two strings S1 and S2, find the longest substring they have in common.

(let ((s1 "Keep playing cards on Friday.  Get smart.")
      (s2 "Thank G-d it's Friday!"))
  (with-track-best ()
    (dotimes (len (length s1))
      (dotimes (offset (- (length s1) len -1))
        (let ((needle (subseq s1 offset (+ offset len))))
          (when (search needle s2 :test #'string=)
            (track needle len)))))))

The outer DOTIMES loop determines the length substring of S1 to look for in S2. The inner DOTIMES loop picks the offset to start the substring of S1. Then, if the substring is found in S2, it is tracked with its score being its length.

Example: Finding the farthest vertex from a point

Given a list of vertexes VERTEX-LIST, find the vertex farthest from a TARGET vertex based on a given DISTANCE function.

(defun find-farthest (target vertex-list distance-fn)
  (with-track-best ()
    (dolist (v vertex-list)
      (track v (funcall distance-fn v target))))))

Example: Finding the three closest vertexes to a point

Given a list of vertexes VERTEX-LIST, find the three that are closest to a TARGET vertex based on a given DISTANCE function.

(defun find-three-closest (target vertex-list distance-fn)
  (with-track-best (:keep 3 :order-by-fn #'<)
    (dolist (v vertex-list)
      (track v (funcall distance-fn v target))))))

The :ORDER-BY-FN function here specifies that the best vectors are the ones with the smallest score. The scores used here are the distance from the TARGET as given by the DISTANCE-FN.

Example: The lowest highest point

Suppose you had a list of various states. For each state you had a list of different cities and their altitude. Find the highest altitude in each state and find the state with the lowest high.

(let ((data '(("Alabama"  ("Birmingham" 664)
                          ("Mobile" 218)
                          ("Montegomery" 221))
              ("Alaska"   ("Anchorage" 144)
                          ("Fairbanks" 531))
              ("Arizona"  ("Grand Canyon" 6606)
                          ("Phoenix" 1132)
                          ("Tuscon"  2641)))))
  (with-track-best (:order-by-fn #'<)
    (dolist (state-info data)
      (multiple-value-bind (city altitude)
          (with-track-best ()
            (dolist (city-info (rest state-info))
              (track (first city-info) (second city-info))))
        (track (list (first state-info) city) altitude)))))

 => (values '("Alaska" "Fairbanks") 531)

The inner DOLIST here tracks the highest city in a given state. The outer DOLIST trackes the lowest of the highest cities.

Example: Finding the lowest and highest numbers in a list

Given a list of numbers, return a list containing the lowest number and highest number from the list.

(with-track-best (:name lowest
                  :order-by-fn #'<
                  :return-best nil)
  (with-track-best (:name highest
                    :return-best nil)
    (dolist (v '(2 4 6 8 10 1 3 5 7 9))
      (track v v lowest)
      (track v v highest))

    (list (first (map-best #'cons lowest))
          (first (map-best #'cons highest)))))

In this example, we used the :NAME to specify two different trackers. In our loop, we tracked each value with both trackers. In the end, we also used the :RETURN-RESULTS NIL directive so that the returned value would be our LIST expression rather than the best result from the LOWEST tracker.

Warning about how ties are handled

If the :KEEP parameter is 1, the first item tracked with the best score will be returned. If the :KEEP parameter is greater than one, there is no guarantee about which items are kept when multiple items of the same score are found. For example, the following form will definitely return (VALUES :EIGHT 8).

(with-track-best ()
  (dolist (c '((:FIVE 5)  (:EIGHT 8)
               (:CINQO 5) (:OCHO 8)
               (:CINQ 5)  (:HUIT 8)))
    (track (first c) (second c))))

=> (values :EIGHT 8)

On the other hand, this snippet will not guarantee the order in which :EIGHT, :OCHO, and :HUIT appear nor which of :FIVE, :CINQO, or :CINQ will be included.

(with-track-best (:keep 4)
  (dolist (c '((:FIVE 5)  (:EIGHT 8)
               (:CINQO 5) (:OCHO 8)
               (:CINQ 5)  (:HUIT 8)))
    (track (first c) (second c))))

=> (values ??? '(8 8 8 5))

To be sure, the answer is deterministic. Given the same inputs in the same order, the same output will be generated. There are two caveats to this:


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 track-best

Author

Patrick Stein <pat@nklein.com>

License

Free

Description

Macros/functions for tracking the best items. See the README.md for more details.

Version

0.1.20130509

Source

track-best.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Modules

Modules are listed depth-first from the system components tree.


Previous: , Up: Modules   [Contents][Index]

3.1 track-best/src

Parent

track-best (system)

Location

src/

Components

Next: , Previous: , Up: Top   [Contents][Index]

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Next: , Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 track-best.asd

Location

track-best.asd

Systems

track-best (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.2 track-best/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

track-best


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.3 track-best/src/types.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/types.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.4 track-best/src/globals.lisp

Dependency

types.lisp (file)

Parent

src (module)

Location

src/globals.lisp

Internal Definitions

*current-best-tracker* (special variable)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.5 track-best/src/insert.lisp

Dependency

globals.lisp (file)

Parent

src (module)

Location

src/insert.lisp

Internal Definitions

insert-tracked-item (function)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.6 track-best/src/methods.lisp

Dependency

insert.lisp (file)

Parent

src (module)

Location

src/methods.lisp

Exported Definitions

Previous: , Up: Lisp files   [Contents][Index]

4.1.7 track-best/src/track-best.lisp

Dependency

methods.lisp (file)

Parent

src (module)

Location

src/track-best.lisp

Exported Definitions

with-track-best (macro)


Previous: , Up: Files   [Contents][Index]

4.2 Other


Previous: , Up: Other files   [Contents][Index]

4.2.1 track-best/README.md

Parent

track-best (system)

Location

README.md


Next: , Previous: , Up: Top   [Contents][Index]

5 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

5.1 track-best

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 Macros

Macro: with-track-best (&key NAME KEEP ORDER-BY-FN ALWAYS-RETURN-LIST RETURN-BEST) &body BODY
Package

track-best

Source

track-best.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

6.1.2 Functions

Function: map-best FN &optional TRACKER
Package

track-best

Source

methods.lisp (file)

Function: track ITEM SCORE &optional TRACKER

Add the ITEM with SCORE to the TRACKER.

Package

track-best

Source

methods.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.1 Special variables

Special Variable: *current-best-tracker*

The current best-tracker instance.

Package

track-best

Source

globals.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Functions

Function: best-item-item INSTANCE
Package

track-best

Source

types.lisp (file)

Function: best-item-p OBJECT
Package

track-best

Source

types.lisp (file)

Function: best-item-score INSTANCE
Package

track-best

Source

types.lisp (file)

Function: best-tracker-best INSTANCE
Function: (setf best-tracker-best) VALUE INSTANCE
Package

track-best

Source

types.lisp (file)

Function: best-tracker-keep INSTANCE
Package

track-best

Source

types.lisp (file)

Function: best-tracker-order-by-fn INSTANCE
Package

track-best

Source

types.lisp (file)

Function: best-tracker-p OBJECT
Package

track-best

Source

types.lisp (file)

Function: copy-best-item INSTANCE
Package

track-best

Source

types.lisp (file)

Function: copy-best-tracker INSTANCE
Package

track-best

Source

types.lisp (file)

Function: insert-tracked-item TRACKER ITEM &optional ALWAYS

Insert the ITEM into the TRACKER. If ALWAYS is true, then do it even though it is not bigger than the last thing in the array.

Package

track-best

Source

insert.lisp (file)

Function: make-best-item &key (SCORE SCORE) (ITEM ITEM)
Package

track-best

Source

types.lisp (file)

Function: make-best-tracker &key (BEST BEST) (KEEP KEEP) (ORDER-BY-FN ORDER-BY-FN)
Package

track-best

Source

types.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.3 Structures

Structure: best-item ()
Package

track-best

Source

types.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: score
Initform

0.0

Readers

best-item-score (function)

Writers

(setf best-item-score) (function)

Slot: item
Readers

best-item-item (function)

Writers

(setf best-item-item) (function)

Structure: best-tracker ()
Package

track-best

Source

types.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: best
Type

track-best::best-item-array

Initform

(make-array 0 :element-type (quote track-best::best-item) :adjustable t)

Readers

best-tracker-best (function)

Writers

(setf best-tracker-best) (function)

Slot: keep
Initform

1

Readers

best-tracker-keep (function)

Writers

(setf best-tracker-keep) (function)

Slot: order-by-fn
Type

track-best::order-by-fn

Initform

(function >)

Readers

best-tracker-order-by-fn (function)

Writers

(setf best-tracker-order-by-fn) (function)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.4 Types

Type: best-item-array &optional LENGTH

Type for an array of BEST-ITEM instances.

Package

track-best

Source

types.lisp (file)

Type: order-by-fn ()
Package

track-best

Source

types.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   M   O   T  
Index Entry  Section

F
File, Lisp, track-best.asd: The track-best<dot>asd file
File, Lisp, track-best/src/globals.lisp: The track-best/src/globals<dot>lisp file
File, Lisp, track-best/src/insert.lisp: The track-best/src/insert<dot>lisp file
File, Lisp, track-best/src/methods.lisp: The track-best/src/methods<dot>lisp file
File, Lisp, track-best/src/package.lisp: The track-best/src/package<dot>lisp file
File, Lisp, track-best/src/track-best.lisp: The track-best/src/track-best<dot>lisp file
File, Lisp, track-best/src/types.lisp: The track-best/src/types<dot>lisp file
File, other, track-best/README.md: The track-best/readme<dot>md file

L
Lisp File, track-best.asd: The track-best<dot>asd file
Lisp File, track-best/src/globals.lisp: The track-best/src/globals<dot>lisp file
Lisp File, track-best/src/insert.lisp: The track-best/src/insert<dot>lisp file
Lisp File, track-best/src/methods.lisp: The track-best/src/methods<dot>lisp file
Lisp File, track-best/src/package.lisp: The track-best/src/package<dot>lisp file
Lisp File, track-best/src/track-best.lisp: The track-best/src/track-best<dot>lisp file
Lisp File, track-best/src/types.lisp: The track-best/src/types<dot>lisp file

M
Module, track-best/src: The track-best/src module

O
Other File, track-best/README.md: The track-best/readme<dot>md file

T
track-best.asd: The track-best<dot>asd file
track-best/README.md: The track-best/readme<dot>md file
track-best/src: The track-best/src module
track-best/src/globals.lisp: The track-best/src/globals<dot>lisp file
track-best/src/insert.lisp: The track-best/src/insert<dot>lisp file
track-best/src/methods.lisp: The track-best/src/methods<dot>lisp file
track-best/src/package.lisp: The track-best/src/package<dot>lisp file
track-best/src/track-best.lisp: The track-best/src/track-best<dot>lisp file
track-best/src/types.lisp: The track-best/src/types<dot>lisp file

Jump to:   F   L   M   O   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
B   C   F   I   M   T   W  
Index Entry  Section

(
(setf best-tracker-best): Internal functions

B
best-item-item: Internal functions
best-item-p: Internal functions
best-item-score: Internal functions
best-tracker-best: Internal functions
best-tracker-keep: Internal functions
best-tracker-order-by-fn: Internal functions
best-tracker-p: Internal functions

C
copy-best-item: Internal functions
copy-best-tracker: Internal functions

F
Function, (setf best-tracker-best): Internal functions
Function, best-item-item: Internal functions
Function, best-item-p: Internal functions
Function, best-item-score: Internal functions
Function, best-tracker-best: Internal functions
Function, best-tracker-keep: Internal functions
Function, best-tracker-order-by-fn: Internal functions
Function, best-tracker-p: Internal functions
Function, copy-best-item: Internal functions
Function, copy-best-tracker: Internal functions
Function, insert-tracked-item: Internal functions
Function, make-best-item: Internal functions
Function, make-best-tracker: Internal functions
Function, map-best: Exported functions
Function, track: Exported functions

I
insert-tracked-item: Internal functions

M
Macro, with-track-best: Exported macros
make-best-item: Internal functions
make-best-tracker: Internal functions
map-best: Exported functions

T
track: Exported functions

W
with-track-best: Exported macros

Jump to:   (  
B   C   F   I   M   T   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
B   I   K   O   S  
Index Entry  Section

*
*current-best-tracker*: Internal special variables

B
best: Internal structures

I
item: Internal structures

K
keep: Internal structures

O
order-by-fn: Internal structures

S
score: Internal structures
Slot, best: Internal structures
Slot, item: Internal structures
Slot, keep: Internal structures
Slot, order-by-fn: Internal structures
Slot, score: Internal structures
Special Variable, *current-best-tracker*: Internal special variables

Jump to:   *  
B   I   K   O   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   B   O   P   S   T  
Index Entry  Section

B
best-item: Internal structures
best-item-array: Internal types
best-tracker: Internal structures

O
order-by-fn: Internal types

P
Package, track-best: The track-best package

S
Structure, best-item: Internal structures
Structure, best-tracker: Internal structures
System, track-best: The track-best system

T
track-best: The track-best system
track-best: The track-best package
Type, best-item-array: Internal types
Type, order-by-fn: Internal types

Jump to:   B   O   P   S   T