Recursive method turning flat structure to recursive
up vote
5
down vote
favorite
3
I often end up working with systems where the data is delivered with some Id property and possibly a parentId prop, but never do anyone tempt to actually give me a nice recursive object to play with.
Now, the code below is merely a suggestion in how to solve these kind of "problems", I've created the FlatObject to simulate an incoming with data.
class Program
{
static void Main(string args)
{
// Fill list with sample data
List<FlatObject> flatObjects = new List<FlatObject>
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6)
};
// call the recursive method
var recursiveObjects = FillRecursive(flatObjects, 0);
}
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();
foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
{
recursiveObjects.Add(new RecursiveObject
{
Id = item.Id,
ParentId = item.ParentId,
Children = FillRecursive(flatObjects, item.Id)
});
}
return recursiveObjects;
}
}
public class FlatObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public FlatObject(int id, int parentId)
{
Id = id;
ParentId = parentId;
}
}
public class RecursiveObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public List<RecursiveObject> Children { get; set; }
}
I am aware of some Linq alternatives to solve the foreach loop but that does hardly not change the approach of this.
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
{
Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
}).ToList();
}
c# linq recursion
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
add a comment |
up vote
5
down vote
favorite
3
I often end up working with systems where the data is delivered with some Id property and possibly a parentId prop, but never do anyone tempt to actually give me a nice recursive object to play with.
Now, the code below is merely a suggestion in how to solve these kind of "problems", I've created the FlatObject to simulate an incoming with data.
class Program
{
static void Main(string args)
{
// Fill list with sample data
List<FlatObject> flatObjects = new List<FlatObject>
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6)
};
// call the recursive method
var recursiveObjects = FillRecursive(flatObjects, 0);
}
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();
foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
{
recursiveObjects.Add(new RecursiveObject
{
Id = item.Id,
ParentId = item.ParentId,
Children = FillRecursive(flatObjects, item.Id)
});
}
return recursiveObjects;
}
}
public class FlatObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public FlatObject(int id, int parentId)
{
Id = id;
ParentId = parentId;
}
}
public class RecursiveObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public List<RecursiveObject> Children { get; set; }
}
I am aware of some Linq alternatives to solve the foreach loop but that does hardly not change the approach of this.
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
{
Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
}).ToList();
}
c# linq recursion
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
4
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40
add a comment |
up vote
5
down vote
favorite
3
up vote
5
down vote
favorite
3
3
I often end up working with systems where the data is delivered with some Id property and possibly a parentId prop, but never do anyone tempt to actually give me a nice recursive object to play with.
Now, the code below is merely a suggestion in how to solve these kind of "problems", I've created the FlatObject to simulate an incoming with data.
class Program
{
static void Main(string args)
{
// Fill list with sample data
List<FlatObject> flatObjects = new List<FlatObject>
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6)
};
// call the recursive method
var recursiveObjects = FillRecursive(flatObjects, 0);
}
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();
foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
{
recursiveObjects.Add(new RecursiveObject
{
Id = item.Id,
ParentId = item.ParentId,
Children = FillRecursive(flatObjects, item.Id)
});
}
return recursiveObjects;
}
}
public class FlatObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public FlatObject(int id, int parentId)
{
Id = id;
ParentId = parentId;
}
}
public class RecursiveObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public List<RecursiveObject> Children { get; set; }
}
I am aware of some Linq alternatives to solve the foreach loop but that does hardly not change the approach of this.
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
{
Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
}).ToList();
}
c# linq recursion
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
I often end up working with systems where the data is delivered with some Id property and possibly a parentId prop, but never do anyone tempt to actually give me a nice recursive object to play with.
Now, the code below is merely a suggestion in how to solve these kind of "problems", I've created the FlatObject to simulate an incoming with data.
class Program
{
static void Main(string args)
{
// Fill list with sample data
List<FlatObject> flatObjects = new List<FlatObject>
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6)
};
// call the recursive method
var recursiveObjects = FillRecursive(flatObjects, 0);
}
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();
foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
{
recursiveObjects.Add(new RecursiveObject
{
Id = item.Id,
ParentId = item.ParentId,
Children = FillRecursive(flatObjects, item.Id)
});
}
return recursiveObjects;
}
}
public class FlatObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public FlatObject(int id, int parentId)
{
Id = id;
ParentId = parentId;
}
}
public class RecursiveObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public List<RecursiveObject> Children { get; set; }
}
I am aware of some Linq alternatives to solve the foreach loop but that does hardly not change the approach of this.
private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
{
Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
}).ToList();
}
c# linq recursion
c# linq recursion
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
edited Mar 25 '14 at 5:45
Jamal♦
30.2k11115226
30.2k11115226
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
asked Dec 20 '11 at 23:09
Eric Herlitz
155227
155227
4
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40
add a comment |
4
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40
4
4
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40
add a comment |
3 Answers
3
active
oldest
votes
up vote
5
down vote
accepted
Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.
Some differences from your original setup:
- The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
- The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
- I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.
The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
}
EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:
- The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the
EmptyEnumerable<RecursiveObject>class (code included). - Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
- The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
- The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (
new FlatObject(9,-1)) and circular references (new FlatObject(10,10)andnew FlatObject(0,2)), just to verify that the implementation can handle these special cases.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public FlatObject(int id)
{
this.Id = id;
}
public FlatObject(int id, int parentId)
: this(id)
{
this.ParentId = parentId;
}
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
private List<RecursiveObject> _Children;
public IEnumerable<RecursiveObject> Children
{
get
{
IEnumerable<RecursiveObject> value = _Children;
if (value == null)
value = EmptyEnumerable<RecursiveObject>.Default;
return value;
}
}
public RecursiveObject(int id)
{
this.Id = id;
}
public void AddChild(RecursiveObject child)
{
if (_Children == null)
_Children = new List<RecursiveObject>();
_Children.Add(child);
child.Parent = this;
}
public bool RemoveChild(RecursiveObject child)
{
if (_Children != null)
{
bool removed = _Children.Remove(child);
if (removed)
child.Parent = null;
return removed;
}
else
{
return false;
}
}
public void AddChildren(IEnumerable<RecursiveObject> children)
{
if (children == null)
throw new ArgumentNullException("children");
if (_Children == null)
_Children = new List<RecursiveObject>(children);
else
_Children.AddRange(children);
foreach (var child in children)
{
child.Parent = this;
}
}
}
class Program
{
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
static void Main(string args)
{
List<FlatObject> flatObjects = new List<FlatObject>()
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6),
new FlatObject(9,-1),
new FlatObject(10,10),
new FlatObject(0,2),
};
var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
}
}
#region Universal Code
class EmptyEnumerator<T> : IEnumerator<T>
{
public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
public T Current
{
get { throw new InvalidOperationException(); }
}
public void Dispose()
{
}
object System.Collections.IEnumerator.Current
{
get { throw new InvalidOperationException(); }
}
public bool MoveNext()
{
return false;
}
public void Reset()
{
}
}
class EmptyEnumerable<T> : IEnumerable<T>
{
public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
public IEnumerator<T> GetEnumerator()
{
return EmptyEnumerator<T>.Default;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
#endregion
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
add a comment |
up vote
1
down vote
You could, perhaps, derive RecursiveObject from FlatObject.
In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
add a comment |
up vote
1
down vote
I'm a fan of immutable objects and collection initializer syntax, myself:
private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};
// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}
private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}
public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}
public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}
public sealed class FlatObject
{
private readonly int id;
private readonly int parentId;
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}
public sealed class RecursiveObject
{
private readonly int id;
private readonly int parentId;
private readonly ReadOnlyCollection<RecursiveObject> children;
public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type ofidto astring, but as long as the accessor can convert it to anint, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
– Jesse C. Slicer
Dec 21 '11 at 14:24
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
|
show 5 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f7032%2frecursive-method-turning-flat-structure-to-recursive%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.
Some differences from your original setup:
- The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
- The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
- I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.
The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
}
EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:
- The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the
EmptyEnumerable<RecursiveObject>class (code included). - Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
- The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
- The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (
new FlatObject(9,-1)) and circular references (new FlatObject(10,10)andnew FlatObject(0,2)), just to verify that the implementation can handle these special cases.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public FlatObject(int id)
{
this.Id = id;
}
public FlatObject(int id, int parentId)
: this(id)
{
this.ParentId = parentId;
}
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
private List<RecursiveObject> _Children;
public IEnumerable<RecursiveObject> Children
{
get
{
IEnumerable<RecursiveObject> value = _Children;
if (value == null)
value = EmptyEnumerable<RecursiveObject>.Default;
return value;
}
}
public RecursiveObject(int id)
{
this.Id = id;
}
public void AddChild(RecursiveObject child)
{
if (_Children == null)
_Children = new List<RecursiveObject>();
_Children.Add(child);
child.Parent = this;
}
public bool RemoveChild(RecursiveObject child)
{
if (_Children != null)
{
bool removed = _Children.Remove(child);
if (removed)
child.Parent = null;
return removed;
}
else
{
return false;
}
}
public void AddChildren(IEnumerable<RecursiveObject> children)
{
if (children == null)
throw new ArgumentNullException("children");
if (_Children == null)
_Children = new List<RecursiveObject>(children);
else
_Children.AddRange(children);
foreach (var child in children)
{
child.Parent = this;
}
}
}
class Program
{
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
static void Main(string args)
{
List<FlatObject> flatObjects = new List<FlatObject>()
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6),
new FlatObject(9,-1),
new FlatObject(10,10),
new FlatObject(0,2),
};
var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
}
}
#region Universal Code
class EmptyEnumerator<T> : IEnumerator<T>
{
public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
public T Current
{
get { throw new InvalidOperationException(); }
}
public void Dispose()
{
}
object System.Collections.IEnumerator.Current
{
get { throw new InvalidOperationException(); }
}
public bool MoveNext()
{
return false;
}
public void Reset()
{
}
}
class EmptyEnumerable<T> : IEnumerable<T>
{
public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
public IEnumerator<T> GetEnumerator()
{
return EmptyEnumerator<T>.Default;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
#endregion
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
add a comment |
up vote
5
down vote
accepted
Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.
Some differences from your original setup:
- The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
- The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
- I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.
The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
}
EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:
- The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the
EmptyEnumerable<RecursiveObject>class (code included). - Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
- The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
- The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (
new FlatObject(9,-1)) and circular references (new FlatObject(10,10)andnew FlatObject(0,2)), just to verify that the implementation can handle these special cases.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public FlatObject(int id)
{
this.Id = id;
}
public FlatObject(int id, int parentId)
: this(id)
{
this.ParentId = parentId;
}
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
private List<RecursiveObject> _Children;
public IEnumerable<RecursiveObject> Children
{
get
{
IEnumerable<RecursiveObject> value = _Children;
if (value == null)
value = EmptyEnumerable<RecursiveObject>.Default;
return value;
}
}
public RecursiveObject(int id)
{
this.Id = id;
}
public void AddChild(RecursiveObject child)
{
if (_Children == null)
_Children = new List<RecursiveObject>();
_Children.Add(child);
child.Parent = this;
}
public bool RemoveChild(RecursiveObject child)
{
if (_Children != null)
{
bool removed = _Children.Remove(child);
if (removed)
child.Parent = null;
return removed;
}
else
{
return false;
}
}
public void AddChildren(IEnumerable<RecursiveObject> children)
{
if (children == null)
throw new ArgumentNullException("children");
if (_Children == null)
_Children = new List<RecursiveObject>(children);
else
_Children.AddRange(children);
foreach (var child in children)
{
child.Parent = this;
}
}
}
class Program
{
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
static void Main(string args)
{
List<FlatObject> flatObjects = new List<FlatObject>()
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6),
new FlatObject(9,-1),
new FlatObject(10,10),
new FlatObject(0,2),
};
var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
}
}
#region Universal Code
class EmptyEnumerator<T> : IEnumerator<T>
{
public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
public T Current
{
get { throw new InvalidOperationException(); }
}
public void Dispose()
{
}
object System.Collections.IEnumerator.Current
{
get { throw new InvalidOperationException(); }
}
public bool MoveNext()
{
return false;
}
public void Reset()
{
}
}
class EmptyEnumerable<T> : IEnumerable<T>
{
public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
public IEnumerator<T> GetEnumerator()
{
return EmptyEnumerator<T>.Default;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
#endregion
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.
Some differences from your original setup:
- The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
- The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
- I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.
The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
}
EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:
- The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the
EmptyEnumerable<RecursiveObject>class (code included). - Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
- The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
- The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (
new FlatObject(9,-1)) and circular references (new FlatObject(10,10)andnew FlatObject(0,2)), just to verify that the implementation can handle these special cases.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public FlatObject(int id)
{
this.Id = id;
}
public FlatObject(int id, int parentId)
: this(id)
{
this.ParentId = parentId;
}
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
private List<RecursiveObject> _Children;
public IEnumerable<RecursiveObject> Children
{
get
{
IEnumerable<RecursiveObject> value = _Children;
if (value == null)
value = EmptyEnumerable<RecursiveObject>.Default;
return value;
}
}
public RecursiveObject(int id)
{
this.Id = id;
}
public void AddChild(RecursiveObject child)
{
if (_Children == null)
_Children = new List<RecursiveObject>();
_Children.Add(child);
child.Parent = this;
}
public bool RemoveChild(RecursiveObject child)
{
if (_Children != null)
{
bool removed = _Children.Remove(child);
if (removed)
child.Parent = null;
return removed;
}
else
{
return false;
}
}
public void AddChildren(IEnumerable<RecursiveObject> children)
{
if (children == null)
throw new ArgumentNullException("children");
if (_Children == null)
_Children = new List<RecursiveObject>(children);
else
_Children.AddRange(children);
foreach (var child in children)
{
child.Parent = this;
}
}
}
class Program
{
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
static void Main(string args)
{
List<FlatObject> flatObjects = new List<FlatObject>()
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6),
new FlatObject(9,-1),
new FlatObject(10,10),
new FlatObject(0,2),
};
var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
}
}
#region Universal Code
class EmptyEnumerator<T> : IEnumerator<T>
{
public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
public T Current
{
get { throw new InvalidOperationException(); }
}
public void Dispose()
{
}
object System.Collections.IEnumerator.Current
{
get { throw new InvalidOperationException(); }
}
public bool MoveNext()
{
return false;
}
public void Reset()
{
}
}
class EmptyEnumerable<T> : IEnumerable<T>
{
public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
public IEnumerator<T> GetEnumerator()
{
return EmptyEnumerator<T>.Default;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
#endregion
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.
Some differences from your original setup:
- The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
- The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
- I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.
The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
}
EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:
- The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the
EmptyEnumerable<RecursiveObject>class (code included). - Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
- The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
- The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (
new FlatObject(9,-1)) and circular references (new FlatObject(10,10)andnew FlatObject(0,2)), just to verify that the implementation can handle these special cases.
class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
public FlatObject(int id)
{
this.Id = id;
}
public FlatObject(int id, int parentId)
: this(id)
{
this.ParentId = parentId;
}
}
class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
private List<RecursiveObject> _Children;
public IEnumerable<RecursiveObject> Children
{
get
{
IEnumerable<RecursiveObject> value = _Children;
if (value == null)
value = EmptyEnumerable<RecursiveObject>.Default;
return value;
}
}
public RecursiveObject(int id)
{
this.Id = id;
}
public void AddChild(RecursiveObject child)
{
if (_Children == null)
_Children = new List<RecursiveObject>();
_Children.Add(child);
child.Parent = this;
}
public bool RemoveChild(RecursiveObject child)
{
if (_Children != null)
{
bool removed = _Children.Remove(child);
if (removed)
child.Parent = null;
return removed;
}
else
{
return false;
}
}
public void AddChildren(IEnumerable<RecursiveObject> children)
{
if (children == null)
throw new ArgumentNullException("children");
if (_Children == null)
_Children = new List<RecursiveObject>(children);
else
_Children.AddRange(children);
foreach (var child in children)
{
child.Parent = this;
}
}
}
class Program
{
public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}
return recursiveObjectsById.Values;
}
static void Main(string args)
{
List<FlatObject> flatObjects = new List<FlatObject>()
{
new FlatObject(1,0),
new FlatObject(2,0),
new FlatObject(3,0),
new FlatObject(4,0),
new FlatObject(5,1),
new FlatObject(6,2),
new FlatObject(7,6),
new FlatObject(8,6),
new FlatObject(9,-1),
new FlatObject(10,10),
new FlatObject(0,2),
};
var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
}
}
#region Universal Code
class EmptyEnumerator<T> : IEnumerator<T>
{
public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
public T Current
{
get { throw new InvalidOperationException(); }
}
public void Dispose()
{
}
object System.Collections.IEnumerator.Current
{
get { throw new InvalidOperationException(); }
}
public bool MoveNext()
{
return false;
}
public void Reset()
{
}
}
class EmptyEnumerable<T> : IEnumerable<T>
{
public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
public IEnumerator<T> GetEnumerator()
{
return EmptyEnumerator<T>.Default;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
#endregion
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
edited Dec 21 '11 at 20:42
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
answered Dec 21 '11 at 18:52
Dr. Wily's Apprentice
88957
88957
add a comment |
add a comment |
up vote
1
down vote
You could, perhaps, derive RecursiveObject from FlatObject.
In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
add a comment |
up vote
1
down vote
You could, perhaps, derive RecursiveObject from FlatObject.
In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
add a comment |
up vote
1
down vote
up vote
1
down vote
You could, perhaps, derive RecursiveObject from FlatObject.
In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
You could, perhaps, derive RecursiveObject from FlatObject.
In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
answered Dec 20 '11 at 23:46
Mike Nakis
1,90111015
1,90111015
add a comment |
add a comment |
up vote
1
down vote
I'm a fan of immutable objects and collection initializer syntax, myself:
private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};
// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}
private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}
public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}
public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}
public sealed class FlatObject
{
private readonly int id;
private readonly int parentId;
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}
public sealed class RecursiveObject
{
private readonly int id;
private readonly int parentId;
private readonly ReadOnlyCollection<RecursiveObject> children;
public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type ofidto astring, but as long as the accessor can convert it to anint, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
– Jesse C. Slicer
Dec 21 '11 at 14:24
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
|
show 5 more comments
up vote
1
down vote
I'm a fan of immutable objects and collection initializer syntax, myself:
private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};
// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}
private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}
public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}
public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}
public sealed class FlatObject
{
private readonly int id;
private readonly int parentId;
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}
public sealed class RecursiveObject
{
private readonly int id;
private readonly int parentId;
private readonly ReadOnlyCollection<RecursiveObject> children;
public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type ofidto astring, but as long as the accessor can convert it to anint, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
– Jesse C. Slicer
Dec 21 '11 at 14:24
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
|
show 5 more comments
up vote
1
down vote
up vote
1
down vote
I'm a fan of immutable objects and collection initializer syntax, myself:
private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};
// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}
private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}
public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}
public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}
public sealed class FlatObject
{
private readonly int id;
private readonly int parentId;
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}
public sealed class RecursiveObject
{
private readonly int id;
private readonly int parentId;
private readonly ReadOnlyCollection<RecursiveObject> children;
public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
I'm a fan of immutable objects and collection initializer syntax, myself:
private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};
// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}
private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}
public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}
public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}
public sealed class FlatObject
{
private readonly int id;
private readonly int parentId;
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}
public sealed class RecursiveObject
{
private readonly int id;
private readonly int parentId;
private readonly ReadOnlyCollection<RecursiveObject> children;
public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}
public int Id { get { return this.id; } }
public int ParentId { get { return this.parentId; } }
public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
answered Dec 20 '11 at 23:58
Jesse C. Slicer
11.3k2740
11.3k2740
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type ofidto astring, but as long as the accessor can convert it to anint, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
– Jesse C. Slicer
Dec 21 '11 at 14:24
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
|
show 5 more comments
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type ofidto astring, but as long as the accessor can convert it to anint, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
– Jesse C. Slicer
Dec 21 '11 at 14:24
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
1
1
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
– Mike Nakis
Dec 21 '11 at 9:44
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
So anyone who uses those objects can read them, yes?
– Jesse C. Slicer
Dec 21 '11 at 13:56
1
1
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
– Mike Nakis
Dec 21 '11 at 14:15
1
1
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type of
id to a string, but as long as the accessor can convert it to an int, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.– Jesse C. Slicer
Dec 21 '11 at 14:24
The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type of
id to a string, but as long as the accessor can convert it to an int, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.– Jesse C. Slicer
Dec 21 '11 at 14:24
1
1
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
I see, the question has already been Skeeted.
– Mike Nakis
Dec 21 '11 at 14:45
|
show 5 more comments
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f7032%2frecursive-method-turning-flat-structure-to-recursive%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
– Mike Nakis
Dec 20 '11 at 23:39
Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).
– Dr. Wily's Apprentice
Dec 21 '11 at 19:40