private static boolean isTree ( int n , boolean [ ] [ ] chart ) { if ( ! chart [ 0 ] [ n ] ) { // Root must be a span. return false ; } for ( int width = 1 ; width <= n ; width ++ ) { for ( int start = 0 ; start <= n - width ; start ++ ) { int end = start + width ; if ( width == 1 ) { if ( ! chart [ start ] [ end ] ) { // All width 1 spans must be set. return false ; } } else { if ( chart [ start ] [ end ] ) { // Count the number of pairs of child spans which could have been combined to form this span. int childPairCount = 0 ; for ( int mid = start + 1 ; mid <= end - 1 ; mid ++ ) { if ( chart [ start ] [ mid ] && chart [ mid ] [ end ] ) { childPairCount ++ ; } } if ( childPairCount != 1 ) { // This span should have been built from exactly one pair of child spans. return false ; } } } } } return true ; }
Returns true if the boolean chart represents a set of spans that form a valid constituency tree false otherwise .