def syllables(self):
        r"""
        Return the syllables of the word.

        Consider a free group element `g = x_1^{n_1} x_2^{n_2} \cdots
        x_k^{n_k}`. The uniquely-determined subwords `x_i^{e_i}`
        consisting only of powers of a single generator are called the
        syllables of `g`.

        OUTPUT:

        The tuple of syllables. Each syllable is given as a pair
        `(x_i, e_i)` consisting of a generator and a non-zero integer.

        EXAMPLES::

            sage: G.<a,b> = FreeGroup()
            sage: w = a^2 * b^-1 * a^3
            sage: w.syllables()
            ((a, 2), (b, -1), (a, 3))
        """
        g = self.gap().UnderlyingElement()
        k = g.NumberSyllables().sage()
        gen = self.parent().gen
        exponent_syllable  = libgap.eval('ExponentSyllable')
        generator_syllable = libgap.eval('GeneratorSyllable')
        result = []
        gen = self.parent().gen
        for i in range(k):
            exponent  = exponent_syllable(g, i+1).sage()
            generator = gen(generator_syllable(g, i+1).sage() - 1)
            result.append( (generator, exponent) )
        return tuple(result)

    def __init__(self, degree, base_ring, special, sage_name, latex_string,
                 gap_command_string, category=None):
        """
        Base class for "named" matrix groups using LibGAP

        INPUT:

        - ``degree`` -- integer. The degree (number of rows/columns of
          matrices).

        - ``base_ring`` -- ring. The base ring of the matrices.

        - ``special`` -- boolean. Whether the matrix group is special,
          that is, elements have determinant one.

        - ``latex_string`` -- string. The latex representation.

        - ``gap_command_string`` -- string. The GAP command to construct
          the matrix group.

        EXAMPLES::

            sage: G = GL(2, GF(3))
            sage: from sage.groups.matrix_gps.named_group import NamedMatrixGroup_gap
            sage: isinstance(G, NamedMatrixGroup_gap)
            True
        """
        from sage.libs.gap.libgap import libgap
        group = libgap.eval(gap_command_string)
        MatrixGroup_gap.__init__(self, degree, base_ring, group,
                                 category=category)
        self._special = special
        self._gap_string = gap_command_string
        self._name_string = sage_name
        self._latex_string = latex_string

def all_installed_packages(ignore_dot_gap=False):
    """
    Return list of all installed packages.

    INPUT:

    - ``ignore_dot_gap`` -- Boolean (default: ``False``). Whether to
      ignore the `.gap/` directory (usually in the user home
      directory) when searching for packages.

    OUTPUT:

    Tuple of strings in alphabetic order.

    EXAMPLES::

        sage: from sage.tests.gap_packages import all_installed_packages
        sage: all_installed_packages()
        (...'GAPDoc'...)
    """
    packages = []
    for path in libgap.eval('GAP_ROOT_PATHS').sage():
        if ignore_dot_gap and path.endswith('/.gap/'):
            continue
        pkg_dir = os.path.join(path, 'pkg')
        if not os.path.exists(pkg_dir):
            continue
        for subdir in os.listdir(pkg_dir):
            if not os.path.isdir(os.path.join(pkg_dir, subdir)):
                continue
            packages.append(subdir.rstrip('-.0123456789'))
    packages.sort()
    return tuple(packages)

def test_packages(packages, only_failures=False):
    """
    Return list of all installed packages.

    INPUT:

    - ``packages`` -- a list/tuple/iterable of strings. The names of
      GAP packages to try to import.

    - ``only_failures`` -- boolean, default ``False``. Whether to only
      include failures in the table.

    OUTPUT:

    A table of the installed packages and whether they load
    successfully.

    EXAMPLES::

        sage: from sage.tests.gap_packages import all_installed_packages, test_packages
        sage: test_packages(['GAPDoc'])
          Status   Package   GAP Output
        +--------+---------+------------+
                   GAPDoc    true

    All packages, including user-installed ones::

        sage: pkgs = all_installed_packages()
        sage: test_packages(pkgs)    # random output
          Status    Package      GAP Output
        +---------+------------+------------+
                    Alnuth       true
                    GAPDoc       true
          Failure   HAPcryst     fail
                    Hap          true
                    autpgrp      true
                    braid        true
                    crime        true
                    ctbllib      true
                    design       true
                    factint      true
                    grape        true
                    guava        true
                    laguna       true
                    polycyclic   true
                    polymaking   true
                    sonata       true
                    toric        true
    """
    rows = [['Status', 'Package', 'GAP Output']]
    for pkg in packages:
        output = libgap.eval('LoadPackage("{0}")'.format(pkg))
        ok = bool(output)
        status = '' if ok else 'Failure'
        if ok and only_failures:
            continue
        rows.append([status, pkg, str(output)])
    from sage.misc.table import table
    return table(rows, header_row=True)

    def eval(self, code):
        """
        Return a semantic handle on the result of evaluating ``code`` in GAP.

        EXAMPLES::

            sage: from mygap import mygap
            sage: C = mygap.eval("Cyclotomics"); C
            Cyclotomics
            sage: C.gap().IsField()
            true
            sage: C.category()
            Category of infinite g a p fields
        """
        return GAP(libgap.eval(code))

    def __init__(self, x, parent):
        """
        The Python constructor.

        See :class:`FreeGroupElement` for details.

        TESTS::

            sage: G.<a,b> = FreeGroup()
            sage: x = G([1, 2, -1, -1])
            sage: x # indirect doctest
            a*b*a^-2
            sage: y = G([2, 2, 2, 1, -2, -2, -1])
            sage: y # indirect doctest
            b^3*a*b^-2*a^-1

            sage: TestSuite(G).run()
            sage: TestSuite(x).run()
        """
        if not isinstance(x, GapElement):
            try:
                l = x.Tietze()
            except AttributeError:
                l = list(x)
            if len(l)>0:
                if min(l) < -parent.ngens() or parent.ngens() < max(l):
                    raise ValueError('generators not in the group')
            if 0 in l:
                raise ValueError('zero does not denote a generator')
            i=0
            while i<len(l)-1:
                if l[i]==-l[i+1]:
                    l.pop(i)
                    l.pop(i)
                    if i>0:
                        i=i-1
                else:
                    i=i+1
            AbstractWordTietzeWord = libgap.eval('AbstractWordTietzeWord')
            x = AbstractWordTietzeWord(l, parent._gap_gens())
        ElementLibGAP.__init__(self, x, parent)

    def __init__(self, generator_orders):
        r"""
        Constructor.

        TESTS::

            sage: from sage.groups.abelian_gps.abelian_group_gap import AbelianGroupGap
            sage: A = AbelianGroup((2,3,4))
            sage: TestSuite(A).run()
        """
        category = Groups().Commutative()
        if 0 in generator_orders:
            if not libgap.LoadPackage("Polycyclic"):
                raise ImportError("unable to import polycyclic package")
            G = libgap.eval("AbelianPcpGroup(%s)" % list(generator_orders))
            category = category.Infinite()
            self.Element = AbelianGroupElement_polycyclic
        else:
            G = libgap.AbelianGroup(generator_orders)
            category = category.Finite().Enumerated()
        AbelianGroup_gap.__init__(self, G, category=category)

    def _is_present(self):
        r"""
        Return whether the Small Groups Library is available in GAP.

        EXAMPLES::

            sage: from sage.features.gap import SmallGroupsLibrary
            sage: SmallGroupsLibrary().is_present()  # optional: database_gap
            FeatureTestResult('Small Groups Library', True)
        """
        from sage.libs.gap.libgap import libgap
        command = 'SmallGroup(13,1)'
        output = None
        presence = False
        try:
            output = str(libgap.eval(command))
            presence = True
        except ValueError as e:
            output = str(e)
        return FeatureTestResult(self, presence,
            reason = "`{command}` evaluated to `{output}` in GAP.".format(command=command, output=output))

    def minpoly(self, var='x'):
        r"""
        The minimal polynomial of ``self`` element over `\QQ`.

        INPUT:

        - ``var`` -- (optional, default 'x') the name of the variable to use.

        EXAMPLES::

            sage: UCF.<E> = UniversalCyclotomicField()

            sage: UCF(4).minpoly()
            x - 4

            sage: UCF(4).minpoly(var='y')
            y - 4

            sage: E(3).minpoly()
            x^2 + x + 1

            sage: E(3).minpoly(var='y')
            y^2 + y + 1

        TESTS::

            sage: for elt in UCF.some_elements():
            ....:     assert elt.minpoly() == elt.to_cyclotomic_field().minpoly()
            ....:     assert elt.minpoly(var='y') == elt.to_cyclotomic_field().minpoly(var='y')

        .. TODO::

            Polynomials with libgap currently does not implement a ``.sage()`` method
            (see :trac:`18266`). It would be faster/safer to not use string to
            construct the polynomial.
        """
        gap_p = libgap.MinimalPolynomial(libgap.eval("Rationals"), self._obj)
        return QQ[var](QQ['x_1'](str(gap_p)))

    def _check_matrix(self, x_sage, x_gap):
        """
        Check whether the matrix ``x`` defines a group element.

        This is used by the element constructor (if you pass
        ``check=True``, the default) that the defining matrix is valid
        for this parent. Derived classes must override this to verify
        that the matrix is, for example, orthogonal or symplectic.

        INPUT:

        - ``x_sage`` -- a Sage matrix in the correct matrix space (degree
          and base ring).

        - ``x_gap`` -- the corresponding LibGAP matrix.

        OUTPUT:

        A ``TypeError`` must be raised if ``x`` is invalid.

        EXAMPLES::

            sage: m1 = matrix(GF(11), [(0, -1), (1, 0)])
            sage: m2 = matrix(GF(11), [(0, -1), (1, -1)])
            sage: G = MatrixGroup([m1, m2])
            sage: G([1,2,0,1])
            [1 2]
            [0 1]
            sage: G([1,1,1,0])
            Traceback (most recent call last):
            ...
            TypeError: matrix is not in the finitely generated group
        """
        from sage.libs.gap.libgap import libgap
        libgap_contains = libgap.eval('\in')
        is_contained = libgap_contains(x_gap, self.gap())
        if not is_contained.sage():
            raise TypeError('matrix is not in the finitely generated group')

    def _element_constructor_(self, elt):
        r"""
        TESTS::

            sage: UCF = UniversalCyclotomicField()
            sage: UCF(3)
            3
            sage: UCF(3/2)
            3/2

            sage: C = CyclotomicField(13)
            sage: UCF(C.gen())
            E(13)
            sage: UCF(C.gen() - 3*C.gen()**2 + 5*C.gen()**5)
            E(13) - 3*E(13)^2 + 5*E(13)^5

            sage: C = CyclotomicField(12)
            sage: zeta12 = C.gen()
            sage: a = UCF(zeta12 - 3* zeta12**2)
            sage: a
            -E(12)^7 + 3*E(12)^8
            sage: C(_) == a
            True

            sage: UCF('[[0, 1], [0, 2]]')
            Traceback (most recent call last):
            ...
            TypeError: [ [ 0, 1 ], [ 0, 2 ] ] of type <type
            'sage.libs.gap.element.GapElement_List'> not valid to initialize an
            element of the universal cyclotomic field

        .. TODO::

            Implement conversion from QQbar (and as a consequence from the
            symbolic ring)
        """
        elt = py_scalar_to_element(elt)

        if isinstance(elt, (Integer, Rational)):
            return self.element_class(self, libgap(elt))
        elif isinstance(elt, (GapElement_Integer, GapElement_Rational, GapElement_Cyclotomic)):
            return self.element_class(self, elt)
        elif not elt:
            return self.zero()

        obj = None
        if isinstance(elt, gap.GapElement):
            obj = libgap(elt)
        elif isinstance(elt, gap3.GAP3Element):
            obj = libgap.eval(str(elt))
        elif isinstance(elt, str):
            obj = libgap.eval(elt)
        if obj is not None:
            if not isinstance(obj, (GapElement_Integer, GapElement_Rational, GapElement_Cyclotomic)):
                raise TypeError("{} of type {} not valid to initialize an element of the universal cyclotomic field".format(obj, type(obj)))
            return self.element_class(self, obj)

        # late import to avoid slowing down the above conversions
        from sage.rings.number_field.number_field_element import NumberFieldElement
        from sage.rings.number_field.number_field import NumberField_cyclotomic, CyclotomicField
        P = parent(elt)
        if isinstance(elt, NumberFieldElement) and isinstance(P, NumberField_cyclotomic):
            n = P.gen().multiplicative_order()
            elt = CyclotomicField(n)(elt)
            coeffs = elt._coefficients()
            return sum(c * self.gen(n,i) for i,c in enumerate(elt._coefficients()))
        else:
            raise TypeError("{} of type {} not valid to initialize an element of the universal cyclotomic field".format(elt, type(elt)))

    def __init__(self, parent, x):
        """
        The Python constructor.

        See :class:`FreeGroupElement` for details.

        TESTS::

            sage: from train_track import *
            sage: G.<a,b> = FreeGroup()
            sage: x = G([1, 2, -1, -1])
            sage: x # indirect doctest
            a*b*a^-2
            sage: y = G([2, 2, 2, 1, -2, -2, -1])
            sage: y # indirect doctest
            b^3*a*b^-2*a^-1
            sage: G("abAbBAB")
            a*b*a^-2*b^-1
            sage: G(['a','b','A','a','A','B'])
            a*b*a^-1*b^-1

            sage: TestSuite(G).run()
            sage: TestSuite(x).run()
        """
        if not isinstance(x, GapElement):
            try:
                l = x.Tietze()
            except AttributeError:
                if isinstance(x,str): # First check wether x is a string of a generator like 'x0'
                    try:
                        x = [parent._names.index(x) + 1]
                    except ValueError:
                        try:
                            x = [-parent._names.index(x.lower()) - 1]
                        except ValueError:
                            pass
                l = list(x)
            for i,a in enumerate(l):
                if isinstance(a,(int,Integer)):
                    if a < -parent.ngens() or parent.ngens() < a or a == 0:
                        raise ValueError('%s does not denote a generator of %s'%(a,parent))
                elif isinstance(a,str):
                    try:
                        l[i] = parent._names.index(a) + 1
                    except ValueError:
                        try:
                            l[i] = -parent._names.index(a.lower()) - 1
                        except ValueError:
                            raise  ValueError('%s is not a generator of %s'%(a,parent))
            i=0
            while i < len(l)-1:
                if l[i] == -l[i+1]:
                    l.pop(i)
                    l.pop(i)
                    if i>0:
                        i = i-1
                else:
                    i = i+1
            AbstractWordTietzeWord = libgap.eval('AbstractWordTietzeWord')
            x = AbstractWordTietzeWord(l, parent._gap_gens())
        ElementLibGAP.__init__(self, parent, x)

                def __invert__(self):
                    r"""
                    Return the inverse of this element.

                    EXAMPLES::

                        sage: from mygap import mygap
                        sage: G = mygap.FreeGroup("a")
                        sage: a, = G.group_generators()
                        sage: a.__invert__()
                        a^-1
                        sage: a^-1
                        a^-1
                        sage: ~a
                        a^-1
                        sage: ~a * a
                        <identity ...>

                    This also works when inverses are defined everywhere but for zero::

                        sage: F = mygap.FiniteField(3)
                        sage: a = F.one(); a
                        Z(3)^0
                        sage: ~a
                        Z(3)^0
                        sage: ~(a+a)
                        Z(3)
                        sage: a = F.zero()
                        sage: ~a
                        Traceback (most recent call last):
                        ...
                        ValueError: 0*Z(3) is not invertible

                    .. WARN::

                        In other cases, GAP may return the inverse in
                        a larger domain without this being noticed by
                        Sage at this point::

                            sage: N = mygap.eval("Integers")
                            sage: x = N.one()

                        Probably acceptable::

                            sage: y = ~(x + x); y
                            1/2

                        Not acceptable::

                            sage: y.parent()
                            Integers

                    Should we have a category for the analogue of
                    MagmasWithInverseIfNonZero, and move this method
                    there?
                    """
                    from sage.libs.gap.libgap import libgap
                    fail = libgap.eval("fail")
                    inverse = self.gap().Inverse()
                    if inverse == fail:
                        raise ValueError("%s is not invertible"%self)
                    return self.parent()(inverse)