class AuthenticatorUtils {

    public static final String NEGOTIATE = "Negotiate";

    private AuthenticatorUtils() {
        // Prevent outside initialization
    }

    public static @Nullable String getHeaderWithPrefix(@Nullable List<String> authenticateHeaders, String prefix) {<FILL_FUNCTION_BODY>}

    private static @Nullable String computeBasicAuthentication(@Nullable Realm realm) {
        return realm != null ? computeBasicAuthentication(realm.getPrincipal(), realm.getPassword(), realm.getCharset()) : null;
    }

    private static String computeBasicAuthentication(@Nullable String principal, @Nullable String password, Charset charset) {
        String s = principal + ':' + password;
        return "Basic " + Base64.getEncoder().encodeToString(s.getBytes(charset));
    }

    public static String computeRealmURI(Uri uri, boolean useAbsoluteURI, boolean omitQuery) {
        if (useAbsoluteURI) {
            return omitQuery && isNonEmpty(uri.getQuery()) ? uri.withNewQuery(null).toUrl() : uri.toUrl();
        } else {
            String path = uri.getNonEmptyPath();
            return omitQuery || !isNonEmpty(uri.getQuery()) ? path : path + '?' + uri.getQuery();
        }
    }

    private static String computeDigestAuthentication(Realm realm, Uri uri) {

        String realmUri = computeRealmURI(uri, realm.isUseAbsoluteURI(), realm.isOmitQuery());

        StringBuilder builder = new StringBuilder().append("Digest ");
        append(builder, "username", realm.getPrincipal(), true);
        append(builder, "realm", realm.getRealmName(), true);
        append(builder, "nonce", realm.getNonce(), true);
        append(builder, "uri", realmUri, true);
        if (isNonEmpty(realm.getAlgorithm())) {
            append(builder, "algorithm", realm.getAlgorithm(), false);
        }

        append(builder, "response", realm.getResponse(), true);

        if (realm.getOpaque() != null) {
            append(builder, "opaque", realm.getOpaque(), true);
        }

        if (realm.getQop() != null) {
            append(builder, "qop", realm.getQop(), false);
            // nc and cnonce only sent if server sent qop
            append(builder, "nc", realm.getNc(), false);
            append(builder, "cnonce", realm.getCnonce(), true);
        }
        builder.setLength(builder.length() - 2); // remove tailing ", "

        // FIXME isn't there a more efficient way?
        return new String(StringUtils.charSequence2Bytes(builder, ISO_8859_1), StandardCharsets.UTF_8);
    }

    private static void append(StringBuilder builder, String name, @Nullable String value, boolean quoted) {
        builder.append(name).append('=');
        if (quoted) {
            builder.append('"').append(value).append('"');
        } else {
            builder.append(value);
        }
        builder.append(", ");
    }

    public static @Nullable String perConnectionProxyAuthorizationHeader(Request request, @Nullable Realm proxyRealm) {
        String proxyAuthorization = null;
        if (proxyRealm != null && proxyRealm.isUsePreemptiveAuth()) {
            switch (proxyRealm.getScheme()) {
                case NTLM:
                case KERBEROS:
                case SPNEGO:
                    List<String> auth = request.getHeaders().getAll(PROXY_AUTHORIZATION);
                    if (getHeaderWithPrefix(auth, "NTLM") == null) {
                        String msg = NtlmEngine.INSTANCE.generateType1Msg();
                        proxyAuthorization = "NTLM " + msg;
                    }

                    break;
                default:
            }
        }

        return proxyAuthorization;
    }

    public static @Nullable String perRequestProxyAuthorizationHeader(Request request, @Nullable Realm proxyRealm) {
        String proxyAuthorization = null;
        if (proxyRealm != null && proxyRealm.isUsePreemptiveAuth()) {

            switch (proxyRealm.getScheme()) {
                case BASIC:
                    proxyAuthorization = computeBasicAuthentication(proxyRealm);
                    break;
                case DIGEST:
                    if (isNonEmpty(proxyRealm.getNonce())) {
                        // update realm with request information
                        final Uri uri = request.getUri();
                        proxyRealm = realm(proxyRealm)
                                .setUri(uri)
                                .setMethodName(request.getMethod())
                                .build();
                        proxyAuthorization = computeDigestAuthentication(proxyRealm, uri);
                    }
                    break;
                case NTLM:
                case KERBEROS:
                case SPNEGO:
                    // NTLM, KERBEROS and SPNEGO are only set on the first request with a connection,
                    // see perConnectionProxyAuthorizationHeader
                    break;
                default:
                    throw new IllegalStateException("Invalid Authentication scheme " + proxyRealm.getScheme());
            }
        }

        return proxyAuthorization;
    }

    public static @Nullable String perConnectionAuthorizationHeader(Request request, @Nullable ProxyServer proxyServer,
                                                                    @Nullable Realm realm) {
        String authorizationHeader = null;

        if (realm != null && realm.isUsePreemptiveAuth()) {
            switch (realm.getScheme()) {
                case NTLM:
                    String msg = NtlmEngine.INSTANCE.generateType1Msg();
                    authorizationHeader = "NTLM " + msg;
                    break;
                case KERBEROS:
                case SPNEGO:
                    String host;
                    if (proxyServer != null) {
                        host = proxyServer.getHost();
                    } else if (request.getVirtualHost() != null) {
                        host = request.getVirtualHost();
                    } else {
                        host = request.getUri().getHost();
                    }

                    try {
                        authorizationHeader = NEGOTIATE + ' ' + SpnegoEngine.instance(
                                realm.getPrincipal(),
                                realm.getPassword(),
                                realm.getServicePrincipalName(),
                                realm.getRealmName(),
                                realm.isUseCanonicalHostname(),
                                realm.getCustomLoginConfig(),
                                realm.getLoginContextName()).generateToken(host);
                    } catch (SpnegoEngineException e) {
                        throw new RuntimeException(e);
                    }
                    break;
                default:
                    break;
            }
        }

        return authorizationHeader;
    }

    public static @Nullable String perRequestAuthorizationHeader(Request request, @Nullable Realm realm) {
        String authorizationHeader = null;
        if (realm != null && realm.isUsePreemptiveAuth()) {

            switch (realm.getScheme()) {
                case BASIC:
                    authorizationHeader = computeBasicAuthentication(realm);
                    break;
                case DIGEST:
                    if (isNonEmpty(realm.getNonce())) {
                        // update realm with request information
                        final Uri uri = request.getUri();
                        realm = realm(realm)
                                .setUri(uri)
                                .setMethodName(request.getMethod())
                                .build();
                        authorizationHeader = computeDigestAuthentication(realm, uri);
                    }
                    break;
                case NTLM:
                case KERBEROS:
                case SPNEGO:
                    // NTLM, KERBEROS and SPNEGO are only set on the first request with a connection,
                    // see perConnectionAuthorizationHeader
                    break;
                default:
                    throw new IllegalStateException("Invalid Authentication " + realm);
            }
        }

        return authorizationHeader;
    }
}

        if (authenticateHeaders != null) {
            for (String authenticateHeader : authenticateHeaders) {
                if (authenticateHeader.regionMatches(true, 0, prefix, 0, prefix.length())) {
                    return authenticateHeader;
                }
            }
        }

        return null;
    
<no_super_class>