Immutable Datastructures

[David Schmitt]

Hi,

I was looking for a library of immutable .net data structures, but
haven't found anything usable except a few interesting blog posts like
those listed in [1].

Failing to find an project already supporting immutability, I was
looking for a place where I could collaborate on such data structures
and found the NGenerics project.

Would you be interested in such things?

Regards, David Schmitt

[1]http://weblogs.asp.net/bleroy/archive/2008/01/16/immutability-in-c.aspx

[rhanekom]

Hi David

We'll definitely be interested in implementing a couple of those -
Huseyn (part of our team), suggested lock-free data structures a while
back.

What do you have in in mind as a starting point?

Riaan

[David Schmitt]

rhanekom wrote:
> Hi David
>
> We'll definitely be interested in implementing a couple of those -
> Huseyn (part of our team), suggested lock-free data structures a while
> back.
>
> What do you have in in mind as a starting point?

An immutable Stack would be an obvious first, as there are already
example implementations out there.

The use case I was researching where immutable Lists/Arrays, which I
currently work around by using ReadOnlyCollection(elements.ToList()).
But I'm very unsatisfied by the IList.IsReadOnly stuff and I would like
to avoid copying the data around.

Finally, immutable Pairs and Triples would also make a nice and simple
addition to provide basic structures.

Regards, David

[husayt]

Hi,
David, if you are looking for collaboration here NGenerics is the
place. Ryaan and the rest of us at NGenerics are very keen at making
this library more useful and will welcome anybody with fresh and
valuable inputs.

Yes, indeed, I was very interested in thread-safe standard data
structures (stacks, lists,queues). But now there is a Task Parallel
Library (TPL - http://en.wikipedia.org/wiki/Task_Parallel_Library#TPL),
which you can already use and is going to be included with .Net 4.0

They have Concurrent Collections there (http://msdn.microsoft.com/en-
us/library/dd460718%28VS.100%29.aspx). So things like stacks, queues,
lists and dictionaries are already implemented (http://
msdn.microsoft.com/en-us/library/system.collections.concurrent%28VS.
100%29.aspx).

When you have officially supported MS classes it wouldn't make sense
for NGenerics to do the same structures, UNLESS our implementation
adds some extra value.

Certainly, going forward it is important to add immutable counterparts
to Ngenerics own data structures and also to other ones MS not going
to cover.

There is a very nice overview of all the various immutable classes and
issues in this blog. (http://blogs.msdn.com/ericlippert/archive/tags/
Immutability/default.aspx) I would recommend to read the comments as
well.

So as a first step we can open Immutable or ThreadSafe namespace and
we (including David) can add our suggested implementations.

Regards,
Huseyn

[David Schmitt]

husayt wrote:
> Yes, indeed, I was very interested in thread-safe standard data
> structures (stacks, lists,queues). But now there is a Task Parallel
> Library (TPL - http://en.wikipedia.org/wiki/Task_Parallel_Library#TPL),
> which you can already use and is going to be included with .Net 4.0
>
> They have Concurrent Collections there (http://msdn.microsoft.com/en-
> us/library/dd460718%28VS.100%29.aspx). So things like stacks, queues,
> lists and dictionaries are already implemented (http://
> msdn.microsoft.com/en-us/library/system.collections.concurrent%28VS.
> 100%29.aspx).
>
> When you have officially supported MS classes it wouldn't make sense
> for NGenerics to do the same structures, UNLESS our implementation
> adds some extra value.

My main motivation is being able to be able "talk" about data that
doesn't change in my code. Being thread safe alone doesn't give me that
guarantee: most tread-safe data is mutable. Using ReadOnlyCollection<>
doesn't give me that guarantee, since the underlying collection can
still be mutated.

> Certainly, going forward it is important to add immutable counterparts
> to Ngenerics own data structures and also to other ones MS not going
> to cover.
>
> There is a very nice overview of all the various immutable classes and
> issues in this blog. (http://blogs.msdn.com/ericlippert/archive/tags/
> Immutability/default.aspx) I would recommend to read the comments as
> well.

That was already on my reading list. Besides the interesting technical
content, the comments are a big warning that immutability is still a
confusing topic for many.

> So as a first step we can open Immutable or ThreadSafe namespace and
> we (including David) can add our suggested implementations.

I've attached a first shot at an immutable Pair with value semantics
That is, a Pair(3,4) is Equal() to all other Pair instances containing
(3,4).

The next step would probably a Triple and then an immutable array.

I'm looking forward to your feedback!

Regards, DavidS

[husayt]

Hi David,
sorry for late reply. I fully agree with your point and also believe
that immutable data structures are niche fit for NGenerics. Your code
and codestyle from what I see agree with rules of of NGeenerics,
especially I like that they all come with unit tests. So they can go
to repository as they are.

I had a chat with fellow members and we would like to invite you to
become contributing member of NGenerics project along with us. If you
accept this, I will arrange a svn access for you and you can then go
forward and add the code above to Immmutable namespace.

Looking forward for your reply.

All the best.
Huseyn

On Oct 10, 12:33 pm, David Schmitt <da...@dasz.at> wrote:
> husayt wrote:
> > Yes, indeed, I was very interested in thread-safe standard data
> > structures (stacks, lists,queues). But now there is a Task Parallel

> > Library (TPL -http://en.wikipedia.org/wiki/Task_Parallel_Library#TPL),

> [PairTest.cs4K ]/*  
>   Copyright 2009 David Schmitt <da...@dasz.at> (http://dasz.at/)
>
>  This program is licensed under the GNU Lesser General Public License (LGPL).  You should
>  have received a copy of the license along with the source code.  If not, an online copy
>  of the license can be found athttp://www.gnu.org/copyleft/lesser.html.
> */
>
> using System;
> using NGenerics.DataStructures.General;
> using NUnit.Framework;
>
> namespace NGenerics.Tests.DataStructures.General
> {
>     [TestFixture]
>     public class PairTest
>     {
>         [TestFixture]
>         public class Construction
>         {
>             private static void construct_and_test<T>(T a, T b)
>             {
>                 var pair = new Pair<object>(a, b);
>                 Assert.AreEqual(pair.A, a);
>                 Assert.AreEqual(pair.B, b);
>             }
>
>             [Test]
>             public void with_values()
>             {
>                 construct_and_test(6, 11);
>             }
>
>             [Test]
>             public void with_references()
>             {
>                 construct_and_test(new object(), new object());
>             }
>
>             [Test]
>             public void with_nulls()
>             {
>                 construct_and_test(null, new object());
>                 construct_and_test(new object(), null);
>                 construct_and_test<object>(null, null);
>             }
>         }
>
>         [TestFixture]
>         public class Equality
>         {
>             private static void compare<T>(T a, T b)
>             {
>                 var pairab1 = new Pair<T>(a, b);
>                 var pairab2 = new Pair<T>(a, b);
>                 var pairba = new Pair<T>(b, a);
>
>                 // copy of the reference to avoid warnings
>                 var pairab1ref = pairab1;
>
>                 Assert.AreEqual(pairab1, pairab1);
>                 Assert.AreEqual(pairab1, pairab2);
>                 Assert.AreEqual(pairab2, pairab1);
>                 Assert.AreNotEqual(pairab1, pairba);
>
>                 Assert.IsTrue(pairab1 == pairab1ref);
>                 Assert.IsTrue(pairab1 == pairab2);
>                 Assert.IsTrue(pairab2 == pairab1);
>                 Assert.IsFalse(pairab1 == pairba);
>
>                 Assert.IsFalse(pairab1 != pairab1ref);
>                 Assert.IsFalse(pairab1 != pairab2);
>                 Assert.IsFalse(pairab2 != pairab1);
>                 Assert.IsTrue(pairab1 != pairba);
>
>                 Assert.AreEqual(pairab1.GetHashCode(), pairab1.GetHashCode());
>                 Assert.AreEqual(pairab1.GetHashCode(), pairab2.GetHashCode());
>             }
>
>             [Test]
>             public void with_values()
>             {
>                 compare(6, 11);
>             }
>
>             [Test]
>             public void with_references()
>             {
>                 compare(new object(), new object());
>             }
>
>             [Test]
>             public void with_nulls()
>             {
>                 compare(null, new object());
>                 compare(new object(), null);
>             }
>         }
>
>         [TestFixture]
>         public class Transformations
>         {
>             private static void reverse<T>(T a, T b)
>             {
>                 var pair = new Pair<T>(a, b);
>
>                 Assert.AreEqual(pair.Reverse().A, b);
>                 Assert.AreEqual(pair.Reverse().B, a);
>             }
>
>             [Test]
>             public void TestReverse()
>             {
>                 reverse(6, 11);
>                 reverse(new object(), new object());
>                 reverse(null, new object());
>                 reverse(new object(), null);
>                 reverse<object>(null, null);
>             }
>
>             [Test]
>             [ExpectedException(typeof(ArgumentNullException))]
>             public void TestReverseNull()
>             {
>                 PairExtensions.Reverse<object>(null);
>             }
>
>             private static void keyvaluepair<T>(T a, T b)
>             {
>                 var pair = new Pair<T>(a, b);
>                 var kvpair = new System.Collections.Generic.KeyValuePair<T, T>(a, b);
>
>                 Assert.AreEqual(pair.ToKeyValuePair(), kvpair);
>             }
>
>             [Test]
>             public void TestToKeyValuePair()
>             {
>                 keyvaluepair(6, 11);
>                 keyvaluepair(new object(), new object());
>                 keyvaluepair(null, new object());
>                 keyvaluepair(new object(), null);
>                 keyvaluepair<object>(null, null);
>             }
>
>             [Test]
>             [ExpectedException(typeof(ArgumentNullException))]
>             public void TestToKeyValuePairNull()
>             {
>                 PairExtensions.ToKeyValuePair<object>(null);
>             }
>         }
>     }
>
>
>
> }
>
>
>
> [Pair.cs7K ]/*  
>   Copyright 2009 David Schmitt <da...@dasz.at> (http://dasz.at/)
>
>  This program is licensed under the GNU Lesser General Public License (LGPL).  You should
>  have received a copy of the license along with the source code.  If not, an online copy
>  of the license can be found athttp://www.gnu.org/copyleft/lesser.html.
> */
>
> using System;
> using NGenerics.Util;
>
> namespace NGenerics.DataStructures.General
> {
>     /// <summary>
>     /// An immutable class representing a pair of values with value semantics.
>     /// </summary>
>     /// <typeparam name="T">The type of object the pair contains.</typeparam>
> #if (!SILVERLIGHT)
>     [Serializable]
> #endif
>     public class Pair<T>
>     {
>         #region Globals
>
>         private readonly T a;
>         private readonly T b;
>
>         #endregion
>
>         #region Construction
>
>         /// <param name="a">The first value.</param>
>         /// <param name="b">The other value.</param>
>         public Pair(T a, T b)
>         {
>             this.a = a;
>             this.b = b;
>         }
>
>         #endregion
>
>         #region Public Members
>
>         /// <summary>
>         /// Gets the A-half of this <see cref="Pair{T}"/>.
>         /// </summary>
>         /// <value>The A-half.</value>
>         public T A
>         {
>             get
>             {
>                 return this.a;
>             }
>         }
>
>         /// <summary>
>         /// Gets the B-half of this <see cref="Pair{T}"/>.
>         /// </summary>
>         /// <value>The B-half.</value>
>         public T B
>         {
>             get
>             {
>                 return this.b;
>             }
>         }
>
>         #endregion
>
>         #region Object Overrides
>
>         /// <summary>
>         /// Creates a user-readable string representation of this Pair.
>         /// </summary>
>         /// <returns>A user-readable string.</returns>
>         public override string ToString()
>         {
>             return String.Format("({0}, {1})", this.a, this.b);
>         }
>
>         /// <summary>
>         /// Compares this Pair to another Pair, based on their parts.
>         /// </summary>
>         /// <param name="obj">The object to compare to.</param>
>         /// <returns>If the <paramref name="obj"/> is a pair of the same objects as this pair, returns true. Returns false otherwise.</returns>
>         public override bool Equals(object obj)
>         {
>             // shortcut reference equality
>             if (Object.ReferenceEquals(this, obj))
>             {
>                 return true;
>             }
>
>             var other = obj as Pair<T>;
>
>             if (other == null)
>             {
>                 return false;
>             }
>
>             return Object.Equals(this.a, other.a) && Object.Equals(this.b, other.b);
>         }
>
>         /// <summary>
>         /// Calculates a hash code from this pair's constituents.
>         /// </summary>
>         /// <returns>A hashcode suitable for use in Hastables and similar structures.</returns>
>         public override int GetHashCode()
>         {
>             return (Object.ReferenceEquals(this.a, null) ? 0 : this.a.GetHashCode())
>                 ^ (Object.ReferenceEquals(this.b, null) ? 0 : this.b.GetHashCode());
>         }
>
>         /// <summary>
>         /// Compares the two Pairs based on their constituents.
>         /// </summary>
>         /// <param name="left">The first element to compare.</param>
>         /// <param name="right">The second element to compare.</param>
>         /// <returns>true, if both pairs have the same contents; false,otherwise.</returns>
>         public static bool operator ==(Pair<T> left, Pair<T> right)
>         {
>             // shortcut reference equality
>             if (Object.ReferenceEquals(left, right))
>             {
>                 return true;
>             }
>
>             return Object.ReferenceEquals(left, null) || left.Equals(right);
>         }
>
>         /// <summary>
>         /// Compares the two Pairs based on their constituents.
>         /// </summary>
>         /// <param name="left">The first element to compare.</param>
>         /// <param name="right">The second element to compare.</param>
>         /// <returns>false, if both pairs have the same contents; true,otherwise.</returns>
>         public static bool operator !=(Pair<T> left, Pair<T> right)
>         {
>             return !(left == right);
>         }
>
>         #endregion
>     }
>
>     /// <summary>
>     /// A few utility methods that do not need access to the private state of a <see cref="Pair{T}"/>.
>     /// </summary>
>     public static class PairExtensions
>     {
>         /// <summary>
>         /// Creates a new <see cref="Pair{T}"/> with A and B switched.
>         /// </summary>
>         /// <typeparam name="T">The type contained in the <see cref="Pair{T}"/>.</typeparam>
>         /// <param name="self">The pair whose constituents are used. May not be null.</param>
>         /// <returns></returns>
>         public static Pair<T> Reverse<T>(this Pair<T> self)
>         {
>             Guard.ArgumentNotNull(self, "self");
>
>             if (Object.Equals(self.A, self.B))
>             {
>                 return self;
>             }
>             else
>             {
>                 return new Pair<T>(self.B, self.A);
>             }
>         }
>
>         public static System.Collections.Generic.KeyValuePair<T, T> ToKeyValuePair<T>(this Pair<T> self)
>         {
>             return new System.Collections.Generic.KeyValuePair<T, T>(self.A, self.B);
>         }
>     }
>
>
>
> }

[David Schmitt]

husayt wrote:
> Hi David,
> sorry for late reply. I fully agree with your point and also believe
> that immutable data structures are niche fit for NGenerics. Your code
> and codestyle from what I see agree with rules of of NGeenerics,
> especially I like that they all come with unit tests. So they can go
> to repository as they are.
>
> I had a chat with fellow members and we would like to invite you to
> become contributing member of NGenerics project along with us. If you
> accept this, I will arrange a svn access for you and you can then go
> forward and add the code above to Immmutable namespace.

I gladly accept the invitation!

My google code account:
http://code.google.com/u/david.black.co.at/

The namespace should be "NGenerics.DataStructures.Immutable"?

Regards, DavidS

>> [PairTest.cs4K ]/*

[husayt]

Excellent. Let me welcome you David. I am sure rest of the guys will
send their greetings and we will be in regular contact from now.

Could you send info about yourself, you want us to put on our team
page about you.
http://code.google.com/p/ngenerics/wiki/Team.

Yes, NGenerics.DataStructures.Immutable sounds right and you can open
a folder for it.

I will just get and open access for you.

Cheers,
Huseyn

> ...
>
> read more »

[husayt]

David can I have added your account to Ngenerics on google code. Can
you try to see if it works. If you have problems send me email address
you want me to get account for.
i couldn't access your google code account.

You can now go forward and commit your code. We have continuous
integration enabled, after your commit we should get binaries crispy
baked straight from factory. ;-))

Riaan, Simon, is there anything else David needs to know??

Thanks.

On Oct 16, 10:13 am, husayt <hus...@gmail.com> wrote:
> Excellent. Let me welcome you David. I am sure rest of the guys will
> send their greetings and we will be in regular contact from now.
>
> Could you send info about yourself, you want us to put on our team

> page about you.http://code.google.com/p/ngenerics/wiki/Team.

> ...
>
> read more »

[Riaan Hanekom]

We'll continue this thread in the ngenerics-developers group.

Riaan