title: Why SortedSet<T>.GetViewBetween isn't O(log N)?
body: <p>In .NET 4.0+, a class <code>SortedSet&lt;T&gt;</code> has a method called <code>GetViewBetween(l, r)</code>, which returns an interface view on a tree part containing all the values between the two specified. Given that <code>SortedSet&lt;T&gt;</code> is implemented as a red-black tree, I naturally expect it to run in <code>O(log N)</code> time. The similar method in C++ is <code>std::set::lower_bound/upper_bound</code>, in Java it's <code>TreeSet.headSet/tailSet</code>, and they are logarithmic.</p>
  
  <p>However, that is not true. The following code runs in 32 sec, whereas the equivalent <code>O(log N)</code> version of <code>GetViewBetween</code> would make this code run in 1-2 sec.</p>
  
  
  
  <pre class="lang-cs prettyprint-override"><code>var s = new SortedSet&lt;int&gt;();
  int n = 100000;
  var rand = new Random(1000000007);
  int sum = 0;
  for (int i = 0; i &lt; n; ++i) {
      s.Add(rand.Next());
      if (rand.Next() % 2 == 0) {
          int l = rand.Next(int.MaxValue / 2 - 10);
          int r = l + rand.Next(int.MaxValue / 2 - 10);
          var t = s.GetViewBetween(l, r);
          sum += t.Min;
      }
  }
  Console.WriteLine(sum);
  </code></pre>
  
  <p>I decompiled System.dll using <a href="http://www.jetbrains.com/decompiler/" rel="noreferrer">dotPeek</a> and here's what I got:</p>
  
  <pre class="lang-cs prettyprint-override"><code>public TreeSubSet(SortedSet&lt;T&gt; Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)
      : base(Underlying.Comparer)
  {
      this.underlying = Underlying;
      this.min = Min;
      this.max = Max;
      this.lBoundActive = lowerBoundActive;
      this.uBoundActive = upperBoundActive;
      this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
      this.count = 0;
      this.version = -1;
      this.VersionCheckImpl();
  }
  
  internal SortedSet&lt;T&gt;.Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
  {
    SortedSet&lt;T&gt;.Node node = this.root;
    while (node != null)
    {
      if (lowerBoundActive &amp;&amp; this.comparer.Compare(from, node.Item) &gt; 0)
      {
        node = node.Right;
      }
      else
      {
        if (!upperBoundActive || this.comparer.Compare(to, node.Item) &gt;= 0)
          return node;
        node = node.Left;
      }
    }
    return (SortedSet&lt;T&gt;.Node) null;
  }
  
  private void VersionCheckImpl()
  {
      if (this.version == this.underlying.version)
        return;
      this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
      this.version = this.underlying.version;
      this.count = 0;
      base.InOrderTreeWalk((TreeWalkPredicate&lt;T&gt;) (n =&gt;
      {
        SortedSet&lt;T&gt;.TreeSubSet temp_31 = this;
        int temp_34 = temp_31.count + 1;
        temp_31.count = temp_34;
        return true;
      }));
  }
  </code></pre>
  
  <p>So, <code>FindRange</code> is obviously <code>O(log N)</code>, but after that we call <code>VersionCheckImpl</code>... which does a linear-time traversal of the found subtree only for recounting its nodes!</p>
  
  <ol>
  <li>Why would you need to do that traversal all the time?</li>
  <li>Why .NET does not contain a <code>O(log N)</code> method for splitting a tree based on key, like C++ or Java? It is <em>really</em> helpful in lots of situations.</li>
  </ol>