Removing Items From IDictionary With Recursion

Question

Anybody have a slicker way to do this? Seems like it should be easier than this, but I'm having a mental block. Basically I need to remove items from an dictionary and recurse into the values of the items that are also dictionaries.

private void RemoveNotPermittedItems(ActionDictionary menu)
{
    var keysToRemove = new List<string>();
    foreach (var item in menu)
    {
        if (!GetIsPermitted(item.Value.Call))
        {
            keysToRemove.Add(item.Key);
        }
        else if (item.Value is ActionDictionary)
        {
            RemoveNotPermittedItems((ActionDictionary)item.Value);
            if (((ActionDictionary)item.Value).Count == 0)
            {
                keysToRemove.Add(item.Key);
            }
        }
    }
    foreach (var key in (from item in menu where keysToRemove.Contains(item.Key) select item.Key).ToArray())
    {
        menu.Remove(key);
    }
}

Action dictionary is like this:

public class ActionDictionary : Dictionary<string, IActionItem>, IActionItem

Answer 1

You don't really need to collect the keys and iterate them again if you iterate the dictionary in reverse (from 'menu.Count - 1' to zero). Iterating in forward order will, of course, yield mutated collection exceptions if you start removing things.

I don't know what an ActionDictionary is, so I couldn't test your exact scenario, but here's an example using just Dictionary<string,object>.

    static int counter = 0;
    private static void RemoveNotPermittedItems(Dictionary<string, object> menu)
    {
        for (int c = menu.Count - 1; c >= 0; c--)
        {
            var key = menu.Keys.ElementAt(c);
            var value = menu[key];
            if (value is Dictionary<string, object>)
            {
                RemoveNotPermittedItems((Dictionary<string, object>)value);
                if (((Dictionary<string, object>)value).Count == 0)
                {
                    menu.Remove(key);
                }
            }
            else if (!GetIsPermitted(value))
            {
                menu.Remove(key);
            }
        }
    }

    // This just added to actually cause some elements to be removed...
    private static bool GetIsPermitted(object value)
    {
        if (counter++ % 2 == 0)
            return false;
        return true;
    }

I also reversed the 'if' statement, but that was just an assumption that you'd want to do type checking before calling a method to act on the item's value...it will work either way assuming 'GetIsPermitted' always returns TRUE for ActionDictionary.

Hope this helps.

Answer 2

While foreach and GetEnumerator fails, a for-loop works,

var table = new Dictionary<string, int>() {{"first", 1}, {"second", 2}};
for (int i = 0; i < table.Keys.Count; i++)//string key in table.Keys)
{
    string key = table.Keys.ElementAt(i);
    if (key.StartsWith("f"))
    {
        table.Remove(key);
    }
}

But ElementAt() is a .NET 3.5 feature.

Answer 3

To start with, your foreach loop is way more complicated than it needs to be. Just do:

foreach (var key in keysToRemove)
{
    menu.Remove(key);
}

I'm slightly surprised that Dictionary doesn't have a RemoveAll method but it doesn't look like it does...

Answer 4

Option 1: A Dictionary is still a Collection. Iterate over menu.Values.

You can iterate over menu.Values and remove them as you iterate. The values won't come in any sorted order (which should be fine for your case). You may need to use a for loop and adjust the index rather than using foreach - the enumerator will throw an exception if you modify the collection while iterating.

(I'll try to add the code when I'm on my dev machine Mon)

Option 2: Create a custom iterator.

Some collections returned from ListBox SelectedItems in Winforms don't really contain the collection, they provide a wrapper around the underlying collection. Kind of like CollectionViewSource in WPF. ReadOnlyCollection does something similar too.

Create a class that can "flatten" your nested dictionaries into something that can enumerate over them like they are a single collection. Implement a delete function that looks like it removes an item from the collection, but really removes from the current dictionary.

Answer 5

In My Opinion, you can define your own generic class deriving from the KeyValuePair<...> both TKey and TValue will be List<T> and you can use the RemoveAll or the RemoveRange of the List<T> in a new RemoveRange() or RemoveAll() method in your derived class to Remove the items you want.

Answer 6

I know you probably found good solution already, but just for the reason of 'slickness' if you could modify your method signatures to (I know it may not be appropriate in your scenario):

private ActionDictionary RemoveNotPermittedItems(ActionDictionary menu)
{
 return new ActionDictionary(from item in menu where GetIsPermitted(item.Value.Call) select item)
.ToDictionary(d=>d.Key, d=>d.Value is ActionDictionary?RemoveNotPermittedItems(d.Value as ActionDictionary) : d.Value));
}

And I can see couple ways where you can use your dictionary with filtered items without modification and materializing new dictionaries.

Answer 7

It's not much less complicated, but some idiomatic changes make it a bit shorter and easier on the eyes:

    private static void RemoveNotPermittedItems(IDictionary<string, IActionItem> menu)
    {
        var keysToRemove = new List<string>();

        foreach (var item in menu)
        {
            if (GetIsPermitted(item.Value.Call))
            {
                var value = item.Value as ActionDictionary;

                if (value != null)
                {
                    RemoveNotPermittedItems(value);
                    if (!value.Any())
                    {
                        keysToRemove.Add(item.Key);
                    }
                }
            }
            else
            {
                keysToRemove.Add(item.Key);
            }
        }

        foreach (var key in keysToRemove)
        {
            menu.Remove(key);
        }
    }

    private static bool GetIsPermitted(object call)
    {
        return ...;
    }

Answer 8

Change the type of the keysToRemove to HashSet<string> and you'll get an O(1) Contains method. With List<string> it's O(n), which is slower as you might guess.

Answer 9

untested until i'm at my VS machine tomorrow :o

private void RemoveNotPermittedItems(ActionDictionary menu)
{
    foreach(var _checked in (from m in menu
                             select new
                             {
                                 gip = !GetIsPermitted(m.Value.Call),
                                 recur = m.Value is ActionDictionary,
                                 item = m
                             }).ToArray())
    {
        ActionDictionary tmp = _checked.item.Value as ActionDictionary;
        if (_checked.recur)
        {
            RemoveNotPermittedItems(tmp);
        }
        if (_checked.gip || (tmp != null && tmp.Count == 0) {
            menu.Remove(_checked.item.Key);
        }
    }
}

Answer 10

I think

public class ActionSet : HashSet<IActionItem>, IActionItem

And

bool Clean(ActionSet nodes)
    {
        if (nodes != null)
        {
            var removed = nodes.Where(n => this.IsNullOrNotPermitted(n) || !this.IsNotSetOrNotEmpty(n) || !this.Clean(n as ActionSet));

            removed.ToList().ForEach(n => nodes.Remove(n));

            return nodes.Any();
        }

        return true;
    }

    bool IsNullOrNotPermitted(IActionItem node)
    {
        return node == null || *YourTest*(node.Call);
    }

    bool IsNotSetOrNotEmpty(IActionItem node)
    {
        var hset = node as ActionSet;
        return hset == null || hset.Any();
    }

Should work fast