Reduce nested list of object by parameter

Question

I need to reduce one collection of nested lists to another. I need to keep only objects which have parameter IsOk == true.

public class Item {
public string Id { get; set; }  
public Item[] Items { get; set; }
public bool IsOk { get; set; }

This is enter json:

                {
                'id': '1',
                'isOk': false,
                'items': [
                    {
                        'id': '21',
                        'isOk': false,
                        'items': [
                            {
                                'id': '31',
                                'isOk': true,
                                'items': [
                                    {
                                        'id': '41',
                                        'isOk': true,
                                        'items': null
                                    },
                                    {
                                        'id': '42',
                                        'isOk': true,
                                        'items': null
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        'id': '22',
                        'isOk': true,
                        'items': [
                            {
                                'id': '32',
                                'isOk': true,
                                'items': [
                                    {
                                        'id': '43',
                                        'isOk': true,
                                        'items': null
                                    },
                                    {
                                        'id': '44',
                                        'isOk': true,
                                        'items': null
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }

This is correct modified json.

        [
            {
                'id': '31',
                'isOk': true,
                'items': [
                    {
                        'id': '41',
                        'isOk': true,
                        'items': null
                    },
                    {
                        'id': '42',
                        'isOk': true,
                        'items': null
                    }
                ]   
            },
                {
                    'id': '22',
                    'isOk': true,
                    'items': [
                        {
                            'id': '32',
                            'isOk': true,
                            'items': [
                                {
                                    'id': '43',
                                    'isOk': true,
                                    'items': null
                                },
                                {
                                    'id': '44',
                                    'isOk': true,
                                    'items': null
                                }
                            ]
                        }
                    ]
                }
            ]

As you see new json have modified hierarchy and keep only objects with property IsOk == true. The biggest problem for me is how to change the hierarchy of the objects. Currently I try to use recursive function but maybe better is to use while loop?

Are you using standard JSON parsing libraries to parse the JSON into C# objects? E.g. https://stackoverflow.com/questions/6620165/how-can-i-parse-json-with-c — Colm Bhandal, May 19 '20 at 07:53
This is just example how the result should look like. I have only this first json and I need to build object to serialize it to this second json. — Michal Sobanski, May 19 '20 at 07:55
It sounds like you want to flatten your structure first and then get only those that are 'IsOk'. If so this answer suggesting using [LINQ-to-JSON](https://stackoverflow.com/questions/32782937/generically-flatten-json-using-c-sharp) my help. — sr28, May 19 '20 at 08:05
Is that the data structure of something that should be a tree? Are more than two Items allowed as descendants of an Item? What you are currently asking for is not trivial at all, as a change in the hierarchy also leads to a change in the data structure (imagine the Item with ID=1 as the root node of a tree, if you remove it without a replacement you don't have a tree anymore, but two of them). I mean, this can be solved, but not just by deserializing the json and without using a suitable data structure (maybe a binary search tree?). — FandangoOnCore, May 30 '20 at 17:16

score 0 · Answer 1 · answered May 30 '20 at 21:10

You can try this. As I stated in the comment to the question it's not a trivial task. The below 5 methods are explained with comments and at the bottom there's an example on how to use them. I tested it on different configurations of the json and seems to work.

        /// <summary>
        /// Flattens the actual result of the json deserialization (a List<Item>).
        /// </summary>
        /// <param name="deserializedObject">The actual result of the json deserialization (a List<Item>).</param>
        /// <param name="flattenedObject">The resulting flattened object.</param>
        private void FlattenDeserializedObject(List<Item> deserializedObject, List<Item> flattenedObject)
        {
            // Null-check on the flattened list.
            if (flattenedObject is null)
                flattenedObject = new List<Item>();
            // Iterate on every Item of the structure.
            for (var i = 0; i < deserializedObject.Count; i++)
            {
                if (deserializedObject[i] is null) continue;
                // Add the item to the flattened structure.
                flattenedObject.Add(deserializedObject[i]);
                // Check if there are descendants, if no the step to the next Item.
                if (deserializedObject[i].Items is null || deserializedObject[i].Items.Count() == 0)
                    continue;
                // There are descendants, recurse on them and update flattenedStructure.
                FlattenDeserializedObject(deserializedObject[i].Items.ToList(), flattenedObject);
            }
        }
        /// <summary>
        /// Creates a dictionary of descendants of an Item having IsOk=true.
        /// Dictionary KEY=[ItemID, VALUE=List of descendants with IsOk=true].
        /// </summary>
        /// <param name="flattenedObject">The flattened list of Items.</param>
        /// <param name="descIds">Dictionary KEY=[ItemID, VALUE=List of descendants with IsOk=true]</param>
        private void GetValidDescendantsIdDictionary(List<Item> flattenedObject, out Dictionary<string, List<string>> descendantsDictionary)
        {
            // Create an instance of the dictionary.
            descendantsDictionary = new Dictionary<string, List<string>>();
            // Get the descendants for every Item.
            foreach (var node in flattenedObject)
            {
                // Create a new list of ids for this Item id.
                descendantsDictionary.Add(node.Id, new List<string>());
                // Get all the isOk=true descendants for a specific node.
                GetValidNodeDescendantsIds(node, descendantsDictionary[node.Id]);
            }
        }
        /// <summary>
        /// Gets all the isOk=true descendants of a specific Item node.
        /// </summary>
        /// <param name="node">Item node.</param>
        /// <param name="descendantIds">List of isOK=true descendant IDs for the node.</param>
        private void GetValidNodeDescendantsIds(Item node, List<string> descendantIds)
        {
            // Null-empty check on the nodes and the direct descendants.
            if (node is null || node.Items is null || node.Items.Length == 0)
                return;
            descendantIds.AddRange(node.Items.Where(x => x.IsOk).Select(x => x.Id));
            // Recurse on the children of the node.
            node.Items.ToList().ForEach(n => GetValidNodeDescendantsIds(n, descendantIds));
        }
        /// <summary>
        /// Removes all the isOk=false items from the flattened structure.
        /// </summary>
        private void RemoveInvalidItemsFromFlattenedObject(List<Item> flattenedObject)
        {
            // Null-empty check on the flattened list.
            if (flattenedObject is null || flattenedObject.Count == 0) return;
            flattenedObject.RemoveAll(x => !x.IsOk);
        }
        /// <summary>
        /// Rebuilds the original structure node by node from the flattened one (without the invalid elements).
        /// Uses the descendants ID dictionary to get the correct position for the new nodes.
        /// Result will be in flattenedStructure.
        /// </summary>
        private void RebuildOriginalStructureFromFlattened(Item node, List<Item> flattenedStructure, Dictionary<string, List<string>> descendantsDictionary)
        {
            if (node is null || node.Items is null || node.Items.Length == 0)
                return;
            // Get the list of descendants from the support dictionary.
            var nodeDescendants = descendantsDictionary[node.Id];

            if (nodeDescendants.Count > 0)
            {
                // If there are isOk descendants, check their level and fix the hierarchy.
                var nodeLevel = int.Parse(node.Id.Substring(0, 1));
                var nextLevelWithNodes = nodeDescendants.Select(x => int.Parse(x.Substring(0, 1))).Min();
                var nextLevelNodeIds = nodeDescendants.Where(x => int.Parse(x.Substring(0, 1)) == nextLevelWithNodes);
                node.Items = flattenedStructure.Where(x => nextLevelNodeIds.Contains(x.Id)).ToArray();
                flattenedStructure.RemoveAll(x => nextLevelNodeIds.Contains(x.Id));
                // Recurse on every children.
                foreach (var n in node.Items)
                    RebuildOriginalStructureFromFlattened(n, flattenedStructure, descendantsDictionary);
            }
            else
            {
                // There are no isOk descendants, reset the Items array to null.
                node.Items = null;
            }
        }

USAGE:

            // json is the path to the json file.
            var items = JsonConvert.DeserializeObject<List<Item>>(json);
            // Create a list for the flattened structure.
            var flattenedObject = new List<Item>();
            // 1) Fill the flattenedObject list by passing the original structure (items).
            FlattenDeserializedObject(items, flattenedObject);
            // 2) Creates a dictionary of valid (isOk=true) descendants for each node.
            GetValidDescendantsIdDictionary(flattenedObject, out Dictionary<string, List<string>> descIds);
            // 3) Remove all the isOk=false nodes from the flattened structure.
            RemoveInvalidItemsFromFlattenedObject(flattenedObject);
            // 4) Rebuild the original structure from the flattened one.
            for (var i=0; i< flattenedObject.Count; i++)
                RebuildOriginalStructureFromFlattened(flattenedObject[i], flattenedObject, descIds);
            // 5) Get the json without the isOk=false nodes, but keeping the initial structure.
            var okJson = JsonConvert.SerializeObject(flattenedObject);

Reduce nested list of object by parameter

1 Answers1