Хитрый, включающий List <T>и приведение объектов

Question

Недавно мне дали этот вопрос на собеседовании, и я не мог понять, как это сделать элегантно.С тех пор, это не давало мне покоя, и я не могу понять, является ли это недостатком знаний о какой-то «современной» технике / технологии, о которой я не знаю, или я просто тупой.Любой совет будет очень кстати.

Проблема

Представьте себе простую иерархию классов:

abstract class Person {
    public string Name { get; set; }
}

class Child : Person { }

class Parent : Person {
    public List<Person> Children { get; set; }
}

class Ancestor : Parent { }

Проблема заключается в том, как обойти иерархию таких объектов и распечататьиз всех людей, с которыми сталкиваются.Таким образом, для следующего сценария:

Ancestor myAncestor = new Ancestor {    
    Name = "GrandDad",
    Children = new List<Person> { 
        new Child { Name = "Aunt" },
        new Child { Name = "Uncle" },
        new Parent {
            Name = "Dad", 
            Children = new List<Person> { 
                new Child { Name = "Me" }, 
                new Child { Name = "Sister" } 
            }
        }
    }
};

результат должен быть примерно таким:

GrandDad  
-    Aunt  
-    Uncle  
-    *Dad  
         -Me  
         -Sister

Вся обработка должна быть выполнена в одном методе, который принимает один параметр типа Ancestor.

Я реализовал, почти не задумываясь, простое рекурсивное решение, но, разумеется, из-за того, что соответствующие объекты связаны друг с другом, не так просто, как все это.

Как бы я ни пытался, я не могу придумать, как это сделать, и мое пост-интервью Гуглингс предложил мне сделать что-то, что (для меня только с рабочим знанием LINQ и List<T>) что-то значительноболее технически продвинутый, чем тот вид web-разработки, который я делал последние десять лет или около того.Это тот случай?Или мне стоит подумать о том, чтобы выйти из процесса разработки программного обеспечения на том основании, что я в нем всякую ерунду?

Обновление

Спасибо вам всем за ваши ответы / предложения.Я принял ответ @Daniel Hilgarth прежде всего потому, что он был единственным, который я мог по-настоящему понять: -o

Answer 1

Я согласен с комментарием Марка о том, что эта система типов не имеет смысла. Тем не менее, вы можете решить это с делегатами. Это немного обманывает, потому что в основном они не более чем методы, но мы идем:

void PrintFamily(Ancestor a)
{
    Action<Parent, int> printParent = null;
    printParent = (parent, level) => 
    {
        var indentation = new string(' ', level * 4);
        var indentationChildren = new string(' ', (level + 1) * 4);
        Console.WriteLine(indentation + parent.Name);
        foreach(var child in parent.Children)
        {
            if(child is Child)
                Console.WriteLine(indentationChildren + child.Name);
            else if(child is Parent)
            {
                printParent((Parent)child, level + 1);
            }
        }
    };

    printParent(a, 0);
}

Answer 2

Это ужасно, но в рамках вопроса (без дополнительных методов, поэтому нельзя добавить полиморфизм / дискриминатор, а метод должен принимать Ancestor, поэтому нет рекурсии метода):

static void Write(Ancestor root)
{
    // stack since depth-first
    var stack = new Stack<Tuple<Person,int>>();
    stack.Push(Tuple.Create((Person)root, 0));

    while(stack.Count > 0)
    {
        var pair= stack.Pop();
        var person = pair.Item1;

        // indentation
        Console.Write(new string('\t', pair.Item2));
        Parent parent = person as Parent;

        // node markers aren't fully specified, but this gets somewhere
        // near; maybe * should actually be checking Children != null &&
        // Children.Count > 0             
        if(person == root) {}
        else if (parent != null) { Console.Write("*");}
        else {Console.Write("-");}            

        Console.WriteLine(person.Name);

        // recursion on the stack
        if(parent != null && parent.Children != null) {
            foreach(var next in Enumerable.Reverse(parent.Children)) {
                stack.Push(Tuple.Create(next, pair.Item2 + 1));
            }
        }
    }
}

Answer 3

internal void ToString(Ancestor root)
{
    Trace.WriteLine(root.Name);
    Trace.Indent();
    foreach(var child in root.Children)
    {
         if(child is Parent)
             ToString(new Ancestor(){Name = child.Name, 
                                     Children = ((Parent)child).Children});
         else
             Trace.WriteLine(child.Name);
    }
    Trace.Unindent();
}

Answer 4

Вот мой путь, используя стек для эмуляции рекурсии:

static void PrintTree(Ancestor ancestor)
{
    Stack<Tuple<int, Person>> PersonStack = new Stack<Tuple<int, Person>>();
    PersonStack.Push(new Tuple<int, Person>(0, ancestor));

    while (PersonStack.Count != 0)
    {
        Tuple<int, Person> NextPerson = PersonStack.Pop();

        Console.WriteLine(new string(' ', NextPerson.Item1) + NextPerson.Item2.Name);

        Parent NextPersonAsParent = NextPerson.Item2 as Parent;
        if (NextPersonAsParent != null && NextPersonAsParent.Children != null)
        {
            foreach (var Child in NextPersonAsParent.Children)
            {
                PersonStack.Push(new Tuple<int, Person>(NextPerson.Item1 + 1, Child));
            }
        }
    }
}

Answer 5

Если вам разрешено (повторно) создавать объекты и использовать их простоту, вы можете использовать это:

    private static void PrintAncestor(Ancestor myAncestor)
    {
        Console.WriteLine(myAncestor.Name);
        foreach (var child in myAncestor.Children)
        {
            string intend = new string(myAncestor.Name.TakeWhile(c => c == '\t').ToArray()) + '\t';

            if (child is Ancestor)
                PrintAncestor(new Ancestor {
                    Children = (child as Ancestor).Children,
                    Name = intend + child.Name
                });

            if (child is Parent)
                PrintAncestor(new Ancestor {
                    Children = (child as Parent).Children,
                    Name = intend + "- *" + child.Name
                });

            if (child is Child)
                Console.WriteLine(intend + "-  " + child.Name);
        }
    }

печать:

GrandDad
        -  Aunt
        -  Uncle
        - *Dad
                -  Me
                -  Sister

Answer 6

Редактировать:

Полиморфное решение, скорее всего, самое простое, но вы должны иметь возможность изменять объекты.Пусть Person реализует виртуальный метод: например, Print(), который будет переопределен в Parent для распечатки дочерних элементов.Отступ можно обработать, указав, например, аргумент уровня отступа. Как вы отметили, ограничения задачи запрещают это .

Структура объекта, представленная в вопросе, довольно бессмысленна, а ограничения довольно узки.Кроме того, тот факт, что вам нужно реализовать метод, который принимает Ancestor и ограничен только этим телом метода, заставляет меня думать, что вопрос был задан специально, чтобы привести вас к стековому подходу.Кроме того, последний имеет важные преимущества в производительности по сравнению с рекурсией.

Уже есть пара хороших примеров стеков, поэтому я бы предложил альтернативный подход к рекурсии, который в принципе должен соответствовать 'не объявлятьправило дополнительных методов, и гораздо более читабельно (если вы знаете, что у вас лямбда:)

Action<IEnumerable<Person>, int> traverseAndPrint = null;
traverseAndPrint =
    (ps, i) =>
    {
        foreach (var p in ps)
        {
            Console.WriteLine("{0}-{1}", new string(' ', i), p.Name);

            if (p is Parent) traverseAndPrint(((Parent)p).Children, i + 1);
        }
    };

traverseAndPrint(new [] {ancestor}, 0);

Answer 7

С небольшим количеством "обмана" (спасибо Даниилу за ides) это использует рекурсию и остается в рамках ограничений задачи.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ это еще раз доказывает, что предложенный класс иерачи является странным. Специально для этой задачи, и я бы не стал использовать эту технику в производстве

  internal static string ToString(Ancestor root){
        Func<Parent, string, string> inner = (x, y) => string.Empty;
        inner = (p, indentation) =>{
                    var parents = p.Children.OfType<Parent>();
                    var children = p.Children.OfType<Child>();
                    var childString =
                        string.Concat
                            (children.Select
                                 (c => indentation + "-" + c.Name + Environment.NewLine));
                    return indentation + "-" + p.Name + Environment.NewLine +
                           childString +
                           string.Concat
                               (parents.Select(par => inner(par, " " + indentation)));
                };
        return inner(root, string.Empty);
    }

Сначала мы объявляем функтор и инициализируем фиктивным значением.

Затем мы создаем лямбда-выражение, которое может называть его self рекурсивно. Тело выражения делает то же, что и метод ниже.

Если бы метод signatur не требовал предка, мы могли бы сделать что-то вроде:

    internal string ToString(Parent parent, string indentation){
        var parents = parent.Children.OfType<Parent>();
        var children = parent.Children.OfType<Child>();
        var childString = children.Select(c => indentation + "-" + c.Name + Environment.NewLine);
        return indentation + "-" + parent.Name + Environment.NewLine + childString +
               string.Concat(parents.Select(par => ToString(par, " " + indentation)));
    }

сначала создайте список всех родителей и одного из всех детей. Затем создайте строку для всех детей (если рекурсия не требуется) и рекурсы для всех родителей