Coverage for local/lib/python2.7/site-packages/sage/combinat/words/word

Hot-keys on this page

r m x p toggle line displays

j k next/prev highlighted chunk

0 (zero) top of page

1 (one) first highlighted chunk

r"""

Datatypes for finite words

"""

#*****************************************************************************

# Vincent Delecroix <20100.delecroix@gmail.com>

# This program is free software: you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation, either version 2 of the License, or

# (at your option) any later version.

# http://www.gnu.org/licenses/

#*****************************************************************************

from __future__ import print_function, absolute_import

from cpython.object cimport Py_EQ, Py_NE

from itertools import islice

cdef class WordDatatype(object):

r"""

The generic WordDatatype class.

Any word datatype must contain two attributes (at least)::

- _parent

- _hash

They are automatically defined here and it's not necessary (and forbidden)

to define them anywhere else.

TESTS::

sage: w = Word([0,1,1,0,0,1])

sage: isinstance(w, sage.combinat.words.word_datatypes.WordDatatype)

True

"""

def __reduce__(self):

r"""

Default pickle support

TESTS::

sage: w = Word([0,1,1,0,0,1])

sage: w.__reduce__()

(Finite words over Set of Python objects of class 'object', ([0, 1, 1, 0, 0, 1],))

"""

return self._parent, (list(self),)

def __hash__(self):

r"""

Returns the hash for this word.

TESTS::

sage: h = hash(Word('abc')) # indirect test

sage: Word('abc').__hash__() == Word('abc').__hash__()

True

sage: tm = words.ThueMorseWord()

sage: hash(tm)

-973965563

"""

cdef int res

if self._hash is None:

res = 5381

for s in islice(self,1024):

res = ((res << 5) + res) + hash(s)

self._hash = res

return self._hash

cdef class WordDatatype_list(WordDatatype):

r"""

Datatype class for words defined by lists.

"""

cdef public list _data

def __init__(self, parent=None, data=None):

r"""

Construct a word with a given parent.

.. NOTE::

It is slower than WordDatatype_str and WordDatatype_tuple.

INPUT:

- ``parent`` - an instance of :class:`Words_all`

- ``data`` - an iterable

EXAMPLES::

sage: w = Word([0,1,1,0])

sage: isinstance(w, sage.combinat.words.word_datatypes.WordDatatype_list)

True

"""

self._parent = parent

if isinstance(data,list):

self._data = data

else:

self._data = list(data)

self._hash = None

def __contains__(self, a):

r"""

Test whether ``a`` is a letter of ``self``.

INPUT:

- ``a`` - anything

OUTPUT:

- boolean

EXAMPLES::

sage: w = Word([0,1,1,0])

sage: 0 in w

True

sage: 3 in w

False

"""

return a in self._data

def __iter__(self):

r"""

Return an iterator that iterates through the letters of self.

EXAMPLES::

sage: w = Word([0,1,1,0])

sage: list(iter(w))

[0, 1, 1, 0]

"""

return iter(self._data)

def __richcmp__(self, other, int op):

r"""

Equality test for self and other if other is an instance of

WordDatype_list.

INPUT:

- ``other`` - a word

- ``op`` - integer: 0, 1, 2, 3, 4 or 5

OUTPUT:

boolean or NotImplemented

EXAMPLES::

sage: w = Word(range(10))

sage: w == w

True

sage: z = Word(range(20))

sage: w == z

False

sage: z == w

False

It works even if the parents are not the same::

sage: Words([0,1])([0,1,1]) == Words([0,1,2])([0,1,1])

True

REFERENCES:

http://docs.cython.org/docs/special_methods.html

"""

if isinstance(other, WordDatatype_list):

if op == Py_EQ:

return self._data == other._data

elif op == Py_NE:

return self._data != other._data

# Otherwise, force FiniteWord_class.__richcmp__ to do it

from sage.combinat.words.word import FiniteWord_class

return FiniteWord_class.__richcmp__(self, other, op)

def __len__(self):

r"""

Return the length of the word.

.. NOTE::

This function will be deprecated in a future version

of Sage. Use ``self.length()`` instead.

EXAMPLES::

sage: w = Word([0,1,1,0])

sage: len(w)

"""

return len(self._data)

def length(self):

r"""

Return the length of the word.

EXAMPLES::

sage: w = Word([0,1,1,0])

sage: w.length()

"""

return len(self._data)

def __getitem__(self, key):

r"""

Implements :meth:`__getitem__` for words stored as lists.

INPUT:

- ``key`` - integer

EXAMPLES::

sage: w = Word(range(100))

sage: w[4]

sage: w[-1]

sage: w[3:10:2]

word: 3579

"""

if isinstance(key, slice):

return self._parent(self._data[key])

else:

return self._data[key]

def __mul__(self, other):

r"""

Return the concatenation of self and other.

INPUT:

- ``other`` - word represented by a list

OUTPUT:

word

EXAMPLES::

sage: w = Word(list(range(10)))

sage: w * w

word: 01234567890123456789

The type of the concatenation is preserved::

sage: type(w)

sage: type(w * w)

"""

if isinstance(other, WordDatatype_list):

return self._parent(self._data + other._data)

else:

return super(WordDatatype_list, self).__mul__(other)

__add__ = __mul__

def count(self, a):

r"""

Returns the number of occurrences of the letter ``a`` in the word

``self``.

INPUT:

- ``a`` - a letter

OUTPUT:

- integer

EXAMPLES::

sage: w = Word([0,1,1,0,1])

sage: w.count(0)

sage: w.count(1)

sage: w.count(2)

"""

return self._data.count(a)

cdef class WordDatatype_str(WordDatatype):

"""

Datatype for words defined by strings.

"""

cdef public str _data

# TODO : allow initialization from non string data

def __init__(self, parent=None, data=None):

r"""

Construct a word with parent ``parent`` from the string ``data``.

INPUT:

- ``parent`` - instance of :class:`Words_all`

- ``data`` - string

EXAMPLES::

sage: w = Word("abba")

sage: isinstance(w, sage.combinat.words.word_datatypes.WordDatatype_str)

True

"""

self._parent = parent

if isinstance(data, str):

self._data = data

else:

self._data = "".join(str(u) for u in data)

self._hash = None

def __iter__(self):

r"""

Return an iterator that iterates through the letters of ``self``.

EXAMPLES::

sage: w = Word('abba')

sage: list(iter(w))

['a', 'b', 'b', 'a']

"""

return iter(self._data)

def __richcmp__(self, other, int op):

r"""

Equality test for self and other if other is an instance of

WordDatype_str.

INPUT:

- ``other`` - a word

- ``op`` - integer: 0, 1, 2, 3, 4 or 5

OUTPUT:

boolean or NotImplemented

EXAMPLES::

sage: w = Word('abcde')

sage: w == w

True

sage: z = Word('epoisudfafgh')

sage: w == z

False

sage: z == w

False

It works even if the parents are not the same::

sage: Words('ab')('ababa') == Words('abcd')('ababa')

True

sage: Words('ab')('ababa') == Word('ababa')

True

REFERENCES:

http://docs.cython.org/docs/special_methods.html

"""

if isinstance(other, WordDatatype_str):

if op == Py_EQ:

return self._data == other._data

elif op == Py_NE:

return self._data != other._data

# Otherwise, force FiniteWord_class.__richcmp__ to do it

from sage.combinat.words.word import FiniteWord_class

return FiniteWord_class.__richcmp__(self, other, op)

def __contains__(self, a):

r"""

Test whether ``a`` is a letter of ``self``.

INPUT:

- ``a`` - anything

EXAMPLES::

sage: w = Word('abba')

sage: 'a' in w

True

sage: 'c' in w

False

"""

# we need to override the non standard comportement of

# the comportment of the __contains__ of python str

if not isinstance(a, str):

return False

if len(a) != 1:

return False

else:

return a in self._data

cpdef _has_factor_naive(self, w):

r"""

A naive test for testing whether the word contains ``w`` as a factor.

.. NOTE::

This just wraps Python's builtin :meth:`__contains__` for :class:`str`.

INPUT:

- ``w`` - a word, or something that behaves like one (list, tuple, str, ...)

OUTPUT:

- boolean

EXAMPLES::

sage: w = Word('abba')

sage: w._has_factor_naive('ba')

True

sage: w._has_factor_naive('bab')

False

"""

if isinstance(w, WordDatatype_str):

return w._data in self._data

elif isinstance(w, str):

return w in self._data

raise ValueError

cpdef find(self, sub, start=0, end=None):

r"""

Returns the index of the first occurrence of sub in self,

such that sub is contained within self[start:end].

Returns -1 on failure.

INPUT:

- ``sub`` - string or word to search for.

- ``start`` - non negative integer (default: 0) specifying

the position from which to start the search.

- ``end`` - non negative integer (default: None) specifying

the position at which the search must stop. If None, then

the search is performed up to the end of the string.

OUTPUT:

non negative integer or -1

EXAMPLES::

sage: w = Word("abbabaabababa")

sage: w.find("a")

sage: w.find("a", 4)

sage: w.find("a", 4, 5)

-1

"""

if end is None:

end = len(self._data)

if isinstance(sub, WordDatatype_str):

return self._data.find(sub._data, start, end)

elif isinstance(sub, str):

return self._data.find(sub, start, end)

else:

return super(WordDatatype_str, self).find(sub, start, end)

def rfind(self, sub, start=0, end=None):

r"""

Returns the index of the last occurrence of sub in self,

such that sub is contained within self[start:end].

Returns -1 on failure.

INPUT:

- ``sub`` - string or word to search for.

- ``start`` - non negative integer (default: 0) specifying

the position at which the search must stop.

- ``end`` - non negative integer (default: None) specifying

the position from which to start the search. If None, then

the search is performed up to the end of the string.

OUTPUT:

non negative integer or -1

EXAMPLES::

sage: w = Word("abbabaabababa")

sage: w.rfind("a")

sage: w.rfind("a", 4, 8)

sage: w.rfind("a", 4, 5)

-1

"""

if end is None:

end = len(self._data)

if isinstance(sub, WordDatatype_str):

return self._data.rfind(sub._data, start, end)

elif isinstance(sub, str):

return self._data.rfind(sub, start, end)

else:

return super(WordDatatype_str, self).rfind(sub, start, end)

def __len__(self):

r"""

Return the length of the word.

.. NOTE::

This function will be deprecated in a future version

of Sage. Use ``self.length()`` instead.

EXAMPLES::

sage: w = Word("abbabaabababa")

sage: len(w)

"""

return len(self._data)

def length(self):

r"""

Return the length of the word.

EXAMPLES::

sage: w = Word("abbabaabababa")

sage: w.length()

"""

return len(self._data)

def __getitem__(self, key):

r"""

Implements the :meth:`__getitem__`.

TESTS::

sage: alphabet = [chr(i) for i in range(97, 123)]

sage: w = Word(alphabet)

sage: w[4]

'e'

sage: w[-1]

'z'

sage: w[3:10:2]

word: dfhj

sage: all(chr(i+97) == w[i] for i in range(w.length()))

True

"""

if isinstance(key, slice):

return self._parent(self._data[key])

return self._data[key]

def __mul__(self, other):

r"""

Return the concatenation of self and other.

INPUT:

- ``other`` - word represented by an str

OUTPUT:

word

EXAMPLES::

sage: w = Word('abcdef')

sage: w * w

word: abcdefabcdef

The type of the concatenation is preserved::

sage: type(w)

sage: type(w * w)

"""

if isinstance(other, WordDatatype_str):

return self._parent(self._data + other._data)

else:

return super(WordDatatype_str, self).__mul__(other)

__add__ = __mul__

def count(self, letter):

r"""

Count the number of occurrences of ``letter``.

INPUT:

- ``letter`` - a letter

OUTPUT:

- integer

EXAMPLES::

sage: w = Word("abbabaabababa")

sage: w.count('a')

sage: w.count('b')

sage: w.count('c')

"""

return self._data.count(letter)

def split(self, sep=None, maxsplit=None):

r"""

Returns a list of words, using sep as a delimiter string.

If maxsplit is given, at most maxsplit splits are done.

Coverage for local/lib/python2.7/site-packages/sage/combinat/words/word_datatypes.pyx : 68%

174 statements 119 run 55 missing 0 excluded