Changes between Version 5 and Version 6 of BinaryHeapsCowan


Ignore:
Timestamp:
12/06/12 22:06:17 (4 years ago)
Author:
cowan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BinaryHeapsCowan

    v5 v6  
    4949`(heap-for-each `''proc''` `''heap''`)` 
    5050 
    51 Applies ''proc'' to ''heap'' in arbitrary order, discarding the returned values.  Returns an unspecified value.  This operation should be O(N) in the size of the heap. 
     51Applies ''proc'' to each element of ''heap'' in arbitrary order, discarding the returned values.  Returns an unspecified value.  This operation should be O(N) in the size of the heap. 
    5252 
    5353`(heap->list `''heap''`)` 
     
    6161`(list->heap `''<''` `''list''`)` 
    6262 
    63 Returns a newly allocated heap containing the elements of ''list'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap. 
     63Returns a newly allocated heap containing the elements of ''list'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the list. 
    6464 
    6565`(heap->vector `''heap''`)` 
     
    7373`(vector->heap `''<''` `''vector''`)` 
    7474 
    75 Returns a newly allocated heap containing the elements of ''vector'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap. 
     75Returns a newly allocated heap containing the elements of ''vector'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the vector. 
     76 
     77== Queues == 
     78 
     79Queues are mutable ordered collections that can contain any Scheme object.  Objects can be added to or removed from either end of a queue.  They are intended to be a thin veneer over lists.  Queues are disjoint from other types of Scheme objects. 
     80 
     81== Procedures == 
     82 
     83`(make-queue)` 
     84 
     85Returns a newly allocated empty queue. 
     86 
     87`(queue `''element''` ...)` 
     88 
     89Returns a newly allocated queue containing the ''elements''.  This operation should be O(n) in the size of the queue. 
     90 
     91`(copy-queue` ''queue''`)` 
     92 
     93Returns a newly allocated queue containing the elements of ''queue''. 
     94 
     95`(queue? `''obj''`)` 
     96 
     97Returns `#t` if ''obj'' is a queue, and `#f` otherwise. 
     98 
     99`(queue-length `''queue''`)` 
     100 
     101Returns the number of elements in ''queue''. 
     102 
     103'''Issue:''' change the name to `queue-size` or `queue-count`? 
     104 
     105`(queue-member? `''queue''` `''element''`)` 
     106 
     107Returns `#t` if ''element'' is a member of ''queue'' (in the sense of `eqv?`) and `#f` otherwise. 
     108 
     109`(queue-first `''queue''` `''element''`)` 
     110 
     111Returns the first element of the queue.  This operation should be O(1). 
     112 
     113`(queue-last`''queue''` `''element''`)` 
     114 
     115Returns the last element of the queue.  This operation should be O(1). 
     116 
     117`(queue-add-first! `''queue''` `''element''`)` 
     118 
     119Adds ''element'' to the beginning of ''queue''.  Returns an unspecified value.  This operation should be O(1). 
     120 
     121`(queue-add-last! `''queue''` `''element''`)` 
     122 
     123Adds ''element'' to the end of ''queue''.  Returns an unspecified value.  This operation should be O(1). 
     124 
     125`(queue-remove-first! `''queue''`)` 
     126 
     127Removes the first element of the queue and returns it.  This operation should be O(1). 
     128 
     129`(queue-remove-last! `''queue''`)` 
     130 
     131Removes the last element of the queue and returns it.  This operation should be O(1). 
     132 
     133'''Issue:''' Maybe return an unspecified result instead?  Returning the removed value is convenient but contrary to the usual Scheme style. 
     134 
     135`(queue-map `''proc queue''`)` 
     136 
     137Applies ''proc'' to each element of ''queue'' in order and returns a newly allocated queue containing the results.  This operation should be O(N) in the size of the queue. 
     138 
     139`(queue-for-each `''proc''` `''queue''`)` 
     140 
     141Applies ''proc'' to each element of ''queue'' in order, discarding the returned values.  Returns an unspecified value.  This operation should be O(N) in the size of the queue. 
     142 
     143`(queue->list `''queue''`)` 
     144 
     145Returns a list containing the members of ''queue'' in order.  It is an error to mutate the result of this procedure, as it may share storage with the queue.  This operation should be O(N) in the size of the queue. 
     146 
     147``(list->queue `''<''` `''list''`)` 
     148 
     149Returns a newly allocated queue containing the elements of ''list'' in order.  It is an error to mutate ''list'' after calling this procedure, as it may share storage with the queue.  This operation should be O(n) in the size of the heap. 
     150 
     151`(queue->vector `''queue''`)` 
     152 
     153Returns a newly allocated vector containing the elements of ''heap'' in order. 
     154 
     155`(vector->queue`''<''` `''vector''`)` 
     156 
     157Returns a newly allocated queue containing the elements of ''vector'' in order.  This operation should be O(n) in the size of the vector.