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

public class Test
{
	public static void Main()
	{
		var candidates = new Dictionary<string, Func<IEnumerable<IEnumerable<int>>, IEnumerable<int>>>
			{
				{ "Original", Candidates.UOIOriginal<int> },
				{ "DoomerOneLine", Candidates.UOIDoomerOneLine<int> },
				{ "DoomerSqlLike", Candidates.UOIDoomerSqlLike<int> },
				{ "Schmelter", Candidates.UOISchmelter<int> },
				{ "Svinja", Candidates.UOISvinja<int> },
				{ "Adricadar", Candidates.UOIAdricadar<int> },
				
			};
			
		var testData = new int[][][]
			{
				new int[][]
				{
					new[] { 1, 1, 2, 3, 4, 5, 7 },
					new[] { 5, 6, 7 },
					new[] { 2, 6, 7, 9 },
					new[] { 4 }
				},
				new int[][]
				{
					new[] { 1, 2, 3 }
				},
				new int[][]
				{
					new int[0] 
				},
				new int[][]
				{}
			};
			
		var validResult = new[] { 2, 4, 5, 6, 7 };
		
		var results = new IEnumerable<int>[1000];
			
		foreach(var pair in candidates)
		{
			var valid = true;
			for (var i = 0; i < testData.Length; i++)
			{
				if (i == 0)
				{
					var timer = Stopwatch.StartNew();
					valid = pair.Value(testData[i]).OrderBy(d => d).SequenceEqual(validResult);
					timer.Stop();
				}
				else
				{
					valid = pair.Value(testData[i]).OrderBy(d => d).SequenceEqual(new int[0]);	
				}
				
				if (!valid)
				{
					break;
				}
			}
			
			Console.WriteLine("{0} valid:{1}", pair.Key, valid);
		}
		
		foreach(var pair in candidates)
		{
			var valid = true;
			var timer = Stopwatch.StartNew();
			for (var i = 0; i < 100000; i++)
			{
				results[i % 1000] = pair.Value(testData[0]);
			}
			timer.Stop();
			
			Console.WriteLine("{0} 100000 iterations in {1}ms", pair.Key, timer.ElapsedMilliseconds);
		}
	}
}

public static class Candidates
{
	public static IEnumerable<T> UOIOriginal<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		var pairs =
            from s1 in source
            from s2 in source
            select new { s1 , s2 };

    	var intersects = pairs
        	.Where(p => p.s1 != p.s2)
        	.Select(p => p.s1.Intersect(p.s2));

    	return intersects.SelectMany(i => i).Distinct();
	}
	
	public static IEnumerable<T> UOIDoomerOneLine<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		return source
			.SelectMany(e => e.Distinct())
    		.GroupBy(e => e)
    		.Where(e => e.Count() > 1)
    		.Select(e => e.Key);
	}
	
	public static IEnumerable<T> UOIDoomerSqlLike<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		return from e in source.SelectMany(e => e.Distinct())
          group e by e into g
          where g.Count() > 1
          orderby g.Key
          select g.Key;
	}
	
	public static IEnumerable<T> UOISvinja<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		var seenElements = new HashSet<T>();
        var repeatedElements = new HashSet<T>();

        foreach (var list in source)
        {
            foreach (var element in list.Distinct())
            {
                if (seenElements.Contains(element))
                {
                    repeatedElements.Add(element);
                }
                else
                {
                    seenElements.Add(element);
                }
            }
        }

        return repeatedElements;
	}
	
	public static IEnumerable<T> UOIAdricadar<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		var result = new List<T>();
	    var sequences = source.ToList();
	    for (int sequenceIdx = 0; sequenceIdx < sequences.Count(); sequenceIdx++)
	    {
	        var sequence = sequences[sequenceIdx];
	
	        for (
	        		int targetSequenceIdx = sequenceIdx + 1; 
	        		targetSequenceIdx < sequences.Count; 
	        		targetSequenceIdx++)
	        {
	            var targetSequence = sequences[targetSequenceIdx];
	            var intersections = sequence.Intersect(targetSequence);
	            result.AddRange(intersections);
	        }
	    }
	
	    return result.Distinct();
	}
	
	public static IEnumerable<T> UOISchmelter<T>(
                                  IEnumerable<IEnumerable<T>> source)
	{
		const int minCount = 2;
		var comparer = EqualityComparer<T>.Default;
	    foreach (T item in source.SelectMany(s => s).Distinct(comparer))
	    {
	        int containedInHowManySequences = 0;
	        foreach (IEnumerable<T> seq in source)
	        {
	            bool contained = seq.Contains(item, comparer);
	            if (contained) containedInHowManySequences++;
	            if (containedInHowManySequences == minCount)
	            {
	                yield return item;
	                break;
	            }
	        }
	    }
	}
}