next up previous
Next: Exported types Up: Data Types Previous: Data Types

User-defined Data Types

The user has to provide two types, Tag which contains what his algorithms require to work and Sigma, the alphabet type. Each of automaton class takes two types as instanciation parameters, the alphabet type and the tag type, however DFA_compact expects a single type, one of the automaton types (DFA_compact is an adapter ).

Type Sigma
Description  An object type encapsulating the type of the alphabet, the type of the
  iterators on this alphabet and a few methods.
Requirements See table page [*] (u_long stands for unsigned long).
Type Tag
Description  An object type storing data needed to run an algorithm.
Requirements See table page [*].

Types Descriptions
Sigma::Alphabet The actual type of the letters on the transitions ($\Sigma$). See table page [*] for alphabet class requirements
Sigma::iterator A forward read-only iterator on $\Sigma$
Static Methods  
Sigma::iterator Sigma::begin() Returns an iterator on the first letter of $\Sigma$
Sigma::iterator Sigma::end() Returns a past-the-end iterator on $\Sigma$
u_long Sigma::size() Returns $\vert\Sigma\vert$
u_long Sigma::map(Alphabet) Maps $\Sigma$ to a range of contiguous integer values $[0,\vert\Sigma\vert)$. Needed by DFA_matrix and DFA_compact classes
Alphabet Sigma::unmap(u_long) Reverse function of map
Alphabet Sigma::separator() Returns the alphabet separator used in input/output on ASCII streams

  Sigma type requirements

Operators Descriptions
ostream& Alphabet::operator << (ostream&) Stream output operator
istream& Alphabet::operator >> (istream&) Stream input operator
Alphabet& Alphabet::operator = (const Alphabet&) Assignment operator
bool Alphabet::operator == (const Alphabet&) Comparison operator
bool Alphabet::operator < (const Alphabet&) Order relation

 Sigma::Alphabet type requirements

ASTL provides two often-used alphabet template classes implemented in the file alphabet.hh :

  Class 		 template <class T, T separator>
		 class Type_alphabet 
Description 		 A type of alphabet based on a type T.
		 All values of the type T are in the alphabet and the mapping iscarried out
		 by casting  T to unsigned long ( T must define acast operator to unsigned
		 long and unsigned long must becastable to T). 
[4ex]Class 		 template <class T, T lower_bound, T upper_bound, T  separator>
		 class Range_alphabet 
Description 		 The alphabet here contains the values of type T in[lower_bound, upper_bound]
		 (a set of contiguous values constituting a subset of T).
Methods Descriptions
Tag& operator = (const Tag&) Assignment operator
void read(istream&) Binary stream input
void write(ostream&) Binary stream output
istream& operator >> (istream&) ASCII stream input operator
ostream& operator << (ostream&) ASCII stream output operator

Tag type requirements  
You will find in the file tag.hh a base class for your tag class implementing these requirements and few useful methods. Here is the interface :
class STag
  bool final();
  void final(bool b);
  bool visited();
  void visited(bool b);
  STag(const STag &t);
  STag& operator = (const STag &t);
  virtual void read(istream &in);
  virtual void write(ostream &out);
  friend ostream& operator << (ostream &out, const STag &t);
  friend istream& operator >> (istream &in, STag &t);
The flags final and visited are stored together in an unsigned char which is declared in protected scope. You can use this class as-is or derive your own tag class from this one and add anything you need to run an algorithm.
next up previous
Next: Exported types Up: Data Types Previous: Data Types
Vincent Lemaout