/* **********************************************************************************
 *
 * Copyright (c) Microsoft Corporation. All rights reserved.
 *
 * This source code is subject to terms and conditions of the Shared Source License
 * for IronPython. A copy of the license can be found in the License.html file
 * at the root of this distribution. If you can not locate the Shared Source License
 * for IronPython, please send an email to ironpy@microsoft.com.
 * By using this source code in any fashion, you are agreeing to be bound by
 * the terms of the Shared Source License for IronPython.
 *
 * You must not remove this notice, or any other, from this software.
 *
 * **********************************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

using IronPython.Compiler;

namespace IronPython.Runtime {

    //!!! Giving up HybridDictionary performance, consider adding list for small sizes
    [PythonType("dict")]
    public class Dict : IMapping, IDictionary<object, object>, IComparable, ICloneable, IPythonEquality, IDictionary, ICodeFormattable, IDictionary<SymbolId,object> {
        internal static readonly IEqualityComparer<object> Comparer = new PythonObjectComparer();

        internal Dictionary<object, object> data;

        #region Constructors
        public Dict() {
            this.data = new Dictionary<object, object>(Comparer);
        }

        public Dict(object o)
            : this() {
            Update(o);
        }

        internal Dict(int size) { data = new Dictionary<object, object>(size, Comparer); }

        /// <summary>
        /// Helper function for creating a dictionary of the specified type (either
        /// Dict's type or a subtype of dict)
        /// </summary>
        internal static object MakeDict(PythonType cls) {
            if (cls == TypeCache.Dict) {
                return new Dict();
            }
            return cls.Call(new object[0]);
        }
        #endregion

        #region Object overrides
        [PythonName("__str__")]
        public override string ToString() {
            return DictOps.ToString(this);
        }

        #endregion

        #region IDictionary<object,object> Members

        public void Add(object key, object value) {
            lock(this) data.Add(DictOps.NullToObj(key), value);
        }

        void Replace(object key, object value) {
            lock (this) data[DictOps.NullToObj(key)] = value;
        }

        public bool ContainsKey(object key) {
            lock (this) return data.ContainsKey(DictOps.NullToObj(key));
        }

        public ICollection<object> Keys {
            get { lock (this) return data.Keys; }
        }

        public bool Remove(object key) {
            lock (this) return data.Remove(DictOps.NullToObj(key));
        }

        public bool TryGetValue(object key, out object value) {
            lock (this) return data.TryGetValue(DictOps.NullToObj(key), out value);
        }

        public ICollection<object> Values {
            get { lock (this) return data.Values; }
        }
       
        #endregion

        #region ICollection<KeyValuePair<object,object>> Members

        public void Add(KeyValuePair<object, object> item) {
            lock (this) data[DictOps.NullToObj(item.Key)] = item.Value;
        }

        [PythonName("clear")]
        public void Clear() {
            lock (this) data.Clear();
        }

        public bool Contains(KeyValuePair<object, object> item) {
            lock (this) return data.ContainsKey(DictOps.NullToObj(item.Key));
        }

        public void CopyTo(KeyValuePair<object, object>[] array, int arrayIndex) {
            lock (this) {
                Dictionary<object, object>.Enumerator ie = data.GetEnumerator();
                while (ie.MoveNext()) {
                    array[arrayIndex++] = new KeyValuePair<object, object>(DictOps.ObjToNull(ie.Current.Key), ie.Current.Value);
                }
            }
        }

        public int Count {
            get { return data.Count; }
        }

        public bool IsReadOnly {
            get { return ((ICollection<KeyValuePair<object, object>>)data).IsReadOnly; }
        }

        public bool Remove(KeyValuePair<object, object> item) {
            lock (this) return data.Remove(DictOps.NullToObj(item.Key));
        }

        #endregion

        #region IEnumerable<KeyValuePair<object,object>> Members

        [PythonName("__iter__")]
        public IEnumerator<KeyValuePair<object, object>> GetEnumerator() {
            return new DictKeyValueEnumerator(data.GetEnumerator());
        }

        #endregion

        #region IEnumerable Members

        [PythonName("__iter__")]
        IEnumerator IEnumerable.GetEnumerator() {
            return new DictKeyEnumerator(data.GetEnumerator());
        }

        #endregion

        #region IMapping Members

        [PythonName("get")]
        public object GetValue(object key) {
            return DictOps.GetIndex(this, key);
        }

        [PythonName("get")]
        public object GetValue(object key, object defaultValue) {
            return DictOps.GetIndex(this, key, defaultValue);
        }

        public virtual object this[object key] {
            get {
                object realKey = DictOps.NullToObj(key);
                object ret;
                lock (this) if (TryGetValue(realKey, out ret)) return ret;
                throw Ops.KeyError("'{0}'", key);
            }
            set {
                lock (this) data[DictOps.NullToObj(key)] = value;
            }
        }

        [PythonName("__delitem__")]
        public virtual void DeleteItem(object key) {
            DictOps.DelIndex(this, key);
        }

        #endregion

        #region IPythonContainer Members

        [PythonName("__len__")]
        public int GetLength() {
            return DictOps.Length(this);
        }

        [PythonName("__contains__")]
        public bool ContainsValue(object value) {
            return DictOps.Contains(this, value);
        }

        #endregion

        #region Python dict implementation

        [PythonName("has_key")]
        public bool HasKey(object key) {
            return DictOps.HasKey(this, key);
        }

        [PythonName("pop")]
        public object Pop(object key) {
            return DictOps.Pop(this, key);
        }

        [PythonName("pop")]
        public object Pop(object key, object defaultValue) {
            return DictOps.Pop(this, key, defaultValue);
        }

        [PythonName("popitem")]
        public Tuple PopItem() {
            return DictOps.PopItem(this);
        }

        [PythonName("setdefault")]
        public object SetDefault(object key) {
            return DictOps.SetDefault(this, key);
        }

        [PythonName("setdefault")]
        public object SetDefault(object key, object defaultValue) {
            return DictOps.SetDefault(this, key, defaultValue);
        }

        [PythonName("keys")]
        public List keys() {
            return DictOps.Keys(this);
        }

        [PythonName("values")]
        public List values() {
            return DictOps.Values(this);
        }

        [PythonName("items")]
        public List Items() {
            return DictOps.Items(this);
        }

        [PythonName("iteritems")]
        public IEnumerator IterItems() {
            return DictOps.IterItems(this);
        }

        [PythonName("iterkeys")]
        public IEnumerator IterKeys() {
            return DictOps.IterKeys(this);
        }

        [PythonName("itervalues")]
        public IEnumerator IterValues() {
            return DictOps.IterValues(this);
        }

        [PythonName("update")]
        public void Update() {
        }

        [PythonName("update")]
        public void Update(object b) {
            DictOps.Update(this, b);
        }

        //!!! These must be able to be done cleaner and faster        
        [PythonName("fromkeys")]
        internal static object FromKeys(object[] keys) {
            Dict ret = new Dict();
            for (int i = 0; i < keys.Length; i++) {
                ret.Add(keys[i], null);
            }
            return ret;
        }

        [PythonName("fromkeysany")]
        private static object fromkeysAny(PythonType cls, object o, object value) {
            object ret = MakeDict(cls);
            if (ret.GetType() == typeof(Dict)) {
                Dict dr = ret as Dict;
                IEnumerator i = Ops.GetEnumerator(o);
                while (i.MoveNext()) {
                    dr[i.Current] = value;
                }
            } else {
                // slow path - user defined dictionary.
                IEnumerator i = Ops.GetEnumerator(o);
                while (i.MoveNext()) {
                    Ops.SetIndex(ret, i.Current, value);
                }
            }
            return ret;
        }

        [PythonClassMethod("fromkeys")]
        public static object FromKeys(PythonType cls, object seq) {
            return FromKeys(cls, seq, null);
        }

        [PythonClassMethod("fromkeys")]
        public static object FromKeys(PythonType cls, object seq, object value) {
            XRange xr = seq as XRange;
            if (xr != null) {
                int n = xr.GetLength();
                object ret = MakeDict(cls);
                if (ret.GetType() == typeof(Dict)) {
                    Dict dr = ret as Dict;
                    for (int i = 0; i < n; i++) {
                        dr[xr[i]] = value;
                    }
                } else {
                    // slow path, user defined dict
                    for (int i = 0; i < n; i++) {
                        Ops.SetIndex(ret, xr[i], value);
                    }
                }
                return ret;
            }
            return fromkeysAny(cls, seq, value);
        }


        #endregion

        #region IComparable Members

        int IComparable.CompareTo(object obj) {
            IDictionary<object,object> other = obj as IDictionary<object,object>;
            // CompareTo is allowed to throw (string, int, etc... all do it if they don't get a matching type)
            if (other == null) throw Ops.TypeError("CompareTo argument must be a Dictionary");

            //!!! too expensive
            List thisItems = DictOps.Items(this);
            List otherItems = DictOps.Items(other);
            thisItems.Sort();
            otherItems.Sort();

            return thisItems.CompareTo(otherItems);
        }

        #endregion

        #region ICloneable Members

        [PythonName("copy")]
        public object Clone() {
            return new Dict(new Dictionary<object, object>(data));
        }

        #endregion

        #region IPythonEquality Members

        [PythonName("__hash__")]
        public object PythonGetHashCode() {
            throw Ops.TypeErrorForUnhashableType("dict");
        }

        [PythonName("__eq__")]
        public object PythonEquals(object other) {
            IDictionary<object, object> oth = null;
            if (!(other is Dict || other is CustomFieldIdDict || other is FieldIdDict))
                return false;

            oth = (IDictionary<object, object>)other;
            Debug.Assert(oth != null);
            Debug.Assert(oth is IPythonEquality);

            if (oth.Count != Count) return false;
            
            List myKeys;
            lock (this) myKeys = this.keys();

            foreach (object o in myKeys) {
                object res;
                if (!oth.TryGetValue(o, out res) || !Ops.EqualRetBool(res , this[o])) return false;
           }
           return true;
        }

        #endregion

        #region IDictionary Members

        void IDictionary.Add(object key, object value) {
            this[key] = value;
        }

        void IDictionary.Clear() {
            DictOps.Clear(this);
        }

        bool IDictionary.Contains(object key) {
            return ContainsKey(key);
        }

        IDictionaryEnumerator IDictionary.GetEnumerator() {
            return data.GetEnumerator();
        }

        bool IDictionary.IsFixedSize {
            get { return false; }
        }

        bool IDictionary.IsReadOnly {
            get { return false; }
        }

        ICollection IDictionary.Keys {
            get { return this.keys(); }
        }

        void IDictionary.Remove(object key) {
            data.Remove(key);            
        }

        ICollection IDictionary.Values {
            get { return values(); }
        }

        object IDictionary.this[object key] {
            get {
                return data[key];
            }
            set {
                data[key] = value;
            }
        }

        #endregion

        #region ICollection Members

        void ICollection.CopyTo(Array array, int index) {            
            throw new Exception("The method or operation is not implemented.");
        }

        int ICollection.Count {
            get { return data.Count; }
        }

        bool ICollection.IsSynchronized {
            get { return false; }
        }

        object ICollection.SyncRoot {
            get { return null; }
        }

        #endregion

        #region ICodeFormattable Members

        [PythonName("__repr__")]
        public virtual string ToCodeString() {
            return ToString();
        }

        #endregion

        #region Fast Attribute Access Support 
        /* IDictionary<SymbolId,object> is implemented on our built-in
         * dictionaries to allow users to assign dictionaries into
         * classes.  These dictionaries will resolve their key via
         * the field table, but only get used when the user does
         * explicit dictionary assignment.
         *
         */

        #region IDictionary<SymbolId,object> Members

        void IDictionary<SymbolId, object>.Add(SymbolId key, object value) {
            Add(SymbolTable.IdToString(key), value);
        }

        bool IDictionary<SymbolId, object>.ContainsKey(SymbolId key) {
            return ContainsKey(SymbolTable.IdToString(key));
        }

        ICollection<SymbolId> IDictionary<SymbolId, object>.Keys {
            get {
                List<SymbolId> res = new List<SymbolId>();
                
                foreach (object item in data.Keys) {
                    string s = item as string;
                    if (s != null) {
                        res.Add(SymbolTable.StringToId(s));
                    }
                }
                return res;
            }
        }

        bool IDictionary<SymbolId, object>.Remove(SymbolId key) {
            return Remove(SymbolTable.IdToString(key));
        }

        bool IDictionary<SymbolId, object>.TryGetValue(SymbolId key, out object value) {
            return TryGetValue(SymbolTable.IdToString(key), out value);
        }

        ICollection<object> IDictionary<SymbolId, object>.Values {
            get { return data.Values; }
        }

        object IDictionary<SymbolId, object>.this[SymbolId key] {
            get {
                return this[SymbolTable.IdToString(key)];
            }
            set {
                this[SymbolTable.IdToString(key)] = value;
            }
        }

        #endregion

        #region ICollection<KeyValuePair<SymbolId,object>> Members

        void ICollection<KeyValuePair<SymbolId, object>>.Add(KeyValuePair<SymbolId, object> item) {
            Add(new KeyValuePair<object, object>(SymbolTable.IdToString(item.Key), item.Value));
        }

        void ICollection<KeyValuePair<SymbolId, object>>.Clear() {
            data.Clear();
        }

        bool ICollection<KeyValuePair<SymbolId, object>>.Contains(KeyValuePair<SymbolId, object> item) {
            object val;
            if (data.TryGetValue(SymbolTable.IdToString(item.Key), out val) && val == item.Value) {
                return true;
            }
            return false;
        }

        void ICollection<KeyValuePair<SymbolId, object>>.CopyTo(KeyValuePair<SymbolId, object>[] array, int arrayIndex) {
            throw new Exception("The method or operation is not implemented.");
        }

        int ICollection<KeyValuePair<SymbolId, object>>.Count {
            get {
                return data.Count;
            }
        }

        bool ICollection<KeyValuePair<SymbolId, object>>.IsReadOnly {
            get { return false; }
        }

        bool ICollection<KeyValuePair<SymbolId, object>>.Remove(KeyValuePair<SymbolId, object> item) {
            return this.Remove(new KeyValuePair<object,object>(SymbolTable.IdToString(item.Key), item.Value));
        }

        #endregion

        #region IEnumerable<KeyValuePair<SymbolId,object>> Members

        IEnumerator<KeyValuePair<SymbolId, object>> IEnumerable<KeyValuePair<SymbolId, object>>.GetEnumerator() {
            foreach(KeyValuePair<object,object> item in data){
                string s = item.Key as string;
                if (s != null) {
                    yield return new KeyValuePair<SymbolId, object>(SymbolTable.StringToId(s), item.Value);
                }
            }
        }

        #endregion

        #endregion
    }

    [PythonType(typeof(Dict))]
    internal class EnvironmentDict : Dict {
        public EnvironmentDict() : base(Environment.GetEnvironmentVariables()) { }

        public override object this[object key] {
            set {
                data[DictOps.NullToObj(key)] = value;

                string s1 = key as string;
                string s2 = value as string;
                if (s1 != null && s2 != null)
                    Environment.SetEnvironmentVariable(s1, s2);
            }
        }

        [PythonName("__delitem__")]
        public override void DeleteItem(object key) {
            base.DeleteItem(key);

            string s = key as string;
            if (s != null)
                Environment.SetEnvironmentVariable(s, string.Empty);
        }
    }

    public static class DictOps {
        static object nullObject = new object();

        public static object GetIndex(IDictionary<object, object> self, object key) {
            return GetIndex(self, key, null);
        }

        public static object GetIndex(IDictionary<object, object> self, object key, object defaultValue) {
            object ret;
            if (self.TryGetValue(key, out ret)) return ret;
            return defaultValue;
        }

        public static object SetDefault(IDictionary<object, object> self, object key) {
            return SetDefault(self, key, null);
        }

        public static object SetDefault(IDictionary<object, object> self, object key, object defaultValue) {
            object ret;
            if (self.TryGetValue(key, out ret)) return ret;
            self[key] = defaultValue;
            return defaultValue;
        }


        public static void DelIndex(IDictionary<object, object> self, object key) {
            if (!self.Remove(key)) {
                throw Ops.KeyError("'{0}'", key);
            }
        }

        public static int Length(IDictionary<object, object> self) {
            return self.Count;
        }

        public static bool Contains(IDictionary<object, object> self, object value) {
            return self.ContainsKey(value);
        }

        public static void Clear(IDictionary<object, object> self) {
            self.Clear();
        }

        public static bool HasKey(IDictionary<object, object> self, object key) {
            return self.ContainsKey(key);
        }

        public static object Pop(IDictionary<object, object> self, object key) {
            //??? perf won't match expected Python perf
            object ret;
            if (self.TryGetValue(key, out ret)) {
                self.Remove(key);
                return ret;
            } else {
                throw Ops.KeyError("'{0}'", key);
            }
        }

        public static object Pop(IDictionary<object, object> self, object key, object defaultValue) {
            //??? perf won't match expected Python perf
            object ret;
            if (self.TryGetValue(key, out ret)) {
                self.Remove(key);
                return ret;
            } else {
                return defaultValue;
            }
        }

        public static Tuple PopItem(IDictionary<object, object> self) {
            IEnumerator<KeyValuePair<object, object>> ie = self.GetEnumerator();
            if (ie.MoveNext()) {
                object key = ie.Current.Key;
                object val = ie.Current.Value;
                self.Remove(key);
                return Tuple.MakeTuple(key, val);
            }
            throw Ops.KeyError("dictionary is empty");
        }

        public static List Items(IDictionary<object, object> self) {
            List ret = List.MakeEmptyList(self.Count);
            foreach (KeyValuePair<object, object> kv in self) {
                ret.AddNoLock(Tuple.MakeTuple(kv.Key, kv.Value));
            }
            return ret;
        }

        public static List Keys(IDictionary<object, object> self) {
            List l = List.Make(self.Keys);
            for (int i = 0; i < l.Count; i++) {
                if (l[i] == nullObject) {
                    l[i] = DictOps.ObjToNull(l[i]);
                    break;
                }
            }
            return l;
        }

        public static List Values(IDictionary<object, object> self) {
            return List.Make(self.Values);
        }

        public static bool AddKeyValue(IDictionary<object,object> self, object o) {
            //!!! optimize for Tuple, List, other easy cases
            //ICollection c = (ICollection)o;
            //!!!if (c.Count != 2) throw Ops.ValueError("dictionary update sequence element has length {0}, 2 required", c.Count);

            IEnumerator i = Ops.GetEnumerator(o); //c.GetEnumerator();
            if (i.MoveNext()) {
                object key = i.Current;
                if (i.MoveNext()) {
                    object value = i.Current;
                    self[key] = value;

                    return !i.MoveNext();
                }
            }
            return false;
        }


        public static void Update(IDictionary<object, object> self, object b) {
            object keysFunc;
            IDictionary dict = b as IDictionary;
            if (dict != null) {
                IDictionaryEnumerator e = dict.GetEnumerator();
                while (e.MoveNext()) {
                    self[DictOps.NullToObj(e.Key)] = e.Value;
                }
            } else if (Ops.TryGetAttr(b, SymbolTable.Keys, out keysFunc)) {
                // user defined dictionary
                IEnumerator i = Ops.GetEnumerator(Ops.Call(keysFunc));
                while (i.MoveNext()) {
                    self[DictOps.NullToObj(i.Current)] = Ops.GetIndex(b, i.Current);
                }
            } else {
                // list of lists (key/value pairs), list of tuples,
                // tuple of tuples, etc...
                IEnumerator i = Ops.GetEnumerator(b);
                int index = 0;
                while (i.MoveNext()) {
                    if (!AddKeyValue(self, i.Current)) {
                        throw Ops.ValueError("dictionary update sequence element #{0} has bad length; 2 is required", index);
                    }
                    index++;
                }
            }
        }
        //!!! not appropriately lazy
        public static IEnumerator IterItems(IDictionary<object, object> self) {
            return Items(self).GetEnumerator();
        }

        public static IEnumerator IterKeys(IDictionary<object, object> self) {
            return Keys(self).GetEnumerator();
        }

        public static IEnumerator IterValues(IDictionary<object, object> self) {
            return Values(self).GetEnumerator();
        }

        public static string ToString(IDictionary<object, object> self) {
            StringBuilder buf = new StringBuilder();
            buf.Append("{");
            bool first = true;
            foreach (KeyValuePair<object, object> kv in self) {
                if (first) first = false;
                else buf.Append(", ");

                if (kv.Key == nullObject)
                    buf.Append("None");
                else
                    buf.Append(Ops.StringRepr(kv.Key));
                buf.Append(": ");
                buf.Append(Ops.StringRepr(kv.Value));
            }
            buf.Append("}");
            return buf.ToString();
        }

        public static object NullToObj(object o) {
            if (o == null) return nullObject;
            return o;
        }

        public static object ObjToNull(object o) {
            if (o == nullObject) return null;
            return o;
        }
    }
   
    public class DictDynamicType : ReflectedType, IFancyCallable {
        public DictDynamicType()
            : base(typeof(Dict)) {
        }

        public object Call(object[] args, string[] names) {
            Initialize();

            object[] newArgs = new object[(args.Length - names.Length) + 1];
            Array.Copy(args, 0, newArgs, 1, newArgs.Length - 1);
            newArgs[0] = TypeCache.Dict;
            Dict ret = (Dict)ctor.Call(newArgs);

            for (int i = 0; i < names.Length; i++) {
                ret[names[i]] = args[i + (newArgs.Length - 1)];
            }
            return ret;
        }
    }

    public class DictKeyValueEnumerator : IEnumerator, IEnumerator<KeyValuePair<object, object>> {
        IEnumerator<KeyValuePair<object, object>> innerEnum;

        public DictKeyValueEnumerator(IEnumerator<KeyValuePair<object, object>> inner) {
            innerEnum = inner;
        }

        public bool MoveNext() {
            return innerEnum.MoveNext();
        }

        public void Reset() {
            innerEnum.Reset();
        }

        object IEnumerator.Current {
            get {
                return new KeyValuePair<object, object>(DictOps.ObjToNull(innerEnum.Current.Key), innerEnum.Current.Value);
            }
        }
        public KeyValuePair<object, object> Current {
            get {
                return new KeyValuePair<object, object>(DictOps.ObjToNull(innerEnum.Current.Key), innerEnum.Current.Value);
            }
        }

        public void Dispose() {
            innerEnum.Dispose();
        }

        [PythonName("__iter__")]
        public object GetEnumerator() {
            return this;
        }
    }

    public class DictKeyEnumerator : IEnumerator, IEnumerator<object> {
        Dictionary<object, object>.Enumerator innerEnum;

        public DictKeyEnumerator(Dictionary<object, object>.Enumerator inner) {
            innerEnum = inner;
        }

        public bool MoveNext() {
            try {
                return innerEnum.MoveNext();
            } catch (InvalidOperationException) {
                throw Ops.RuntimeError("dictionary changed size during iteration");
            }
        }

        public void Reset() {
            ((IEnumerator)innerEnum).Reset();
        }

        public object Current {
            get {
                try {
                    return DictOps.ObjToNull(innerEnum.Current.Key);
                } catch (InvalidOperationException) {
                    throw Ops.RuntimeError("dictionary changed size during iteration");
                }
            }
        }

        public void Dispose() {
            innerEnum.Dispose();
        }

        [PythonName("__iter__")]
        public object GetEnumerator() {
            return this;
        }
    }

}