1import sys
2
3try:
4    reversed = reversed
5except NameError:
6    def reversed(sequence):
7        """reversed(sequence) -> reverse iterator over values of the sequence
8
9        Return a reverse iterator
10        """
11        if hasattr(sequence, '__reversed__'):
12            return sequence.__reversed__()
13        if not hasattr(sequence, '__getitem__'):
14            raise TypeError("argument to reversed() must be a sequence")
15        return reversed_iterator(sequence)
16
17    class reversed_iterator(object):
18
19        def __init__(self, seq):
20            self.seq = seq
21            self.remaining = len(seq)
22
23        def __iter__(self):
24            return self
25
26        def next(self):
27            i = self.remaining
28            if i > 0:
29                i -= 1
30                item = self.seq[i]
31                self.remaining = i
32                return item
33            raise StopIteration
34
35        def __length_hint__(self):
36            return self.remaining
37
38try:
39    any = any
40except NameError:
41    def any(iterable):
42        for x in iterable:
43            if x:
44                return True
45        return False
46
47try:
48    all = all
49except NameError:
50    def all(iterable):
51        for x in iterable:
52            if not x:
53                return False
54        return True
55
56try:
57    sorted = sorted
58except NameError:
59    builtin_cmp = cmp # need to use cmp as keyword arg
60
61    def sorted(iterable, cmp=None, key=None, reverse=0):
62        use_cmp = None
63        if key is not None:
64            if cmp is None:
65                def use_cmp(x, y):
66                    return builtin_cmp(x[0], y[0])
67            else:
68                def use_cmp(x, y):
69                    return cmp(x[0], y[0])
70            l = [(key(element), element) for element in iterable]
71        else:
72            if cmp is not None:
73                use_cmp = cmp
74            l = list(iterable)
75        if use_cmp is not None:
76            l.sort(use_cmp)
77        else:
78            l.sort()
79        if reverse:
80            l.reverse()
81        if key is not None:
82            return [element for (_, element) in l]
83        return l
84
85try:
86    set, frozenset = set, frozenset
87except NameError:
88    from sets import set, frozenset
89
90# pass through
91enumerate = enumerate
92
93try:
94    BaseException = BaseException
95except NameError:
96    BaseException = Exception
97
98try:
99    GeneratorExit = GeneratorExit
100except NameError:
101    class GeneratorExit(Exception):
102        """ This exception is never raised, it is there to make it possible to
103        write code compatible with CPython 2.5 even in lower CPython
104        versions."""
105        pass
106    GeneratorExit.__module__ = 'exceptions'
107
108_sysex = (KeyboardInterrupt, SystemExit, MemoryError, GeneratorExit)
109
110try:
111    callable = callable
112except NameError:
113    def callable(obj):
114        return hasattr(obj, "__call__")
115
116if sys.version_info >= (3, 0):
117    exec ("print_ = print ; exec_=exec")
118    import builtins
119
120    # some backward compatibility helpers
121    _basestring = str
122    def _totext(obj, encoding=None, errors=None):
123        if isinstance(obj, bytes):
124            if errors is None:
125                obj = obj.decode(encoding)
126            else:
127                obj = obj.decode(encoding, errors)
128        elif not isinstance(obj, str):
129            obj = str(obj)
130        return obj
131
132    def _isbytes(x):
133        return isinstance(x, bytes)
134    def _istext(x):
135        return isinstance(x, str)
136
137    text = str
138    bytes = bytes
139
140
141    def _getimself(function):
142        return getattr(function, '__self__', None)
143
144    def _getfuncdict(function):
145        return getattr(function, "__dict__", None)
146
147    def _getcode(function):
148        return getattr(function, "__code__", None)
149
150    def execfile(fn, globs=None, locs=None):
151        if globs is None:
152            back = sys._getframe(1)
153            globs = back.f_globals
154            locs = back.f_locals
155            del back
156        elif locs is None:
157            locs = globs
158        fp = open(fn, "r")
159        try:
160            source = fp.read()
161        finally:
162            fp.close()
163        co = compile(source, fn, "exec", dont_inherit=True)
164        exec_(co, globs, locs)
165
166else:
167    import __builtin__ as builtins
168    _totext = unicode
169    _basestring = basestring
170    text = unicode
171    bytes = str
172    execfile = execfile
173    callable = callable
174    def _isbytes(x):
175        return isinstance(x, str)
176    def _istext(x):
177        return isinstance(x, unicode)
178
179    def _getimself(function):
180        return getattr(function, 'im_self', None)
181
182    def _getfuncdict(function):
183        return getattr(function, "__dict__", None)
184
185    def _getcode(function):
186        try:
187            return getattr(function, "__code__")
188        except AttributeError:
189            return getattr(function, "func_code", None)
190
191    def print_(*args, **kwargs):
192        """ minimal backport of py3k print statement. """
193        sep = ' '
194        if 'sep' in kwargs:
195            sep = kwargs.pop('sep')
196        end = '\n'
197        if 'end' in kwargs:
198            end = kwargs.pop('end')
199        file = 'file' in kwargs and kwargs.pop('file') or sys.stdout
200        if kwargs:
201            args = ", ".join([str(x) for x in kwargs])
202            raise TypeError("invalid keyword arguments: %s" % args)
203        at_start = True
204        for x in args:
205            if not at_start:
206                file.write(sep)
207            file.write(str(x))
208            at_start = False
209        file.write(end)
210
211    def exec_(obj, globals=None, locals=None):
212        """ minimal backport of py3k exec statement. """
213        __tracebackhide__ = True
214        if globals is None:
215            frame = sys._getframe(1)
216            globals = frame.f_globals
217            if locals is None:
218                locals = frame.f_locals
219        elif locals is None:
220            locals = globals
221        exec2(obj, globals, locals)
222
223if sys.version_info >= (3, 0):
224    def _reraise(cls, val, tb):
225        __tracebackhide__ = True
226        assert hasattr(val, '__traceback__')
227        raise cls.with_traceback(val, tb)
228else:
229    exec ("""
230def _reraise(cls, val, tb):
231    __tracebackhide__ = True
232    raise cls, val, tb
233def exec2(obj, globals, locals):
234    __tracebackhide__ = True
235    exec obj in globals, locals
236""")
237
238def _tryimport(*names):
239    """ return the first successfully imported module. """
240    assert names
241    for name in names:
242        try:
243            __import__(name)
244        except ImportError:
245            excinfo = sys.exc_info()
246        else:
247            return sys.modules[name]
248    _reraise(*excinfo)
249