Document number:	DXXXXR0
Date:	2018-01-20
Project:	ISO/IEC JTC1 SC22 WG21 Programming Language C++
Audience:	Library Evolution Working Group/Reflection Working Group
Reply-to:	Vicente J. Botet Escribá <vicente.botet@wanadoo.fr>

C++ Ordinal types and associated containers

=============================================

Abstract

This paper proposes the addition of Ordinal types which are isomorphic to 0..N as well as containers using Ordinal types as elements or indexes

ordinal_set using a bit for each element of the Ordinal type.
ordinal_array using an Ordinal type as index.
ordinal_range a run-time range view of an Ordinal type.

Introduction

With the advent of more strong typing, like bounded integers month, weekday, we have now that these types cannot be used directly as index of std::bit_set. Kevlin Henney presented in Flag Waiving Flag_Waiving a safe design for enum sets which is based on the association of an enumeration element and its position on the enumeration itself or to some kind of transformation (bit flags) to the range 0..N.

This paper propose a generalization of those enum_set to any type that is isomorphic to 0..N and name those types Ordinal types.

Motivation and Scope

With the advent of more strong typing, like bounded integers month, weekday, we have now that these types cannot be used directly as index of std::bit_set. Kevlin Henney presented in Flag Waiving Flag_Waiving a safe design for enum sets which is based on the association of an enumeration element and its position on the enumeration itself or to some kind of transformation (bit flags) to the range 0..N.

Let's see how we can use a strong bounded_int<1,10> as element of a set. As bounded_int<1,10> is isomorphic to 0..9 we could use a std::bitset to represent the set

using B = bounded_int<1,10> ;
using S = std::bitset<10> ;
S set;
B b;
do_something(set[int(b)-1]);

However we need to do an explicit mapping from the bounded integer to its position in the range 0..9 using the formula int(b)-1.

With ordinal_set<B> we avoid the explicit size of the ordinal type as well as the transformation which make the code more readable and safe.

using B = bounded_int<1,10> ;
using S = ordinal_set<B> ;
S set;
B b;
do_something(set[b]);

We have that types as bounded_int cannot be used as index of arrays even if bounded_int was implicitly convertible to int, as the value and the range are not the same. The same kind of transformation must be used when we want to use a bounded int as index of an std::array.

using B = bounded_int<1,10> ;
using A = array<X,B::size> ;
A arr;
B b;
do_something(arr[int(b)-1]);

Again ordinal_array avoids the explicit size and transformation.

using B = bounded_int<1,10> ;
using A = ordinal_array<X,B> ;
A arr;
B b;
do_something(arr[b]);

The range-v3 library [RangeV3] proposes some integral range views. Given a type that is isomorphic to 0..N, it is natural to consider the type itself as the range of its values.

Without

using B = bounded_int<1,10> ;
for (int i = B::first_index; i<=B::last_index, ++i )
    do_someting(B(i));

With iota view we can simplify the things a little bit, but we need to state explicitly the bounds.

using B = bounded_int<1,10> ;
for (auto b : iota(B::first; B::last) )
    do_someting(b);

With ordinal_range we use directly the bounded ordinal type, instead of seen the associated bounds.

using B = bounded_int<1,10> ;
for (auto b : ordinal_range<B>())
    do_someting(b);

This kind of types are found in language as Ada, which defines attributes on enumerations like first, last, succ, val, pos, ... This association has constant time complexity most of the time, as usual enumerations follows linear or exponential (base 2) progressions.

Examples of libraries that have tried to cope with some of these aspects are:

Boost.Enum by Frank Laub, takes care of scoping, underlying type, iteration and string conversions, but doesn't take care of avoiding implicit conversion and portability to C++11 scoped enums. This thread Smart enums and this one safe assign of int to enum are quite interesting. Unfortunately there were no concrete proposal.
Boost.SmartEnums has complex design to take care of iteration.
BEnum.

But most of them have been restricted to enum to string conversions. This paper doesn't take in account this conversion, as we will have it almost for free with static reflection.

Proposal

This paper proposes to add the following

Ordinal types isomorphic to 0..N.
Containers using Ordinal types as elements or indexes
- ordinal_set using a bit for each element of the Ordinal type.
- ordinal_array using an Ordinal type as index.
- ordinal_range a run-time range view of an Ordinal type.

Design Rationale

Ordinal types

So, an ordinal type is a type that is isomorphic to the range 0..N. The N conditions the size of the type, and we need two functions that map the isomorphism, val from the position to the ordinal type and pos from the ordinal type to the position.

Traits based customization concept

The design of this proposal is based on a traits specialization instead of using ADL. The main reason is to make the mapping of ordinal types explicit, and the second is that we need to customize operations size and pos that don't have an Ordinal type as function parameter, but as template parameter.

The alternative would be to add an additional parameter that coveys the Ordinal type.

size_t ordinal_size(identity_type<O>);
O ordinal_val(identity_type<O>, size_t);
size_t ordinal_pos(O);

`ordinal_set` for ordinal types with small cardinality

ordinal_set implementation would use as underlying type a std::bitset as the interface is based on std::bitset.

However for ordinal sets with a small cardinality, we could expect to use a more compact memory than the one used by bitset.

Before proposing an ordinal_set that could have a more compact representation, we believe that we need to generalize the bitset interface with an additional block type. Lets, call it basic_bitset<N, Block>. In this way bitset<N> could have as representation a basic_bitset<N, long>. Then we could define a basic_ordinal_set<O, Block=long>. This proposal, doesn't propose such a basic_bitset<N, long> type yet.

`ordinal_range` and the Range views

The range library proposes an integral range view factory std::experimental:ranges::iota.

ordinal_range<O> should be a model of a Range. In order to limit the dependencies between TS, this paper doesn't propose yet to see it as a range, but in fact it ordinal_range<O> is Range.

Impact on the standard

These changes are entirely based on library extensions and do not require any language features beyond what is available in C++17. There are however some classes in the standard that can be customized.

Once we will have reflection, we could reflect enums with unique values as ordinal types.

Proposed Wording

The proposed changes are expressed as edits to N4564 the Working Draft - C++ Extensions for Library Fundamentals V2.

Add a "Ordinal Types" section

Ordinal Types

Ordinal types are types that are isomorphic to the range 0..n. They can be used as index of ordinal arrays, as element of an ordinal set or as element of an ordinal range.

Ordinal requirements

A Ordinal is a type that supports the size/val/pos functions. A type O meets the requirements of Ordinal if:

O satisfies the requirements of EqualityComparable DefaultConstructible, and Destructible,
the expressions shown in the table below are valid and have the indicated semantics, and
T satisfies all the other requirements of this sub-clause.

In Table X below, o denotes an rvalue of type O, p denotes a rvalue of type index_t an alias of int.

Expression	Return Type	Operational Semantics
std::experiental::ordinal::size<O>()	std::experiental::ordinal::index_t	number of elements in O
std::experiental::ordinal::val<O>(p)	O	value at position p, for p in 0..(size-1)
std::experiental::ordinal::pos(o)	index_t	position of o

Header <experimental/ordinal> synopsis [ordinal.synop]

namespace std {
namespace experimental {
inline namespace fundamentals_v3 {
namespace ordinal {
  using index_t =  int;

  template <class TC, class Enabler=void>
    struct traits {};
    
  template <class Ordinal>
    constexpr index_t size() noexcept;
  template <class Ordinal>
    constexpr Ordinal val(index_t pos);
  template <class Ordinal>
    constexpr index_t pos(Ordinal&& val) noexcept;   
  template <class Ordinal>
    constexpr Ordinal first() noexcept;
  template <class Ordinal>
    constexpr Ordinal last() noexcept;
  template <class Ordinal>
    constexpr Ordinal succ(Ordinal&& val);
  template <class Ordinal>
    constexpr Ordinal pred(Ordinal&& val);

  template <class T, T Low, T High, T Step = T{1}, class SizeType=index_t>
    struct arithmetic_traits;  
  template <class T>
    struct logarithmic_traits;
  template <typename T>
    struct integral_traits; 
    
  template <> struct traits<int>;
  template <> struct traits<short>;
  template <> struct traits<signed char>;
  template <> struct traits<unsigned int>;
  template <> struct traits<unsigned short>;
  template <> struct traits<unsigned char>;
  template <> struct traits<bool>;
        
}

  template <class T>
    struct is_ordinal;
  template <class T>
    struct is_ordinal<const T>;
  template <class T>
    struct is_ordinal<volatile T>;
  template <class T>
    struct is_ordinal<const volatile T>;    
  template <class T>
    inline constexpr bool is_ordinal_v;
}
}
}

Class Template `traits` [ordinal.traits]

namespace ordinal {
    template <class T, class Enabler=void>
        struct traits {};
}

This traits must be specialized for a type to become an Ordinal type. The specialization must define the 3 customization points size, val and pos.

Next follows the archetype of this customization

namespace ordinal {
    template <>
    struct traits<O>
    {
      using size = integral_constant<index_t, S>;
      static O val(index_t p);
      static index_t pos(O u);
    };
}

where the specialization shall have the following semantics:

ordinal::traits<O>::size::value and ordinal::traits<O>::size{} should give the number of elements of the Ordinal type O.
ordinal::traits<O>::val(p) should give the value at the position p in the Ordinal type O.
ordinal::traits<O>::pos(o) should give the position of the value o in the Ordinal type O.