/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You 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 org.apache.harmony.tests.java.util;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;

public class RefSortedMap<K, V> extends java.util.AbstractMap<K, V>
        implements SortedMap<K, V>, Cloneable, Serializable {

    private static final long serialVersionUID = 1L;

    private static final class MapEntry<K, V> implements Map.Entry<K, V> {

        final K key;
        V value;

        MapEntry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V v) {
            V res = value;
            value = v;
            return res;
        }

        public int hashCode() {
            return (getKey() == null ? 0 : getKey().hashCode())
                    ^ (getValue() == null ? 0 : getValue().hashCode());
        }

        public boolean equals(Object object) {
            if (this == object) {
                return true;
            }
            if (object instanceof Map.Entry) {
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
                return (getKey() == null ? entry.getKey() == null : getKey().equals(entry
                        .getKey()))
                        && (getValue() == null ? entry.getValue() == null : getValue()
                        .equals(entry.getValue()));
            }
            return false;
        }
    }

    transient ArrayList<MapEntry<K, V>> entries = new ArrayList<MapEntry<K, V>>();
    transient int modCnt;

    private final Comparator<? super K> comparator;

    class SubMap extends java.util.AbstractMap<K, V>
            implements SortedMap<K, V>, Cloneable {

        final boolean hasStart, hasEnd;
        final K start, end;

        SubMap(boolean hasFirst, K first, boolean hasLast, K last) {
            this.hasStart = hasFirst;
            this.start = first;
            this.hasEnd = hasLast;
            this.end = last;
            if (hasStart && hasEnd && compare(start, end) >= 0) {
                throw new IllegalArgumentException();
            }
        }

        @Override
        public Set<java.util.Map.Entry<K, V>> entrySet() {
            return new AbstractSet<Entry<K, V>>() {

                @Override
                public Iterator<java.util.Map.Entry<K, V>> iterator() {
                    return new Iterator<Entry<K, V>>() {
                        int modCnt = RefSortedMap.this.modCnt;
                        int offset = SubMap.this.size() > 0 ?
                                bsearch(SubMap.this.firstKey()) - 1 :
                                entries.size();

                        public boolean hasNext() {
                            if (modCnt != RefSortedMap.this.modCnt) {
                                throw new ConcurrentModificationException();
                            }
                            return offset + 1 < entries.size()
                                    && isInRange(entries.get(offset + 1).getKey());
                        }

                        public Map.Entry<K, V> next() {
                            if (modCnt != RefSortedMap.this.modCnt) {
                                throw new ConcurrentModificationException();
                            }
                            if (!hasNext()) {
                                throw new NoSuchElementException();
                            }
                            offset++;
                            return entries.get(offset);
                        }

                        public void remove() {
                            if (modCnt != RefSortedMap.this.modCnt) {
                                throw new ConcurrentModificationException();
                            }
                            modCnt++;
                            RefSortedMap.this.modCnt++;
                            RefSortedMap.this.entries.remove(offset);
                            offset--;
                        }

                    };
                }

                @Override
                public int size() {
                    try {
                        int lastIdx = bsearch(SubMap.this.lastKey());
                        int firstIdx = bsearch(SubMap.this.firstKey());
                        return lastIdx - firstIdx + 1;
                    } catch (NoSuchElementException e) {
                        return 0;
                    } catch (ArrayIndexOutOfBoundsException e) {
                        return 0;
                    }
                }

            };
        }

        public Comparator<? super K> comparator() {
            return RefSortedMap.this.comparator();
        }

        public K firstKey() {
            if (!hasStart) {
                K res = RefSortedMap.this.firstKey();
                if (!isInRange(res)) {
                    throw new NoSuchElementException();
                }
                return res;
            }
            int idx = bsearch(start);
            if (idx >= 0) {
                return start;
            }
            if (-idx - 1 >= entries.size() || !isInRange(entries.get(-idx - 1).getKey())) {
                throw new NoSuchElementException();
            }
            return entries.get(-idx - 1).getKey();
        }

        public SortedMap<K, V> headMap(K key) {
            if (!isInRange(key)) {
                throw new IllegalArgumentException();
            }
            return new SubMap(hasStart, start, true, key);
        }

        public K lastKey() {
            if (!hasEnd) {
                K res = RefSortedMap.this.lastKey();
                if (!isInRange(res)) {
                    throw new NoSuchElementException();
                }
                return res;
            }
            int idx = bsearch(end);
            idx = idx >= 0 ? idx - 1 : -idx - 2;
            if (idx < 0 || !isInRange(entries.get(idx).getKey())) {
                throw new NoSuchElementException();
            }
            return entries.get(idx).getKey();
        }

        public SortedMap<K, V> subMap(K startKey, K endKey) {
            if (!isInRange(startKey)) {
                throw new IllegalArgumentException();
            }
            if (!isInRange(endKey)) {
                throw new IllegalArgumentException();
            }
            return new SubMap(true, startKey, true, endKey);
        }

        public SortedMap<K, V> tailMap(K key) {
            if (!isInRange(key)) {
                throw new IllegalArgumentException();
            }
            return new SubMap(true, key, hasEnd, end);
        }

        private boolean isInRange(K key) {
            if (hasStart && compare(key, start) < 0) {
                return false;
            }
            if (hasEnd && compare(key, end) >= 0) {
                return false;
            }
            return true;
        }

    }

    public RefSortedMap() {
        this((Comparator<? super K>) null);
    }

    @SuppressWarnings("unchecked")
    public int compare(K start, K end) {
        return comparator != null ? comparator.compare(start, end)
                : ((Comparable<K>) start).compareTo(end);
    }

    @SuppressWarnings("unchecked")
    public RefSortedMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
        cmp = createCmp();
    }

    public RefSortedMap(Map<? extends K, ? extends V> map) {
        this();
        putAll(map);
    }

    public RefSortedMap(SortedMap<K, ? extends V> map) {
        this(map.comparator());
        putAll(map);
    }

    public Comparator<? super K> comparator() {
        return comparator;
    }

    public Set<Map.Entry<K, V>> entrySet() {
        return tailMap(firstKey()).entrySet();
    }

    public K firstKey() {
        return entries.get(0).getKey();
    }

    public SortedMap<K, V> headMap(K key) {
        return new SubMap(false, null, true, key);
    }

    public Set<K> keySet() {
        return tailMap(firstKey()).keySet();
    }

    public K lastKey() {
        return entries.get(entries.size() - 1).getKey();
    }

    public SortedMap<K, V> subMap(K startKey, K endKey) {
        return new SubMap(true, startKey, true, endKey);
    }

    public SortedMap<K, V> tailMap(K key) {
        return new SubMap(true, key, false, null);
    }

    public Collection<V> values() {
        return tailMap(firstKey()).values();
    }

    public void clear() {
        entries.clear();
    }

    public boolean containsKey(Object arg0) {
        return bsearch(arg0) >= 0;
    }

    public boolean containsValue(Object arg0) {
        for (V v : values()) {
            if (arg0.equals(v)) {
                return true;
            }
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    public V get(Object arg0) {
        int idx = bsearch(arg0);
        return idx >= 0 ? entries.get(idx).getValue() : null;
    }

    public boolean isEmpty() {
        return entries.isEmpty();
    }

    public V put(K arg0, V arg1) {
        modCnt++;
        int idx = bsearch(arg0);
        if (idx >= 0) {
            return entries.get(idx).setValue(arg1);
        }
        entries.add(-idx - 1, new MapEntry<K, V>(arg0, arg1));
        return null;
    }

    public void putAll(Map<? extends K, ? extends V> arg0) {
        for (Map.Entry<? extends K, ? extends V> e : arg0.entrySet()) {
            put(e.getKey(), e.getValue());
        }
    }

    @SuppressWarnings("unchecked")
    public V remove(Object arg0) {
        modCnt++;
        int idx = bsearch(arg0);
        if (idx < 0) {
            return null;
        }
        return entries.remove(idx).getValue();
    }

    transient private Comparator<MapEntry<K, V>> cmp = createCmp();

    Comparator<MapEntry<K, V>> createCmp() {
        return new Comparator<MapEntry<K, V>>() {

            public int compare(MapEntry<K, V> arg0, MapEntry<K, V> arg1) {
                return RefSortedMap.this.compare(arg0.getKey(), arg1.getKey());
            }

        };
    }

    @SuppressWarnings("unchecked")
    private int bsearch(Object arg0) {
        return Collections.binarySearch(entries, new MapEntry<K, V>((K) arg0, null), cmp);
    }

    public int size() {
        return entries.size();
    }

    public RefSortedMap<K, V> clone() {
        return new RefSortedMap<K, V>(this);
    }

    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(size());
        for (Map.Entry<K, V> e : entrySet()) {
            stream.writeObject(e.getKey());
            stream.writeObject(e.getValue());
        }
    }

    @SuppressWarnings("unchecked")
    private void readObject(ObjectInputStream stream) throws IOException,
            ClassNotFoundException {

        cmp = createCmp();
        stream.defaultReadObject();
        int size = stream.readInt();
        entries = new ArrayList<MapEntry<K, V>>(size);
        for (int i = 0; i < size; i++) {
            put((K) stream.readObject(), (V) stream.readObject());
        }
    }

}