Click here to Skip to main content
Click here to Skip to main content

EnumTree

, 12 Jun 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
A class and attribute to allow accessing enum values as a tree

Background

I was intrigued by this[^] article, but, as you can see by my comments on it, while I like the concept, I find the implementation leaves much to be desired. So I wrote my own version.

EnumTreeAttribute

The EnumTreeAttribute is used to decorate the enumeration, borrowing the AnimalKind enumeration from the original article, and applying this Attribute we get:

public enum AnimalKind
{
    [PIEBALD.Attributes.EnumTreeAttribute()]
    ClassMask       =                0xF000 ,
    [PIEBALD.Attributes.EnumTreeAttribute()]
    SubclassMask    = ClassMask    | 0x0F00 ,
    [PIEBALD.Attributes.EnumTreeAttribute()]
    MemberMask      = SubclassMask | 0x00FF ,

    DomesticAnimals =                0x1000 ,
      Dog           =                0x1100 ,
        Dalmation   =                0x1101 ,
...
}

(The complete enumeration is included in the EnumTreeTest.cs file.)

As with most Attributes, there isn't much code involved; this one doesn't contain any instance values. However, because hitting Reflection to get Attributes repeatedly is not very efficient, the class has a static method to get and cache the decorated members.

To get the list of the mask values, use:

System.Collections.Generic.IList<AnimalKind> masks = 
    PIEBALD.Attributes.EnumTreeAttribute.Masks<AnimalKind>() ;

If the enumeration appears in the cache, the cached list is returned. Otherwise the method uses Reflection to get the decorated values then caches and returns the List. The returned List will be sorted and readonly.

[System.AttributeUsageAttribute(System.AttributeTargets.Field)]
public sealed class EnumTreeAttribute : System.Attribute
{
    private static readonly System.Collections.Generic.Dictionary<System.Type,
        object> masks =
        new System.Collections.Generic.Dictionary<System.Type,object>() ;

    public static System.Collections.Generic.IList<T>
    Masks<T>
    (
    )
    {
        System.Collections.Generic.IList<T> result ;

        lock ( masks )
        {
            System.Type thetype = typeof(T) ;

            if ( masks.ContainsKey ( thetype ) )
            {
                result = (System.Collections.Generic.IList<T>) masks [ thetype ] ;
            }
            else
            {
                if ( !thetype.IsEnum )
                {
                    throw ( new System.ArgumentException ( "T must be an Enum" ) ) ;
                }

                System.Collections.Generic.List<T> temp = 
                    new System.Collections.Generic.List<T>() ;

                foreach ( System.Reflection.FieldInfo val in thetype.GetFields() )
                {
                    if 
                    ( 
                        val.GetCustomAttributes
                        (
                            typeof(EnumTreeAttribute)
                        ,
                            false
                        ).Length > 0 
                    )
                    {
                        temp.Add ( (T) val.GetValue ( null ) ) ;
                    }
                }

                temp.TrimExcess() ;

                temp.Sort() ;

                masks [ thetype ] = result = temp.AsReadOnly() ;
            }
        }

        return ( result ) ;
    }
}

I strongly suggest the use of a cache whenever using Reflection to access Attributes or other static (non-changing) information. The savings in clock cycles outweighs the cost in memory.

EnumTree

EnumTree is a static generic class which requires an enumeration as its type parameter. Once contructed, the following structures will hold the values and their relationships.

public static partial class EnumTree<T> 
where T : System.IComparable
{
    private sealed class Branch
    {
        public System.Collections.Generic.IList<T> Ancestors = 
            new System.Collections.Generic.List<T>() ;
 
        public System.Collections.Generic.IList<T> Children  =
            new System.Collections.Generic.List<T>() ;
    }
 
    private static readonly System.Collections.Generic.Dictionary<T,Branch> members ;
 
    private static readonly System.Collections.Generic.IList<T> roots ;
}

The following fields are included as well, mostly as a convenience and to improve readability.

private static readonly PIEBALD.Types.EnumOperators<T>.DelegateT And = 
    PIEBALD.Types.EnumOperators<T>.And ;
 
private static readonly PIEBALD.Types.EnumOperators<T>.DelegateBool Equal = 
    PIEBALD.Types.EnumOperators<T>.Equal ;
 
public static readonly System.Type BaseType = typeof(T) ;

Constructor

The constructor will automatically access the masks from the EnumTreeAttributes, read the enumeration's values, and build and cache the tree.

I'll attempt to explain the algorithm by walking through the processing of the first three (non-mask) members of the above enumeration.

1) The foreach sets tvalue to DomesticAnimals (0x1000)
1.1) Add a Branch for DomesticAnimals to the tree
1.2) Determine the tvalue's parentage by iterating the masks
1.2.1) The first mask is ClassMask (0xF000)
1.2.1.1) Set tparent to tvalue (0x1000) & ClassMask (0xF000)
1.2.1.2) Because tparent (0x1000) equals tvalue (0x1000) we can stop iterating the masks.
1.3) Because tvalue (0x1000) has no ancestors, we add it to the List of root members.

2) The foreach sets tvalue to Dog (0x1100)
2.1) Add a Branch for Dog to the tree
2.2) Determine the tvalue's parentage by iterating the masks
2.2.1) The first mask is ClassMask (0xF000)
2.2.1.1) Set tparent to tvalue (0x1100) & ClassMask (0xF000)
2.2.1.2) Because tparent (0x1000) does not equal tvalue (0x1100) we prepend the tparent to the tvalue's List of Ancestors.
2.2.2) The second mask is SubClassMask (0xFF00)
2.2.2.1) Set tparent to tvalue (0x1100) & SubClassMask (0xFF00)
2.2.2.2) Because tparent (0x1100) equals tvalue (0x1100) we can stop iterating the masks.
2.3) Because tvalue (0x1100) has at least one Ancestor, we add it to the first Ancestor's List of Children.

3) The foreach sets tvalue to Dalmation (0x1101)
3.1) Add a Branch for Dalmation to the tree
3.2) Determine the tvalue's parentage by iterating the masks
3.2.1) The first mask is ClassMask (0xF000)
3.2.1.1) Set tparent to tvalue (0x1101) & ClassMask (0xF000)
3.2.1.2) Because tparent (0x1000) does not equal tvalue (0x1101) we prepend the tparent to the tvalue's List of Ancestors.
3.2.2) The second mask is SubClassMask (0xFF00)
3.2.2.1) Set tparent to tvalue (0x1101) & SubClassMask (0xFF00)
3.2.2.1) Because tparent (0x1100) does not equal tvalue (0x1101) we prepend the tparent to the tvalue's List of Ancestors.
3.2.3) The third mask is MemberMask (0xFFFF)
3.2.3.1) Set tparent to tvalue (0x1101) & MemberMask (0xFFFF)
3.2.3.2) Because tparent (0x1101) equals tvalue (0x1101) we can stop iterating the masks.
3.3) Because tvalue (0x1101) has at least one Ancestor, we add it to the first Ancestor's List of Children.

static EnumTree
(
)
{
    if ( !BaseType.IsEnum )
    {
        throw ( new System.ArgumentException ( "T must be an Enum" ) ) ;
    }
 
    if ( BaseType.GetCustomAttributes ( typeof(System.FlagsAttribute) ,
        false ).Length > 0 )
    {
        throw ( new System.ArgumentException (
            "The enum must not have a FlagsAttribute" ) ) ;
    }
 
    System.Collections.Generic.IList<T> masks = GetMasks() ;
 
    System.Array values = System.Enum.GetValues ( BaseType ) ;
 
    members = new System.Collections.Generic.Dictionary<T,Branch> ( values.Length ) ;
 
    roots = new System.Collections.Generic.List<T> ( values.Length ) ;
 
    T tparent ;
 
    foreach ( T tvalue in values )
    {
        if ( members.ContainsKey ( tvalue ) )
        {
            throw ( new System.ArgumentException
            (
                "The enum contains duplicate values"
            ,
                tvalue.ToString()
            ) ) ;
        }
 
        if ( Equal ( tvalue , default(T) ) )
        {
            throw ( new System.ArgumentException
            (
                "The enum contains a zero value"
            ,
                tvalue.ToString()
            ) ) ;
        }
 
        members [ tvalue ] = new Branch() ;
 
        /* Only non-mask values can have ancestors and children */
        if ( !masks.Contains ( tvalue ) )
        {
            /* Run through the list of masks to determine the value's ancestors */
            for ( int runner = 0 ; runner < masks.Count ; runner++ )
            {
                tparent = And ( tvalue , masks [ runner ] ) ;
 
                if ( !members.ContainsKey ( tparent ) )
                {
                    throw ( new System.ArgumentException ( string.Format
                    (
                        "The value {0} ({1:X}) has invalid parentage ({2:X})"
                    ,
                        tvalue.ToString()
                    ,
                        tvalue
                    ,
                        tparent
                    ) ) ) ;
                }
 
                /* If we've found all the ancestors, there's no need to check more */
                /* masks */
                if ( Equal ( tvalue , tparent ) )
                {
                    break ;
                }
 
                if ( members [ tvalue ].Ancestors.Contains ( tparent ) )
                {
                    throw ( new System.ArgumentException ( string.Format
                    (
                        "The value {0} ({1:0X}) has invalid parentage ({2:0X})"
                    ,
                        tvalue.ToString()
                    ,
                        tvalue
                    ,
                        tparent
                        ) ) ) ;
                }
 
                /* Prepend the parent to the list of ancestors */
                members [ tvalue ].Ancestors.Insert ( 0 , tparent ) ;
            }
 
            if ( members [ tvalue ].Ancestors.Count == 0 )
            {
                roots.Add ( tvalue ) ;
            }
            else
            {
                /* If it's not a root, add it to its parent's list of children */
                members [ members [ tvalue ].Ancestors [ 0 ] ].Children.Add ( tvalue ) ;
            }
        }
    }
 
    /* Replace all the Lists with readonly Lists */
    foreach ( T t in members.Keys )
    {
        MakeListReadOnly ( ref members [ t ].Ancestors ) ;

        MakeListReadOnly ( ref members [ t ].Children ) ;
    }
 
    MakeListReadOnly ( ref roots ) ;
 
    return ;
}

Microsoft recommends making collections readonly if they're to be made available outside the class, so I use this method to freeze the Lists once they're complete.

private static void
MakeListReadOnly
(
    ref System.Collections.Generic.IList<T> List
)
{
    System.Collections.Generic.List<T> temp = 
        List as System.Collections.Generic.List<T> ;
 
    if ( temp != null )
    {
        temp.TrimExcess() ;
        List = temp.AsReadOnly() ;
    }
 
    return ;
}

The following methods are used to get information from the tree.

GetMasks

Retrieve the List of mask values.

public static System.Collections.Generic.IList<T>
GetMasks
(
)
{
    return ( PIEBALD.Attributes.EnumTreeAttribute.Masks<T>() ) ;
}

GetValues

Retrieve all the values of the enumeration.

public static System.Collections.Generic.IList<T>
GetValues
(
)
{
    return ( (System.Collections.Generic.IList<T>) System.Enum.GetValues ( BaseType ) ) ;
}

GetRoots

Retrieve the List of root values.

public static System.Collections.Generic.IList<T>

GetRoots
(
)
{
    return ( roots ) ;
}

GetChildren

Retrieve the List of the value's children. Note that this and the other methods that take parameters of type T must check the parameter values to be sure that they are valid.

public static System.Collections.Generic.IList<T>
GetChildren
(
    T Parent
)
{
    if ( !members.ContainsKey ( Parent ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Parent" 
        ,
            Parent 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    return ( members [ Parent ].Children ) ;
}

GetAncestors

Retrieve the List of the value's ancestors.

public static System.Collections.Generic.IList<T>
GetAncestors
(
    T Child
)
{
    if ( !members.ContainsKey ( Child ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child" 
        ,
            Child 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    return ( members [ Child ].Ancestors ) ;
}

GetCommonAncestors

This constructs a list of the values that appear among the ancestors of both children. Please note that I feel that this process is rather intensive, so if you need to do this frequently I suggest you devise your own method.

public static System.Collections.Generic.IList<T>
GetCommonAncestors
(
    T Child1
,
    T Child2
)
{
    if ( !members.ContainsKey ( Child1 ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child1" 
        ,
            Child1 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    if ( !members.ContainsKey ( Child2 ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child2" 
        ,
            Child2 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    System.Collections.Generic.IList<T> result = 
        new System.Collections.Generic.List<T>() ;
    
    if ( !roots.Contains ( Child1 ) && !roots.Contains ( Child2 ) )
    {

        System.Collections.Generic.Stack<T> anc1 = 
        new System.Collections.Generic.Stack<T> 
        (  
            members [ Child1 ].Ancestors
        ) ;
        
        System.Collections.Generic.Stack<T> anc2 = 
        new System.Collections.Generic.Stack<T> 
        (  
            members [ Child2 ].Ancestors
        ) ;
        
        while 
        ( 
            ( anc1.Count > 0 )
        &&
            ( anc2.Count > 0 )
        &&
            Equal 
            ( 
                anc1.Peek() 
            , 
                anc2.Peek() 
            )
        )
        {
            result.Add ( anc1.Pop() ) ;

            anc2.Pop() ;
        }
    }
    
    MakeListReadOnly ( ref result ) ;
                
    return ( result ) ;
}

IsChild

This tests whether or not the Child is one of Parent's children.

public static bool
IsChild
(
    T Child
,
    T Parent
)
{
    if ( !members.ContainsKey ( Parent ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Parent" 
        ,
            Parent 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    if ( !members.ContainsKey ( Child ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child" 
        ,
            Child 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    return ( members [ Parent ].Children.Contains ( Child ) ) ;
}

IsDescendant

This tests whether or not the Parent is one of Child's ancestors.

public static bool
IsDescendant
(
    T Child
,
    T Parent
)
{
    if ( !members.ContainsKey ( Parent ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Parent" 
        ,
            Parent 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    if ( !members.ContainsKey ( Child ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child" 
        ,
            Child 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    return ( members [ Child ].Ancestors.Contains ( Parent ) ) ;
}

AreSiblings

This tests whether or not the two values have the same parent. Note that root values are not siblings.

public static bool
AreSiblings
(
    T Child1
,
    T Child2
)
{
    if ( !members.ContainsKey ( Child1 ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child1" 
        ,
            Child1 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    if ( !members.ContainsKey ( Child2 ) )
    {
        throw ( new System.ArgumentOutOfRangeException 
        ( 
            "Child2" 
        ,
            Child2 
        , 
            "That value does not exist in the enum"
        ) ) ;
    }
    
    return 
    ( 
        !roots.Contains ( Child1 )
    && 
        !roots.Contains ( Child2 )
    && 
        Equal 
        ( 
            members [ Child1 ].Ancestors [ 0 ]
        ,
            members [ Child2 ].Ancestors [ 0 ]
        )
    ) ;
}

Using the Code

Because EnumTree is a static class, construction is handled automatically, you don't instantiate it, you just use the methods:

foreach ( AnimalKind beast in PIEBALD.Types.EnumTree<AnimalKind>.GetValues() ) ...
As you probably don't want to type that all out each time, you will probably use a using directive; I suggest you make an alias:
using AnimalKindTree=PIEBALD.Types.EnumTree<AnimalKind> ;
 
...
 
foreach ( AnimalKind beast in AnimalKindTree.GetValues() ) ...

The included EnumTreeTest.cs file demonstrates this and other things that can be done with an EnumTree and an appropriate enumeration.

History

2008-06-12 First submitted

License

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

Share

About the Author

PIEBALDconsult
Software Developer (Senior)
United States United States
BSCS 1992 Wentworth Institute of Technology
 
Originally from the Boston (MA) area. Lived in SoCal for a while. Now in the Phoenix (AZ) area.
 
OpenVMS enthusiast, ISO 8601 evangelist, photographer, opinionated SOB, acknowledged contrarian
 
---------------
 
"If you need help knowing what to think, let me know and I'll tell you." -- Jeffrey Snover [MSFT]
 
"Typing is no substitute for thinking." -- R.W. Hamming
 
"I find it appalling that you can become a programmer with less training than it takes to become a plumber." -- Bjarne Stroustrup
 
ZagNut’s Law: Arrogance is inversely proportional to ability.
 
"Well blow me sideways with a plastic marionette. I've just learned something new - and if I could award you a 100 for that post I would. Way to go you keyboard lovegod you." -- Pete O'Hanlon
 
"linq'ish" sounds like "inept" in German -- Andreas Gieriet
 
"Things would be different if I ran the zoo." -- Dr. Seuss
 
"Wrong is evil, and it must be defeated." – Jeff Ello
 
"A good designer must rely on experience, on precise, logical thinking, and on pedantic exactness." -- Nigel Shaw
 
“It’s always easier to do it the hard way.” -- Blackhart

“If Unix wasn’t so bad that you can’t give it away, Bill Gates would never have succeeded in selling Windows.” -- Blackhart

"Omit needless local variables." -- Strunk... had he taught programming
 

 
"We learn more from our mistakes than we do from getting it right the first time."
 
My first rule of debugging: "If you get a different error message, you're making progress."
 
My golden rule of database management: "Do not unto others' databases as you would not have done unto yours."
 
My general rule of software development: "Design should be top-down, but implementation should be bottom-up."

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 12 Jun 2008
Article Copyright 2008 by PIEBALDconsult
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid