package edu.cmu.cs;

import edu.cmu.cs.glacier.qual.Immutable;

/**
 * The map item.
 *
 * @author BaseX Team 2005-16, BSD License
 * @author Leo Woerteler
 */
@Immutable
public final class Map {
    private final HashBucket @Immutable[] buckets;

    /**
     * Constructor.
     */
    public Map() {
        buckets = null;
    }

    private Map(int capacity) {
        buckets = new HashBucket @Immutable [capacity];
    }

    private Map(HashBucket @Immutable[] buckets) {
        this.buckets = buckets;
    }

    private int bucketForObject(Object o) {
        if (o == null) {
            return 0;
        }
        return o.hashCode() % buckets.length;
    }

    /**
     * Deletes a key from this map.
     * @param key key to delete (must not be {@code null})
     * @return updated map if changed, {@code this} otherwise
     */
    public Map delete(final Object key) {
        int bucket = bucketForObject(key);
        HashBucket hashBucket = buckets[bucket];

        if (hashBucket == null) {
            return this;
        }

        HashBucket[] newBuckets = buckets.clone();
        newBuckets[bucket] = hashBucket.delete(key);

        return new Map(newBuckets.clone());
    }

    /**
     * Gets the value from this map.
     * @param key key to look for (must not be {@code null})
     * @return bound value if found, {@code null}otherwise
     */
    public Object get(final Object key) {
        int bucket = bucketForObject(key);
        HashBucket hashBucket = buckets[bucket];

        if (hashBucket == null) {
            return null;
        }
        return hashBucket.get(key);
    }

    /**
     * Checks if the given key exists in the map.
     * @param key key to look for (must not be {@code null})
     * @return {@code true()} if the key exists, {@code false()} otherwise
     */
    public boolean contains(final Object key) {
        int bucket = bucketForObject(key);
        HashBucket hashBucket = buckets[bucket];

        if (hashBucket == null) {
            return false;
        }
        return hashBucket.contains(key);
    }

    private int numBuckets(int minBuckets) {
        final int[] sizes = {1, 3, 7, 13, 31, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739};

        for (int i = 0; i < sizes.length; i++) {
            if (minBuckets < sizes[i]) {
                return sizes[i];
            }
        }
        return sizes[sizes.length - 1];
    }

    /**
     * Puts the given value into this map and replaces existing keys.
     * @param key key to insert (must not be {@code null})
     * @param value value to insert
     * @return updated map if changed, {@code this} otherwise

     */
    public Map put(final Object key, final Object value) {


        HashBucket newBuckets[] = null;

        if (buckets == null) {
            newBuckets = new HashBucket[numBuckets(1)];
        }
        else if (mapSize() > buckets.length / 2) { // Assume load factor of 2
            // Resize
            // Should really optimize this. This is very expensive.
            Map newMap = new Map(numBuckets(buckets.length * 2));
            for (int i = 0; i < buckets.length; i++) {
                HashBucket bucketContents = buckets[i];
                if (bucketContents != null) {
                    newMap = bucketContents.copyIntoMap(newMap);
                }
            }
            newBuckets = newMap.buckets.clone();
        }
        else {
            newBuckets = buckets.clone();
        }

        HashBucket newList = null;

        int hash = key.hashCode();
        int bucket = hash % newBuckets.length;

        if (newBuckets[bucket] == null) {
            newList = new HashBucket(key, value);
        }
        else
        {
            newList = newBuckets[bucket].put(key, value);
        }
        newBuckets[bucket] = newList;
        return new Map(newBuckets.clone());
    }

    /**
     * Number of values contained in this map.
     * @return size
     */
    public int mapSize() {
        int size = 0;
        for (HashBucket l : buckets) {
            if (l != null) {
                size += l.size();
            }
        }
        return size;
    }

    public String toDebugString() {
        final StringBuilder sb = new StringBuilder("map {\n");
        for (int i = 0; i < buckets.length; i++) {
            sb.append("[" + i + "] = ");
            if (buckets[i] == null) {
                sb.append("(null)\n");
            }
            else {
                buckets[i].toDebugString(sb, " ");
                sb.append("\n");
            }
        }
        return sb.append('}').toString();
    }


    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("map {");
        if (buckets != null) {
            for (int i = 0; i < buckets.length; i++) {
                if (buckets[i] != null) {
                    buckets[i].toString(sb);
                }
            }
        }
        return sb.append('}').toString();
    }
}
