using System;
using System.Collections;

namespace Orciid.Core.Util
{
    /// <summary>
    /// Utility class to work with arrays of integers
    /// </summary>
    /// <remarks>
    /// This class contains some utility methods that work with arrays of integers
    /// </remarks>
	public sealed class IntegerListTools
	{
        /// <summary>
        /// Find common elements in two arrays of integers
        /// </summary>
        /// <remarks>
        /// If either array is <c>null</c>, this method returns <c>null</c>.
        /// If elements appear multiple times in either array, it is returned multiple times.
        /// </remarks>
        /// <example>
        /// a:[1, 2, 2, 2, 4] b:[1, 2, 2, 3, 4, 5] --> [1, 2, 2, 4]
        /// </example>
        /// <param name="a">The first array of integers</param>
        /// <param name="b">The second array of integers</param>
        /// <returns>An array of unique integers that appear in both <c>a</c> and <c>b</c></returns>
		public static int[] Intersect(int[] a, int[] b)
		{
			if (a == null || b == null)
				return null;

			Hashtable list;
			int[] c;
			
			if (a.Length > b.Length)
			{
				list = new Hashtable(b.Length);
				foreach (int i in b)
					if (!list.ContainsKey(i))
						list.Add(i, 1);
					else
						list[i] = ((int)list[i]) + 1;
				c = a;
			}
			else
			{
				list = new Hashtable(a.Length);
				foreach (int i in a)
					if (!list.ContainsKey(i))
						list.Add(i, 1);
					else
						list[i] = ((int)list[i]) + 1;
				c = b;
			}
			
			ArrayList result = new ArrayList();

			foreach (int i in c)
				if (list.ContainsKey(i))
				{
					int count = (int)list[i];
					result.Add(i);
					count--;
					if (count == 0)
						list.Remove(i);
					else
						list[i] = count;
				}

			if (result.Count == 0)
				return null;
			else
				return (int[])result.ToArray(typeof(int));
		}
	
	}
}
