source: project/wiki/eggref/5/srfi-117 @ 36364

Last change on this file since 36364 was 36364, checked in by Jeremy Steward, 20 months ago

Adds C5 wiki page for srfi-117

File size: 9.1 KB
Line 
1== SRFI-117: Queues based on lists
2
3List queues are mutable ordered collections that can contain any Scheme object.
4Each list queue is based on an ordinary Scheme list containing the elements of
5the list queue by maintaining pointers to the first and last pairs of the list.
6It's cheap to add or remove elements from the front of the list or to add
7elements to the back, but not to remove elements from the back. List queues are
8disjoint from other types of Scheme objects.
9
10[[toc:]]
11
12== Installation
13
14 $ chicken-install srfi-117
15
16or
17
18 $ chicken-install srfi-117 -test
19
20if you want to run the tests for the egg in addition.
21
22== SRFI Description
23
24For a full description of this SRFI, see the full SRFI
25[[http://srfi.schemers.org/srfi-117/srfi-117.html|document]]. This
26documentation covers the API only.
27
28== List Queues
29
30=== Constructors
31
32<procedure>(make-list-queue list [last])</procedure>
33
34Returns a newly allocated list queue containing the elements of {{list}} in
35order.  The result shares storage with {{list}}. If the last argument is not
36provided, this operation is O(n) where n is the length of {{list}}.
37
38However, if last is provided, {{make-list-queue}} returns a newly allocated
39list queue containing the elements of the {{list}} whose first pair is first
40and whose last pair is last. It is an error if the pairs do not belong to the
41same list. Alternatively, both first and last can be the empty list. In either
42case, the operation is O(1).
43
44'''Note:''' To apply a non-destructive list procedure to a list queue and return a
45new list queue, use {{(make-list-queue (proc (list-queue-list list-queue)))}}.
46
47<procedure>(list-queue element ...)</procedure>
48
49Returns a newly allocated list queue containing the {{elements}}. This
50operation is O(n) where n is the number of elements.
51
52<procedure>(list-queue-copy list-queue)</procedure>
53
54Returns a newly allocated list queue containing the elements of {{list-queue}}.
55This operation is O(n) where n is the length of {{list-queue}}.
56
57<procedure>(list-queue-unfold stop? mapper successor seed [queue])</procedure>
58
59Performs the following algorithm:
60
61If the result of applying the predicate {{stop?}} to {{seed}} is true, return
62{{queue}}.  Otherwise, apply the procedure {{mapper}} to {{seed}}, returning a
63value which is added to the front of {{queue}}. Then get a new seed by applying
64the procedure {{successor}} to {{seed}}, and repeat this algorithm.
65
66If {{queue}} is omitted, a newly allocated list queue is used.
67
68<procedure>(list-queue-unfold-right stop? mapper successor seed [queue])</procedure>
69
70Performs the following algorithm:
71
72If the result of applying the predicate {{stop?}} to {{seed}} is true, return
73the list queue. Otherwise, apply the procedure {{mapper}} to {{seed}},
74returning a value which is added to the back of the list queue. Then get a new
75seed by applying the procedure {{successor}} to {{seed}}, and repeat this
76algorithm.
77
78If {{queue}} is omitted, a newly allocated list queue is used.
79
80=== Predicates
81
82<procedure>(list-queue? obj)</procedure>
83
84Returns {{#t}} if {{obj}} is a list queue, and {{#f}} otherwise. This operation
85is O(1).
86
87<procedure>(list-queue-empty? list-queue)</procedure>
88
89Returns {{#t}} if {{list-queue}} has no elements, and {{#f}} otherwise. This
90operation is O(1).
91
92=== Accessors
93
94<procedure>(list-queue-front list-queue)</procedure>
95
96Returns the first element of {{list-queue}}. If the list queue is empty, it is
97an error. This operation is O(1).
98
99<procedure>(list-queue-back list-queue)</procedure>
100
101Returns the last element of {{list-queue}}. If the list queue is empty, it is
102an error. This operation is O(1).
103
104<procedure>(list-queue-list list-queue)</procedure>
105
106Returns the list that contains the members of {{list-queue}} in order. The
107result shares storage with {{list-queue}}. This operation is O(1).
108
109<procedure>(list-queue-first-last list-queue)</procedure>
110
111Returns two values, the first and last pairs of the list that contains the
112members of {{list-queue}} in order. If {{list-queue}} is empty, returns two
113empty lists. The results share storage with {{list-queue}}. This operation is
114O(1).
115
116=== Mutators
117
118<procedure>(list-queue-add-front! list-queue element)</procedure>
119
120Adds element to the beginning of {{list-queue}}. Returns an unspecified value.
121This operation is O(1).
122
123<procedure>(list-queue-add-back! list-queue element)</procedure>
124
125Adds element to the end of {{list-queue}}. Returns an unspecified value. This
126operation is O(1).
127
128<procedure>(list-queue-remove-front! list-queue)</procedure>
129
130Removes the first element of {{list-queue}} and returns it. If the list queue
131is empty, it is an error. This operation is O(1).
132
133<procedure>(list-queue-remove-back! list-queue)</procedure>
134
135Removes the last element of {{list-queue}} and returns it. If the list queue is
136empty, it is an error. This operation is O(n) where n is the length of
137{{list-queue}}, because queues do not not have backward links.
138
139<procedure>(list-queue-remove-all! list-queue)</procedure>
140
141Removes all the elements of {{list-queue}} and returns them in order as a list.
142This operation is O(1).
143
144<procedure>(list-queue-set-list! list-queue list [last])</procedure>
145
146Replaces the list associated with {{list-queue}} with {{list}}, effectively
147discarding all the elements of {{list-queue}} in favor of those in {{list}}.
148Returns an unspecified value. This operation is O(n) where n is the length of
149{{list}}. If {{last}} is provided, it is treated in the same way as in
150{{make-list-queue}}, and the operation is O(1).
151
152'''Note:''' To apply a destructive list procedure to a list queue, use
153{{(list-queue-set-list! (proc (list-queue-list list-queue)))}}.
154
155<procedure>(list-queue-append list-queue ...)</procedure>
156
157Returns a list queue which contains all the elements in front-to-back order
158from all the {{list-queues}} in front-to-back order. The result does not share
159storage with any of the arguments. This operation is O(n) in the total number
160of elements in all queues.
161
162<procedure>(list-queue-append! list-queue ...)</procedure>
163
164Returns a list queue which contains all the elements in front-to-back order
165from all the {{list-queue}}s in front-to-back order. It is an error to assume
166anything about the contents of the {{list-queue}}s after the procedure returns.
167This operation is O(n) in the total number of queues, not elements. It is not
168part of the R7RS-small list API, but is included here for efficiency when pure
169functional append is not required.
170
171<procedure>(list-queue-concatenate list-of-list-queues)</procedure>
172
173Returns a list queue which contains all the elements in front-to-back order
174from all the list queues which are members of {{list-of-list-queues}} in
175front-to-back order. The result does not share storage with any of the
176arguments. This operation is O(n) in the total number of elements in all
177queues. It is not part of the R7RS-small list API, but is included here to make
178appending a large number of queues possible in Schemes that limit the number of
179arguments to apply.
180
181=== Mapping
182
183<procedure>(list-queue-map proc list-queue)</procedure>
184
185Applies {{proc}} to each element of {{list-queue}} in unspecified order and
186returns a newly allocated list queue containing the results. This operation is
187O(n) where n is the length of {{list-queue}}.
188
189<procedure>(list-queue-map! proc list-queue)</procedure>
190
191Applies {{proc}} to each element of {{list-queue}} in front-to-back order and
192modifies {{list-queue}} to contain the results. This operation is O(n) in the
193length of {{list-queue}}. It is not part of the R7RS-small list API, but is
194included here to make transformation of a list queue by mutation more
195efficient.
196
197<procedure>(list-queue-for-each proc list-queue)</procedure>
198
199Applies {{proc}} to each element of {{list-queue}} in front-to-back order,
200discarding the returned values. Returns an unspecified value. This operation is
201O(n) where n is the length of {{list-queue}}.
202
203== Repository
204
205[[https://github.com/ThatGeoGuy/srfi-117|Github]]
206
207== Version History
208
209; 1.4 : Fixes egg synopsis for C5
210; 1.3 : Adds CHICKEN 5 support
211; 1.2 : Adds standard README.org to SRFI and fixes hardcoded .so in setup
212; 1.1 : Packages egg without extraneous files
213; 1.0 : Initial release
214
215== License
216
217Copyright (C) John Cowan (2014-2016). All Rights Reserved.
218
219Permission is hereby granted, free of charge, to any person obtaining a copy of
220this software and associated documentation files (the "Software"), to deal in
221the Software without restriction, including without limitation the rights to
222use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
223of the Software, and to permit persons to whom the Software is furnished to do
224so, subject to the following conditions:
225
226The above copyright notice and this permission notice shall be included in all
227copies or substantial portions of the Software.
228
229THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
230IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
231FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
232AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
233LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
234OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
235SOFTWARE.
Note: See TracBrowser for help on using the repository browser.