Sunday, July 28, 2013

Fairly easy

The prior post had some easy exercises.  This is easy, too.

Every audit record in a repository has a unique serial number (relative to the repository).  We want a way to represent sets of serial numbers.

Exercise 4:  Implement these:

Constructors:
  • bitmap->serial-number-set repository vector-1b
  • range->serial-number-set repository start end
    Start is inclusive, end is exclusive.
  • list->serial-number-set repository list
Selectors and predicates:
  • serial-number-set? object
  • serial-number-set/repository serial-number-set
  • serial-number-set/empty? serial-number-set
  • serial-number-set/equal? left-serial-number-set right-serial-number-set
  • serial-number-set/member? serial-number-set serial-number
  • serial-number-set->bitmap serial-number-set

These return new sets rather than mutate the old ones:
  • serial-number-set/adjoin serial-number-set serial-number
  • serial-number-set/remove serial-number-set serial-number
  • serial-number-set/union left-serial-number-set right-serial-number-set
  • serial-number-set/exclusive-or left-serial-number-set right-serial-number-set
  • serial-number-set/intersection left-serial-number-set right-serial-number-set
Two more:
  • serial-number-set/intersaction? left-serial-number-set right-serial-number-set
    Returns true if the intersection is not empty. Ought to be faster than (serial-number-set/empty? (serial-number/intersection left right))
  • serial-number-set/last-serial-number serial-number-set
    Returns the largest serial number in the set.

We'll use serial numbers and serial-number-sets so we can refer to audit-records and sets of audit-records without needing the records themselves.  We can only get to the records within a transaction, but we can refer to them by serial number outside of a transaction.

No comments: