<p dir="auto">Based on my knowledge regarding BTrees (I know how they are built, how they work and I also know what a B+ tree is), which I know is by far not the best, I think you might really want to use a B+ Tree](<a href="https://en.wikipedia.org/wiki/B%2B_tree" rel="nofollow">https://en.wikipedia.org/wiki/B%2B_tree</a>) if you do not already.<br>
That would make the predecessor and successor methods currently discussed <a href="https://github.com/rust-lang/rfcs/pull/1195" data-hovercard-type="pull_request" data-hovercard-url="/rust-lang/rfcs/pull/1195/hovercard">here</a> quite fast with considerable memory-overhead, also it would make implementing iterators (and cursors) and therefore the range API a lot easier and probably faster.</p>
<p dir="auto">If I am missing something, please tell me.</p>
<p dir="auto">Looking through the rustc source code, it seems like many potential areas for typestate predicates involve cases where a value has an enum type and is known to be built with one of a subset of that enum type's constructors. I'm especially noticing this now that I'm going through and making all <code class="notranslate">alt</code>s exhaustive. For example:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="enum foo {bar, quux, baz}

fn whee(x: foo) -&gt; int {
  alt x {
     bar { 42 }
     _ { fail &quot;The impossible happened!&quot;; }
  }
}"><pre class="notranslate"><code class="notranslate">enum foo {bar, quux, baz}

fn whee(x: foo) -&gt; int {
  alt x {
     bar { 42 }
     _ { fail "The impossible happened!"; }
  }
}
</code></pre></div>
<p dir="auto">We'd like to give <code class="notranslate">whee</code> a type that says <code class="notranslate">x</code> must be constructed with constructor <code class="notranslate">bar</code> -- in other words, a type that's a refinement on <code class="notranslate">foo</code> -- so that we don't need to write the <code class="notranslate">fail</code> case (because we can statically check that <code class="notranslate">x</code> is in the right subset of <code class="notranslate">foo</code>). We can do this right now with typestate predicates. However, datasort refinements seem to be a common enough case that it might be worth treating them separately. Also, datasort refinements can be implemented without needing to worry about any of the purity issues that have made typestate difficult, because once something of <code class="notranslate">enum</code> type is constructed, its tag is immutable.</p>
<p dir="auto">The other reason to handle this separately from typestate is that the compiler never uses typestate information to eliminate any checks (since predicates may be unsound), whereas datasort refinements can be checked statically and used to eliminate unnecessary tests in <code class="notranslate">alt</code>s.</p>
<p dir="auto">Thoughts?</p>