previousnext
ASTL homeSTL home
Sigma

Description

This is one of the two types a user need to provide when using ASTL automata.
It encapsulates the type of the alphabet, the type of the iterators on this alphabet and a few methods.

Refinement of

Associated types

Alphabet type X::Alphabet the actual type of the letters on the transitions
iterator type X::const_iterator A forward read-only iterator on

Notation

S A type that is a model of Sigma
s an object of type S
l an object of type S::Alphabet

Definitions

The size of a alphabet is the number of elements it contains. The size is a nonnegative number.

Valid expressions

the following expressions must be valid.
Name Expression Type requirements Return type
Beginning of s.begin()   S::const_iterator
End of s.end()   S::const_iterator
Size s.size()   unsigned long
Mapping s.map(l)   unsigned long
Unmapping s.unmap(n) n must be compatible with unsigned long S::Alphabet

Expression semantics

Name Expression Precondition Semantics Postcondition
Beginning of s.begin()   Returns an iterator pointing to the first letter of s.begin() is either dereferenceable or past-the-end. It is past-the-end if and only if s.size() == 0.
End of s.end()   Returns a past the end iterator on s.end() is past-the-end.
Size s.size()   Returns ||. s.size() >= 0
Mapping s.map(l)   Maps to a range of contiguous integer values [0,||]. Needed by DFA_matrix and DFA_compact  
Unmapping s.unmap(n)   Reverse function of map  

Complexity guarantees


Invariants

s.map(s.unmap(n))==n
s.unmap(s.map(l))==l

Models