EnumTree

• Download source - 15.04 KB

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() ) ...

using AnimalKindTree=PIEBALD.Types.EnumTree<AnimalKind> ;
 
...
 
foreach ( AnimalKind beast in AnimalKindTree.GetValues() ) ...