Friend NotInheritable Class IdentifierCreationService
    Implements IIdentifierCreationService
    Private serviceProvider As IServiceProvider = Nothing

    Friend Sub New(ByVal serviceProvider As IServiceProvider)
        Me.serviceProvider = serviceProvider
    End Sub

    Sub ValidateIdentifier(ByVal activity As Activity, ByVal identifier As String) Implements IIdentifierCreationService.ValidateIdentifier
        If identifier Is Nothing Then
            Throw New ArgumentNullException("identifier")
        End If
        If activity Is Nothing Then
            Throw New ArgumentNullException("activity")
        End If
        If activity.Name.ToLower().Equals(identifier.ToLower()) Then
            Return
        End If
        Dim identifiers As New ArrayList()
        Dim rootActivity As Activity = GetRootActivity(activity)
        identifiers.AddRange(GetIdentifiersInCompositeActivity(CType(rootActivity, CompositeActivity)))
        identifiers.Sort()
        If identifiers.BinarySearch(identifier.ToLower(), StringComparer.OrdinalIgnoreCase) >= 0 Then
            Throw New ArgumentException(String.Format("Duplicate Component Identifier 0}", identifier))
        End If
    End Sub

    Sub EnsureUniqueIdentifiers(ByVal parentActivity As CompositeActivity, ByVal childActivities As ICollection) Implements IIdentifierCreationService.EnsureUniqueIdentifiers

        If parentActivity Is Nothing Then
            Throw New ArgumentNullException("parentActivity")
        End If
        If childActivities Is Nothing Then
            Throw New ArgumentNullException("childActivities")
        End If
        Dim allActivities As New List(Of Activity)()

        Dim activities As New Queue(childActivities)
        While activities.Count > 0

            Dim activity As Activity = CType(activities.Dequeue(), Activity)
            If TypeOf activity Is CompositeActivity Then
                For Each child As Activity In CType(activity, CompositeActivity).Activities
                    activities.Enqueue(child)
                Next
            End If

            'If we are moving activities, we need not regenerate their identifiers
            If CType(activity, IComponent).Site IsNot Nothing Then
                Continue While
            End If

            allActivities.Add(activity)
        End While

        ' get the root activity
        Dim rootActivity As CompositeActivity = CType(GetRootActivity(parentActivity), CompositeActivity)
        Dim identifiers As New ArrayList() ' all the identifiers in the workflow
        identifiers.AddRange(GetIdentifiersInCompositeActivity(rootActivity))

        For Each activity As Activity In allActivities

            Dim finalIdentifier As String = activity.Name

            ' now loop until we find a identifier that hasn't been used.
            Dim baseIdentifier As String = GetBaseIdentifier(activity)
            Dim index As Integer = 0

            identifiers.Sort()
            While finalIdentifier Is Nothing Or _
            finalIdentifier.Length = 0 Or _
            identifiers.BinarySearch(finalIdentifier.ToLower(), StringComparer.OrdinalIgnoreCase) >= 0
                finalIdentifier = String.Format("0}1}", baseIdentifier, ++index)
            End While

            ' add new identifier to collection 
            identifiers.Add(finalIdentifier)
            activity.Name = finalIdentifier
        Next
    End Sub

    Private Shared Function GetIdentifiersInCompositeActivity(ByVal CompositeActivity As CompositeActivity) As IList
        Dim identifiers As New ArrayList()
        If CompositeActivity IsNot Nothing Then
            identifiers.Add(CompositeActivity.Name)
            Dim allChildren As IList(Of Activity) = GetAllNestedActivities(CompositeActivity)
            For Each activity As Activity In allChildren
                identifiers.Add(activity.Name)
            Next
        End If

        Return ArrayList.ReadOnly(identifiers)
    End Function

    Private Shared Function GetBaseIdentifier(ByVal activity As Activity)
        Dim baseIdentifier As String = activity.GetType().Name
        Dim b As New StringBuilder(baseIdentifier.Length)
        For i As Integer = 0 To baseIdentifier.Length
            If Char.IsUpper(baseIdentifier(i)) And (i = 0 Or i = baseIdentifier.Length - 1 Or Char.IsUpper(baseIdentifier(i + 1))) Then
                b.Append(Char.ToLower(baseIdentifier(i)))
            Else
                b.Append(baseIdentifier.Substring(i))
                Exit For
            End If
        Next
        Return b.ToString()
    End Function

    Private Shared Function GetRootActivity(ByVal activity As Activity) As Activity
        If activity Is Nothing Then
            Throw New ArgumentException("activity")
        End If

        While activity.Parent IsNot Nothing
            activity = activity.Parent
        End While

        Return activity
    End Function

    Private Shared Function GetAllNestedActivities(ByVal compositeActivity As CompositeActivity) As Activity()

        If compositeActivity Is Nothing Then
            Throw New ArgumentNullException("compositeActivity")
        End If

        Dim nestedActivities As New ArrayList()
        Dim compositeActivities As New Queue()
        compositeActivities.Enqueue(compositeActivity)
        While compositeActivities.Count > 0

            Dim compositeActivity2 As CompositeActivity = CType(compositeActivities.Dequeue(), CompositeActivity)

            For Each activity As Activity In compositeActivity2.Activities
                nestedActivities.Add(activity)
                If activity Is compositeActivity Then
                    compositeActivities.Enqueue(activity)
                End If
            Next

            For Each activity As Activity In compositeActivity2.EnabledActivities
                If Not nestedActivities.Contains(activity) Then
                    nestedActivities.Add(activity)
                    If (activity Is compositeActivity) Then
                        compositeActivities.Enqueue(activity)
                    End If
                End If
            Next
        End While
        Return CType(nestedActivities.ToArray(GetType(Activity)), Activity())
    End Function