Open sets backend

[elefthei]

We can take full advantage of the sequential structure of characters, skips and others in Reef and introduce Open sets.

  /// An Open set of ranges is an efficient representation for ranges of characters, integers etc
  /// that might or might not be closed. For example,
  /// { (0,3), (5,6), (8, *) }
  ///
  /// It implements the operations [union, negation, concatenation, unit, annhiliation]
  #[derive(Debug, Clone, Hash, PartialEq, Eq)]
  pub struct OpenRange<C> {
      pub start: C,
      pub end: Option<C>
  }
  
  #[derive(Debug, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]  
  pub struct OpenSet<C>(BTreeSet<OpenRange<C>>);  

Figure out a gadget for those, I think aggregate range proofs are a very good candidate for this. Or maybe argue in this issue why structure doesn't matter and it's all O(logn) in the end.

EDIT: reponening, this is used in section 4.6 of the Zombie paper and indeed shows promise

[elefthei]

Consider as an example the character class [A-Za-z]
Naively you can check c \in [A-Za-z] by verifying
(c - 'A')*(c - 'B')* ... *(c-'Z') *(c - 'a') * ... * (c-'z') = 0
which is the diminishing polynomial.
And nlookup can already do this in check logn where n is the polynomial degree.

Instead, their character class check takes log|Λ| constraints, and its for sure true that |Λ| > n for all n, so I think we do better than that and don't need to implement this.

[elefthei]

meh nlookup has big constants for hashing, so logn * 256 constraints