Changes between Version 9 and Version 10 of ImmutableDataStructuresWortman


Ignore:
Timestamp:
06/18/13 20:15:35 (4 years ago)
Author:
kevinwortman
Comment:

Add imap-update draft 2

Legend:

Unmodified
Added
Removed
Modified
  • ImmutableDataStructuresWortman

    v9 v10  
    519519 
    520520I don't think the imap/IMAP naming conflict is important at all. 
     521 
     522=== Update procedure draft 2 === 
     523 
     524{{{#!scheme 
     525(imap-update map key present-proc absent-proc) 
     526}}} 
     527 
     528A continuation-based universal update procedure. Attempts to find a key {{{key-match}}} equal to {{{key}}} in {{{map}}}, and its associated {{{value}}}. When such a {{{key-match}}} is found, returns the result of calling 
     529{{{#!scheme 
     530(present-proc key-match value replace remove) 
     531}}} 
     532. {{{replace}}} is a procedure such that 
     533{{{#!scheme 
     534(replace new-value) 
     535}}} 
     536returns a new version of {{{map}}} in which the {{{key}}} maps to {{{new-value}}} instead of {{{value}}}. 
     537 
     538{{{remove}}} is a thunk such that 
     539{{{#!scheme 
     540(remove) 
     541}}} 
     542returns a new version of {{{map}}} with no association for {{{key}}}.  
     543 
     544When no such {{{key-match}}} is found, {{{imap-update}}} returns the result of calling 
     545{{{#!scheme 
     546(absent-proc insert) 
     547}}} 
     548. {{{insert}}} is a procedure such that 
     549{{{#!scheme 
     550(insert new-value) 
     551}}} 
     552returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. 
     553 
     554The {{{imap-update}}}, {{{replace}}}, {{{remove}}}, and {{{insert}}} procedures may take O(log n) time each. Thus if {{{present-proc}}} and {{{absent-proc}}} take constant time and call their passed-in continuations at most once (or even a constant number of times), the entire update process takes O(log n) time.