Finding unions of objects in lists (compound objects / nested lists)

Question

(I have rewritten the question to try to better provide an example of what I am trying to do. I apologize if this is a confusing question still...)

In what way would it be possible to find the union of n-many sets of objects that are contained as properties of other objects?

Using the following as an example:

class Author
{
    public string FirstName;
    public string LastName;
}

class Magazine
{
    public string Title;
    public string ISBN;

    public List<Article> TOC;
}

class Article
{
    public string Title;
    public string Header;
    public string Body;

    public int PageNumber;

    public Magazine Source;
    public Author Author;
}

• I am given a List<Magazine> which contains a List<Article>.
• The Article object has a Magazine and Author objects as properties (the article may exist 1:N to the magazine - as a copy or reprint).
• In fact, I am treating each article as an independent object. I do not care about the List<Magazine> which was given to me. I have been asked to provide a List<Author>.
• Before being given this List, I have NO knowledge of the possible Articles or Authors.

This data which I am provided looks like this (in treeview layout).

Magazine01
    Article01 (Title, Header, ... Magazine01, Author01)
    Article02 (Title, Header, ... Magazine01, Author02)
    Article03 (Title, Header, ... Magazine01, Author03)
Magazine02
    Article04 (Title, Header, ... Magazine02, Author04)
    Article05 (Title, Header, ... Magazine02, Author05)
    Article06 (Title, Header, ... Magazine02, Author04)
Magazine03
    Article07 (Title, Header, ... Magazine03, Author03)
    Article08 (Title, Header, ... Magazine03, Author02)
    Article09 (Title, Header, ... Magazine03, Author01)

This data which I have been asked to provide looks like this (in treeview layout).

Author01
    Article01 (Title, Header, ... Magazine01, Author01)
    Article09 (Title, Header, ... Magazine03, Author01)
Author02
    Article02 (Title, Header, ... Magazine01, Author02)
    Article08 (Title, Header, ... Magazine03, Author02)
Author03
    Article03 (Title, Header, ... Magazine01, Author03)
    Article07 (Title, Header, ... Magazine03, Author03)
Author04
    Article04 (Title, Header, ... Magazine02, Author04)
    Article06 (Title, Header, ... Magazine02, Author04)
Author05
    Article05 (Title, Header, ... Magazine02, Author05)

• The List<Magazine> I am given will be in no particular order.
• I am not trying to sort the output yet, but that would be nice.
• There may be n-many Magazines where each issue has n-many Articles.
• As a result, an Author may have n-many Articles.
• As I receive the Magazine objects, I am aggregating the Articles into a List<Article> (but I am not dead set on continuing to do this, it seemed like a good idea...)

---

In what way can I reduce the looping through the list of articles other than my (shameful) "reduction by attrition" method below:

List<Magazine> magazineList; // Magazines contain a list of Articles which contain an Author.
List<Article> articleList; // As each Magazine is created, a summary list of the Articles is recorded here (I realize that this is probably unnecessary, but that is an aside to my problem)
Bag<Author> authorBag;

for (i = 0; i < (Magazines.Count - 1); i++)
{
    BuildAuthorBag();
}

ParseArticleList();

//...

BuildAuthorBag()
{
    // Finds occurrences of Author in the Article list of each Magazine.
    // Limits the inclusion of Author based on preferences ( i > 1, 2, etc. )
}

ParseArticleList()
{
    // I clone the articleList (i.e. tmpArticleList)
    // I create two lists of Article type.  One will be the new leaf nodes.  The second is a swap list.

    // Using the authorBag...

    // In a loop...
    // I create the new parent node from the current Author in the bag.
    // Then, find occurrences of the Author in the tmpArticleList adding that Article as a child node to the parent node.
    // or...
    // I place them into the second list to be swapped for the tmpArticleList before the next loop.
}

Answer 1

From what I could understand, you need something like this. (I'm using VS2010 and C# 4, but any version that supports LINQ should do).

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

namespace SO6299404
{
    class Author
    {
        public string FirstName;
        public string LastName;
    }

    class Magazine
    {
        public string Title;
        public string ISBN;

        public List<Article> TOC;


        // Code Until the end of the class is for testing only
        public void Dump()
        {
            Dump(0);
        }

        public void Dump(int indent)
        {
            Console.WriteLine("".PadLeft(indent) + Title);
            if (TOC != null)
            {
                foreach (Article article in TOC)
                {
                    article.Dump(indent + 2);
                }
            }
        }
    }

    class Article
    {
        public string Title;
        public string Header;
        public string Body;

        public int PageNumber;

        public Magazine Source;
        public Author Author;

        // Code Until the end of the class is for testing only
        public void Dump()
        {
            Dump(0);
        }

        public void Dump(int indent)
        {
            string author = Author == null ? "" : Author.FirstName;
            Console.WriteLine("".PadLeft(indent) + Title + ", " + author);
        }
    }

    // A foreach extension. Not strictly nescessary, but having this extension
    // makes it a bit easier to write foreach loops
    public static class EnumerableExtension
    {
        public static void Foreach<T>(this IEnumerable<T> enumerable, Action<T> action)
        {
            if (enumerable == null) throw new ArgumentNullException("enumerable");
            if (action == null) throw new ArgumentNullException("action");

            foreach (T value in enumerable)
                action(value);
        }
    }

    class Program
    {

        static void Main()
        {
            List<Magazine> magazines = SetupTestCase();

            // Let's print out our test case
            Console.WriteLine("==[Setup]===========================");
            magazines.Foreach(x => x.Dump());

            // So now we need to extraxct all Authors and list articles belonging to them
            // First we get Authorl; Article pair and then we group by Authors
            var temp = magazines.SelectMany(m => m.TOC, (a, b) => new {b.Author, Article = b}).GroupBy(x => x.Author);

            // Ok, we are done. Let's print out the results
            Console.WriteLine("==[REsult]===========================");
            temp.Foreach(x =>
            {
                Console.WriteLine(x.Key.FirstName);
                x.Foreach( y => y.Article.Dump(2));
            });

        }

        // The code from here until the end of the class is for generating a test case only

        private static List<Magazine> SetupTestCase()
        {
            // Let's set up a test case similar to the example in the question

            // We generate 5 Authors
            Author[] authors = Seed(1, 5).Select(x => GenerateTestAuthor(x.ToString())).ToArray();

            // And 9 Articles
            Article[] articles = Seed(1,9).Select(x => GenerateTestArticle(x.ToString())).ToArray();

            // This defines how articles are connected to authors
            int[] articleToAuthor = new[] {0,1,2,3,4,3,2,1,0};

            // Let's connect articles and authors as per definition abbove
            Seed(9).Foreach(x=> {articles[x].Author = authors[articleToAuthor[x]];});

            // Now 3 Magazines
            Magazine[] magazines = Seed(1,3).Select(x => GenerateTestMagazine(x.ToString())).ToArray();

            // This deines which articles go in which magazine
            int[] articleToMagazine = new[] {0,0,0,1,1,1,2,2,2};

            // Let's add artices to the Magazines
            Seed(9).Foreach(x=> magazines[articleToMagazine[x]].TOC.Add(articles[x]));

            // And now let us link back from articles to Magazines
            magazines.Foreach(x => x.TOC.Foreach(z => z.Source = x));
            return magazines.ToList();
        }

        static IEnumerable<int> Seed(int start, int count)
        {
            return Enumerable.Range(start, count);
        }

        static IEnumerable<int> Seed(int n)
        {
            return Seed(0, n);
        }

        static Article GenerateTestArticle(string id)
        {
            return new Article
            {
                Title = "Title" + id,
                Header = "Title" + id,
                Body = "Title" + id,
                PageNumber = 1,
            };
        }

        static Author GenerateTestAuthor(string id)
        {
            return new Author
            {
                FirstName = "Author" + id,
                LastName = "Author" + id,
            };
        }

        static Magazine GenerateTestMagazine(string id)
        {
            return new Magazine
            {
                Title = "Magazine" + id,
                ISBN = "Magazine" + id,
                TOC = new List<Article>()
            };
        }
    }
}

And this is what I'm seeing on screen, when I ran it.

==[Setup]===========================
Magazine1
    Title1, Author1
    Title2, Author2
    Title3, Author3
Magazine2
    Title4, Author4
    Title5, Author5
    Title6, Author4
Magazine3
    Title7, Author3
    Title8, Author2
    Title9, Author1
==[REsult]===========================
Author1
    Title1, Author1
    Title9, Author1
Author2
    Title2, Author2
    Title8, Author2
Author3
    Title3, Author3
    Title7, Author3
Author4
    Title4, Author4
    Title6, Author4
Author5
    Title5, Author5

Answer 2

Would this suit your needs?

  public class Student
  {
    public List<Course> Courses { get; set; }
    public List<Grade> Grades { get; set; }

    public Dictionary<Course, Grade> CourseGrades { get; set; }
  }

  public class Course
  {
    public int Id { get; set; }
  }

  public class Grade
  {
    public double Value { get; set; }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var c0 = new Course() { Id = 0 };
      var c1 = new Course() { Id = 1 };

      var students = new List<Student>()
      {
        new Student() { CourseGrades = new Dictionary<Course,Grade>()
        { 
          { c0, new Grade() { Value = 2 } },
          { c1 , new Grade() { Value = 1 } }
        }},
        new Student() { CourseGrades = new Dictionary<Course,Grade>()
        { 
          { c1 , new Grade() { Value = 3 } },
          { c0 , new Grade() { Value = 4 } }
        }},
      };


      Dictionary<Course, List<Grade>> courseGrades = SelectUnion(students.SelectMany(s => s.CourseGrades), cg => cg.Key, cg => cg.Value);
    }

    private static Dictionary<TKey, List<TValue>> SelectUnion<TSource, TKey, TValue>(IEnumerable<TSource> set, Func<TSource, TKey> keyGen, Func<TSource, TValue> valueGen)
    {
      var result = new Dictionary<TKey, List<TValue>>();

      foreach (var src in set)
      {
        var key = keyGen(src);
        if (!result.ContainsKey(key))
        {
          result[key] = new List<TValue>();
        }

        result[key].Add(valueGen(src));
      }

      return result;
    }

I understand that this really likely only fits the example you gave. So if this not sufficient, perhaps you could provide an example structure of the end result you want so we know what to shoot for.