330 | | (imap-update set key present-proc absent-proc) |
331 | | }}} |
332 | | |
333 | | A continuation-based universal update procedure. Attempts to find a key {{{key-match}}} equal to {{{key}}} in {{{set}}}. When such a {{{key-match}}} is found, calls |
334 | | {{{#!scheme |
335 | | (present-proc key-match value update remove) |
336 | | }}} |
337 | | which must either tail-call |
338 | | {{{#!scheme |
339 | | (update new-key new-value ret) |
340 | | }}} |
341 | | to replace {{{key}}} with {{{new-key}}} and the corresponding value with {{{new-value}}}, or tail-call |
342 | | {{{#!scheme |
343 | | (remove ret) |
344 | | }}} |
345 | | to remove the assocition from {{{map}}}. In either case {{{ret}}} will be one of the values returned from the enclosing {{{imap-update}}} call. |
346 | | |
347 | | When no such {{{key-match}}} is found, {{{imap-update}}} calls |
348 | | {{{#!scheme |
349 | | (absent-proc insert ignore) |
350 | | }}} |
351 | | which should either tail-call |
352 | | {{{#!scheme |
353 | | (insert new-key value ret) |
354 | | }}} |
355 | | to insert {{{new-key}}} and {{{value}}} into {{{map}}}, or else tail-call |
356 | | {{{#!scheme |
357 | | (ignore ret) |
358 | | }}} |
359 | | to leave {{{map}}} unchanged. Again, {{{ret}}} will be returned from the enclosing {{{imap-update}}} call. |
360 | | |
361 | | In any case, {{{imap-update}}} returns |
362 | | {{{#!scheme |
363 | | (values new-map ret) |
364 | | }}} |
365 | | where {{{new-map}}} is a new map reflecting the indicated modification, if any; and {{{ret}}} is the return value produced by one of the continuations. O(log n) time. |
366 | | |
| 330 | (imap-update map key absent-proc present-proc) |
| 331 | }}} |
| 332 | |
| 333 | A 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 |
| 334 | {{{#!scheme |
| 335 | (absent-proc insert) |
| 336 | }}} |
| 337 | . {{{insert}}} is a procedure such that |
| 338 | {{{#!scheme |
| 339 | (insert new-value) |
| 340 | }}} |
| 341 | returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. |
| 342 | |
| 343 | When {{{key-match}}} exists, returns the result of calling |
| 344 | {{{#!scheme |
| 345 | (present-proc key-match value replace remove) |
| 346 | }}} |
| 347 | . {{{replace}}} is a procedure such that |
| 348 | {{{#!scheme |
| 349 | (replace new-value) |
| 350 | }}} |
| 351 | returns a new version of {{{map}}} in which the {{{key}}} maps to {{{new-value}}} instead of {{{value}}}. |
| 352 | |
| 353 | {{{remove}}} is a thunk such that |
| 354 | {{{#!scheme |
| 355 | (remove) |
| 356 | }}} |
| 357 | returns a new version of {{{map}}} with no association for {{{key}}}. |
| 358 | |
| 359 | The {{{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. |
511 | | |
512 | | === Update procedure draft 2 === |
513 | | |
514 | | {{{#!scheme |
515 | | (imap-update map key absent-proc present-proc) |
516 | | }}} |
517 | | |
518 | | A 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 |
519 | | {{{#!scheme |
520 | | (absent-proc insert) |
521 | | }}} |
522 | | . {{{insert}}} is a procedure such that |
523 | | {{{#!scheme |
524 | | (insert new-value) |
525 | | }}} |
526 | | returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. |
527 | | |
528 | | When {{{key-match}}} exists, 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 | | }}} |
536 | | returns 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 | | }}} |
542 | | returns a new version of {{{map}}} with no association for {{{key}}}. |
543 | | |
544 | | The {{{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. |