Changes between Version 10 and Version 11 of ImmutableDataStructuresWortman


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

Rearrange absent-proc and present-proc and clarify running times

Legend:

Unmodified
Added
Removed
Modified
  • ImmutableDataStructuresWortman

    v10 v11  
    523523 
    524524{{{#!scheme 
    525 (imap-update map key present-proc absent-proc) 
    526 }}} 
    527  
    528 A 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 
     525(imap-update map key absent-proc present-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 no such {{{key-match}}} is found, returns the result of calling 
     529{{{#!scheme 
     530(absent-proc insert) 
     531}}} 
     532. {{{insert}}} is a procedure such that 
     533{{{#!scheme 
     534(insert new-value) 
     535}}} 
     536returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. 
     537 
     538When {{{key-match}}} exists, returns the result of calling 
    529539{{{#!scheme 
    530540(present-proc key-match value replace remove) 
     
    542552returns a new version of {{{map}}} with no association for {{{key}}}.  
    543553 
    544 When 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 }}} 
    552 returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. 
    553  
    554 The {{{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. 
     554The {{{imap-update}}}, {{{insert}}}, {{{replace}}}, and {{{remove}}} procedures may take O(log n) time each. Thus if {{{absent-proc}}} and {{{present-proc}}} take constant (or even O(log n)) time and call their passed-in continuations at most once (or even any constant number of times), the entire update process takes O(log n) time.