5

I'm looking for an interval tree C# collection class.

I need to be able to add intervals, idealy 2D, otherwise perhaps I could combine two standard 1D interval trees.

I also need to be able to find out what intervals overlap a given interval.

I found this intervaltree.codeplex.com but

There are no downloads associated with this release.

edit:

Continue here: C# using others code

Community
  • 1
  • 1
alan2here
  • 3,223
  • 6
  • 37
  • 62
  • If the intervals are roughly the same and have a relatively small upper bound on the size you can get away with a simple 2D array. That's what I did in my RTS game a few years ago. – CodesInChaos Jan 07 '12 at 22:07
  • I've put a download file of the source in the download page. Hope it will now be easier. – Ido Ran Jul 02 '12 at 09:56

5 Answers5

7

I just wrote another implementation which can be found here: https://github.com/mbuchetics/RangeTree

It also comes with an asynchronous version which rebuilds the tree using the Task Parallel Library (TPL).

mbuchetics
  • 1,370
  • 1
  • 17
  • 34
4

There is a download on the codeplex page: http://intervaltree.codeplex.com/SourceControl/list/changesets -> Right hand side -> Download

ChrisWue
  • 18,612
  • 4
  • 58
  • 83
  • Thanks. That site is confusing. – alan2here Jan 07 '12 at 22:20
  • Additionally "Solution folders are not supported in this version of the application" so I can't open the project properly, but it seems three .cs files are important. Copying them into the project I want to use them in results in "Cannot autodetect which importer to use for "Interval.cs". There are no importers which handle this file type. Specify the importer that handles this file type in your project.". Any ideas beyond just copy + paste all the code from all files into the project I want to use the class in? – alan2here Jan 07 '12 at 22:24
  • @alan2here I did not have any problems opening the solution in VS 2010. – ChrisWue Jan 07 '12 at 22:38
  • I'm using Microsoft Visual C# 2010 Express. – alan2here Jan 07 '12 at 22:50
  • 1
    Maybe I need a question on detecting which importer to use for the three cs files. – alan2here Jan 07 '12 at 23:00
  • @alan2here It opens fine under VS2010 standard. The reference required in addition to the 3 .cs files is PowerCollections. – One-One Jan 11 '12 at 11:28
  • @desaivv Although the powercollections are not needed. .NET 4.0 brings it all out of the box. I submitted a patch which removes the dependencies – ChrisWue Jan 11 '12 at 17:49
  • Hi, I'm the developer of intervaltree.codeplex.com - If there is a problem with this project I'll be happy to help. Just open an issue on codeplex page or contact me directly. Ido. – Ido Ran Jul 01 '12 at 12:53
3

you can find another c# implementation for an interval tree (based on a self balancing avl tree) @ http://code.google.com/p/intervaltree/

cos
  • 97
  • 1
3

For future visitors, I've written an implementation as well https://github.com/vvondra/Interval-Tree

vvondra
  • 3,022
  • 1
  • 21
  • 34
3

Yet another implementation can be found at https://github.com/erdomke/RangeTree. Unlike other implementations, it aims to have an interface that is similar to IDictionary<TKey, TValue> where possible. It can be used as follows:

var tree = new RangeTree<int, string>()
{
    { 0, 10, "1" },
    { 20, 30, "2" },
    { 15, 17, "3" },
    { 25, 35, "4" },
};

// Alternatively, use the Add method, for example:
// tree.Add(0, 10, "1");

var results1 = tree[5]; // 1 item: [0 - 10] "1"
erdomke
  • 4,980
  • 1
  • 24
  • 30
  • I really appreciate the interface of this implementation, but it would be helpful if the project was on Nuget. – AAAton Mar 25 '19 at 15:02
  • There's already a nuget for it, @AAAton : https://www.nuget.org/packages/RangeTree/ – Tarc Feb 25 '22 at 19:55