# smartset.py - data structure for revision set

#

# Copyright 2010 Matt Mackall <mpm@selenic.com>

#

# This software may be used and distributed according to the terms of the

# GNU General Public License version 2 or any later version.

from __future__ import absolute_import

from . import (

    encoding,

    error,

    pycompat,

    util,

)

def _formatsetrepr(r):

    """Format an optional printable representation of a set

    ========  =================================

    type(r)   example

    ========  =================================

    tuple     ('<not %r>', other)

    bytes     '<branch closed>'

    callable  lambda: '<branch %r>' % sorted(b)

    object    other

    ========  =================================

    """

    if r is None:

        return ''

    elif isinstance(r, tuple):

        return r[0] % util.rapply(pycompat.maybebytestr, r[1:])

    elif isinstance(r, bytes):

        return r

    elif callable(r):

        return r()

    else:

def _typename(o):

    return pycompat.sysbytes(type(o).__name__).lstrip('_')

class abstractsmartset(object):

    def __nonzero__(self):

        """True if the smartset is not empty"""

        raise NotImplementedError()

    __bool__ = __nonzero__

    def __contains__(self, rev):

        """provide fast membership testing"""

        raise NotImplementedError()

    def __iter__(self):

        """iterate the set in the order it is supposed to be iterated"""

        raise NotImplementedError()

    # Attributes containing a function to perform a fast iteration in a given

    # direction. A smartset can have none, one, or both defined.

    #

    # Default value is None instead of a function returning None to avoid

    # initializing an iterator just for testing if a fast method exists.

    fastasc = None

    fastdesc = None

    def isascending(self):

        """True if the set will iterate in ascending order"""

        raise NotImplementedError()

    def isdescending(self):

        """True if the set will iterate in descending order"""

        raise NotImplementedError()

    def istopo(self):

        """True if the set will iterate in topographical order"""

        raise NotImplementedError()

    def min(self):

        """return the minimum element in the set"""

        if self.fastasc is None:

            v = min(self)

        else:

            for v in self.fastasc():

                break

            else:

                raise ValueError('arg is an empty sequence')

        self.min = lambda: v

        return v

    def max(self):

        """return the maximum element in the set"""

        if self.fastdesc is None:

            return max(self)

        else:

            for v in self.fastdesc():

                break

            else:

                raise ValueError('arg is an empty sequence')

        self.max = lambda: v

        return v

    def first(self):

        """return the first element in the set (user iteration perspective)

        Return None if the set is empty"""

        raise NotImplementedError()

    def last(self):

        """return the last element in the set (user iteration perspective)

        Return None if the set is empty"""

        raise NotImplementedError()

    def __len__(self):

        """return the length of the smartsets

        This can be expensive on smartset that could be lazy otherwise."""

        raise NotImplementedError()

    def reverse(self):

        """reverse the expected iteration order"""

        raise NotImplementedError()

    def sort(self, reverse=False):

        """get the set to iterate in an ascending or descending order"""

        raise NotImplementedError()

    def __and__(self, other):

        """Returns a new object with the intersection of the two collections.

        This is part of the mandatory API for smartset."""

        if isinstance(other, fullreposet):

            return self

        return self.filter(other.__contains__, condrepr=other, cache=False)

    def __add__(self, other):

        """Returns a new object with the union of the two collections.

        This is part of the mandatory API for smartset."""

        return addset(self, other)

    def __sub__(self, other):

        """Returns a new object with the substraction of the two collections.

        This is part of the mandatory API for smartset."""

        c = other.__contains__

        return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),

                           cache=False)

    def filter(self, condition, condrepr=None, cache=True):

        """Returns this smartset filtered by condition as a new smartset.

        `condition` is a callable which takes a revision number and returns a

        boolean. Optional `condrepr` provides a printable representation of

        the given `condition`.

        This is part of the mandatory API for smartset."""

        # builtin cannot be cached. but do not needs to

        if cache and util.safehasattr(condition, 'func_code'):

            condition = util.cachefunc(condition)

        return filteredset(self, condition, condrepr)

    def slice(self, start, stop):

        """Return new smartset that contains selected elements from this set"""

        if start < 0 or stop < 0:

            raise error.ProgrammingError('negative index not allowed')

        return self._slice(start, stop)

    def _slice(self, start, stop):

        # sub classes may override this. start and stop must not be negative,

        # but start > stop is allowed, which should be an empty set.

        ys = []

        it = iter(self)

        for x in xrange(start):

            y = next(it, None)

            if y is None:

                break

        for x in xrange(stop - start):

            y = next(it, None)

            if y is None:

                break

            ys.append(y)

        return baseset(ys, datarepr=('slice=%d:%d %r', start, stop, self))

class baseset(abstractsmartset):

    """Basic data structure that represents a revset and contains the basic

    operation that it should be able to perform.

    Every method in this class should be implemented by any smartset class.

    This class could be constructed by an (unordered) set, or an (ordered)

    list-like object. If a set is provided, it'll be sorted lazily.

    >>> x = [4, 0, 7, 6]

    >>> y = [5, 6, 7, 3]

    Construct by a set:

    >>> xs = baseset(set(x))

    >>> ys = baseset(set(y))

    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]

    [[0, 4, 6, 7, 3, 5], [6, 7], [0, 4]]

    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]

    ['addset', 'baseset', 'baseset']

    Construct by a list-like:

    >>> xs = baseset(x)

    >>> ys = baseset(i for i in y)

    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]

    [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]

    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]

    ['addset', 'filteredset', 'filteredset']

    Populate "_set" fields in the lists so set optimization may be used:

    >>> [1 in xs, 3 in ys]

    [False, True]

    Without sort(), results won't be changed:

    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]

    [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]

    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]

    ['addset', 'filteredset', 'filteredset']

    With sort(), set optimization could be used:

    >>> xs.sort(reverse=True)

    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]

    [[7, 6, 4, 0, 5, 3], [7, 6], [4, 0]]

    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]

    ['addset', 'baseset', 'baseset']

    >>> ys.sort()

    >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]

    [[7, 6, 4, 0, 3, 5], [7, 6], [4, 0]]

    >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]

    ['addset', 'baseset', 'baseset']

    istopo is preserved across set operations

    >>> xs = baseset(set(x), istopo=True)

    >>> rs = xs & ys

    >>> type(rs).__name__

    'baseset'

    >>> rs._istopo

    True

    """

    def __init__(self, data=(), datarepr=None, istopo=False):

        """

        datarepr: a tuple of (format, obj, ...), a function or an object that

                  provides a printable representation of the given data.

        """

        self._ascending = None

        self._istopo = istopo

        if isinstance(data, set):

            # converting set to list has a cost, do it lazily

            self._set = data

            # set has no order we pick one for stability purpose

            self._ascending = True

        else:

            if not isinstance(data, list):

                data = list(data)

            self._list = data

        self._datarepr = datarepr

    @util.propertycache

    def _set(self):

        return set(self._list)

    @util.propertycache

    def _asclist(self):

        asclist = self._list[:]

        asclist.sort()

        return asclist

    @util.propertycache

    def _list(self):

        # _list is only lazily constructed if we have _set

        assert r'_set' in self.__dict__

        return list(self._set)

    def __iter__(self):

        if self._ascending is None:

            return iter(self._list)

        elif self._ascending:

            return iter(self._asclist)

        else:

            return reversed(self._asclist)

    def fastasc(self):

        return iter(self._asclist)

    def fastdesc(self):

        return reversed(self._asclist)

    @util.propertycache

    def __contains__(self):

        return self._set.__contains__

    def __nonzero__(self):

        return bool(len(self))

    __bool__ = __nonzero__

    def sort(self, reverse=False):

        self._ascending = not bool(reverse)

        self._istopo = False

    def reverse(self):

        if self._ascending is None:

            self._list.reverse()

        else:

            self._ascending = not self._ascending

        self._istopo = False

    def __len__(self):

        if r'_list' in self.__dict__:

            return len(self._list)

        else:

            return len(self._set)

    def isascending(self):

        """Returns True if the collection is ascending order, False if not.

        This is part of the mandatory API for smartset."""

        if len(self) <= 1:

            return True

        return self._ascending is not None and self._ascending

    def isdescending(self):

        """Returns True if the collection is descending order, False if not.

        This is part of the mandatory API for smartset."""

        if len(self) <= 1:

            return True

        return self._ascending is not None and not self._ascending

    def istopo(self):

        """Is the collection is in topographical order or not.

        This is part of the mandatory API for smartset."""

        if len(self) <= 1:

            return True

        return self._istopo

    def first(self):

        if self:

            if self._ascending is None:

                return self._list[0]

            elif self._ascending:

                return self._asclist[0]

            else:

                return self._asclist[-1]

        return None

    def last(self):

        if self:

            if self._ascending is None:

                return self._list[-1]

            elif self._ascending:

                return self._asclist[-1]

            else:

                return self._asclist[0]

        return None

    def _fastsetop(self, other, op):

        # try to use native set operations as fast paths

        if (type(other) is baseset and r'_set' in other.__dict__ and r'_set' in

            self.__dict__ and self._ascending is not None):

            s = baseset(data=getattr(self._set, op)(other._set),

                        istopo=self._istopo)

            s._ascending = self._ascending

        else:

            s = getattr(super(baseset, self), op)(other)

        return s

    def __and__(self, other):

        return self._fastsetop(other, '__and__')

    def __sub__(self, other):

        return self._fastsetop(other, '__sub__')

    def _slice(self, start, stop):

        # creating new list should be generally cheaper than iterating items

        if self._ascending is None:

            return baseset(self._list[start:stop], istopo=self._istopo)

        data = self._asclist

        if not self._ascending:

            start, stop = max(len(data) - stop, 0), max(len(data) - start, 0)

        s = baseset(data[start:stop], istopo=self._istopo)

        s._ascending = self._ascending

        return s

    @encoding.strmethod

    def __repr__(self):

        d = {None: '', False: '-', True: '+'}[self._ascending]

        s = _formatsetrepr(self._datarepr)

        if not s:

            l = self._list

            # if _list has been built from a set, it might have a different

            # order from one python implementation to another.

            # We fallback to the sorted version for a stable output.

            if self._ascending is not None: