Module intervals

Interval data structure and handling functions.

Copyright © 2007-2014 Zuse Institute Berlin

Version: $Id$

Authors: Thorsten Schuett (schuett@zib.de), Florian Schintke (schintke@zib.de), Nico Kruber (kruber@zib.de).

Description

Interval data structure and handling functions.

All intervals created by methods of this module are normalized, i.e. simple intervals having unambiguous representations and complex intervals being lists of simple intervals sorted by the order given by interval_sort/2. Such a list contains no adjacent intervals except for those wrapping around, i.e. the first and the last element of the list. This representation is thus unambiguous as well.

Data Types

continuous_interval()

continuous_interval() = interval()

interval()

interval() = [simple_interval()]

[] -> empty interval [simple_interval(),...] -> union of the simple intervals

invalid_interval()

abstract datatype: invalid_interval()

invalid_simple_interval()

invalid_simple_interval() = {key()} | all | simple_interval2()

key()

key() = rt_chord:key() | 0

?MINUS_INFINITY_TYPE unnecessary (should be included in ?RT:key()) but needed for fewer dialyzer warnings

left_bracket()

left_bracket() = '(' | '['

non_empty_interval()

non_empty_interval() = interval()

right_bracket()

right_bracket() = ')' | ']'

simple_interval()

simple_interval() = {key()}
                  | {left_bracket(),
                     key(),
                     key(),
                     right_bracket()}
                  | {left_bracket(), key(), PLUS_INFINITY, ')'}
                  | all

{term()} -> one element interval {'[', A::term(), B::term(), ']'} -> closed interval [A, B] {'(', A::term(), B::term(), ']'} -> half-open interval (A, B], aka ]A, B] {'[', A::term(), B::term(), ')'} -> half-open interval [A, B), aka [A, B[ {'(', A::term(), B::term(), ')'} -> open interval (A, B), aka ]A, B[ all -> half open interval [?MINUS_INFINITY, ?PLUS_INFINITY)

simple_interval2()

simple_interval2() = {left_bracket(),
                      key(),
                      key(),
                      right_bracket()}
                   | {left_bracket(),
                      key(),
                      340282366920938463463374607431768211456,
                      ')'}

Function Index

all/0Creates an interval covering the whole key space.
empty/0Creates an empty interval.
from_elements/1Creates an interval from a list of elements.
get_bounds/1Gets the outer bounds of a given non-empty interval including brackets.
get_elements/1Gets all elements inside the interval and returnes a "rest"-interval, i.e.
get_simple_intervals/1returns a list of simple intervals that make up Interval.
in/2X \in I.
intersection/2Creates the intersection of two intervals.
is_adjacent/2Checks whether two intervals are adjacent, i.e.
is_all/1Checks whether the given interval is covering everything.
is_continuous/1Checks whether the given interval is a continuous interval, i.e.
is_empty/1Checks whether the given interval is empty.
is_left_of/2X and Y are adjacent and Y follows X.
is_non_empty/1Checks whether the given interval is non-empty (mainly for tester type checker).
is_right_of/2X and Y are adjacent and X follows Y.
is_subset/2Returns true if A is a subset of B, i.e.
is_well_formed/1Checks whether the given interval is normalized, i.e.
is_well_formed_simple/1Checks whether a given simple interval is normalized.
minus/2Subtracts the second from the first interval.
new/1Creates an interval covering a single element.
new/4Creates a new interval depending on the given brackets, i.e.: - closed interval [A, B], - half-open interval (A, B], aka ]A, B] - half-open interval [A, B), aka [A, B[ - open interval (A, B), aka ]A, B[ The new interval may wrap around, e.g.
simple_interval_to_interval/1Converts a simple interval (e.g.
split/2Splits a continuous interval in X roughly equally-sized subintervals, the result of non-continuous intervals is undefined.
split_feeder/2
tester_create_continuous_interval/4
tester_create_interval/1Brings a list of intervals into normal form, i.e.
tester_create_non_empty_interval/2
tester_create_simple_interval/1Brings a simple interval into normal form, i.e.
union/1Creates the union of a list of intervals.
union/2Creates the union of two intervals.
wraps_around/4Determines whether an interval with the given borders wraps around, i.e.

Function Details

empty/0

empty() -> interval()

Creates an empty interval.

all/0

all() -> interval()

Creates an interval covering the whole key space.

new/1

new(X :: key()) -> interval()

Creates an interval covering a single element.

new/4

new(LeftBr :: left_bracket(),
    Begin :: key(),
    End :: key() | 340282366920938463463374607431768211456,
    RightBr :: right_bracket()) ->
       interval()

Creates a new interval depending on the given brackets, i.e.: - closed interval [A, B], - half-open interval (A, B], aka ]A, B] - half-open interval [A, B), aka [A, B[ - open interval (A, B), aka ]A, B[ The new interval may wrap around, e.g. if A > B. If '[A,A]' is given, an interval with the element A is created. The special cases '(A,A)', '[A,A)', '(A,A]' and '(?PLUS_INFINITY,?MINUS_INFINITY,)' translate to an empty interval. '[?MINUS_INFINITY,?PLUS_INFINITY)' translates to 'all'.

from_elements/1

from_elements(Elements :: [key()]) -> interval()

Creates an interval from a list of elements.

is_empty/1

is_empty(X1 :: interval()) -> boolean()

Checks whether the given interval is empty.

is_non_empty/1

is_non_empty(I :: interval()) -> boolean()

Checks whether the given interval is non-empty (mainly for tester type checker).

is_all/1

is_all(X1 :: interval()) -> boolean()

Checks whether the given interval is covering everything.

intersection/2

intersection(A :: interval(), B :: interval()) -> interval()

Creates the intersection of two intervals. Precondition: is_well_formed(A) andalso is_well_formed(B).

is_subset/2

is_subset(A :: interval(), B :: interval()) -> boolean()

Returns true if A is a subset of B, i.e. the intersection of both is A. Precondition: is_well_formed(A) andalso is_well_formed(B).

in/2

in(X :: key(), I :: interval()) -> boolean()

X \in I. Precondition: is_well_formed(I).

tester_create_interval/1

tester_create_interval(List :: invalid_interval() | interval()) ->
                          interval()

Brings a list of intervals into normal form, i.e. sort, eliminate empty intervals from the list, convert intervals that wrap around into a set of intervals not wrapping around, merge adjacent intervals. Note: Outside this module, use only for testing - all intervals generated by this module are normalized! Note: This function also corrects values which are to small, i.e. less than ?MINUS_INFINITY, or too large, i.e. greater than or equal to ?PLUS_INFINITY which is only needed if types are created based on (potentially) inprecise type defs, e.g. in the unit tests. For internal use prefer normalize_internal/1 which does not fix values and is thus faster.

tester_create_non_empty_interval/2

tester_create_non_empty_interval(List :: [simple_interval(), ...],
                                 FallbackElem :: key()) ->
                                    non_empty_interval()

tester_create_continuous_interval/4

tester_create_continuous_interval(LBr :: left_bracket(),
                                  Key :: key(),
                                  RKey :: key()
                                        | 340282366920938463463374607431768211456,
                                  RBr :: right_bracket()) ->
                                     continuous_interval()

tester_create_simple_interval/1

tester_create_simple_interval(I0 :: invalid_simple_interval()) ->
                                 simple_interval()

Brings a simple interval into normal form, i.e. if it is a real interval, its keys must be in order. Note: Outside this module, use only for testing - all intervals generated by this module are normalized! Note: This function also corrects values which are to small, i.e. less than ?MINUS_INFINITY, or too large, i.e. greater than or equal to ?PLUS_INFINITY which is only needed if types are created based on (potentially) inprecise type defs, e.g. in the unit tests.

is_well_formed/1

is_well_formed(List :: invalid_interval() | interval()) ->
                  boolean()

Checks whether the given interval is normalized, i.e. not wrapping around and no 'interval' with equal borders (see normalize_internal/1). Use only for testing - all intervals generated by this module are well-formed, i.e. normalized!

is_well_formed_simple/1

is_well_formed_simple(X1 :: simple_interval()) -> boolean()

Checks whether a given simple interval is normalized. Complex intervals or any other value are considered 'not normalized'.

union/2

union(A :: interval(), B :: interval()) -> interval()

Creates the union of two intervals.

union/1

union(List :: [interval()]) -> interval()

Creates the union of a list of intervals.

is_continuous/1

is_continuous(X1 :: interval()) -> boolean()

Checks whether the given interval is a continuous interval, i.e. simple intervals are always continuous, complex intervals are continuous if they contain 2 simple intervals which are adjacent and wrap around. Note: empty intervals are not continuous!

get_bounds/1

get_bounds(T :: interval()) -> simple_interval2()

Gets the outer bounds of a given non-empty interval including brackets. Note that here 'all' transfers to {'[', ?MINUS_INFINITY, ?PLUS_INFINITY, ')'}, {Key} to {'[', Key, Key, ']'} and [{'[',?MINUS_INFINITY,Key,')'},{'(',Key,?PLUS_INFINITY,')'}] to {'(', Key, Key, ')'}. Other continuous normalized intervals that wrap around (as well as the first two) are returned the same way they can be constructed with new/4. Note: the bounds of non-continuous intervals are not optimal! Note: this method will only work on non-empty intervals and will throw an exception otherwise!

get_elements/1

get_elements(I :: interval()) ->
                {Elements :: [key()], RestInt :: interval()}

Gets all elements inside the interval and returnes a "rest"-interval, i.e. the interval without the elements.

is_adjacent/2

is_adjacent(A :: interval(), B :: interval()) -> boolean()

Checks whether two intervals are adjacent, i.e. the intervals are both continuous, their union is continuous and their intersection is empty, e.g. ('(A,B]', '(B,C)') with A=/=B and B=/=C. Note: intervals like (A,B), (B,C) are not considered adjacent because the element b would be between these two.

minus/2

minus(A :: interval(), TB :: interval()) -> interval()

Subtracts the second from the first interval.

wraps_around/4

wraps_around(LeftBr :: left_bracket(),
             X :: key(),
             Last :: key()
                   | 340282366920938463463374607431768211456,
             RightBr :: right_bracket()) ->
                boolean()

Determines whether an interval with the given borders wraps around, i.e. the interval would cover the (non-existing) gap between ?PLUS_INFINITY and ?MINUS_INFINITY.

is_left_of/2

is_left_of(X :: interval(), Y :: interval()) -> boolean()

X and Y are adjacent and Y follows X

is_right_of/2

is_right_of(X :: interval(), Y :: interval()) -> boolean()

X and Y are adjacent and X follows Y

split_feeder/2

split_feeder(I :: continuous_interval(), Parts :: 1..255) ->
                {continuous_interval(), pos_integer()}

split/2

split(I :: continuous_interval(), Parts :: pos_integer()) ->
         [continuous_interval()]

Splits a continuous interval in X roughly equally-sized subintervals, the result of non-continuous intervals is undefined. Returns: List of adjacent intervals

get_simple_intervals/1

get_simple_intervals(Interval :: interval()) ->
                        [simple_interval()]

returns a list of simple intervals that make up Interval

simple_interval_to_interval/1

simple_interval_to_interval(SInterval :: simple_interval()) ->
                               interval()

Converts a simple interval (e.g. from get_simple_intervals/1) to a valid interval().


Generated by EDoc, Aug 2 2016, 13:42:10.