/*
 * Copyright (C) 2013 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package android.app;

import static android.app.ActivityThread.DEBUG_CONFIGURATION;

import android.annotation.NonNull;
import android.annotation.Nullable;
import android.content.pm.ActivityInfo;
import android.content.res.AssetManager;
import android.content.res.CompatibilityInfo;
import android.content.res.Configuration;
import android.content.res.Resources;
import android.content.res.ResourcesImpl;
import android.content.res.ResourcesKey;
import android.hardware.display.DisplayManagerGlobal;
import android.os.IBinder;
import android.util.ArrayMap;
import android.util.DisplayMetrics;
import android.util.LocaleList;
import android.util.Log;
import android.util.Pair;
import android.util.Slog;
import android.view.Display;
import android.view.DisplayAdjustments;
import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.util.ArrayUtils;

import java.lang.ref.WeakReference;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.WeakHashMap;
import java.util.function.Predicate;

/** @hide */
public class ResourcesManager {
    static final String TAG = "ResourcesManager";
    private static final boolean DEBUG = false;

    private static ResourcesManager sResourcesManager;

    /**
     * Predicate that returns true if a WeakReference is gc'ed.
     */
    private static final Predicate<WeakReference<Resources>> sEmptyReferencePredicate =
            new Predicate<WeakReference<Resources>>() {
                @Override
                public boolean test(WeakReference<Resources> weakRef) {
                    return weakRef == null || weakRef.get() == null;
                }
            };

    private String[] mSystemLocales = {};
    private final HashSet<String> mNonSystemLocales = new HashSet<>();
    private boolean mHasNonSystemLocales = false;

    /**
     * The global compatibility settings.
     */
    private CompatibilityInfo mResCompatibilityInfo;

    /**
     * The global configuration upon which all Resources are based. Multi-window Resources
     * apply their overrides to this configuration.
     */
    private final Configuration mResConfiguration = new Configuration();

    /**
     * A mapping of ResourceImpls and their configurations. These are heavy weight objects
     * which should be reused as much as possible.
     */
    private final ArrayMap<ResourcesKey, WeakReference<ResourcesImpl>> mResourceImpls =
            new ArrayMap<>();

    /**
     * A list of Resource references that can be reused.
     */
    private final ArrayList<WeakReference<Resources>> mResourceReferences = new ArrayList<>();

    /**
     * Each Activity may have only one Resources object.
     */
    private final WeakHashMap<IBinder, WeakReference<Resources>> mActivityResourceReferences =
            new WeakHashMap<>();

    /**
     * A cache of DisplayId to DisplayAdjustments.
     */
    private final ArrayMap<Pair<Integer, DisplayAdjustments>, WeakReference<Display>> mDisplays =
            new ArrayMap<>();

    public static ResourcesManager getInstance() {
        synchronized (ResourcesManager.class) {
            if (sResourcesManager == null) {
                sResourcesManager = new ResourcesManager();
            }
            return sResourcesManager;
        }
    }

    public Configuration getConfiguration() {
        return mResConfiguration;
    }

    DisplayMetrics getDisplayMetricsLocked() {
        return getDisplayMetricsLocked(Display.DEFAULT_DISPLAY);
    }

    /**
     * Protected so that tests can override and returns something a fixed value.
     */
    @VisibleForTesting
    protected DisplayMetrics getDisplayMetricsLocked(int displayId) {
        DisplayMetrics dm = new DisplayMetrics();
        final Display display =
                getAdjustedDisplay(displayId, DisplayAdjustments.DEFAULT_DISPLAY_ADJUSTMENTS);
        if (display != null) {
            display.getMetrics(dm);
        } else {
            dm.setToDefaults();
        }
        return dm;
    }

    private static void applyNonDefaultDisplayMetricsToConfiguration(
            @NonNull DisplayMetrics dm, @NonNull Configuration config) {
        config.touchscreen = Configuration.TOUCHSCREEN_NOTOUCH;
        config.densityDpi = dm.densityDpi;
        config.screenWidthDp = (int) (dm.widthPixels / dm.density);
        config.screenHeightDp = (int) (dm.heightPixels / dm.density);
        int sl = Configuration.resetScreenLayout(config.screenLayout);
        if (dm.widthPixels > dm.heightPixels) {
            config.orientation = Configuration.ORIENTATION_LANDSCAPE;
            config.screenLayout = Configuration.reduceScreenLayout(sl,
                    config.screenWidthDp, config.screenHeightDp);
        } else {
            config.orientation = Configuration.ORIENTATION_PORTRAIT;
            config.screenLayout = Configuration.reduceScreenLayout(sl,
                    config.screenHeightDp, config.screenWidthDp);
        }
        config.smallestScreenWidthDp = config.screenWidthDp; // assume screen does not rotate
        config.compatScreenWidthDp = config.screenWidthDp;
        config.compatScreenHeightDp = config.screenHeightDp;
        config.compatSmallestScreenWidthDp = config.smallestScreenWidthDp;
    }

    public boolean applyCompatConfigurationLocked(int displayDensity,
            @NonNull Configuration compatConfiguration) {
        if (mResCompatibilityInfo != null && !mResCompatibilityInfo.supportsScreen()) {
            mResCompatibilityInfo.applyToConfiguration(displayDensity, compatConfiguration);
            return true;
        }
        return false;
    }

    /**
     * Returns an adjusted {@link Display} object based on the inputs or null if display isn't
     * available.
     *
     * @param displayId display Id.
     * @param displayAdjustments display adjustments.
     */
    public Display getAdjustedDisplay(final int displayId,
            @Nullable DisplayAdjustments displayAdjustments) {
        final DisplayAdjustments displayAdjustmentsCopy = (displayAdjustments != null)
                ? new DisplayAdjustments(displayAdjustments) : new DisplayAdjustments();
        final Pair<Integer, DisplayAdjustments> key =
                Pair.create(displayId, displayAdjustmentsCopy);
        synchronized (this) {
            WeakReference<Display> wd = mDisplays.get(key);
            if (wd != null) {
                final Display display = wd.get();
                if (display != null) {
                    return display;
                }
            }
            final DisplayManagerGlobal dm = DisplayManagerGlobal.getInstance();
            if (dm == null) {
                // may be null early in system startup
                return null;
            }
            final Display display = dm.getCompatibleDisplay(displayId, key.second);
            if (display != null) {
                mDisplays.put(key, new WeakReference<>(display));
            }
            return display;
        }
    }

    /**
     * Creates an AssetManager from the paths within the ResourcesKey.
     *
     * This can be overridden in tests so as to avoid creating a real AssetManager with
     * real APK paths.
     * @param key The key containing the resource paths to add to the AssetManager.
     * @return a new AssetManager.
    */
    @VisibleForTesting
    protected AssetManager createAssetManager(@NonNull final ResourcesKey key) {
        AssetManager assets = new AssetManager();

        // resDir can be null if the 'android' package is creating a new Resources object.
        // This is fine, since each AssetManager automatically loads the 'android' package
        // already.
        if (key.mResDir != null) {
            if (assets.addAssetPath(key.mResDir) == 0) {
                return null;
            }
        }

        if (key.mSplitResDirs != null) {
            for (final String splitResDir : key.mSplitResDirs) {
                if (assets.addAssetPath(splitResDir) == 0) {
                    return null;
                }
            }
        }

        if (key.mOverlayDirs != null) {
            for (final String idmapPath : key.mOverlayDirs) {
                assets.addOverlayPath(idmapPath);
            }
        }

        if (key.mLibDirs != null) {
            for (final String libDir : key.mLibDirs) {
                if (libDir.endsWith(".apk")) {
                    // Avoid opening files we know do not have resources,
                    // like code-only .jar files.
                    if (assets.addAssetPath(libDir) == 0) {
                        Log.w(TAG, "Asset path '" + libDir +
                                "' does not exist or contains no resources.");
                    }
                }
            }
        }
        return assets;
    }

    private Configuration generateConfig(@NonNull ResourcesKey key, @NonNull DisplayMetrics dm) {
        Configuration config;
        final boolean isDefaultDisplay = (key.mDisplayId == Display.DEFAULT_DISPLAY);
        final boolean hasOverrideConfig = key.hasOverrideConfiguration();
        if (!isDefaultDisplay || hasOverrideConfig) {
            config = new Configuration(getConfiguration());
            if (!isDefaultDisplay) {
                applyNonDefaultDisplayMetricsToConfiguration(dm, config);
            }
            if (hasOverrideConfig) {
                config.updateFrom(key.mOverrideConfiguration);
                if (DEBUG) Slog.v(TAG, "Applied overrideConfig=" + key.mOverrideConfiguration);
            }
        } else {
            config = getConfiguration();
        }
        return config;
    }


    private ResourcesImpl createResourcesImpl(@NonNull ResourcesKey key) {
        AssetManager assets = createAssetManager(key);
        DisplayMetrics dm = getDisplayMetricsLocked(key.mDisplayId);
        Configuration config = generateConfig(key, dm);
        ResourcesImpl impl = new ResourcesImpl(assets, dm, config, key.mCompatInfo);
        if (DEBUG) {
            Slog.d(TAG, "- creating impl=" + impl + " with key: " + key);
        }
        return impl;
    }

    /**
     * Finds a cached ResourcesImpl object that matches the given ResourcesKey.
     *
     * @param key The key to match.
     * @return a ResourcesImpl if the key matches a cache entry, null otherwise.
     */
    private ResourcesImpl findResourcesImplForKey(@NonNull ResourcesKey key) {
        WeakReference<ResourcesImpl> weakImplRef = mResourceImpls.get(key);
        ResourcesImpl impl = weakImplRef != null ? weakImplRef.get() : null;
        if (impl != null && impl.getAssets().isUpToDate()) {
            return impl;
        }
        return null;
    }

    /**
     * Find the ResourcesKey that this ResourcesImpl object is associated with.
     * @return the ResourcesKey or null if none was found.
     */
    private ResourcesKey findKeyForResourceImpl(@NonNull ResourcesImpl resourceImpl) {
        final int refCount = mResourceImpls.size();
        for (int i = 0; i < refCount; i++) {
            WeakReference<ResourcesImpl> weakImplRef = mResourceImpls.valueAt(i);
            ResourcesImpl impl = weakImplRef != null ? weakImplRef.get() : null;
            if (impl != null && resourceImpl == impl) {
                return mResourceImpls.keyAt(i);
            }
        }
        return null;
    }

    /**
     * Gets an existing Resources object tied to this Activity, or creates one if it doesn't exist
     * or the class loader is different.
     */
    private Resources getOrCreateResourcesForActivityLocked(@NonNull IBinder activityToken,
            @NonNull ClassLoader classLoader, @NonNull ResourcesImpl impl) {
        // This is a request tied to an Activity, meaning we will need to update all
        // Activity related Resources to match this configuration.
        WeakReference<Resources> weakResourceRef = mActivityResourceReferences.get(activityToken);
        Resources resources = weakResourceRef != null ? weakResourceRef.get() : null;
        if (resources == null || !Objects.equals(resources.getClassLoader(), classLoader)) {
            resources = new Resources(classLoader);
            mActivityResourceReferences.put(activityToken, new WeakReference<>(resources));
            if (DEBUG) {
                Slog.d(TAG, "- creating new ref=" + resources);
            }
        } else {
            if (DEBUG) {
                Slog.d(TAG, "- using existing ref=" + resources);
            }
        }

        if (resources.getImpl() != impl) {
            if (DEBUG) {
                Slog.d(TAG, "- setting ref=" + resources + " with impl=" + impl);
            }

            // Setting an impl is expensive because we update all ThemeImpl references.
            // too.
            resources.setImpl(impl);
        }
        return resources;
    }

    /**
     * Gets an existing Resources object if the class loader and ResourcesImpl are the same,
     * otherwise creates a new Resources object.
     */
    private Resources getOrCreateResourcesLocked(@NonNull ClassLoader classLoader,
            @NonNull ResourcesImpl impl) {
        // Find an existing Resources that has this ResourcesImpl set.
        final int refCount = mResourceReferences.size();
        for (int i = 0; i < refCount; i++) {
            WeakReference<Resources> weakResourceRef = mResourceReferences.get(i);
            Resources resources = weakResourceRef != null ? weakResourceRef.get() : null;
            if (resources != null &&
                    Objects.equals(resources.getClassLoader(), classLoader) &&
                    resources.getImpl() == impl) {
                if (DEBUG) {
                    Slog.d(TAG, "- using existing ref=" + resources);
                }
                return resources;
            }
        }

        // Create a new Resources reference and use the existing ResourcesImpl object.
        Resources resources = new Resources(classLoader);
        resources.setImpl(impl);
        mResourceReferences.add(new WeakReference<>(resources));
        if (DEBUG) {
            Slog.d(TAG, "- creating new ref=" + resources);
            Slog.d(TAG, "- setting ref=" + resources + " with impl=" + impl);
        }
        return resources;
    }

    /**
     * Gets or creates a new Resources object associated with the IBinder token. References returned
     * by this method live as long as the Activity, meaning they can be cached and used by the
     * Activity even after a configuration change. If any other parameter is changed
     * (resDir, splitResDirs, overrideConfig) for a given Activity, the same Resources object
     * is updated and handed back to the caller. However, changing the class loader will result in a
     * new Resources object.
     * <p/>
     * If activityToken is null, a cached Resources object will be returned if it matches the
     * input parameters. Otherwise a new Resources object that satisfies these parameters is
     * returned.
     *
     * @param activityToken Represents an Activity. If null, global resources are assumed.
     * @param resDir The base resource path. Can be null (only framework resources will be loaded).
     * @param splitResDirs An array of split resource paths. Can be null.
     * @param overlayDirs An array of overlay paths. Can be null.
     * @param libDirs An array of resource library paths. Can be null.
     * @param displayId The ID of the display for which to create the resources.
     * @param overrideConfig The configuration to apply on top of the base configuration. Can be
     * null. Mostly used with Activities that are in multi-window which may override width and
     * height properties from the base config.
     * @param compatInfo The compatibility settings to use. Cannot be null. A default to use is
     * {@link CompatibilityInfo#DEFAULT_COMPATIBILITY_INFO}.
     * @param classLoader The class loader to use when inflating Resources. If null, the
     * {@link ClassLoader#getSystemClassLoader()} is used.
     * @return a Resources object from which to access resources.
     */
    public Resources getResources(@Nullable IBinder activityToken,
            @Nullable String resDir,
            @Nullable String[] splitResDirs,
            @Nullable String[] overlayDirs,
            @Nullable String[] libDirs,
            int displayId,
            @Nullable Configuration overrideConfig,
            @NonNull CompatibilityInfo compatInfo,
            @Nullable ClassLoader classLoader) {
        final ResourcesKey key = new ResourcesKey(
                resDir,
                splitResDirs,
                overlayDirs,
                libDirs,
                displayId,
                overrideConfig != null ? new Configuration(overrideConfig) : null, // Copy
                compatInfo);

        classLoader = classLoader != null ? classLoader : ClassLoader.getSystemClassLoader();

        final boolean findSystemLocales;
        final boolean hasNonSystemLocales;
        synchronized (this) {
            findSystemLocales = (mSystemLocales.length == 0);
            hasNonSystemLocales = mHasNonSystemLocales;

            if (DEBUG) {
                Throwable here = new Throwable();
                here.fillInStackTrace();
                Slog.w(TAG, "!! Get resources for activity=" + activityToken + " key=" + key, here);
            }

            if (activityToken != null) {
                ResourcesImpl resourcesImpl = findResourcesImplForKey(key);
                if (resourcesImpl != null) {
                    if (DEBUG) {
                        Slog.d(TAG, "- using existing impl=" + resourcesImpl);
                    }
                    return getOrCreateResourcesForActivityLocked(activityToken, classLoader,
                            resourcesImpl);
                }

                // We will create the ResourcesImpl object outside of holding this lock.

            } else {
                // Clean up any dead references so they don't pile up.
                ArrayUtils.unstableRemoveIf(mResourceReferences, sEmptyReferencePredicate);

                // Not tied to an Activity, find a shared Resources that has the right ResourcesImpl
                ResourcesImpl resourcesImpl = findResourcesImplForKey(key);
                if (resourcesImpl != null) {
                    if (DEBUG) {
                        Slog.d(TAG, "- using existing impl=" + resourcesImpl);
                    }
                    return getOrCreateResourcesLocked(classLoader, resourcesImpl);
                }

                // We will create the ResourcesImpl object outside of holding this lock.
            }
        }

        // If we're here, we didn't find a suitable ResourcesImpl to use, so create one now.
        ResourcesImpl resourcesImpl = createResourcesImpl(key);

        final String[] systemLocales = findSystemLocales
                ? AssetManager.getSystem().getLocales() : null;
        final String[] nonSystemLocales = resourcesImpl.getAssets().getNonSystemLocales();
        // Avoid checking for non-pseudo-locales if we already know there were some from a previous
        // Resources. The default value (for when hasNonSystemLocales is true) doesn't matter,
        // since mHasNonSystemLocales will also be true, and thus isPseudoLocalesOnly would not be
        // able to affect mHasNonSystemLocales.
        final boolean isPseudoLocalesOnly = hasNonSystemLocales ||
                LocaleList.isPseudoLocalesOnly(nonSystemLocales);

        synchronized (this) {
            if (mSystemLocales.length == 0) {
                mSystemLocales = systemLocales;
            }
            mNonSystemLocales.addAll(Arrays.asList(nonSystemLocales));
            mHasNonSystemLocales = mHasNonSystemLocales || !isPseudoLocalesOnly;

            ResourcesImpl existingResourcesImpl = findResourcesImplForKey(key);
            if (existingResourcesImpl != null) {
                if (DEBUG) {
                    Slog.d(TAG, "- got beat! existing impl=" + existingResourcesImpl
                            + " new impl=" + resourcesImpl);
                }
                resourcesImpl.getAssets().close();
                resourcesImpl = existingResourcesImpl;
            } else {
                // Add this ResourcesImpl to the cache.
                mResourceImpls.put(key, new WeakReference<>(resourcesImpl));
            }

            final Resources resources;
            if (activityToken != null) {
                resources = getOrCreateResourcesForActivityLocked(activityToken, classLoader,
                        resourcesImpl);
            } else {
                resources = getOrCreateResourcesLocked(classLoader, resourcesImpl);
            }
            return resources;
        }
    }

    /**
     * Updates an Activity's Resources object with overrideConfig. The Resources object
     * that was previously returned by
     * {@link #getResources(IBinder, String, String[], String[], String[], int, Configuration,
     * CompatibilityInfo, ClassLoader)} is
     * still valid and will have the updated configuration.
     * @param activityToken The Activity token.
     * @param overrideConfig The configuration override to update.
     */
    public void updateResourcesForActivity(@NonNull IBinder activityToken,
            @Nullable Configuration overrideConfig) {
        final ClassLoader classLoader;
        final ResourcesKey oldKey;
        synchronized (this) {
            // Extract the ResourcesKey that was last used to create the Resources for this
            // activity.
            WeakReference<Resources> weakResRef = mActivityResourceReferences.get(activityToken);
            final Resources resources = weakResRef != null ? weakResRef.get() : null;
            if (resources == null) {
                Slog.e(TAG, "can't update resources for uncached activity " + activityToken);
                return;
            }

            classLoader = resources.getClassLoader();
            oldKey = findKeyForResourceImpl(resources.getImpl());
            if (oldKey == null) {
                Slog.e(TAG, "can't find ResourcesKey for resources impl=" + resources.getImpl());
                return;
            }
        }

        // Update the Resources object with the new override config and all of the existing
        // settings.
        getResources(activityToken, oldKey.mResDir, oldKey.mSplitResDirs, oldKey.mOverlayDirs,
                oldKey.mLibDirs, oldKey.mDisplayId, overrideConfig, oldKey.mCompatInfo,
                classLoader);
    }

    /* package */ void setDefaultLocalesLocked(@NonNull LocaleList locales) {
        final int bestLocale;
        if (mHasNonSystemLocales) {
            bestLocale = locales.getFirstMatchIndexWithEnglishSupported(mNonSystemLocales);
        } else {
            // We fallback to system locales if there was no locale specifically supported by the
            // assets. This is to properly support apps that only rely on the shared system assets
            // and don't need assets of their own.
            bestLocale = locales.getFirstMatchIndexWithEnglishSupported(mSystemLocales);
        }
        // set it for Java, this also affects newly created Resources
        LocaleList.setDefault(locales, bestLocale);
    }

    public final boolean applyConfigurationToResourcesLocked(@NonNull Configuration config,
                                                             @Nullable CompatibilityInfo compat) {
        if (!mResConfiguration.isOtherSeqNewer(config) && compat == null) {
            if (DEBUG || DEBUG_CONFIGURATION) Slog.v(TAG, "Skipping new config: curSeq="
                    + mResConfiguration.seq + ", newSeq=" + config.seq);
            return false;
        }
        int changes = mResConfiguration.updateFrom(config);
        // Things might have changed in display manager, so clear the cached displays.
        mDisplays.clear();
        DisplayMetrics defaultDisplayMetrics = getDisplayMetricsLocked();

        if (compat != null && (mResCompatibilityInfo == null ||
                !mResCompatibilityInfo.equals(compat))) {
            mResCompatibilityInfo = compat;
            changes |= ActivityInfo.CONFIG_SCREEN_LAYOUT
                    | ActivityInfo.CONFIG_SCREEN_SIZE
                    | ActivityInfo.CONFIG_SMALLEST_SCREEN_SIZE;
        }

        Configuration localeAdjustedConfig = config;
        final LocaleList configLocales = config.getLocales();
        if (!configLocales.isEmpty()) {
            setDefaultLocalesLocked(configLocales);
            final LocaleList adjustedLocales = LocaleList.getAdjustedDefault();
            if (adjustedLocales != configLocales) { // has the same result as .equals() in this case
                // The first locale in the list was not chosen. So we create a modified
                // configuration with the adjusted locales (which moves the chosen locale to the
                // front).
                localeAdjustedConfig = new Configuration();
                localeAdjustedConfig.setTo(config);
                localeAdjustedConfig.setLocales(adjustedLocales);
                // Also adjust the locale list in mResConfiguration, so that the Resources created
                // later would have the same locale list.
                if (!mResConfiguration.getLocales().equals(adjustedLocales)) {
                    mResConfiguration.setLocales(adjustedLocales);
                    changes |= ActivityInfo.CONFIG_LOCALE;
                }
            }
        }

        Resources.updateSystemConfiguration(localeAdjustedConfig, defaultDisplayMetrics, compat);

        ApplicationPackageManager.configurationChanged();
        //Slog.i(TAG, "Configuration changed in " + currentPackageName());

        Configuration tmpConfig = null;

        for (int i = mResourceImpls.size() - 1; i >= 0; i--) {
            ResourcesKey key = mResourceImpls.keyAt(i);
            ResourcesImpl r = mResourceImpls.valueAt(i).get();
            if (r != null) {
                if (DEBUG || DEBUG_CONFIGURATION) Slog.v(TAG, "Changing resources "
                        + r + " config to: " + localeAdjustedConfig);
                int displayId = key.mDisplayId;
                boolean isDefaultDisplay = (displayId == Display.DEFAULT_DISPLAY);
                DisplayMetrics dm = defaultDisplayMetrics;
                final boolean hasOverrideConfiguration = key.hasOverrideConfiguration();
                if (!isDefaultDisplay || hasOverrideConfiguration) {
                    if (tmpConfig == null) {
                        tmpConfig = new Configuration();
                    }
                    tmpConfig.setTo(localeAdjustedConfig);
                    if (!isDefaultDisplay) {
                        dm = getDisplayMetricsLocked(displayId);
                        applyNonDefaultDisplayMetricsToConfiguration(dm, tmpConfig);
                    }
                    if (hasOverrideConfiguration) {
                        tmpConfig.updateFrom(key.mOverrideConfiguration);
                    }
                    r.updateConfiguration(tmpConfig, dm, compat);
                } else {
                    r.updateConfiguration(localeAdjustedConfig, dm, compat);
                }
                //Slog.i(TAG, "Updated app resources " + v.getKey()
                //        + " " + r + ": " + r.getConfiguration());
            } else {
                //Slog.i(TAG, "Removing old resources " + v.getKey());
                mResourceImpls.removeAt(i);
            }
        }

        return changes != 0;
    }
}