AlgoPy

# coding: utf8
#
# AlgoPy.py
#
# Author : SCR 05/2016, 06/2018
#
# Intégration des types algorithmiques
#
# versions Python : 2.7, 3.4
#
# v3: intégration pour 2.7
# v4: type file, suppression str.ecrire, lecture booléen, typage tableaux
# v5: anglicisation

# from forbiddenfruit import curse
#
# Intégration directe de la fonction curse du module forbiddenfruit
# pour faciliter la distribution
#
# Author: Lincoln de Sousa
# Home Page: https://github.com/clarete/forbiddenfruit
#
# Copyright (C) 2013 Lincoln Clarete <lincoln@comum.org>

from __future__ import print_function

import ctypes
import inspect
from functools import wraps
from collections import defaultdict

try:
    import __builtin__
except ImportError:
    # Python 3 support
    import builtins as __builtin__
#import builtins as __builtin__

#__version__ = '0.1.2'

#__all__ = 'curse', 'curses', 'reverse'


Py_ssize_t = \
    hasattr(ctypes.pythonapi, 'Py_InitModule4_64') \
    and ctypes.c_int64 or ctypes.c_int


class PyObject(ctypes.Structure):
    pass

PyObject._fields_ = [
    ('ob_refcnt', Py_ssize_t),
    ('ob_type', ctypes.POINTER(PyObject)),
]

class SlotsProxy(PyObject):
    _fields_ = [('dict', ctypes.POINTER(PyObject))]

def patchable_builtin(klass):
    # It's important to create variables here, we want those objects alive
    # within this whole scope.
    name = klass.__name__
    target = klass.__dict__

    # Hardcore introspection to find the `PyProxyDict` object that contains the
    # precious `dict` attribute.
    proxy_dict = SlotsProxy.from_address(id(target))
    namespace = {}

    # This is the way I found to `cast` this `proxy_dict.dict` into a python
    # object, cause the `from_address()` function returns the `py_object`
    # version
    ctypes.pythonapi.PyDict_SetItem(
        ctypes.py_object(namespace),
        ctypes.py_object(name),
        proxy_dict.dict,
    )
    return namespace[name]


@wraps(__builtin__.dir)
def __filtered_dir__(obj=None):
    name = hasattr(obj, '__name__') and obj.__name__ or obj.__class__.__name__
    if obj is None:
        # Return names from the local scope of the calling frame, taking into
        # account indirection added by __filtered_dir__
        calling_frame = inspect.currentframe().f_back
        return sorted(calling_frame.f_locals.keys())
    return sorted(set(__dir__(obj)).difference(__hidden_elements__[name]))

# Switching to the custom dir impl declared above
__hidden_elements__ = defaultdict(list)
__dir__ = dir
__builtin__.dir = __filtered_dir__


def curse(klass, attr, value, hide_from_dir=False):
    """Curse a built-in `klass` with `attr` set to `value`

    This function monkey-patches the built-in python object `attr` adding a new
    attribute to it. You can add any kind of argument to the `class`.

    It's possible to attach methods as class methods, just do the following:

      >>> def myclassmethod(cls):
      ...     return cls(1.5)
      >>> curse(float, "myclassmethod", classmethod(myclassmethod))
      >>> float.myclassmethod()
      1.5

    Methods will be automatically bound, so don't forget to add a self
    parameter to them, like this:

      >>> def hello(self):
      ...     return self * 2
      >>> curse(str, "hello", hello)
      >>> "yo".hello()
      "yoyo"
    """
    dikt = patchable_builtin(klass)

    old_value = dikt.get(attr, None)
    old_name = '_c_%s' % attr   # do not use .format here, it breaks py2.{5,6}
    if old_value:
        dikt[old_name] = old_value

    if old_value:
        dikt[attr] = value

        try:
            dikt[attr].__name__ = old_value.__name__
        except (AttributeError, TypeError):  # py2.5 will raise `TypeError`
            pass
        try:
            dikt[attr].__qualname__ = old_value.__qualname__
        except AttributeError:
            pass
    else:
        dikt[attr] = value

    if hide_from_dir:
        __hidden_elements__[klass.__name__].append(attr)
#
#
# Fin extrait de forbiddenfruit
#

import sys
import math
import random

#
# lecture, écriture avec type :
# input, lire, écrire, écrireF
#

if sys.version_info[0] > 2:
    _input = __builtin__.input
else:
    _input = __builtin__.raw_input

def _input_bool(*args):
    inputString = _input(*args)
    res = inputString.lower() == str(True).lower()
    if not (res or inputString.lower() == str(False).lower()):
        raise TypeError("Expected " + str(True) + " or " + str(False)
                        + ", but found : " + inputString)
    return res

def input(*args):
    n = len(args)
    if n > 2:
        raise TypeError("Expected 0 to 2 parameters, but found : "
                        + str(len(args)))
    elif n == 0 or (n == 1 and isinstance(args[0], str)):
        res = _input(*args)
    elif args[-1] == bool:
        res = _input_bool(*args[0:-1])
    else:
        res = args[-1](_input(*args[0:-1]))
    return res


def printf(form, *args, **kwargs):
    s = form.format(*args)
    __builtin__.print(s, **kwargs)


#
# caractères : classe char sous-classe de str
#

class char(str):
    def __new__(cls, arg):
        if (type(arg) is int):
            self = chr(arg)
        else:
            self = super(char, cls).__new__(cls, arg)
            if len(self) != 1:
                raise TypeError("Expected a character, but string of length 2 "
                                + "found : " + repr(self))
        return self

#
# implémentation des chaînes par intégration du TDA dans la classe native str
# Limites : impossibilité de surcharger l'opérateur | avec forbiddenfruit
#

def _size(self):
    return __builtin__.len(self)
curse(str, "size", _size)

def _isEmpty(self):
    return __builtin__.len(self) == 0
curse(str, "isEmpty", _isEmpty)

def _substring(self, p, n):
    if p < 0 or p > self.size():
        raise IndexError("Index out of range : " + str(p))
    if n < 0:
        raise ValueError("Number of characters is not positive or null : "
                         + str(n))
    if p + n > self.size():
        raise IndexError("Index plus number of characters is out of range : "
            + str(p) + " + " + str(n))
    return self[p:p+n]
curse(str, "substring", _substring)

def _add(self, c):
    if not isinstance(c, str):
        raise TypeError("add() expected a character, but "
                        + repr(type(c).__name__) + " found")
    if len(c) != 1:
        raise ValueError("add() expected a single character, "
                         "but string of length "
                            + str(len(c)) + " found")
    return self + c
curse(str, "add", _add)

def _get(self, k):
    if k < 0 or k >= self.size():
        raise IndexError("Index out of range : " + str(k))
    return self[k]
curse(str, "get", _get)


# Tableaux :

class arrayMeta(type):
    def __getitem__(self, index):
        res = __builtin__.object.__new__(array)
        if type(index) is tuple:
            res.__init__(*index)
        else:
            res.__init__(index)
        return res

    def __call__(self, *args):
        res = object.__new__(array)
        dim = len(args)
        if dim == 0:
            res = array[0]
        else:
            if not type(args[0]) is tuple:
                t0 = args[0]
                dims = ()
            else:
                t0 = array(*args[0])
                dims = t0._array__dims
            res = array[(len(args),) + dims]
            res._array__data[0] = t0;
            for i in range(1, dim):
                if type(args[i]) is tuple:
                    ti = array(*args[i])
                    dimi = ti._array__dims
                else:
                    ti = args[i]
                    dimi = ()
                if (dimi != dims):
                    raise TypeError("Inconsistent dimensions : " + str(args[i]))
                res._array__data[i] = ti
        return res


# extrait de future.utils ; compatibilité Python 2 et 3 pour les métaclasses

def with_metaclass(meta, *bases):
    """
    Function from jinja2/_compat.py. License: BSD.
    Use it like this::
        class BaseForm(object):
            pass
        class FormType(type):
            pass
        class Form(with_metaclass(FormType, BaseForm)):
            pass
    This requires a bit of explanation: the basic idea is to make a
    dummy metaclass for one level of class instantiation that replaces
    itself with the actual metaclass.  Because of internal type checks
    we also need to make sure that we downgrade the custom metaclass
    for one level to something closer to type (that's why __call__ and
    __init__ comes back from type etc.).
    This has the advantage over six.with_metaclass of not introducing
    dummy classes into the final MRO.
    """
    class metaclass(meta):
        __call__ = type.__call__
        __init__ = type.__init__
        def __new__(cls, name, this_bases, d):
            if this_bases is None:
                return type.__new__(cls, name, (), d)
            return meta(name, bases, d)

    return metaclass('temporary_class', None, {})


#class array(metaclass=arrayMeta):
class array(with_metaclass(arrayMeta)):

    """ le type tableau :
    - implémenté avec des listes
    - peut être multidimensionnel et dans ce cas est représenté par un tableau
        de tableau ;
    - peut être initialisé
    """

    def __init__(self, *dims):
        rank = len(dims)
        self.__dims = dims
        dim = self.__dims[0]
        if rank > 1:   # tableau multidimensionnel
            self.__data = [ array[dims[1:]]
                               for i in range(dim) ]
        else:
            self.__data = [ None for i in range(dim) ]

    def _verifindex(self, index):
        if not type(index) is int:
            raise TypeError("Bad index type : expecting 'int'"
                             + " but was "
                             + repr(type(index).__name__))
        if index < 0 or index >= self.__dims[0]:
            raise IndexError("Index out of range : " + str(index))

    def _getitemloc(self, index):
        if type(index) is tuple and len(index) != self.rank():
            raise IndexError("Bad dimension count : expecting "
                             + str(self.rank()) + " but was "
                             + str(len(index)))
        if type(index) is int and self.rank() != 1:
            raise IndexError("Bad dimension count : expecting "
                             + str(self.rank()) + " but was 1")

        t = self
        if type(index) is tuple:
            for i in index[:-1]:
                t._verifindex(i)
                t = t.__data[i]
            index = index[-1]
        t._verifindex(index)
        return t.__data, index

    def __getitem__(self, index):
        data, index = self._getitemloc(index)
        return data[index]

    def __setitem__(self, index, val):
        data, index = self._getitemloc(index)
        data[index] = val

    def rank(self):
        return len(self.__dims)

    def size(self, *index):
        t = len(index)
        if t > 1:
            raise TypeError("size() takes 0 or 1 positional arguments but "
                + str(len(index)) + " was given")
        if t == 0:
            produit = self.__dims[0]
            for i in range(1, self.rank()):
                produit = produit * self.__dims[i]
            res = produit
        else:
            index = index[0]
            if index >= self.rank():
                raise IndexError("Index of dimensions out of range : "
                                 + str(index))
            res = self.__dims[index]
        return res

    def _str(self):
        if self.rank() > 1:
            res = '(' + ", ".join(p._str() for p in self.__data)+ ')'
        else:
            res = '(' + ", ".join(repr(p) for p in self.__data)+ ')'
        return res

    def __repr__(self):
        return (self.__class__.__name__ + self._str())

    __str__ = __repr__

    def __iter__(self):
        def _array_iter():
            for t in self.__data:
                for elt in t:
                    yield elt
        if self.rank() == 1:
            res = iter(self.__data)
        else:
            res = _array_iter()
        return res


#
# comportement commun pile, file, liste
#

class _container(object):

    def __init__(self, data, *vals):
        self.__data = data
        for val in vals:
            self.add(val)

    def isEmpty(self):
        return self.size() == 0

    def add(self, element):
        self.__data.append(element)

    def size(self):
        return len(self.__data)

    def __str__(self):
        return (self.__class__.__name__
                    + '(' + ", ".join(repr(p) for p in self.__data)+ ')')

    __repr__ = __str__



#
# stack : implémentation de pile par délégation à la classe native  deque
#

from collections import deque

class stack(_container):
    """ le type stack """
    def __init__(self, *vals):
        super(stack, self).__init__(deque(), *vals)
        self.__data = self._container__data

    def get(self):
        if self.isEmpty():
            raise IndexError("get() on empty stack")
        return self.__data[-1]

    def remove(self):
        if self.isEmpty():
            raise IndexError("remove() on empty stack")
        self.__data.pop()

#
# queue : implémentation de file par délégation à la classe native deque
#

class queue(_container):
    """ le type queue """
    def __init__(self, *vals):
        super(queue, self).__init__(deque(), *vals)
        self.__data = self._container__data

    def get(self):
        if self.isEmpty():
            raise IndexError("get() on empty queue")
        return self.__data[0]

    def remove(self):
        if self.isEmpty():
            raise IndexError("remove() on empty queue")
        self.__data.popleft()

#
# implémentation des listes par délégation à la classe native list
#

class list(_container):
    """ le type liste """
    def __init__(self, *vals):
        super(list, self).__init__(__builtin__.list(), *vals)
        self.__data = self._container__data

    def _verifindex(self, pos, inc = 0):
        if not type(pos) is int:
            raise TypeError("Bad index type : expecting 'int' "
                             + "but was "
                             + repr(type(pos).__name__))
        if pos < 0 or pos >= self.size() + inc:
            raise IndexError("Index out of range : " + str(pos))

    def get(self, pos):
        self._verifindex(pos)
        return self.__data[pos]

    def set(self, pos, val):
        self._verifindex(pos)
        self.__data[pos] = val

    def insert(self, pos, val):
        self._verifindex(pos, 1)
        self.__data.insert(pos, val)

    def remove(self, pos):
        self._verifindex(pos)
        self.__data.pop(pos)

    def __iter__(self):
        return self.__data.__iter__()

class dict():
    """ le type table """
    def __init__(self, *vals):
        try:
            self.__data = __builtin__.dict(*vals)
        except (TypeError, ValueError):
            self.__data = __builtin__.dict(vals)

    def isEmpty(self):
        return self.size() == 0

    def size(self):
        return len(self.__data)

    def get(self, key):
        return self.__data[key]

    def set(self, key, val):
        if (not self.contains(key)):
            raise KeyError(key)
        self.__data[key] = val

    def contains(self, key):
        return key in self.__data

    def add(self, key, val):
        if (key in self.__data):
            raise KeyError("Key already exists : " + repr(key))
        self.__data[key] = val

    def remove(self, key):
        self.__data.pop(key)

    def items(self):
        return list(*self.__data.items())

    def __str__(self):
        return (self.__class__.__name__
                    + '('
                    + ", ".join(repr((k, v)) for k,v in self.__data.items())
                    + ')')

    __repr__ = __str__


#
# Exécution
#

def execute(prog, nb=1):
    if prog.__module__ == "__main__":
        module = sys.modules["__main__"]
        filename = module.__file__
        print("AlgoPy: Analyse du code source de", filename)
        if sys.version_info[0] > 2:
            with open(filename, encoding='utf-8') as f:
                code = f.read()
        else:
            with open(filename, "rb") as f:
                code = f.read()

        print()
        RestrictionVisitor(code).visit()
        print()

        import doctest
        failure_count, test_count = doctest.testmod(verbose=False)
        print("AlgoPy: Exécution des tests de documentation:",
                  failure_count, "erreur(s) pour",
                  test_count, "test(s)."
                  )
        print()

        print("Algopy: Exécution de", prog.__name__, "dans", filename)
        print()

        import timeit
        time = timeit.timeit(
                      prog.__name__+"()",
                      setup="from __main__ import " + prog.__name__,
                      number=nb
                      )
        print("\nAlgoPy: Temps d'exécution:",
                  "{:f}".format(time)
                  ,
                  "seconde(s)"
                  )
        print()

# analyse du code source

import ast

def _message(lineno, *s):
    print("Ligne", lineno, ":", *s)

class RestrictionVisitor(ast.NodeVisitor):
    _function_def = False
    _function_ret = None
    _lineno = 0

    def __init__(self, code):
        self._tree = ast.parse(code)
        self._lines = [None] + code.splitlines()  # None at [0] so we can index lines from 1

    def visit(self, node = None):
        super(RestrictionVisitor, self).visit(node if node else self._tree)

    def visit_Str(self, node):
        line = self._lines[node.lineno]
        apostrophe = line[node.col_offset]
        if len(node.s) != 1 and apostrophe == "'":
            _message(node.lineno,
                    "l'apostrophe simple doit être réservée",
                    "à l'écriture des caractères")

    def visit_In(self, node):
        _message(self._lineno,
                "l'opérateur conditionnel 'in' ne doit pas être utilisé")
        self.generic_visit(node)

    def visit_NotIn(self, node):
        _message(self._lineno,
                "l'opérateur conditionnel 'not in' ne doit pas être utilisé")
        self.generic_visit(node)

    def visit_Compare(self, node):
        if len(node.ops) > 1:
            _message(node.lineno,
                    "les comparaisons ne doivent utiliser qu'un seul opérateur")
        self._lineno = node.lineno
        self.generic_visit(node)

    def visit_IfExp(self, node):
        _message(node.lineno,
                "l'expression conditionnelle ne doit pas être utilisée")
        self.generic_visit(node)

    def visit_Subscript(self, node):
        if not isinstance(node.slice, ast.Index):
            _message(node.lineno,
                    "les indices par tranches ne doivent pas être utilisées")
        self.generic_visit(node)

    def visit_Break(self, node):
        _message(node.lineno,
                "l'instruction 'break' ne doit pas être utilisée")

    def visit_Continue(self, node):
        _message(node.lineno,
                "l'instruction 'continue' ne doit pas être utilisée")

    def visit_For(self, node):
        if node.orelse:
            _message(node.lineno,
                    "l'instruction 'for/else' ne doit pas être utilisée")
        self.generic_visit(node)

    def visit_While(self, node):
        if node.orelse:
            _message(node.lineno,
                    "l'instruction 'while/else' ne doit pas être utilisée")
        self.generic_visit(node)

    def visit_If(self, node):
        if not node.orelse:
            _message(node.lineno,
                    "l'instruction 'else' est absente")
        self.generic_visit(node)

    def visit_FunctionDef(self, node):
        function_def = self._function_def
        function_ret = self._function_ret
        if function_def:
            _message(node.lineno,
                    "les fonctions imbriquées ne doivent pas être utilisées")
        else:
            self._function_def = True
        if isinstance(node.body[-1], ast.Return):
            self._function_ret = node.body[-1]
        if (node.args.vararg
            or (sys.version_info[0] > 2 and node.args.kwonlyargs)
            or node.args.kwarg):
            _message(node.lineno,
                    "les sous-programmes doivent être définies",
                    "avec des paramètres positionnels uniquement")
        if (node.args.defaults
            or (sys.version_info[0] > 2 and node.args.kw_defaults)):
            _message(node.lineno,
                    "les sous-programmes ne doivent pas comporter",
                    "des paramètres initialisés par défaut")
        if not ast.get_docstring(node, False):
            _message(node.lineno,
                    "le sous-programme", repr(node.name),
                    "n'a pas de commentaire de documentation")


        self.generic_visit(node)
        self._function_def = function_def
        self._function_ret = function_ret

    def visit_Return(self, node):
        if self._function_ret != node:
            _message(node.lineno,
                    "l'instruction 'return' doit être la dernière instruction",
                    "d'un sous-programme")

    def visit_Global(self, node):
        _message(node.lineno,
                "les variables déclarées 'global' ne doivent pas être utilisées")

    def visit_Nonlocal(self, node):
        _message(node.lineno,
                "les variables déclarées 'nonlocal' ne doivent pas être utilisées")

if __name__ == "__main__":
    import doctest
    doctest.testfile("AlgoPyV5Test.txt", verbose=True)