Closest Matching NameToken Algo

Recently worked on a GWT app. This app has a components laid out in a hierarchy. A Primary Page has a set of Tabs. Each Tab has a primary Section listing primary objects and a secondary section listing contents for the selected primary object. Also each tab has a command bar to which commands can be contributed. Since this is a GWT app, every section here is a GWT Presenter widget.


The requirement here was to be able to contribute commands in one or more sections mentioned above using wildcards in a GIN module. And in the code for the given section, we should be able to retrieve commands contributed for that section.

Here was my  solution to this problem :

Every Presenter is assigned a unique ID (let say PresenterContext) based on where its contributed. E.g.
"Inbox:_:SignOff:_:SecondaryWorkArea" signifies a presenter in Inbox (Primary Page) > SignOff (Tab) > SecondaryWorkArea.

Commands are contributed in GIN module using such presenter context IDs. And same command can be contributed to multiple Presenter Contexts. Here are different examples of Contributions for a command :

private String m_contributions[] = new String[] { "", 
            "Inbox", 
            "Inbox:_:PrimaryWorkArea", 
            "Inbox:_:SecondaryWorkArea", 
            "Inbox:_:SecondaryWorkArea:_:SignOff", 
            "Inbox:_:SignOff:_:PrimaryWorkArea", 
            "Inbox:_:SignOff:_:SecondaryWorkArea", 
            "Inbox:_:SignOff", 
            "Inbox:_:MyTasks", 
            "Inbox:_:MyTasks:_:SignOff",  
            "Inbox:_:MyTasks:_:SecondaryWorkArea", 
            "Inbox:_:MyTasks:_:SecondaryWorkArea:_:SignOff", 
            "PrimaryWorkArea", 
            "SecondaryWorkArea", 
            "SecondaryWorkArea:_:SignOff",  
            "SignOff", 
            "ShowObject:_:SecondaryWorkArea:_:Attachments"  
    };

And here is a test method with desired output :

    @Test
    public void testGetClosestMatchingContext()
    {
        String input = "Inbox:_:AllTasks:_:SecondaryWorkArea:_:Attachments"; 
        String matchingContribution = .getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "Inbox:_:SecondaryWorkArea", matchingContribution ); 

        input = "Inbox:_:AllTasks:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "Inbox:_:SignOff", matchingContribution ); 

        input = "MyTasks:_:SecondaryWorkArea:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "SecondaryWorkArea:_:SignOff", matchingContribution ); 

        input = "AllTasks:_:SecondaryWorkArea:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "SecondaryWorkArea:_:SignOff", matchingContribution ); 

        input = "Inbox:_:AllTasks:_:SecondaryWorkArea:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "Inbox:_:SecondaryWorkArea:_:SignOff", matchingContribution ); 

        input = "ShowObject:_:Attachements"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertNull( matchingContribution );

        input = "ShowObject:_:PrimaryWorkArea:_:Attachements"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "PrimaryWorkArea", matchingContribution ); 

        input = "ShowObject:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "SignOff", matchingContribution ); 

        input = "ShowObject:_:SecondaryWorkArea:_:SignOff"; 
        matchingContribution = getClosestMatchingContext( input, m_contributions );
        Assert.assertEquals( "SecondaryWorkArea:_:SignOff", matchingContribution ); 
    }

Here is the Algo to get closest matching context for an input presenter context:

   
    public String getClosestMatchingContext( String targetContext, String[] contributedContextIDs )
    {
        String tokens[] = split( targetContext );
        String[] lastMatch = contributedContextIDs;
        String result = null;

        int index = 0;

        for( String token : tokens )
        {
            String[] currentMatch = startingWithToken( token, lastMatch, index );
            if( currentMatch != null && currentMatch.length > 0 )
            {
                String match = endingWithToken( token, currentMatch );
                if( match != null )
                {
                    result = match;
                }
                if( result != null )
                {
                    lastMatch = currentMatch;
                    index++;
                }
            }
        }

        return result;
    }

    /**
     * Splits the context id into separate tokens
     * 
     * @param contextID presenter context ID
     * @return array of tokens
     */
    private String[] split( String contextID )
    {
        String[] tokens = contextID.split( IPresenterContext.ID_SEPARATOR );
        if( tokens == null )
        {
            tokens = new String[0];
        }
        return tokens;

    }

    /**
     * Finds the contributions that end with given token
     * 
     * @param token context token
     * @param contributions contributed context IDs
     * @return closest matching context contribution for the specified token, else null is returned.
     */
    private String endingWithToken( String token, String[] contributions )
    {
        assert token != null;
        assert contributions != null;

        String tokenWithSperator = IPresenterContext.ID_SEPARATOR + token;

        for( String contribution : contributions )
        {
            if( contribution.equals( token ) || contribution.endsWith( tokenWithSperator ) )
            {
                return contribution;
            }
        }

        return null;
    }

    /**
     * Finds the contributions that start with specified token.
     * 
     * @param iToken input token
     * @param contributions context contributions
     * @param index index in the specified contributions array to search for in the contributions array
     * @return contributions starting with specified token, else an empty Array is returned.
     */
    private String[] startingWithToken( String iToken, String[] contributions, int index )
    {
        assert iToken != null;
        assert contributions != null;
        assert index >= 0;

        List<String> matches = new ArrayList<>();
        for( String contribution : contributions )
        {
            String[] tokens = split( contribution );
            if( tokens.length > index && tokens[index].equals( iToken ) )
            {
                matches.add( contribution );
            }
        }
        return matches.toArray( new String[0] );
    }