Click here to Skip to main content
Click here to Skip to main content
Technical Blog

FindControl: Recursive DFS, BFS, and Leaf to Root Search with Pruning

, 24 Oct 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
Recursive DFS, BFS, and Leaf to Root search with pruning.

I have nefarious reason for posting this. It’s a prerequisite for another post I want to do on control mapping within javascript when you have one control which affects another and there’s no good spaghetti-less way to hook them together. But first, I need to talk about my nifty FindControl extensions. Whether you turn this in to an extension method or just place it in your page’s base class, you may find these handy.

We’ve all used FindControl and realized it’s a pretty lazy function that only searches its direct children and not the full control hierarchy. Let’s step back and consider what we’re searching before jumping to the code. What is the control hierarchy? It is a tree data structure whose root node is Page. The most common recursive FindControl extension starts at Page or a given parent node and performs a depth-first traversal over all the child nodes.

Depth-first search
Search order: a-b-d-h-e-i-j-c-f-k-g

/// <span class="code-SummaryComment"><summary>
</span>/// Recurse through the controls collection checking for the id
/// <span class="code-SummaryComment"></summary>
</span>/// <span class="code-SummaryComment"><param name="control">The control we're checking</param>
</span>/// <span class="code-SummaryComment"><param name="id">The id to find</param>
</span>/// <span class="code-SummaryComment"><returns>The control, if found, or null</returns>
</span>public static Control FindControlEx(this Control control, string id)
{
    //Check if this is the control we're looking for
    if (control.ID == id)
        return control;

    //Recurse through the child controls
    Control c = null;
    for (int i = 0; i < control.Controls.Count && c == null; i++)
        c = FindControlEx((Control)control.Controls[i], id);

    return c;
}

You will find many examples of the above code on the net. This is the “good enough” algorithm of choice. If you have ever wondered about it’s efficiency, read on. Close you’re eyes and picture the complexity of the seemingly innocent form… how every table begets rows begets cells begets the controls within the cell and so forth. Before long you realize there can be quite a complex control heirarchy, sometimes quite deep, even in a relatively simple page.

Now imagine a page with several top-level composite controls, some of them rendering deep control heirachies (like tables). As the designer of the page you have inside knowledge about the layout and structure of the controls contained within. Therefore, you can pick the best method of searching that data structure. Looking at the diagram above and imagine the b-branch was much more complex and deep. Now say what we’re trying to find is g. With depth-first you would have to search the entiretly of the b-branch before moving on to the c-branch and ultimately finding the control in g. For this scenario, a breadth-first search would make more sense as we won’t waste time searching a complex and potentially deep branch when we know the control is close to our starting point, the root.

Breadth-first search

Search order: a-b-c-d-e-f-g-h-i-j-k

/// <span class="code-SummaryComment"><summary>
</span>/// Finds the control via a breadth first search.
/// <span class="code-SummaryComment"></summary>
</span>/// <span class="code-SummaryComment"><param name="control">The control we're checking</param>
</span>/// <span class="code-SummaryComment"><param name="id">The id to find</param>
</span>/// <span class="code-SummaryComment"><returns>If found, the control.  Otherwise null</returns>
</span>public static Control FindControlBFS(this Control control, string id)
{
    Queue<Control> queue = new Queue<Control>();
    //Enqueue the root control
    queue.Enqueue(control);

    while (queue.Count > 0)
    {
        //Dequeue the next control to test
        Control ctrl = queue.Dequeue();
        foreach (Control child in ctrl.Controls)
        {
            //Check if this is the control we're looking for
            if (child.ID == id)
                return child;
            //Place the child control on in the queue
            queue.Enqueue(child);
        }
    }

    return null;
}

Recently I had a scenario where I needed to link 2 controls together that coexisted in the ItemTemplate of a repeater. The controls existed in separate composite controls.

102411_1147_findcontrol5.png

In this example I need to get _TexBoxPerformAction’s ClientID to enable/disable it via _ChechBoxEnable. Depending on the size of the data the repeater is bound to there may be hundreds of instances of the repeater’s ItemTemplate. How do I guarantee I get the right one? The above top-down FindControl algorithms would return he first match of _TextBoxPerformAction, not necessarily the right one. To solve this predicament, we need a bottom-up approach to find the control closest to us. By working our way up the control hierarchy we should be able to find the textbox within the same ItemTemplate instance guaranteeing we have the right one. The problem is, as we work our way up we will be repeatedly searching an increasingly large branch we’ve already seen. We need to prune the child branch we’ve already seen so we don’t search it over and over again as we work our way up.

To start we are in node 5 and need to get to node 1 to find our control. We recursively search node 5 which yields no results.

Next we look at node 5′s parent. We’ve already searched node 5, so we will prune it. Now recursively search node 4, which includes node 3, yielding no results.

Next we look at node 4′s parent. We have already searched node 4 and its children so we prune it.

Last we recursively search node 2, which includes node 1, yielding a result!

So here we can see that pruning saved us searching an entire branch repeatedly. And the best part is we only need to keep track of one id to prune.

/// <span class="code-SummaryComment"><summary>
</span>/// Finds the control from the leaf node to root node.
/// <span class="code-SummaryComment"></summary>
</span>/// <span class="code-SummaryComment"><param name="ctrlSource">The control we're checking</param>
</span>/// <span class="code-SummaryComment"><param name="id">The id to find</param>
</span>/// <span class="code-SummaryComment"><returns>If found, the control.  Otherwise null</returns>
</span>public static Control FindControlLeafToRoot(this Control ctrlSource, string id)
{
    Control ctrlParent = ctrlSource.Parent;
    Control ctrlTarget = null;
    string pruneId     = null;

    while (ctrlParent != null &&
           ctrlTarget == null)
    {
        ctrlTarget     = FindControl(ctrlParent, id, pruneId);
        pruneId        = ctrlParent.ClientID;
        ctrlParent     = ctrlParent.Parent;
    }
    return ctrlTarget;
}

/// <span class="code-SummaryComment"><summary>
</span>/// Recurse through the controls collection checking for the id
/// <span class="code-SummaryComment"></summary>
</span>/// <span class="code-SummaryComment"><param name="control">The control we're checking</param>
</span>/// <span class="code-SummaryComment"><param name="id">The id to find</param>
</span>/// <span class="code-SummaryComment"><param name="pruneClientID">The client ID to prune from the search.</param>
</span>/// <span class="code-SummaryComment"><returns>If found, the control.  Otherwise null</returns>
</span>public static Control FindControlEx(this Control control, string id, string pruneClientID)
{
    //Check if this is the control we're looking for
    if (control.ID == id)
        return control;

    //Recurse through the child controls
    Control c = null;
    for (int i = 0; i < control.Controls.Count && c == null; i++)
    {
        if (control.Controls[i].ClientID != pruneClientID)
            c = FindControlEx((Control)control.Controls[i], id, pruneClientID);
    }

    return c;
}

Now we have an efficient algorithm for searching leaf to root without wasting cycles searching the child branch we’ve come from. All this puts me in mind jQuery’s powerful selection capabilities. I’ve never dreamed up a reason for it yet, but searching for a collection of controls would be easy to implement and following jQuery’s lead we could extend the above to search for far more than just an ID.


License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Chris_Green
Software Developer (Senior) Storm Technology Ltd.
Ireland Ireland
Formerly a C++ client developer, nowadays I’m all about C# and ASP.NET. I work for a consulting firm which specializes in .NET technologies. Over the years I have mastered some and played with many aspects of .NET.
 
Follow my blog as I catalogue the more arcane problems I encounter and their solutions at CodingLifestyle.com

Comments and Discussions

 
QuestionNice PinmemberInfRes2-Nov-11 1:20 
SuggestionControl-itis PinmemberRichard Deeming1-Nov-11 9:37 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 25 Oct 2011
Article Copyright 2011 by Chris_Green
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid