IdentifierField Class Reference

This is the individual specification for the range of one ExpandedIdentifier IdentifierField. More...

#include <IdentifierField.h>

Collaboration diagram for IdentifierField:

Public Types
enum	continuation_mode {   none, has_next, has_previous, has_both,   has_wrap_around }
using	element_type = ExpandedIdentifier::element_type
using	size_type = ExpandedIdentifier::size_type
using	element_vector = std::vector< element_type >
using	index_vector = std::vector< size_type >
using	BoundedRange = std::pair< element_type, element_type >

Public Member Functions
	IdentifierField ()=default
	Create a wild-card value. More...
	IdentifierField (element_type value)
	Create a unique value (understood as : low bound = high bound = value) More...
	IdentifierField (element_type minimum, element_type maximum)
	Create a full range specification (with explicit min and max) More...
	IdentifierField (const element_vector &values)
	Create with enumerated values. More...
bool	wrap_around () const
element_type	get_minimum () const
	Query the values. More...
std::pair< element_type, element_type >	get_minmax () const
element_type	get_maximum () const
const element_vector &	get_values () const
bool	get_previous (element_type current, element_type &previous) const
	Returns false if previous/next is at end of range, or not possible. More...
bool	get_next (element_type current, element_type &next) const
size_type	get_indices () const
const index_vector &	get_indexes () const
size_type	get_bits () const
	Return the number of bits needed to store a value of this field. More...
element_type	get_value_at (size_type index) const
size_type	get_value_index (element_type value) const
bool	match (element_type value) const
	The basic match operation Given a value, test to see if it satisfies the constraints for this field. More...
bool	overlaps_with (const IdentifierField &other) const
	Check whether two IdentifierFields overlap (Are there any values which satisfy the constraints of both fields?) More...
void	clear ()
	Set methods. More...
void	set (element_type minimum, element_type maximum)
void	add_value (element_type value)
void	set (const element_vector &values)
void	set (bool wraparound)
void	set_next (int next)
void	set_previous (int previous)
void	operator|= (const IdentifierField &other)
	Find the union of two fields. More...
	operator std::string () const
bool	operator== (const IdentifierField &other) const
void	show () const
bool	check_for_both_bounded ()
	Check mode - switch from enumerated to both_bounded if possible. More...
void	optimize ()
	Optimize - try to switch mode to both_bounded, set up lookup table for finding index from value. More...
bool	empty () const
	If true, this field does not have any constraints, and may hold any value representable by element_type. More...
bool	isBounded () const
bool	isEnumerated () const

Static Public Attributes
static constexpr auto	minimum_possible = std::numeric_limits<element_type>::min()
static constexpr auto	maximum_possible = std::numeric_limits<element_type>::max()
static constexpr auto	invalidValues = element_vector{}

Private Member Functions
void	set_minimum (element_type value)
void	set_maximum (element_type value)
void	create_index_table ()
	Create index table from value table. More...
template<class T >
T *	dataPtr ()

Private Attributes
element_type	m_minimum {}
element_type	m_maximum {}
std::variant< element_vector, BoundedRange >	m_data {}
index_vector	m_indexes {}
size_type	m_size {}
element_type	m_previous {}
element_type	m_next {}
bool	m_empty {true}
continuation_mode	m_continuation_mode {none}

Static Private Attributes
static constexpr int	m_maxNumberOfIndices = 100

Detailed Description

This is the individual specification for the range of one ExpandedIdentifier IdentifierField.

A field specifies a constraint on the values it may contain. This may take one of three forms:

• Completely unconstrained. In this case, empty() will return true, implying that the field may hold any value representable by element_type. (Yes, it's a bad name and means the opposite of what you may think...) An empty field is made by the default constructor, and also by calling clear().
• A bounded (inclusive) range. In this case, isBounded() will return true, get_maximum/get_minimum will return the ends of the range, and get_indices() will return the number of values in the range (maximum - minimum + 1). A bounded field may be made by calling the constructor with a minimum and maximum, or by calling set() with the same arguments. The range is also stored in m_data as the BoundedRange option.
• An enumeration. In this case, isEnumerated() will return true, get_maximum/get_minimum will return the minimum and maximum enumeration values, and get_indices() will return the number of enumeration values. get_values() will return a (sorted) vector of all the values. An enumerated field may be made by passing a vector to the constructor or set(), or by calling add_value() with individual values. The values are stored in m_data as the element_vector option.

Each valid value is assigned an index, starting with 0. For bounded ranges, this just starts from the minimum value and counts up. For enumerations, it is the index of that particular enumeration value. You can convert between values and indices using get_value_at() and get_value_index(). For value->index conversions, a lookup table is used if optimize() has been called and the spread of values is not too large. get_indices() will return this table.

As far as users of this class see, there is not really a distinction between a dense enumeration and a bounded range. In fact, check_for_both_bounded()/optimize() will convert a dense enumeration to a bounded range.

Given a value, one can ask for the next/previous valid value using get_next()/get_previous(). For an enumeration, this will return the next or previous enumeration value. If you try to call get_next() for the maximum value in the range, or get_previous() from the minimum, then they will by default fail (return false). This can be changed by calling set_next()/set_previous() to specify explictly values to be returned in these cases, or by calling set(true) to enable wraparound mode; in that case, calling get_next() for the maximum value will return the minimum value, and analogously for get_previous().

Other operations include:

• get_bits(): Return the number of bits needed to store a value of this field.

match(): Given a value, test whether it satisfies the constraints for this field.

• overlaps_with(): Test to see if there are any values which satisfy the constraints of both fields.
• operator|=(): Find the union of two fields. Note: does not correctly handle the cases of an enumeration and a bounded range or two disjoint bounded ranges! If either is empty (meaning no constraint), then the result will be empty.
  • operator==(): Test if two fields have identical constraints. However, a dense enumeration will not compare identically to an equivalent bounded range.

Definition at line 82 of file IdentifierField.h.

Member Typedef Documentation

BoundedRange

using IdentifierField::BoundedRange = std::pair<element_type, element_type>

Definition at line 89 of file IdentifierField.h.

element_type

using IdentifierField::element_type = ExpandedIdentifier::element_type

Definition at line 85 of file IdentifierField.h.

element_vector

using IdentifierField::element_vector = std::vector <element_type>

Definition at line 87 of file IdentifierField.h.

index_vector

using IdentifierField::index_vector = std::vector <size_type>

Definition at line 88 of file IdentifierField.h.

size_type

using IdentifierField::size_type = ExpandedIdentifier::size_type

Definition at line 86 of file IdentifierField.h.

Member Enumeration Documentation

continuation_mode

enum IdentifierField::continuation_mode

Enumerator
none
has_next
has_previous
has_both
has_wrap_around

Definition at line 94 of file IdentifierField.h.

                        { 
    none, 
    has_next, 
    has_previous, 
    has_both,
    has_wrap_around
  } ; 

Constructor & Destructor Documentation

IdentifierField() [1/4]

IdentifierField::IdentifierField ( )

default

Create a wild-card value.

IdentifierField() [2/4]

IdentifierField::IdentifierField

(

element_type

value

)

Create a unique value (understood as : low bound = high bound = value)

Definition at line 83 of file IdentifierField.cxx.

    :
    m_minimum(value),
    m_maximum(value),
    m_data{BoundedRange{value, value}},
    m_empty{false}{
  //    
} 

IdentifierField() [3/4]

IdentifierField::IdentifierField	(	element_type	minimum,
		element_type	maximum
	)

Create a full range specification (with explicit min and max)

Definition at line 93 of file IdentifierField.cxx.

                                                                           { 
  set(minimum, maximum);    
} 

IdentifierField() [4/4]

IdentifierField::IdentifierField

(

const element_vector &

values

)

Create with enumerated values.

Definition at line 99 of file IdentifierField.cxx.

                                                             { 
  set(values);     
}

Member Function Documentation

add_value()

void IdentifierField::add_value

(

element_type

value

)

Definition at line 250 of file IdentifierField.cxx.

                                             {
  if (auto * p = dataPtr<element_vector>(); !p)  {
    clear();
    m_data = element_vector(1,value);//now its enumerated
    m_size = 1;
  } else {
    //check whether value already exists in the enumeration vector
    if (std::ranges::binary_search(*p, value)) return;
    p->push_back(value); 
    std::ranges::sort(*p); 
    m_size = p->size();
  }
  m_minimum = get_values().front(); 
  m_maximum = get_values().back(); 
  m_empty = false;
} 

check_for_both_bounded()

bool IdentifierField::check_for_both_bounded

(

)

Check mode - switch from enumerated to both_bounded if possible.

Definition at line 430 of file IdentifierField.cxx.

                                        {
  if (m_empty) return false;
  if (isEnumerated()) {
    //the enumerated values are kept sorted
    if (m_size-1 == static_cast<size_type>(m_maximum - m_minimum)){
      m_data = BoundedRange{m_minimum, m_maximum}; 
      return true;
    }
  }
  return false;
}

clear()

void IdentifierField::clear

(

)

Set methods.

Definition at line 224 of file IdentifierField.cxx.

                        { 
  m_minimum  = 0; 
  m_maximum  = 0; 
  m_previous = 0;
  m_next     = 0;
  m_continuation_mode = none;
  m_data = element_vector{};
  m_indexes.clear();
  m_empty = true; 
} 

create_index_table()

void IdentifierField::create_index_table ( )

private

Create index table from value table.

Create index table from value table

Definition at line 444 of file IdentifierField.cxx.

                                    {
  if (m_empty) return;
  if (isEnumerated()) {
    size_type size = m_maximum - m_minimum + 1;
    // return if we are over the maximum desired vector table size  
    if (size > m_maxNumberOfIndices) {
        m_indexes.clear();
        return;
    }
    // Set up vectors for decoding
    m_indexes = std::vector<size_type>(size, 0);
    size_type index{};
    int i{};
    auto &v = std::get<element_vector>(m_data);
    for (const auto & thisValue: v) {
      if (const auto idx=(thisValue - m_minimum); idx < (int)size) {
        m_indexes[idx] = index;
        index++;
      } else {
        std::cout << "size, value, index, i " 
        << size << " " << thisValue << " "
        << index << " " << i++ << "  min, max " 
        << m_minimum << " " 
        << m_maximum 
        << std::endl;
      }
    }
  }
}

dataPtr()

template<class T >

T* IdentifierField::dataPtr ( )

inlineprivate

Definition at line 195 of file IdentifierField.h.

{return std::get_if<T>(&m_data);}

empty()

bool IdentifierField::empty ( ) const

inline

If true, this field does not have any constraints, and may hold any value representable by element_type.

Definition at line 182 of file IdentifierField.h.

{return m_empty;}  

get_bits()

ExpandedIdentifier::size_type IdentifierField::get_bits

(

)

const

Return the number of bits needed to store a value of this field.

Definition at line 40 of file IdentifierField.cxx.

                                                           {
  size_t indices = get_indices ();
  if (--indices) return  std::bit_width(indices);
  return 1;
}

get_indexes()

const index_vector& IdentifierField::get_indexes ( ) const

inline

Definition at line 141 of file IdentifierField.h.

{return m_indexes;}

get_indices()

size_type IdentifierField::get_indices ( ) const

inline

Definition at line 140 of file IdentifierField.h.

{return m_size;}

get_maximum()

element_type IdentifierField::get_maximum ( ) const

inline

Definition at line 130 of file IdentifierField.h.

{return m_maximum;} 

get_minimum()

element_type IdentifierField::get_minimum ( ) const

inline

Query the values.

Definition at line 121 of file IdentifierField.h.

{return m_minimum;}

get_minmax()

std::pair<element_type, element_type> IdentifierField::get_minmax ( ) const

inline

Definition at line 125 of file IdentifierField.h.

                     {
    return {m_minimum, m_maximum};
  }

get_next()

bool IdentifierField::get_next	(	element_type	current,
		element_type &	next
	)		const

Definition at line 149 of file IdentifierField.cxx.

                                                                       {
  if (m_empty){
    next = current + 1; 
    return (current != maximum_possible);
  }
    
  if (isBounded()){
    if (current == m_maximum) {
      if (has_wrap_around == m_continuation_mode) {
          next = m_minimum;
          return (true); 
      }
      if (has_next == m_continuation_mode || has_both == m_continuation_mode) {
          next = m_next;
          return (true); 
      }
      next = current;
      return (false);
    }
    next = current + 1; 
    return (true); 
  }
  const auto & values= get_values();
  size_type index = get_value_index(current);
  if ((index == values.size() - 1) || (index == 0 && current != values.front())) {
    if (has_wrap_around == m_continuation_mode) {
        next = values.front();
        return (true); 
    }
    if (has_next == m_continuation_mode || has_both == m_continuation_mode) {
        next = m_next;
        return (true); 
    }
    next = current;
    return (false);
  }
  ++index;
  next = values[index];
  return true;
}

get_previous()

bool IdentifierField::get_previous	(	element_type	current,
		element_type &	previous
	)		const

Returns false if previous/next is at end of range, or not possible.

Definition at line 106 of file IdentifierField.cxx.

                                                                               {
  if (m_empty){
    previous = current - 1; 
    return (current != minimum_possible);
  }
  if (isBounded()){
    if (current == m_minimum) {
      if (has_wrap_around == m_continuation_mode) {
          previous = m_maximum;
          return (true); 
      }
      if (has_previous == m_continuation_mode || has_both == m_continuation_mode) {
          previous = m_previous;
          return (true); 
      }
      previous = current;
      return (false);
    }
    previous = current - 1; 
    return (true); 
  }
  const auto & values= get_values();
  size_type index = get_value_index(current);
  if (index == 0) {
    if (has_wrap_around == m_continuation_mode) {
        previous = values.back();
        return (true); 
    }
    if (has_previous == m_continuation_mode || has_both == m_continuation_mode) {
        previous = m_previous;
        return (true); 
    }
    previous = current;
    return (false);
  }
  --index;
  previous = values[index];
  return true;
}

get_value_at()

IdentifierField::element_type IdentifierField::get_value_at ( size_type  index ) const

inline

Definition at line 209 of file IdentifierField.h.

                                                   { 
  // Only both_bounded and enumerated are valid to calculate the
  // value.
  // both_bounded is the more frequent case and so comes first.
  if (m_empty) return 0;
  if (const auto * p{std::get_if<BoundedRange>(&m_data)}; p) {
    if (index >= (size_type) (p->second - p->first + 1)) {
      throw std::out_of_range("IdentifierField::get_value_at");
    }
    return (p->first + index); 
  }
  return ((std::get<element_vector>(m_data)).at(index)); 
 
} 

get_value_index()

ExpandedIdentifier::size_type IdentifierField::get_value_index

(

element_type

value

)

const

Definition at line 49 of file IdentifierField.cxx.

                                                        {
  // Only both_bounded and enumerated are valid to calculate the
  // index.
  // both_bounded if the more frequent case and so comes first.
  if (isBounded()) {
    return (value - m_minimum); 
  } 
  const auto & v = get_values();
  if (v.size()==1) return 0;
  if (not m_indexes.empty()) {
    // Table has been created, do simple lookup
    assert (value >= m_minimum && value - m_minimum < (int)m_indexes.size());
    return (m_indexes.at(value - m_minimum));
  } else {
    auto it = std::ranges::find(v, value);
    if (it != v.end()) return std::distance(v.begin(), it);
  }
  return 0;
}

get_values()

const element_vector& IdentifierField::get_values ( ) const

inline

Definition at line 133 of file IdentifierField.h.

                     { 
    if (isBounded()) return invalidValues;
    return std::get<element_vector>(m_data);
  } 

isBounded()

bool IdentifierField::isBounded ( ) const

inline

Definition at line 184 of file IdentifierField.h.

{return std::holds_alternative<BoundedRange>(m_data);} 

isEnumerated()

bool IdentifierField::isEnumerated ( ) const

inline

Definition at line 185 of file IdentifierField.h.

{return std::holds_alternative<element_vector>(m_data);}

match()

bool IdentifierField::match

(

element_type

value

)

const

The basic match operation Given a value, test to see if it satisfies the constraints for this field.

Definition at line 71 of file IdentifierField.cxx.

                                               {  
  if (isBounded()) {
    return ((value >= m_minimum) && (value <= m_maximum)); 
  }
  if (m_empty) return true;
  const auto & v = get_values();
  return (std::ranges::find(v, value)!=v.end());
} 

operator std::string()

IdentifierField::operator std::string

(

)

const

Definition at line 343 of file IdentifierField.cxx.

                                           { 
  std::string result; 
  if (m_empty) { 
      result = "*"; 
  }  else  { 
    const auto & [minimum, maximum]  = get_minmax(); 
    if (minimum == maximum)  { 
      result =  std::to_string(minimum);
    } else  { 
      if (isEnumerated())  { 
        std::string prefix;
        for (size_type i = 0; i < get_indices (); ++i)  { 
          result += prefix+std::to_string(get_value_at(i));
          prefix = ",";
        } 
      } else { 
        result = std::format("{}:{}", minimum, maximum);
      } 
    } 
  } 
  return result; 
} 

operator==()

bool IdentifierField::operator==

(

const IdentifierField &

other

)

const

Definition at line 368 of file IdentifierField.cxx.

                                                                {
    if (m_data != other.m_data)   return false;
    return (true);
}

operator|=()

void IdentifierField::operator|=

(

const IdentifierField &

other

)

Find the union of two fields.

Note: does not correctly handle the cases of an enumeration and a bounded range or two disjoint bounded ranges! If either is empty (meaning no constraint), then the result will be empty.

If there is no overlap we should build a multi-segment specification. The current algorithm is only correct if the overlap in not empty !! A multi-segment specification might also be implemented as an expanded enumerated set (not very optimized !!)

Definition at line 319 of file IdentifierField.cxx.

                                                          {
  if (m_empty or other.m_empty){
    clear();
    m_size = 1;
    return;
  } 
  if (isEnumerated() and other.isEnumerated()){
     set(other.get_values ());
     return;
  }
  // all other cases...
  const auto min = std::min(m_minimum, other.m_minimum);
  const auto max = std::max(m_maximum, other.m_maximum);
  set(min, max);
}

optimize()

void IdentifierField::optimize

(

)

Optimize - try to switch mode to both_bounded, set up lookup table for finding index from value.

Check mode - switch from enumerated to both_bounded if possible

Definition at line 422 of file IdentifierField.cxx.

                          {
  if (not check_for_both_bounded()) create_index_table();    
}

overlaps_with()

bool IdentifierField::overlaps_with

(

const IdentifierField &

other

)

const

Check whether two IdentifierFields overlap (Are there any values which satisfy the constraints of both fields?)

Definition at line 194 of file IdentifierField.cxx.

                                                                  { 
  if (m_empty or other.m_empty) return true;
  //
  if (isBounded() and other.isBounded()){
    return ((m_minimum <= other.m_maximum) && (m_maximum >= other.m_minimum));
  }
  //
  if (isBounded() and other.isEnumerated()  ){
    const element_vector& ev = other.get_values(); 
    for (const auto & v: ev) { 
      if (v >= m_minimum and v<= m_maximum) return (true); 
    } 
    return false;
  } else if (isEnumerated() and other.isBounded()){
    const element_vector& ev = get_values(); 
    for (const auto & v: ev){ 
      if ((v >= other.m_minimum) and (v <= other.m_maximum)) return (true); 
    } 
    return false;
  } 
  // Both fields are enumerated only if there is possibility of overlap 
  if ((m_minimum <= other.m_maximum) && (m_maximum >= other.m_minimum))  { 
    return share_element(get_values(), other.get_values());
  } 
  return (false); 
} 

set() [1/3]

void IdentifierField::set

(

bool

wraparound

)

Definition at line 287 of file IdentifierField.cxx.

                                    { 
  if (wraparound) {
    m_continuation_mode = has_wrap_around;
  }
} 

set() [2/3]

void IdentifierField::set

(

const element_vector &

values

)

set() [3/3]

void IdentifierField::set	(	element_type	minimum,
		element_type	maximum
	)

Definition at line 237 of file IdentifierField.cxx.

                                                                { 
  if (minimum == maximum) {
      add_value(minimum);
  } else {
    std::tie(m_minimum,m_maximum)  = std::minmax(minimum,maximum); 
    m_data = BoundedRange{m_minimum,m_maximum};
    m_size = m_maximum - m_minimum + 1;
  }
  m_empty=false;
} 

set_maximum()

void IdentifierField::set_maximum ( element_type  value )

private

set_minimum()

void IdentifierField::set_minimum ( element_type  value )

private

set_next()

void IdentifierField::set_next

(

int

next

)

Definition at line 295 of file IdentifierField.cxx.

                                   {
  if (has_previous == m_continuation_mode) {
    m_continuation_mode = has_both;
  } else {
    m_continuation_mode = has_next;
  }
  m_next = next;
}

set_previous()

void IdentifierField::set_previous

(

int

previous

)

Definition at line 307 of file IdentifierField.cxx.

                                           {
  if (has_next == m_continuation_mode) {
    m_continuation_mode = has_both;
  } else {
    m_continuation_mode = has_previous;
  }
  m_previous = previous;
}

show()

void IdentifierField::show

(

)

const

Definition at line 376 of file IdentifierField.cxx.

                            {
  std::cout << "min/max " << m_minimum << " " << m_maximum << " "; 
  std::cout << "values  ";
  for (const auto& v: get_values()) {
      std::cout << v << " ";
  }
  std::cout << "indexes  ";
  for (const auto & idx: m_indexes) {
      std::cout << idx << " ";
  }
  std::cout << "indices  " << m_size << " ";
  std::cout << "prev  " << m_previous << " ";
  std::cout << "next  " << m_next << " ";
  std::cout << "mode  ";
  if (m_empty){
      std::cout << "unbounded  ";
  }else if (isBounded()){
      std::cout << "both_bounded  ";
  }else if (isEnumerated()) {
      std::cout << "enumerated  ";
  }
  std::cout << "cont mode  ";
  switch (m_continuation_mode) { 
  case IdentifierField::none: 
      std::cout << "none  ";
      break; 
  case IdentifierField::has_next: 
      std::cout << "has_next  ";
      break; 
  case IdentifierField::has_previous: 
      std::cout << "has_previous  ";
      break; 
  case IdentifierField::has_both:
      std::cout << "has_both  ";
      break; 
  case IdentifierField::has_wrap_around:
      std::cout << "has_wrap_around  ";
      break; 
  }
  std::cout << std::endl;
}

wrap_around()

bool IdentifierField::wrap_around ( ) const

inline

Definition at line 116 of file IdentifierField.h.

{ return (has_wrap_around == m_continuation_mode);}  

Member Data Documentation

invalidValues

constexpr auto IdentifierField::invalidValues = element_vector{}

staticconstexpr

Definition at line 92 of file IdentifierField.h.

m_continuation_mode

continuation_mode IdentifierField::m_continuation_mode {none}

private

Definition at line 205 of file IdentifierField.h.

m_data

std::variant<element_vector, BoundedRange> IdentifierField::m_data {}

private

Definition at line 199 of file IdentifierField.h.

m_empty

bool IdentifierField::m_empty {true}

private

Definition at line 204 of file IdentifierField.h.

m_indexes

index_vector IdentifierField::m_indexes {}

private

Definition at line 200 of file IdentifierField.h.

m_maximum

element_type IdentifierField::m_maximum {}

private

Definition at line 198 of file IdentifierField.h.

m_maxNumberOfIndices

constexpr int IdentifierField::m_maxNumberOfIndices = 100

staticconstexprprivate

Definition at line 188 of file IdentifierField.h.

m_minimum

element_type IdentifierField::m_minimum {}

private

Definition at line 197 of file IdentifierField.h.

m_next

element_type IdentifierField::m_next {}

private

Definition at line 203 of file IdentifierField.h.

m_previous

element_type IdentifierField::m_previous {}

private

Definition at line 202 of file IdentifierField.h.

m_size

size_type IdentifierField::m_size {}

private

Definition at line 201 of file IdentifierField.h.

maximum_possible

constexpr auto IdentifierField::maximum_possible = std::numeric_limits<element_type>::max()

staticconstexpr

Definition at line 91 of file IdentifierField.h.

minimum_possible

constexpr auto IdentifierField::minimum_possible = std::numeric_limits<element_type>::min()

staticconstexpr

Definition at line 90 of file IdentifierField.h.

---

The documentation for this class was generated from the following files:

• IdentifierField.h
• IdentifierField.cxx