public K findLessOrEqual()

in core-avl/src/main/java/org/apache/directory/server/core/avltree/ArrayTree.java [694:838]

• 110 lines of code
• 20 McCabe index (conditional complexity)

    public K findLessOrEqual( K key )
    {
        if ( key == null )
        {
            return null;
        }

        switch ( size )
        {
            case 0:
                return null;

            case 1:
                if ( comparator.compare( array[0], key ) <= 0 )
                {
                    return array[0];
                }
                else
                {
                    return null;
                }

            case 2:
                int res = comparator.compare( array[0], key );

                if ( res > 0 )
                {
                    return null;
                }
                else if ( res == 0 )
                {
                    return array[0];
                }

                res = comparator.compare( array[1], key );

                if ( res == 0 )
                {
                    return array[1];
                }
                else if ( comparator.compare( array[1], key ) > 0 )
                {
                    return array[0];
                }
                else
                {
                    return array[1];
                }

            default:
                // Split the array in two parts, the left part an the right part
                int current = size >> 1;
                int start = 0;
                int end = size - 1;

                while ( end - start + 1 > 2 )
                {
                    res = comparator.compare( array[current], key );

                    if ( res == 0 )
                    {
                        return array[current];
                    }
                    else if ( res < 0 )
                    {
                        start = current;
                        current = ( current + end + 1 ) >> 1;
                    }
                    else
                    {
                        end = current;
                        current = ( current + start + 1 ) >> 1;
                    }
                }

                switch ( end - start + 1 )
                {
                    case 1:
                        // Three cases :
                        // o The value is equal to the current position, or below
                        // the current position :
                        //   - if the current position is at the beginning
                        //     of the array, return null
                        //   - otherwise, return the previous position in the array
                        // o The value is above the current position :
                        //   - return the current position
                        res = comparator.compare( array[start], key );

                        if ( res > 0 )
                        {
                            // start can be equal to 0. Check that
                            if ( start == 1 )
                            {
                                return null;
                            }
                            else
                            {
                                return array[start - 1];
                            }
                        }
                        else
                        {
                            return array[start];
                        }

                    case 2:
                        // Four cases :
                        // o the value is equal the current position, or below 
                        //   the first position :
                        //   - if the current position is at the beginning
                        //     of the array, return null
                        //   - otherwise, return the previous element
                        // o the value is above the first position but below
                        //   or equal the second position, return the first position
                        // o otherwise, return the second position
                        res = comparator.compare( array[start], key );

                        if ( res > 0 )
                        {
                            if ( start == 0 )
                            {
                                return null;
                            }
                            else
                            {
                                return array[start - 1];
                            }
                        }

                        res = comparator.compare( array[start + 1], key );

                        if ( res > 0 )
                        {
                            return array[start];
                        }
                        else
                        {
                            return array[start + 1];
                        }

                    default:
                        return null;
                }
        }
    }