An alphabet is a set of symbols. In theory, any object represented in a binary form can be seen as in a set of symbols, with all possible valid bit patterns in the set. The math::alphabet class represents a bounded set of symbols explicitly. This makes it possible to

  1. check whether two objects are in the same set, and whether an element supposed to be in the set actually is; and
  2. to represent elements more tersely, which improves performance. math::alphabet represents symbols internally by integers.

There is an additional twist to math::alphabet. The symbols can be of two types:

  • A “normal symbol”, which is a value of the main symbol type. For example, this may be of type std::string. New symbols are added with method math::alphabet::add_symbol().
  • A “special symbol”, which is of an empty type other than the symbol type. An “empty” type has no value, but any two objects of such a type must compare equal. “Must compare equal” means that the type that operator== returns is a compile-time constant with value true. New special symbols can be added with free function (!) math::add_special_symbol().


template <class NormalSymbol, class Tag = void, std::size_t max_normal_symbol_num = 0xFFFFFF7F, class SpecialSymbols = meta::vector<>, std::size_t special_symbol_headroom = 0x80>
class math::alphabet

Alphabet of symbols.

This deals with two types of symbols: normal symbols, and special symbols. Normal symbols are all of one type, but have different values. For example, they can be words in a word list. Special symbols are compile-time symbols: they have different types, but no meaningful value. Objects of these types must always compare equal to each other. For example, these could be the “empty” symbol, which might be program-internal.

Symbols are assigned a dense (integer) type, too. The first normal symbol is assigned a value of 0, the second of 1, et cetera. Special symbols are assigned negative values from -1 down. This makes debugging easier.

The integer type is chosen automatically as the smallest integer that can contain the set. By default, space is reserved in a 32-bit integer with 128 special symbols.

Normal symbols are added to an alphabet at run time. To make sure that they cannot be accidentally re-used, symbols cannot be removed from an alphabet.

Special symbols are added at compile time, as it were, with the add_special_symbol function, which returns the alphabet with the extra special symbol type. This alphabet shares the set of normal symbols with its parent. If a normal symbol is added to its parent, the symbol is at the same tim added to it.

  • NormalSymbol -

    The type for normal symbols.

  • Tag -

    An arbitrary type that can be used to distinguish alphabets at compile time. The default value is void.

  • max_normal_symbol_num -

    The number of normal symbols to reserve room for. The default value uses all of 32 bits, except for 129 symbols.

  • SpecialSymbols -

    The special symbol types contained in the alphabet, as a meta range. The default value is meta::vector<>.

  • special_symbol_headroom -

    The maximum number of special symbols. The default value is 128.

Public Type

typedef detail::int_type_for< max_normal_symbol_num+special_symbol_headroom >::type dense_type

Signed integer type that is used for dense symbols.

typedef NormalSymbol normal_symbol_type

The normal symbol type. Equal to NormalSymbol.

typedef dense_symbol< dense_type, Tag > dense_symbol_type

The dense symbol type. This is an object type, with inside the smallest integer type that can fit all symbols in the set.

Public Functions


Construct an alphabet that is empty apart from any special symbols.

dense_symbol_type add_symbol(NormalSymbol const & symbol)

Add a new normal symbol to the alphabet.

The dense representation of the symbol.

dense_symbol_type get_dense(NormalSymbol const & symbol) const

An dense representation of the symbol.
  • symbol -

    The representation. This can be of the normal symbol type, or of any of the special symbol types.

bool is_special_symbol(dense_symbol_type const & dense) const

true iff the dense symbol denotes a special symbol. The dense symbol can be a general dense symbol, or have a specific value type.

template <class SuspectedSymbol>
bool is_symbol_type(dense_symbol_type const & dense) const

Check whether an dense symbol represents a specific type. If SuspectedSymbol is a compile-time symbol and dense is a compile-time representation, the result is a compile-time constant.

  • SuspectedSymbol -

    The type that it is suspected the symbol might represent.

  • dense -

    The symbol to be checked. This can be a run-time or a compile-time symbol.

template <class SuspectedSymbol>
SuspectedSymbol const & get_symbol(dense_symbol_type const & dense) const

Retrieve the symbol represented by the dense symbol passed in.


SuspectedSymbol is the actual type of the symbol. If this is not the case, then an assertion may be triggered.

The dense symbol exists, at run time, in the alphabet. If this is not the case, symbol_not_found_of will be thrown.

  • SuspectedSymbol -

    The return type, which should be the actual type of the symbol.

template <class Function>
void visit_type(Function && function, dense_symbol_type const & dense) const

Dispatch a function with two parameters: the symbol type corresponding to symbol wrapped as an symbol_type object, and the original symbol.

template <class Value, class Tag>
class math::dense_symbol

Represent a symbol from an alphabet with an integer. There is usually no reason to explicitly use this class; alphabet will normally produce objects of this class.

This class has all comparison operators. The ordering is not meaningful: all it does is provide a strict weak ordering (which corresponds to the strict weak ordering on the underlying id’s). There is no relation to the ordering of the normal symbols.

This class also supports boost::hash.

  • Value -

    The integer type that the symbol is mapped to. This type can also be a compile-time constant (normally rime::constant), if the value is known at compile time, which is often the case for special symbols.

  • Tag -

    A user-defined tag to distinguish alphabets at compile time. Must be the same as the Tag template parameter of the matching alphabet.

Public Functions

template <class Value2>
dense_symbol(dense_symbol< Value2, Tag > const & that)

Copy constructor that takes a compile-time symbol if this is a run-time symbol.

Value id() const

Return the dense id of the symbol. This always returns an object, not an reference: the object may be constructed on the fly.

template <class NewSpecialSymbol, class NormalSymbol, class Tag, std::size_t max_normal_symbol_num, class SpecialSymbols, std::size_t special_symbol_headroom>
auto add_special_symbol(alphabet< NormalSymbol, Tag, max_normal_symbol_num, SpecialSymbols, special_symbol_headroom > const & a)

Return a new alphabet with a new special symbol added to it. If the alphabet already contains the symbol, then return the alphabet itself.

class math::alphabet_overflow

Exception that is thrown on an attempt to add another element to an alphabet when it is full.

class math::symbol_not_found

Exception that can be thrown when a symbol is not contained in an alphabet. An object should normally be of derived type symbol_not_found_of.

template <class Symbol>
class math::symbol_not_found_of

Exception that can be thrown when a symbol is not contained in an alphabet.

  • Symbol -

    The type of the symbol that was not found.

Public Functions

Symbol const & symbol() const

The symbol that was not found.

Table Of Contents

Previous topic

Extending the sublibrary

Next topic

Range library

This Page