I hate that warning when using C5 (HashSet).
Is it possible to fix that?

The C5 NuGet package does not work in mono 2.10.8.1. When I run the following test program:

using System;

namespace C5Test
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello world 1");
            C5.HashSet<int> x = new C5.HashSet<int>();
            Console.WriteLine ("Hello World 2");
            Console.ReadLine();
        }
    }
}

on mono 2.10.8.1 referencing C5 2.2.4881.16939, I get:

greg@Kubuntu:~/dev/MyMediaLite/src/C5Test/bin/Debug$ mono C5Test.exe
Could not load signature of C5.ICollectionValue`1[T]:Exists due to: 
Could not load signature of C5.ICollectionValue`1[T]:Exists due to: 

Unhandled Exception: System.TypeLoadException: A type load exception has occurred.
[ERROR] FATAL UNHANDLED EXCEPTION: System.TypeLoadException: A type load exception has occurred.                                                                
greg@Kubuntu:~/dev/MyMediaLite/src/C5Test/bin/Debug$ mono C5Test.exe            
Could not load signature of C5.ICollectionValue`1[T]:Exists due to:             
Could not load signature of C5.ICollectionValue`1[T]:Exists due to: 

Unhandled Exception: System.TypeLoadException: A type load exception has occurred.
[ERROR] FATAL UNHANDLED EXCEPTION: System.TypeLoadException: A type load exception has occurred.

When referencing the latest a version built from the latest git, I get:

greg@Kubuntu:~/dev/MyMediaLite/src/C5Test/bin/Debug$ mono C5Test.exe
Hello world 1
Missing method FirstOrDefault in assembly /home/greg/dev/MyMediaLite/src/C5Test/bin/Debug/C5.dll, type System.Linq.Enumerable

Unhandled Exception: System.IO.FileNotFoundException: Could not load file or assembly 'System.Core, Version=2.0.5.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e, Retargetable=Yes' or one of its dependencies.
File name: 'System.Core, Version=2.0.5.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e, Retargetable=Yes'
  at C5.HashSet`1[System.Int32]..ctor () [0x00000] in <filename unknown>:0 
  at C5Test.MainClass.Main (System.String[] args) [0x00000] in <filename unknown>:0 
[ERROR] FATAL UNHANDLED EXCEPTION: System.IO.FileNotFoundException: Could not load file or assembly 'System.Core, Version=2.0.5.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e, Retargetable=Yes' or one of its dependencies.
File name: 'System.Core, Version=2.0.5.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e, Retargetable=Yes'
  at C5.HashSet`1[System.Int32]..ctor () [0x00000] in <filename unknown>:0 
  at C5Test.MainClass.Main (System.String[] args) [0x00000] in <filename unknown>:0 

If I edit the C5 .csproj and replace

<Import Project="$(MSBuildExtensionsPath32)\Microsoft\Portable\$(TargetFrameworkVersion)\Microsoft.Portable.CSharp.targets" />

with

<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />

to make it a non-PCL project and recompile and have my test program reference the resulting dll, the test program works as expected.

I get the same results with mono 2.10.8 on Windows. If I use mono 3.0.10 on Windows instead, everything works.

This all leads me to believe that mono does not support PCL libraries until somewhere between 2.10.8.1 and 3.0.10. Ubuntu 13.10 Saucy Salamander comes out in 4 days and is still on mono 2.10.8.1.

Could C5 offer a non-PCL net40 build in the NuGet package or a separate non-PCL package or something? I am attempting to package MyMediaLite for NuGet. I switched MyMediaLite from storing dependencies in a lib folder to using NuGet packages so that it can declare dependencies, which involved upgrading C5 because the version MyMediaLite previously used is older than the oldest C5 Nuget package.

Support for MyMediaLite on Linux is a priority, especially because the primary developer works in Linux, and we cannot realistically claim support for Linux if it does not work on the latest version of the most popular distro. I'd like to avoid creating an unofficial non-PCL C5 package just so MyMediaLite can depend on it or bundling a non-PCL C5 inside the MyMediaLite package if possible.

C5 cannnot be added through nuget to a Portable Library project. Since it looks like the C5 library is built as a Portable Library, this should be possible by adding C5 to the parent "lib" folder in the nuget package:

...
<file src="bin\Release\*.dll" target="lib\" /> <file src="bin\Release\*.pdb" target="lib\" /> <file src="bin\Release\*.xml" target="lib\" />
...

Let me know if I can help out -- great project!

David Faivre

C5 2.4.5891.40110 (NuGet)
Net 4.5.2

The full log is:

Successfully installed 'C5 2.2.5073.27396'.
Successfully uninstalled 'C5 2.2.5073.27396'.
Install failed. Rolling back...
Could not install package 'C5 2.2.5073.27396'. You are trying to install this package into a project that targets '.NETFramework,Version=v4.5', but the package does not contain any assembly references that are compatible with that framework. For more information, contact the package author.

The current file version is 2.4.0.0 and the assembly something like 2.4.59...

Our deployed app seems to have a problem in loading the assembly because of this. We keep getting the error "The located assembly's manifest definition does not match the assembly reference" on runtime.

I have a C5.TreeSet<double>

Given a value x, I'd like to search the set S for the greatest index i such S[j] <= x for all j ≤ i (similar to Python's bisect.bisect). How can I do that?

I was previously using List<T> with BinarySearch

Reproduced from http://stackoverflow.com/questions/30624322/how-to-search-c5-treeset

.NET 4.5 introduced a new interface IReadOnlyList<T> https://msdn.microsoft.com/en-us/library/hh192385%28v=vs.110%29.aspx

Represents a read-only collection of elements that can be accessed by index.

This is analogous to C5's IIndexed<T>

A sequenced collection, where indices of items in the order are maintained

I think C5.IIndexed<T> should implement IReadOnlyList<T>.

When I try to use the bracket operator with an IDictionary or a HashDictionary, e.g.:

            var myDict = new HashDictionary<String, String>();
            myDict["foo"] = "bar";

it compiles fine, but the editor gives me a wavy line and the above error. I'm guessing this is a problem with my tools, more than the library, but have you seen it and/or do you have any idea how to fix it? I can work around it with Find() and UpdateOrAdd(), but the bracket syntax would be a lot nicer.

I'm using version 2.1.4492.18142, from NuGet, with VS 2010, C# 4.0, and Resharper.

GuardedDictionary implements the Keys property as 'return dict.Keys;' with a TODO:
//TODO: guard with a read-only wrapper? Probably so!

GuardedSortedDictionary implements the Keys property as 'return null;'

The implementations should be fixed, in particular the one in GuardedSortedDictionary.

The implementations should probably wrap the keys of the wrapped dictionary in a GuardedCollection / GuardedSorted.

Reading through the documentation and O(log n) performance for doing this[i] on a sorted array doesn't seem right. Shouldn't indexed access to an array be O(1)?

C5 HashedLinkedList raises an assertion error at the method splittaggroup when adding lots of elements. In the attached image example, the list had close to 4 million integers.

As the debugger shows, previous-taggroup-tag (ptgt) is equal to int.MaxValue - 1 and next-taggroup-tag (ntgt) is equal to int.MaxValue. So those values do not verify the assertion that ptgt + 1 <= ntgt - 1.

"The C5 Generic Collection Library for C# and CLI" technical report states at section 13.8 Implementation of hashed linked lists:

Note, however, that the typical case of always inserting at the end of the list seems to be close to the worst-case scenario for maintaining the tags.

That is the case.

You can run this simple program that tries to reproduce this error: https://github.com/ovidiomanteiga/C5HashedLinkedListAssertionError

What is the state of this project?

The #warning tags included by the devs in the source code indicating incorrect behavior and suspicions isn't particularly confidence inspiring given there haven't been any updates in a long time.

I would likr\e to port this Generic Collection to Java if it is ok with the author.

Hi,
I have tried to open the project in VS2010. It won't load the main project with reagard to its project type. What kind of project is it?

Description

SortedDictionaryBase<K,V> currently has FindMin/Max() and DeleteMin/Max(). These work on single items, but it would be useful to have range variants to efficiently get multiple items at once.

Solution

Add variants, such as FindMinRange(int numItems) and DeleteMinRange(int numItems).

Describe alternatives you've considered

For DeleteMinRange(), one could call DeleteMin() multiple times. But this is likely is not as efficient as a range implementation which can perform the entire operation at once.
For FindMinRange(), calling FindMin() multiple times wouldn't work. One could workaround this by calling RangeAll() and iterating through that. But that seems roundabout and is not immediately obvious.
There are also the RangeFrom(K bot) and RangeTo(K top), but those don't allow specifying numItems as a parameter. 

Additional context

Eventually, these variants could be added to PriorityQueue<T> as well. But implementing it in IntervalHeap<T> will take some effort. 

Similart to #23, should be as simple as creating a new folder in your NuGet package called portable-net45+netcore45+wpa81+MonoAndroid1+MonoTouch

Hi,

I went over relevant sections in the doc but still a bit confused about this. Can I have one (and only one) thread updating tree while multiple other threads reading it snapshot?

Thanks

Hi,

I am trying to use your library in my unity game.
I copied the CS folder in my project, and it seems to be working well, but I get this two compilation errors.

Assets/C5/IReadOnlyCollection.cs(8,22): error CS1961: The covariant type parameter T' must be invariantly valid onSystem.Collections.Generic.IReadOnlyCollection'

Assets/C5/IReadOnlyList.cs(8,22): error CS1961: The covariant type parameter T' must be invariantly valid onSystem.Collections.Generic.IReadOnlyList'

Thanks for advance.

when open solution using vs2010, c5 project load failed, said that "the project type is not supported by this installation"

Check the comments here and here.

It would be great if the NuGet packages had xmldoc files.

The old C5 library documentation states that the collections are all serializable via the binary formatter. Has this been deliberately changed for the newer C5 library?

I don't want to sound like I'm looking a gift-horse in the mouth, after all entire library is being given to us for free, but I have to say that I'm disappointed in the fact that the time-space complexity of the data structures is not documented. To me, that would be the first thing someone will look at. Like, if I look at, for instance, a hashed linked lists, it would be nice if it said what the cost is for look ups, insertion, etc. That's one of the main criterion for selecting a data-structure.

Hi. This appears to be a fantastic library, but where is the documentation?

The homepage at http://www.itu.dk/research/c5/ links to detailed documentation for "Version 1.1.0 of 2008-02-10" . Where is the documentation for the current major version (version 2)?

I'm a bit annoyed currently because this page tells me to "use Sandcastle to build the documentation".

Nice sentiment when information on how to actually use that is a bit sparse. Not to mention that using the included Sandcastle project file results in this:

 SHFB: Warning BE0006: Unable to locate any documentation sources for 'C:\Users\xxxx\C5-master\C5\bin\Release\C5.dll' (Configuration: Debug Platform: AnyCPU)

Hi guys. After downloading the code, i tried to open the solution in VS 2015 but no project was loaded.Is there a brach that can be open with that version of microsoft VS ? Thanks.

Statement of the question.

Why do you use deprecated out- and ref-parameters to return values? «Framework Design Guidelines» say:
http://msdn.microsoft.com/en-us/library/ms182146.aspx
http://msdn.microsoft.com/en-us/library/ms182131.aspx

In the methods like Find(...) a preferred interface is an option type (maybe monad): http://en.wikipedia.org/wiki/Option_type. This is a way it is done in standard libraries of functional programming languages. It really gives far more easy-to-use API!

After a certain (rather long) sequence of Add/Replace/DeleteMin operations, FindMin() will return an incorrect item (ie. there is a smaller value in the heap than the one returned). Additionally, Check() returns false, suggesting that the heap has been corrupted.

I am using revision: fc2109e
The sequence of operations which breaks it: https://dl.dropboxusercontent.com/u/9116381/BreakIntervalHeap.cs

Hi!

Can't find anything about thread safety in the documentation. Are all collections thread safe or not? Especially I'm interested in IntervalHeap.

Hi Guys,

I've noticed a few collections are inconsistent whether they define a default constructor or not, this can have implications for things like the new() generic constraint.

I've created a patch that adds a default constructor to the ones that I found were missing, diff attached.

[default_constructor.diff.txt]
(https://github.com/sestoft/C5/files/1680304/default_constructor.diff.txt)
[default_constructor.diff.txt]

I get the following message when trying to install your package in a portable project targeting .NET 4.5.

AFAIK the fix is to create a new folder in your nuget lib folder named portable-net45+win+wpa81+wp80 and drop the C5.dll in it before publishing it again.

Installing 'C5 2.3.0.1'.
Successfully installed 'C5 2.3.0.1'.
Adding 'C5 2.3.0.1' to Provision.Core.
Uninstalling 'C5 2.3.0.1'.
Successfully uninstalled 'C5 2.3.0.1'.
Install failed. Rolling back...
Could not install package 'C5 2.3.0.1'. 
You are trying to install this package into a project that targets 'portable-net45+win+wpa81+wp80', 
but the package does not contain any assembly references or content files that are compatible with that framework. 
For more information, contact the package author.

The MoveNextAfterUpdate() test in ArrayListTest seems to contain a mistake causing it to test the wrong thing:

[Test]
public void MoveNextAfterUpdate()
{
    list.Add(5);
    list.Add(8);
    list.Add(5);

    SCG.IEnumerator<int> e = list.GetEnumerator();

    e.MoveNext();
    list.Add(99); // <-- Bug: this should be Update()
    Assert.Throws<CollectionModifiedException>(() => e.MoveNext());
}

The test checks if calling Add() makes the enumerator fail. It should probably be a call to Update() instead.

I'm not sure if this mistake has been duplicated elsewhere.

I have SP1 installed, PLT just doesn't recognize it.
Also, I have the Express Editions installed so some extensions don't work for me anyway.

I get this error message after an attempt to build the library:

Error Cannot infer TargetFrameworkIdentifier and/or TargetFrameworkVersion from TargetFramework='portable-net40+sl50+win8+wpa81+wp8'. They must be specified explicitly. C5 C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\MSBuild\Sdks\Microsoft.NET.Sdk\build\Microsoft.NET.TargetFrameworkInference.targets 84

Please, any tip to build the library ?

Thanks.

Originally submitted by Erik Meijer, Microsoft, on 20120422. Complicated-looking code using TreeBag and snapshots failed, data structure was inconsistent with tree.size and root.size disagreeing.

Investigations show that Add has never been able to increased item multiplicity beyond 1, because the assignment "root = cursor;" had been left out in the addIterative method of the Bag version of the tree data structure. Fixed on github.

A subtle bug in ArrayBase<T> will cause an infinite loop when adding very large enumerables to array-based collections. The bug can be triggered by the following code:

var arrayList = new ArrayList<bool>();
var items = new bool[(1 << 30) + 1]; // 2^30 + 1 = 1,073,741,825
arrayList.AddAll(items);

The problem arises when the large array is added to the list. In order for ArrayList<T>, which inherits from ArrayBase<T>, to add the very large enumerable, it must first allocate an array big enough to contain all the enumerable's items. The expand() method in ArrayBase<T> is used to enlarge the underlying array:

protected virtual void expand(int newcapacity, int newsize)
{
    System.Diagnostics.Debug.Assert(newcapacity >= newsize);
    int newlength = array.Length;

     while (newlength < newcapacity) newlength *= 2;

     T[] newarray = new T[newlength];

     Array.Copy(array, newarray, newsize);
     array = newarray;
}

ArrayBase<T> stores its items in array, whose length is always a positive power of two.
The method is called with the required capacity and the collection's current count – in the example above, newcapacity is 2^30 + 1 and newsize is 0. The method will take the current size of the array and double it until it is not less than the required capacity.

The problem arises when we double the integer newlength for long enough. When newlength is 2^30 and still less than newcapacity, it is doubled, giving an expected value of 2^31. The integer range in C#, however, is -2,147,483,648 (-2^31) to 2,147,483,647 (2^31 - 1), which causes newlength to overflow. Doubling the integer again makes it zero. The loop condition is now always true, since newlength remains zero even when doubled.

The easiest solution is probably to wrap the multiplication in checked:

protected virtual void expand(int newcapacity, int newsize)
{
    System.Diagnostics.Debug.Assert(newcapacity >= newsize);
    int newlength = array.Length;

     while (newlength < newcapacity)
         newlength = checked(newlength * 2);

     T[] newarray = new T[newlength];

     Array.Copy(array, newarray, newsize);
     array = newarray;
}

When the multiplication causes an overflow, an OverflowException is thrown. This does not fix the problem, but it does ensure that the problem does not go unnoticed.

Result StackTrace:

at C5.CollectionBase`1.modifycheck(Int32 thestamp)
   at C5.TreeSet`1.Enumerator.MoveNext()
   at C5.DictionaryBase`2.ValuesCollection.ValueEnumerator.MoveNext()
   at System.Linq.Enumerable.LastOrDefault[TSource](IEnumerable`1 source)

When I updated my C5 nuget from Dec 16th to Feb 17th (first of the day) I get this error when running unit tests.

EDIT: See next comment for an example.

The collection being used is TreeDictionary<,>.
Order of events: TreeDictionary uses default empty constructor.
TreeDictionary.Contains() called twice, returning false each time.
TreeDictionary.UpdateOrAdd() is called 10 times. Successful add each time.

Values.Count() and Keys.Count() is queried once each.

Values.LastOrDefault is called once.
UpdateOrAdd() is called again.

Values.LastOrDefault() is called again. This call then throws the exception.

I decided to look through the github changes (there are lots of non-code changes), and then a whole bunch of 'Sorry, we could not display the changes to this file because there were too many other changes to display.'

I'm going to keep looking, if I find the cause I'll post back here.

Seems reasonable to expect a "Set" to implement System.Collections.Generic.ISet, especially since the TreeSet in Java does just that. Is there any particular reason why that was left out?

Even though C5 will compile successfully for a Windows 10 UWP, attempting to build a store package using .NET Native compilation will result in an Infinite Expansion exception that leads to an overflow.

I realize Windows 10 support is not listed here, but wanted to make sure you guys are aware of the issue.

In ArrayListTest events are not properly tested. The method listen() only adds event handlers to the Added event, thereby ignoring all other events:

private void listen() {
    seen.Listen(list, EventTypeEnum.Added);
}

This is correctly done in the HashedArrayListTest class:

private void listen() {
    seen.Listen(list, EventTypeEnum.All);
}

Be aware that fixing the listen() method will cause the Listenable() test to fail. It can, however, easily be fixed by inlining the method:

[Test]
public void Listenable()
{
    Assert.AreEqual(EventTypeEnum.All, list.ListenableEvents);
    Assert.AreEqual(EventTypeEnum.None, list.ActiveEvents);
    seen.Listen(list, EventTypeEnum.Added); // <-- Bug fix
    Assert.AreEqual(EventTypeEnum.Added, list.ActiveEvents);
}

Hi. Could you clarify (in the readme, and the Nuget page) exactly what the "BSD-style license" is? This might sound pernickety, but it's helpful to using the library at companies that are particular about open source (we have a set list of licences).

https://www.nuget.org/packages/C5

I'm not exactly sure why, but the error goes away when you click on the DLL, then change the CPU to x86 in Platform Settings, under the tab that has the Unity logo. Maybe that's just a requirement, and if so might be worth an update to the README.

Unhandled Exception: System.Reflection.ReflectionTypeLoadException: The classes in the module cannot be loaded.
  at (wrapper managed-to-native) System.Reflection.Assembly:GetTypes (bool)
  at System.Reflection.Assembly.GetTypes () [0x00000] in <filename unknown>:0 
  at Mono.CSharp.RootNamespace.ComputeNamespaces (System.Reflection.Assembly assembly, System.Type extensionType) [0x00000] in <filename unknown>:0 
  at Mono.CSharp.RootNamespace.ComputeNamespace (Mono.CSharp.CompilerContext ctx, System.Type extensionType) [0x00000] in <filename unknown>:0 
  at Mono.CSharp.GlobalRootNamespace.ComputeNamespaces (Mono.CSharp.CompilerContext ctx) [0x00000] in <filename unknown>:0 
  at Mono.CSharp.Driver.LoadReferences () [0x00000] in <filename unknown>:0 
  at Mono.CSharp.Driver.Compile () [0x00000] in <filename unknown>:0 
  at Mono.CSharp.Driver.Main (System.String[] args) [0x00000] in <filename unknown>:0 

Missing method .ctor in assembly /Users/Keith/Code/astar-unity/Assets/C5.dll, type System.Runtime.Versioning.TargetFrameworkAttribute
The class System.Runtime.Versioning.TargetFrameworkAttribute could not be loaded, used in C5
Can't find custom attr constructor image: /Users/Keith/Code/astar-unity/Assets/C5.dll mtoken: 0x0a0009bf

Hi,

Can you please update the Nuget?

This project already has a working appveyor.yml file. So this should be as easy as setting up an appveyor account (free) and adding this project.

Hi,

Glad you put it up on github in the end! :)

When using the nuget, there are no xml files in the package. There should be XML files so that we can get intellisense documentation for methods and types.

Regards

the C5 NuGet package should be signed. Otherwise, it can't be used in a strongly named assembly

The README says to build for Mono with:

xbuild C5.Mono.csproj

Unfortunately there isn't a C5.Mono.csproj file in the repo.

Description

When Importing C5 into Unity 2019.3 a whole slew of errors occur. I've seen references that c5 is/was actually compatible with Unity and I even have access to an older c5.dll that works, but was hoping to get this into Unity

Solution

Version of c5 that is able to be integrated into Unity