From 0559473fbfc28f5b05a9a23402dad28865c46231 Mon Sep 17 00:00:00 2001 From: David Thompson Date: Sat, 2 Oct 2021 07:58:32 -0400 Subject: doc: Add API docs for array lists, heaps, and queues. --- doc/api.texi | 152 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 150 insertions(+), 2 deletions(-) (limited to 'doc') diff --git a/doc/api.texi b/doc/api.texi index e79cca1..87ff7cd 100644 --- a/doc/api.texi +++ b/doc/api.texi @@ -1,10 +1,10 @@ @menu * Kernel:: The fundamental components. -* Math:: Linear algebra, spatial partitioning, and more. +* Math:: Vectors, matrices, bounding boxes, and more. * Graphics:: 2D and 3D rendering. * Audio:: Make some noise. * Scripting:: Bringing the game world to life. -* Data Structures:: Spatial partitioning and more. +* Data Structures:: Queues, heaps, spatial partitioning, and more. @end menu @node Kernel @@ -5210,11 +5210,159 @@ Clear all messages and scripts awaiting messages in @var{channel}. @section Data Structures @menu +* Array Lists:: Dynamically expanding vectors. +* Queues:: First-in, first-out data structure. +* Heaps:: Binary heaps. * Quadtrees:: Spatial partitioning with recursive subdivision. * Grids:: Spatial partitioning with a fixed grid. * Path Finding:: Generic A* path finding. @end menu +@node Array Lists +@subsection Array Lists + +The @code{(chickadee data array-list)} module provides an array/vector +that dynamically expands to hold all of the data that is added to it. +It is named after the @code{ArrayList} class in Java. + +In addition to being used as a dynamic vector, it can also be used as +a stack via the @code{array-list-push!} and @var{array-list-pop!} +procedures. + +@deffn {Procedure} make-array-list [initial-capacity] +Return a new empty array list with an initial capacity of +@var{initial-capacity}, or 32 by default. +@end deffn + +@deffn {Procedure} array-list items ... +Return a new array list with @var{items} in it. +@end deffn + +@deffn {Procedure} array-list? obj +Return @code{#t} if @var{obj} is an array list. +@end deffn + +@deffn {Procedure} array-list-empty? array-list +Return @code{#t} if @var{array-list} is empty. +@end deffn + +@deffn {Procedure} array-list-size array-list +Return the current size of @var{array-list}. +@end deffn + +@deffn {Procedure} array-list-ref array-list i +Return the item in @var{array-list} at index @var{i}. +@end deffn + +@deffn {Procedure} array-list-set! array-list i value +Set the value in @var{array-list} at index @var{i} to @var{value}. +@end deffn + +@deffn {Procedure} array-list-push! array-list item +Append @var{item} to @var{array-list}. +@end deffn + +@deffn {Procedure} array-list-pop! array-list +Remove and return the last object in @var{array-list}. +@end deffn + +@deffn {Procedure} array-list-delete! array-list item [#:equal? equal?] [#:fast? #f] +Delete @var{item} from @var{array-list}. Use @var{equal?} as the +equivalence predicate, which defaults to Guile's @code{equal?} +procedure. By default, deletion preserves the order of the array, but +takes linear time in the worst case. If @var{fast?} is @code{#t} then +@var{item} will deleted in constant time, but order is not preserved. +@end deffn + +@deffn {Procedure} array-list-clear! array-list +Remove all items from @var{array-list}. +@end deffn + +@deffn {Procedure} array-list-for-each proc array-list +Apply PROC with each item in @var{array-list}. +@end deffn + +@deffn {Procedure} array-list-fold proc init array-list +Apply @var{proc} to all items in @var{array-list} to build a result and +return that result. @var{init} is the initial result. If there are +no objects in the vicinity of @var{rect}, just @var{init} is returned. +@end deffn + +@node Queues +@subsection Queues + +The @code{(chickadee data queue)} module provides a mutable queue that +is more memory efficient than Guile's built-in @code{(ice-9 q)} +module. + +@deffn {Procedure} make-queue +Return a new, empty queue. +@end deffn + +@deffn {Procedure} queue? obj +Return @code{#t} if @var{obj} is a queue. +@end deffn + +@deffn {Procedure} queue-empty? queue +Return @code{#t} if @var{queue} is empty. +@end deffn + +@deffn {Procedure} queue-length queue +Return the current length of @var{queue}. +@end deffn + +@deffn {Procedure} enqueue! queue item +Add @var{item} to @var{queue}. +@end deffn + +@deffn {Procedure} dequeue! queue +Remove and return the first item in @var{queue}. +@end deffn + +@deffn {Procedure} queue-clear! queue +Remove all items from @var{queue}. +@end deffn + +@node Heaps +@subsection Heaps + +The @code{(chickadee data heap)} module provides a binary heap data +structure. The heap orders data from smallest to largest, according +to a custom comparison predicate, making it a good choice for priority +queues. + +@deffn {Procedure} make-heap [#:< <] +Return a new heap that uses the predicate @var{<} to determine order. +@end deffn + +@deffn {Procedure} heap? obj +Return @code{#t} if @var{obj} is a heap. +@end deffn + +@deffn {Procedure} heap-empty? heap +Return @code{#t} if @var{heap} is empty. +@end deffn + +@deffn {Procedure} heap-size heap +Return the current size of @var{heap}. +@end deffn + +@deffn {Procedure} heap-min heap +Return the minimum item in @var{heap}. +@end deffn + +@deffn {Procedure} heap-insert! heap item +Add @var{item} to @var{heap}. +@end deffn + +@deffn {Procedure} heap-remove! heap +Remove the minimum item in @var{heap}. +@end deffn + +@deffn {Procedure} heap-clear! heap +Remove all items from @var{heap}. +@end deffn + @node Quadtrees @subsection Quadtrees -- cgit v1.2.3