package com.atlassian.bitbucket.util;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.annotation.Nonnull;
import javax.annotation.concurrent.NotThreadSafe;
import java.util.Arrays;

import static com.google.common.base.Preconditions.checkArgument;

/**
 * Data structure with {@link java.util.Set}-like semantics that supports mixing short and long SHA hashes.
 * Compared to {@link java.util.TreeSet}, {@code SortedShaSet} has a more compact in-memory representation but
 * comparable insert / contains / remove performance. In high frequency usage, this results in fewer GC operations
 * and better performance.
 * <p>
 * {@code null} and empty values are <em>NOT</em> supported.
 *
 * @since 4.7
 */
@NotThreadSafe
public class SortedShaSet {

    private static final Logger log = LoggerFactory.getLogger(SortedShaSet.class);

    private static final int INITIAL_SIZE = 8;
    private static final int MAX_SIZE = Integer.MAX_VALUE;

    private int length;
    private String[] values;

    public SortedShaSet() {
        values = new String[INITIAL_SIZE];
    }

    /**
     * @param sha the value to add
     * @return {@code true} if the value was added, {@code false} if the value was already present
     */
    public boolean add(@Nonnull String sha) {
        //noinspection ConstantConditions
        checkArgument(sha != null && !"".equals(sha), "sha cannot be empty");
        int index = Arrays.binarySearch(values, 0, length, sha, ShaUtils::compare);
        if (index >= 0) {
            // already contained in the array
            return false;
        }
        // binarySearch returns ((-insertion point) - 1) if not found; reconstruct the insertion point
        index = ~index;
        if (length == values.length) {
            // at capacity, expand the array and insert in the right place
            int newCapacity = length + (length >> 1);
            if (newCapacity < 0) {
                if (length == MAX_SIZE) {
                    // cannot grow the array beyond the requested size
                    throw new IllegalStateException("Cannot grow the array beyond " + length + " elements");
                }
                newCapacity = MAX_SIZE;
            }
            log.trace("Increasing capacity from {} to {}", length, newCapacity);
            String[] expanded = new String[newCapacity];
            System.arraycopy(values, 0, expanded, 0, index);
            System.arraycopy(values, index, expanded, index + 1, length - index);
            values = expanded;
        } else if (index < length) {
            // room left in the array. Make room for the new element by shifting everything after index by 1 pos
            System.arraycopy(values, index, values, index + 1, length - index);
        }
        values[index] = sha;
        ++length;
        return true;
    }

    /**
     * @param sha the value to search for
     * @return {@code true} if the {@code SortedShaSet} contains {@code sha}
     */
    public boolean contains(@Nonnull String sha) {
        return !"".equals(sha) && Arrays.binarySearch(values, 0, length, sha, ShaUtils::compare) >= 0;
    }

    /**
     * @param i the index of the value to retrieve
     * @return the value
     * @throws IndexOutOfBoundsException if the index is out of bounds
     */
    @Nonnull
    public String get(int i) {
        if (i < 0 || i >= length) {
            throw new IndexOutOfBoundsException("Index " + i + " is out of bounds; size = " + length);
        }
        return values[i];
    }

    /**
     * @param sha the value to search for
     * @return the value's index or {@code -1} if not found
     */
    public int indexOf(@Nonnull String sha) {
        if ("".equals(sha)) {
            return -1;
        }
        return Math.max(-1, Arrays.binarySearch(values, 0, length, sha, ShaUtils::compare));
    }

    /**
     * @param sha the value to remove
     * @return {@code true} if the value was removed, otherwise {@code false}
     */
    public boolean remove(@Nonnull String sha) {
        int i = Arrays.binarySearch(values, 0, length, sha, ShaUtils::compare);
        if (i < 0 || "".equals(sha)) {
            // not contained in the array
            return false;
        }

        System.arraycopy(values, i + 1, values, i, length - 1 - i);
        values[length - 1] = null;
        --length;
        return true;
    }

    /**
     * @return the number of items in the {@code SortedShaSet}
     */
    public int size() {
        return length;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        SortedShaSet that = (SortedShaSet) o;
        if (this.length != that.length) {
            return false;
        }
        for (int i = 0; i < length && i < that.length; ++i) {
            if (ShaUtils.compare(values[i], that.values[i]) != 0) {
                return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = 31;
        for (int i = 0; i < length; ++i) {
            result = 31 * result + (values[i].charAt(0));
        }
        return result;
    }
}
