from collections.abc import MutableSequence, MutableMapping

class Lict(MutableSequence, MutableMapping):
    """
    List / dictionary hybrid container

    Lict attempts to provide an API for a list which supports optional element
    keys in addition to normal positional indices.  For Lict, index types are
    int and slice.  Keys may be any other type except for None, as None
    indicates an unkeyed value.

    Nearly all of the operations you'd except to perform on list or dict are
    implemented here.  However, in cases of conflict, the list behavior is
    usually preferred (for example: iter(Lict) iterates over values instead of
    keys).  In general, Licts are slightly more list-like, since keys are
    optional, but sequence is required.

    Licts can be constructed from any iterable, including other Licts.  When
    constructing from mappings, similar heuristics as dict's are used to parse
    key values.

    In addition to keys and indices, slices may be used to return, modify, or
    delete a portion of a Lict.  The start and end fields of a slice may be
    either keys or indices, however the step field must be an integer as usual.

    When assigning to a non-existent key, the new element is sequentially
    inserted at the end of the Lict.
    """

    def __init__(self, values=None):
        """Construct new Lict, optionally populated by the given iterable."""
        self.__keys = []
        self.__vals = []
        if values is not None:
            self.extend(values)

    def __repr__(self):
        """Return human-readable Lict."""
        s = ""
        for i in range(len(self)):
            if self.__keys[i] is not None:
                s += f"{repr(self.__keys[i])}: "
            s += f"{repr(self.__vals[i])}, "
        return f"{{[{s[:-2]}]}}"

    def __copy__(self):
        """Return shallow copy of object."""
        return self.copy()

    def copy(self):
        """Return shallow copy of object."""
        return Lict(self)

    def key2idx(self, arg):
        """
        Return value of index type for the given input.

        For keys, return the corresponding index, or raise KeyError.
        For slices, return a slice with components converted to index type.

        If arg is already an index (or None) it is returned as-is with no
        assertions made.
        """
        if isinstance(arg, slice):
            return slice(self.key2idx(arg.start), self.key2idx(arg.stop), arg.step)
        if isinstance(arg, int) or arg is None:
            return arg
        try:
            return self.__keys.index(arg)
        except ValueError as ex:
            raise KeyError(f"Lict: Key does not exist: {arg}") from ex

    def idx2key(self, arg):
        """
        Return value of key type for the given input.

        For indices, return the corresponding key, None, or raise IndexError.
        For slices, return a slice with components converted to key type.

        If arg is already a key type (or None) it is returned as-is with no
        assertions made.
        """
        if isinstance(arg, slice):
            return slice(self.idx2key(arg.start), self.idx2key(arg.stop), arg.step)
        if not isinstance(arg, int) or arg is None:
            return arg
        return self.__keys[arg]

    def haskey(self, arg):
        """
        Test existence of key in Lict object.

        `x in Lict` only tests for the _value_ x in Lict.  This is consistent
        with list behavior.  This method is provided to test keys as well.
        Raises TypeError on any index type.
        """
        if arg is None:
            return False
        if isinstance(arg, (int, slice)):
            raise TypeError(f"Lict: Unsupported key type: {type(arg)}")
        return arg in self.__keys

    def __assign_slice(self, i, value):
        """Update Lict values according to element slice."""
        value = Lict(value)
        tmp = self.copy()
        tmp.__keys[i] = value.__keys
        tmp.__vals[i] = value.__vals

        check_keys = [ x for x in tmp.__keys if x is not None ]
        if len(check_keys) != len(set(check_keys)):
            raise ValueError("Lict: Slice assignment results in duplicate keys")

        self.__keys = tmp.__keys
        self.__vals = tmp.__vals

    # collections.abc abstract methods

    def __len__(self):
        """Return number of elements in Lict."""
        assert len(self.__keys) == len(self.__vals)
        return len(self.__keys)

    def __getitem__(self, arg):
        """Return value for given index, key, or slice."""
        i = self.key2idx(arg)
        if isinstance(i, slice):
            return Lict(zip(self.__keys[i], self.__vals[i]))
        return self.__vals[i]

    def __setitem__(self, arg, value):
        """Set value for given index, key, or slice."""
        try:
            i = self.key2idx(arg)
        except KeyError:
            self.append(value, arg)
        else:
            if isinstance(i, slice):
                self.__assign_slice(i, value)
            else:
                self.__vals[i] = value

    def __delitem__(self, arg):
        """Delete value for given index, key, or slice."""
        i = self.key2idx(arg)
        del self.__keys[i]
        del self.__vals[i]

    def insert(self, where, value, key=None):
        """Insert value into Lict.  Optionally apply the given key."""
        if self.haskey(key):
            raise KeyError(f"Lict: Key is not unique: {key}")
        i = self.key2idx(where)
        self.__keys.insert(i, key)
        self.__vals.insert(i, value)

    # Sequence overrides

    def append(self, value, key=None):
        """Append value to Lict.  Optionally apply the given key."""
        self.insert(len(self), value, key)

    def extend(self, values):
        """Append all values in given iterable to the Lict."""
        try: values = [ [k, v] for k, v in values.items() ]
        except:
            try: values = [ [k, v] for k, v in iter(values) ]
            except: values = [ [None, v] for v in iter(values) ]
        for k, v in values:
            self.append(v, k)

    def reverse(self):
        """Reverse the sequence of Lict in-place.  Keys follow values."""
        self.__keys.reverse()
        self.__vals.reverse()

    # Mapping overrides

    def get(self, key, default=None):
        """Return value for given key, or default if unable."""
        try: return self[key]
        except: return default

    def popitem(self):
        """Pop a key-value pair from the Lict and return it."""
        return (self.__keys.pop(), self.__vals.pop())

    def items(self):
        """Return an iterable of key-value pairs."""
        return list(zip(self.__keys, self.__vals))

    def keys(self):
        """Return an iterable of the Lict's keys."""
        return [ x for x in self.__keys if x is not None ]

    def values(self):
        """Return an iterable of the Lict's values."""
        return list(self.__vals)

    def update(self, values):
        """Method is unsupported."""
        raise NotImplementedError