[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Interface view of dictionaries

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 are here. Eventually, the entire history will be moved there, including any new messages.

Lets examine your proposed API for dictionaries, and contrast it with 

On Sat, Oct 25, 2003 at 12:27:54PM -0700, bear wrote:
> (create-*) 

> (*-insert! dict datum key),
*-put dictionary key value

>      ;; fetch is a key lookup.
> (*-fetch dict key),
*-get dict key

> (*-fetch-deleting! dict key)
(define (*-fetch-deleting! dict key)
  (let ([rv (*-get dict key)])
    (*-remove! dict key)

Additionally, fetch-deleting! does not map to many dictionaries, for 
example disk file database, *without* doing the above.

>      ;; get just gets one or more elements without caring which.
> (*-get-one dict)
(*-get-left dict)

> (*-get-one-deleting! dict)
As in [A], with the same caveats.

> (*-get-n dict num)
> (*-get-n-deleting! dict num)
Trivially defined with enumeration.
>      ;; the following two are for functions of the signature
>      ;; (callback dict keyval dataval)
> (*-foreach dict callback)
> (*-foreach! dict callback)
(collection-fold-left dict fold-function)
;; a copy is made of the dict to protect it from side effects
Are you generating a new collection?  Then *-map is the name you want.  
for-each implies iteration over values (which is what the enumerators 
are for).  

>      ;; side effects happen to the dictionary.
> (*-size dict) ;; returns number of datum/key pairs stored
The same.

> (get-iterator dict)   ;; returns an iterator function that
>                       ;; takes a key arg and returns some "next" key,
>                       ;; or takes '() and returns some (arbitrarily
>                       ;; chosen for unordered dictionaries) "first" key.
> (*-nextkey dict) ;; same as function returned from get-iterator
> (*-nextkey dict key) ;; same as returned from the get-iterator func above
> (*-lastkey dict)     ;; same as returned from the get-reversed-iterator func
> (get-reversed-iterator dict)

See Olegs post on the hazards of iterators.

> ;; the following is a test to see whether the "Ordered dictionary"
> ;; interface is also provided. The test for ordered dictionaries could
> ;; be part of the interface for all dictionaries.
> (ordered-dict? dict)
(ordered-collection? dict)

<snip>Efficiency procs
Best left to a separate SRFI.
> Some dictionaries would also provide the "ordered dictionary"
> interface -- which includes
> (create-* <key ordering function>)
(make-* ordering-function)
> (*-fetchfirst dict)  ;; returns 1 entry
(*-get-left dict)

> (*-fetchfirst dict number) ;; returns number entries
[B] Trivially implemented with collection-fold-left

> (*-fetchfirst-deleting! dict)
> (*-fetchfirst-deleting! dict number)
See [A]

> (*-fetchlast dict)
(*-get-right dict)
> (*-fetchlast dict number)
See [B]

> (*-fetchlast-deleting! dict)
> (*-fetchlast-deleting! dict number)
See [A]

> (*-fetchrange dict key1 key2)
Possibly novel, but also implementable with enumeration

> (*-fetch-next-n dict key1 number)
> (*-fetch-next-n-deleting! dict key1 number)
> (*-fetch-prev-n dict key1 number)
> (*-fetch-prev-n-deleting! dict key1 number)
> (*-fetchrange-deleting! dict key1 key2)
Above + [A]

> (*-firstkey dict)
One step in enumeration

> (dictionary? htable) => #t
> (dictionary? pqueue) => #t
> (dictionary? btree) => #t
> (dictionary? olist) => #t
> (dictionary? alyst) => #t
Already exists.

> (ordered-dict? htable) => #f
> (ordered-dict? alyst) => #f
> (ordered-dict? olist) => #t
> (ordered-dict? btree) => #t
> (ordered-dict? pqueue) => #t
(and (dictionary? coll) (ordered-collection? coll))

So, you see, your API is almost *exactly* like the current SRFI apart 
from minor naming variations.  Where it differs, there has been strong 
refutation for that approach.  I must ask, did you *read* the SRFI 


Attachment: pgpfMK6fIOCI3.pgp
Description: PGP signature