mafutrct

[C#] On How to break up this long but clean method

2009-07-09T11:11:26-07:00

I fooled around with the code some more and this is the result so far.

		protected override Dictionary<GloballyFilteredPositionSource, DevicePosition> Reconfigure (
			Dictionary<GloballyFilteredPositionSource, DevicePosition> rawPositions)
		{
			/*
			 * with world unset, return current positions.
			 */
			if (World == null) {
				return rawPositions;
			}

			/*
			 * remove invalid positions
			 */
			var positions = rawPositions.Where (x => x.Value != null);

			/*
			 * create precomputed distance info
			 */
			IEnumerable<Composition> compositions = CreateCompositions (positions);

			/*
			 * find and store best matches
			 */
			var resultingMatches = new Dictionary<GloballyFilteredPositionSource, DevicePosition> ();
			foreach (var pos in positions) {
				resultingMatches.Add (pos.Key, pos.Value);
			}

			while (compositions.Any ()) {
				/*
				 * find best assignment
				 */
				var bestMatch = compositions.First ();

				/*
				 * remove used sources and destinations
				 */
				compositions = compositions.Where (x => x.Pair.Key != bestMatch.Pair.Key);
				compositions = compositions.Where (x => x.Target != bestMatch.Target);
				compositions = compositions.ToList (); // tested: improves performance

				/*
				 * ultimately add current pair to results
				 */
				DevicePosition dpResult = new DevicePosition (
					bestMatch.Target.Center,
					bestMatch.Pair.Value.Time);
				resultingMatches[bestMatch.Pair.Key] = dpResult;
			}

			return resultingMatches;
		}

		private List<Composition> CreateCompositions (
			IEnumerable<KeyValuePair<GloballyFilteredPositionSource, DevicePosition>> positions)
		{
			/*
			 * gather all valid volumes
			 */
			IEnumerable<Volume> projectionVolumes =
				from room in World.GetRooms ()
				where "1".Equals (room.GetAttribute (WantDeviceConstant))
				select room.Volume;
			projectionVolumes = projectionVolumes.ToList ();

			/*
			 * build all pairs
			 */
			IEnumerable<Composition> compositions =
				from src in positions
				from target in projectionVolumes
				select new Composition (src, target);

			/*
			 * apply filter
			 */
			compositions = compositions.Where (x => x.Dist < MaxDist);
			compositions = compositions.ToList ();

			/*
			 * presort
			 */
			compositions = compositions.OrderBy (x => x.Dist);

			return compositions.ToList ();
		}

[C#] On IEnumerable<> comparision extension method

2009-07-06T13:11:02-07:00

Petar: I'm not sure about the 'where T : class' part. Doesn't this prevent usage of the function with IEnumerable<int>? Apart from that I really like your suggestions.

This is the code I'm currently using:

		/// <summary>
		/// Compares the content of two enumerables for equality. Order
		/// of elements does NOT matter. Elements may exist multiple
		/// times. <c>null</c> is both a valid key and value.
		/// 
		/// O(n). (?) Fast for elements with well distributed hashcode.
		/// </summary>
		public static bool ContentEquals<T> (
			this IEnumerable<T> first,
			IEnumerable<T> second,
			IEqualityComparer<T> comparer)
		{
			// Declare a dictionary to count the occurrence of the items in the collection			
			Dictionary<T, int> itemCounts = new Dictionary<T, int> (comparer);

			// null references are stored here.
			int zero = 0;

			// Element count
			int items = 0;

			// Increase the count for each occurrence of the item in the first collection
			foreach (T item in first) {
				if (item == null) {
					zero++;
				}
				else {
					items++;

					int count = 0;
					itemCounts.TryGetValue (item, out count);
					itemCounts[item] = ++count;
				}
			}

			// Decrease the count for each occurrence of the item in the second collection
			foreach (T item in second) {
				if (item == null) {
					zero--;
				}
				else {
					items--;
					if (items < 0) {
						// Mismatching number of elements
						return false;
					}

					int count = 0;
					if (itemCounts.TryGetValue (item, out count)) {
						itemCounts[item] = --count;
					}
					else {
						// There was no occurrence of this item in the first collection, thus the collections are not equal
						return false;
					}
				}
			}

			// Number of elements must match
			if (items != 0) {
				return false;
			}

			// Number of nulls has to be equal
			if (zero != 0) {
				return false;
			}

			// The count of each item should be 0 if the contents of the collections are equal
			foreach (int value in itemCounts.Values) {
				if (value != 0) {
					return false;
				}
			}

			// The collections are equal
			return true;
		}

[C#] How to break up this long but clean method

2009-07-06T12:33:02-07:00

A lot of refactoring finally resulted in this long method. I think the code is quite clean and easy to understand. It uses linq a lot, and I'm not really familiar with linq yet, so I figured there are some improvements possible in this area. Also, I'd like to split this method up a bit, so VS does not complain about the admittedly big LOC.

		protected override Dictionary<GloballyFilteredPositionSource, DevicePosition> Reconfigure (
			Dictionary<GloballyFilteredPositionSource, DevicePosition> positions)
		{
			/*
			 * with world unset, return current positions.
			 */
			if (World == null) {
				return positions;
			}

			/*
			 * gather all valid volumes
			 */
			List<Volume> projectionVolumes = new List<Volume> ();

			foreach (Room r in World.GetRooms ()) {
				if ("1".Equals (r.GetAttribute (WantDeviceConstant))) {
					projectionVolumes.Add (r.Volume);
				}
			}

			/*
			 * create precomputed distance info
			 */
			var compositions =
				/*
				 * for each combination...
				 */
				from src in positions
				from target in projectionVolumes

				/*
				 * remove invalid positions
				 */
				where src.Value != null

				/*
				 * create bunch of info
				 */
				select new {
					Pair = src,
					Target = target,
					Dist = target.Dist (src.Value.Position),
				};

			/*
			 * apply filter
			 */
			compositions = compositions.Where (x => x.Dist < MaxDist);

			/*
			 * presort
			 */
			compositions = compositions.OrderBy (x => x.Dist);

			/*
			 * store result
			 */
			compositions = compositions.ToList ();

			/*
			 * find and store best matches
			 */
			Dictionary<GloballyFilteredPositionSource, DevicePosition> resultingMatches
				= new Dictionary<GloballyFilteredPositionSource, DevicePosition> (positions);

			while (compositions.Any ()) {
				/*
				 * find best assignment
				 */
				var bestMatch = compositions.First ();

				/*
				 * remove used sources and destinations
				 */
				compositions = compositions.Where (x => x.Pair.Key != bestMatch.Pair.Key);
				compositions = compositions.Where (x => x.Target != bestMatch.Target);
				compositions = compositions.ToList (); // tested: improves performance

				/*
				 * ultimately add current pair to results
				 */
				DevicePosition dpResult = new DevicePosition (
					bestMatch.Target.Center,
					bestMatch.Pair.Value.Time);
				resultingMatches[bestMatch.Pair.Key] = dpResult;
			}

			return resultingMatches;
		}

[C#] On IEnumerable<> comparision extension method

2009-06-25T08:45:28-07:00

That's interesting, the default extensions are really more sophisticated than I imagined. :)

I was just about to run a performance test of your suggestion when I noticed that "This method returns those elements in first that do not appear in second. It does not also return those elements in second that do not appear in first."

I guess this means we'd have to do the Except-comparision twice.... :(

Looking for a workaround, I stumbled upon Enumerable.Distinct, but that method does not work for multiple occurrences of the same item in the list :-\

[C#] On IEnumerable<> comparision extension method

2009-06-22T09:59:29-07:00

Ants: I think the complexity would increase to O(n*n) that way. Usage of a dictionary seems mandatory.

[C#] IEnumerable<> comparision extension method

2009-06-22T07:08:07-07:00

VS08 grants only a maintainability index of 49, but I found no way to improve this method. I'd be glad if you could point out some ideas.

/// <summary>
/// Compares the content of two enumerables for equality. Order
/// of elements does NOT matter. Elements may exist multiple
/// times. <c>null</c> is both a valid key and value.
/// 
/// O(n). Fast for elements with well distributed hashcode.
/// </summary>
public static bool ContentEquals<T> (
	this IEnumerable<T> first,
	IEnumerable<T> second,
	IEqualityComparer<T> comparer)
{
	// Declare a dictionary to count the occurence of the items in the collection			
	Dictionary<T, int> itemCounts = new Dictionary<T, int> (comparer);

        // null references are stored here.
	int zero = 0;

	// Increase the count for each occurence of the item in the first collection
	foreach (T item in first) {
		if (item == null) {
			zero++;
		}
		else if (itemCounts.ContainsKey (item)) {
			itemCounts[item]++;
		}
		else {
			itemCounts[item] = 1;
		}
	}

	// Decrease the count for each occurence of the item in the second collection
	foreach (T item in second) {
		if (item == null) {
			zero--;
		}
		else if (itemCounts.ContainsKey (item)) {
			itemCounts[item]--;
		}
		else {
			// There was no occurence of this item in the first collection, thus the collections are not equal
			return false;
		}
	}

	// The count of each item should be 0 if the contents of the collections are equal
	foreach (int value in itemCounts.Values) {
		if (value != 0) {
			return false;
		}
	}
	if (zero != 0) {
		return false;
	}

	// The collections are equal
	return true;
}

[C#] Find random point inside a tree of geometrical object

2009-05-07T14:32:17-07:00

Volume is an abstract geometrical object. It contains a capacity.
CompositeVolume implements Volume. It contains a list of subvolumes.

I want to find a random position inside a CompositeVolume. Depending on the size of each subvolume I select one of them (bigger => higher probability), and let it select a random position in itself.

I'm pretty satisfied with the code as it stands, but since I'm new to C# and especially to .net 3.5, I wondered how it could be improved. I'm open for all suggestions. :)

Edit:
- "Random" is actually a static member of the class. I added it to the code. Sorry about that.
- Simply selecing a random entry in the list is not possible, because I want to take the Capacity property into consideration. Given two Subvolumes with Capacity 1.f and 2.f, the latter should be selected twice as often.

public class CompositeVolume : Volume
{
	private readonly Random Random = new Random();

	public override Collection<Volume> Subvolumes // stub
	{
		get;
		set;
	}

	public override float Capacity // stub
	{
		get;
	}

	// this is the interesting part:
	public override Vec GetRandomPosition ()
	{
		if (Subvolumes.Count == 0) {
			return null;
		}
		else {
			float sum = 0f;
			Dictionary<Volume, float> map = new Dictionary<Volume, float> ();
			foreach (Volume v in Subvolumes) {
				sum += v.Capacity;
				map[v] = sum;
			}

			float select = (float) Random.NextDouble () * sum;
			Volume inner = map.First (pair => pair.Value >= select).Key;

			return inner.GetRandomPosition ();
		}
	}
}

[C#] On Find the list's last satisfying element and skip the rest

2009-04-27T11:54:09-07:00

Thanks a lot to both of you, that was the idea I was looking for. :)

[C#] Find the list's last satisfying element and skip the rest

2009-04-17T09:43:26-07:00

First of all, i'm new to this site, so please point out mistakes of this submit.

I'm trying to improve some older code that was written for .net 3.0 with features found in 3.5. The current version works fine, but it seems like it takes more lines than actually needed.

Purpose of this function is to find two values in a list. One of them is simply the first value.
The second value is supposed to be that last value that lies within a time range. However, not the last value in the whole list, but the last satisfying value just before the first not-satisfying value.

Sadly, I found no nice way to refactor the while loop. Everything else (except for that while) is not much of a problem.

using System;
using System.Collections.Generic;
using System.Linq;

public class DevicePosition
{
	// stub
	public DateTime Time;
}

public class Foo
{
	// this should be IEnumerable.
	private IEnumerator<DevicePosition> ValidPositions()
	{
		// stub
		return null;
	}

	public bool FindRecentRepresentatives(
		int milliseconds,
		out DevicePosition current,
		out DevicePosition previous)
	{
		if (milliseconds <= 0) {
			throw new ArgumentOutOfRangeException ("milliseconds");
		}

		current = null;
		previous = null;

		IEnumerator<DevicePosition> valids = ValidPositions ();
		valids.MoveNext ();
		current = valids.Current;

		if (current != null) {
			long minTime = current.Time.Ticks - TimeSpan.FromMilliseconds (milliseconds).Ticks;

			// this is the difficult part:
			while (valids.MoveNext ()) {
				if (valids.Current.Time.Ticks < minTime) {
					break;
				}
				previous = valids.Current;
			}
		}
		return (current != null) && (previous != null);
	}
}