▼Data:   Data Structures
On this page:
make-integer-set
integer-set-contents
set-integer-set-contents!
integer-set?
well-formed-set?
make-range
intersect
subtract
union
split
complement
symmetric-difference
member?
get-integer
foldr
partition
count
subset?
8.8
  top  contents  ← prev  up  next → 

8 Integer Sets

 (require data/integer-set) package: base

This library provides functions for working with finite sets of integers. This module is designed for sets that are compactly represented as groups of intervals, even when their cardinality is large. For example, the set of integers from -1000000 to 1000000 except for 0, can be represented as {[-1000000, -1], [1, 1000000]}. This data structure would not be a good choice for the set of all odd integers between 0 and 1000000, which would be {[1, 1], [3, 3], ... [999999, 999999]}.

In addition to the integer set abstract type, a well-formed set is a list of pairs of exact integers, where each pair represents a closed range of integers, and the entire set is the union of the ranges. The ranges must be disjoint and increasing. Further, adjacent ranges must have at least one integer between them. For example: '((-1 . 2) (4 . 10)) is a well-formed-set as is '((1 . 1) (3 . 3)), but '((1 . 5) (6 . 7)), '((1 . 5) (-3 . -1)), '((5 . 1)), and '((1 . 5) (3 . 6)) are not.

An integer set implements the stream and sequence generic interfaces.

Example:
> (for/list ([i (make-integer-set '((2 . 3)
                                    (5 . 6)
                                    (10 . 15)))])
    i)

'(2 3 5 6 10 11 12 13 14 15)

procedure

(make-integer-set wfs) → integer-set?

  wfs : well-formed-set?
Creates an integer set from a well-formed set.

procedure

(integer-set-contents s) → well-formed-set?

  s : integer-set?
Produces a well-formed set from an integer set.

procedure

(set-integer-set-contents! s wfs) → void?

  s : integer-set?
  wfs : well-formed-set?
Mutates an integer set.

procedure

(integer-set? v) → boolean?

  v : any/c
Returns #t if v is an integer set, #f otherwise.

procedure

(well-formed-set? v) → boolean?

  v : any/c
Recognizes (listof (cons/c exact-integer? exact-integer?)), where the result of (flatten v) is sorted by <=, the elements of the pairs in the list are distinct (and thus strictly increasing), and the second element in a pair is at least one less than the first element of the subsequent pair.

Examples:
> (well-formed-set? '((-1 . 2) (4 . 10)))

#t

> (well-formed-set? '((1 . 1) (3 . 3)))

#t

> (well-formed-set? '((1 . 5) (6 . 7)))

#f

> (well-formed-set? '((1 . 5) (-3 . -1)))

#f

> (well-formed-set? '((5 . 1)))

#f

> (well-formed-set? '((1 . 5) (3 . 6)))

#f

procedure

(make-range) → integer-set?

(make-range elem) → integer-set?
  elem : exact-integer?
(make-range start end) → integer-set?
  start : exact-integer?
  end : exact-integer?
Produces, respectively, an empty integer set, an integer set containing only elem, or an integer set containing the integers from start to end inclusive, where (<= start end).

procedure

(intersect x y) → integer-set?

  x : integer-set?
  y : integer-set?
Returns the intersection of the given sets.

procedure

(subtract x y) → integer-set?

  x : integer-set?
  y : integer-set?
Returns the difference of the given sets (i.e., elements in x that are not in y).

procedure

(union x y) → integer-set?

  x : integer-set?
  y : integer-set?
Returns the union of the given sets.

procedure

(split x y) → 
integer-set? integer-set? integer-set?
  x : integer-set?
  y : integer-set?
Produces three values: the first is the intersection of x and y, the second is the difference x remove y, and the third is the difference y remove x.

procedure

(complement s start end) → integer-set?

  s : integer-set?
  start : exact-integer?
  end : exact-integer?
Returns a set containing the elements between start to end inclusive that are not in s, where (<= start-k end-k).

procedure

(symmetric-difference x y) → integer-set?

  x : integer-set?
  y : integer-set?
Returns an integer set containing every member of x and y that is not in both sets.

procedure

(member? k s) → boolean?

  k : exact-integer?
  s : integer-set?
Returns #t if k is in s, #f otherwise.

procedure

(get-integer set) → (or/c exact-integer? #f)

  set : integer-set?
Returns a member of set, or #f if set is empty.

procedure

(foldr proc base-v s) → any/c

  proc : (exact-integer? any/c . -> . any/c)
  base-v : any/c
  s : integer-set?
Applies proc to each member of s in ascending order, where the first argument to proc is the set member, and the second argument is the fold result starting with base-v. For example, (foldr cons null s) returns a list of all the integers in s, sorted in increasing order.

procedure

(partition s) → (listof integer-set?)

  s : (listof integer-set?)
Returns the coarsest refinement of the sets in s such that the sets in the result list are pairwise disjoint. For example, partitioning the sets that represent '((1 . 2) (5 . 10)) and '((2 . 2) (6 . 6) (12 . 12)) produces the a list containing the sets for '((1 . 1) (5 . 5) (7 . 10)) '((2 . 2) (6 . 6)), and '((12 . 12)).

procedure

(count s) → exact-nonnegative-integer?

  s : integer-set?
Returns the number of integers in the given integer set.

procedure

(subset? x y) → boolean?

  x : integer-set?
  y : integer-set?
Returns true if every integer in x is also in y, otherwise #f.

  top  contents  ← prev  up  next →