Util Documentation

This page contains the Util Package documentation.

The memoize Module

cmpy.util.memoize.memoize_method(func)

Memoizer for methods, where cache is stored in `self’.

cmpy.util.memoize.clear_cache(func)

Decorator for methods which clears the memoized cache on each call.

cmpy.util.memoize.memoize(func)

The period Module

Functions pertaining to periodicity.

cmpy.util.period.word_periodicity(word, base=False)

Returns the periodicity of a word.

For example, “10101010” is a word, which has “10” repeating. So the period is 2 and the base is “10”. If base=True, we return the base as well.

Notice that “1010” also repeats in this word. The periodicity is the given by the smallest subword which repeats in the word.

cmpy.util.period.periodic_word_iter(period, alphabet, shift=False)

Generator of all periodic words over the alphabet.

For example, period=2 and alphabet=[‘0’,‘1’], will generate:
[‘0’,‘1’] and [‘1’,‘0’]

If shift=True, then we output words which are shifts of each other. For example, 100 and 001 are both words which have period 3, but when considered as a process, they are the same process. To obtain only those words which generate unique periodic processes, set shift=False.

The kddict Module

class cmpy.util.kddict.key_defaultdict

Bases: collections.defaultdict

Methods

clear(() -> None.  Remove all items from D.)
copy(() -> a shallow copy of D.)
fromkeys(...) v defaults to None.
get((k[,d]) -> D[k] if k in D, ...)
has_key((k) -> True if D has a key k, else False)
items(() -> list of D’s (key, value) pairs, ...)
iteritems(() -> an iterator over the (key, ...)
iterkeys(() -> an iterator over the keys of D)
itervalues(...)
keys(() -> list of D’s keys)
pop((k[,d]) -> v, ...) If key is not found, d is returned if given, otherwise KeyError is raised
popitem(() -> (k, v), ...) 2-tuple; but raise KeyError if D is empty.
setdefault((k[,d]) -> D.get(k,d), ...)
update(([E, ...) If E present and has a .keys() method, does: for k in E: D[k] = E[k]
values(() -> list of D’s values)
viewitems(...)
viewkeys(...)
viewvalues(...)
class cmpy.util.kddict.keymode_defaultdict(default_factory, mode)

Bases: collections.defaultdict

Methods

clear(() -> None.  Remove all items from D.)
copy(() -> a shallow copy of D.)
fromkeys(...) v defaults to None.
get((k[,d]) -> D[k] if k in D, ...)
has_key((k) -> True if D has a key k, else False)
items(() -> list of D’s (key, value) pairs, ...)
iteritems(() -> an iterator over the (key, ...)
iterkeys(() -> an iterator over the keys of D)
itervalues(...)
keys(() -> list of D’s keys)
pop((k[,d]) -> v, ...) If key is not found, d is returned if given, otherwise KeyError is raised
popitem(() -> (k, v), ...) 2-tuple; but raise KeyError if D is empty.
setdefault((k[,d]) -> D.get(k,d), ...)
update(([E, ...) If E present and has a .keys() method, does: for k in E: D[k] = E[k]
values(() -> list of D’s values)
viewitems(...)
viewkeys(...)
viewvalues(...)
class cmpy.util.kddict.selfkey_defaultdict

Bases: collections.defaultdict

Methods

clear(() -> None.  Remove all items from D.)
copy(() -> a shallow copy of D.)
fromkeys(...) v defaults to None.
get((k[,d]) -> D[k] if k in D, ...)
has_key((k) -> True if D has a key k, else False)
items(() -> list of D’s (key, value) pairs, ...)
iteritems(() -> an iterator over the (key, ...)
iterkeys(() -> an iterator over the keys of D)
itervalues(...)
keys(() -> list of D’s keys)
pop((k[,d]) -> v, ...) If key is not found, d is returned if given, otherwise KeyError is raised
popitem(() -> (k, v), ...) 2-tuple; but raise KeyError if D is empty.
setdefault((k[,d]) -> D.get(k,d), ...)
update(([E, ...) If E present and has a .keys() method, does: for k in E: D[k] = E[k]
values(() -> list of D’s values)
viewitems(...)
viewkeys(...)
viewvalues(...)

The parsetree Module

class cmpy.util.parsetree.MachineWordListGenerator(**keywords)

Bases: object

This class generates allowable, forbidden, and irreducible forbidden word lists from a machine.

Methods

allowable_words(**keywords) Returns the allowable words keyed by word length.
create_lists(**keywords)
flatten(word_dictionary) Returns a list of words from a dictionary of words keyed by length.
forbidden_words(**keywords) Returns the forbidden words.
generate_word_list() Generates a list of words keyed by length.
ifw([sort])
ifw_iter()
irreducible_forbidden_words(**keywords) Returns the irreducible forbidden words.
allowable_words(**keywords)

Returns the allowable words keyed by word length.

self.create_list(**keywords) must have been called already.

Optional keywords:

flatten = False
If True, then we return a flattened list of words instead of a dictionary keyed by word lengths.
create_lists(**keywords)
flatten(word_dictionary)

Returns a list of words from a dictionary of words keyed by length.

forbidden_words(**keywords)

Returns the forbidden words.

self.create_list(**keywords) must have been called already.

Optional keywords:

flatten = False
If True, then we return a flattened list of words instead of a dictionary keyed by word lengths.
generate_word_list()

Generates a list of words keyed by length.

ifw(sort=True)
ifw_iter()
irreducible_forbidden_words(**keywords)

Returns the irreducible forbidden words.

self.create_list(**keywords) must have been called already.

Optional keywords:

flatten = False
If True, then we return a flattened list of words instead of a dictionary keyed by word lengths.
class cmpy.util.parsetree.DFS(alphabet, depth, **keywords)

Bases: cmpy.util.parsetree.SearchTree

This class acts as a depth-first search, given an alphabet, for a tree of a specified depth.

>>> import cmpy
>>> a = cmpy.DFS(alphabet=['0','1'], depth=2)
>>> a.next()
()
>>> a.next()
('0')
>>> a.next()
('0','0')
>>> a.next()
('0','1')
>>> a.next()
('1')
>>> a.next()
('1','0')
>>> a.next()
('1','1')

At any time, set self.current_word_is_forbidden to True, and the algorithm will prune the tree at the next level.

Methods

backtrack()
contains_word_marked_forbidden(word) Returns True if the word contains a word marked as forbidden.
next() Responsible for returning the next word in the iteration.
next_word()
update_words_marked_forbidden() Adds the current word to dictionary of words marked forbidden.
backtrack()
next()

Responsible for returning the next word in the iteration.

next_word()
class cmpy.util.parsetree.BFS(alphabet, depth=None, **keywords)

Bases: cmpy.util.parsetree.SearchTree

This class acts as a breadth-first serach, given an alphabet, for a tree of a specified depth.

>>> import cmpy
>>> a = cmpy.BFS(alphabet=['0','1'], depth=2)
>>> a.next()
()
>>> a.next()
('0',)
>>> a.next()
('1',)
>>> a.next()
('0','0')
>>> a.next()
('0','1')
>>> a.next()
('1','0')
>>> a.next()
('1','1')

At any time, set self.current_word_is_forbidden to True, and the algorithm will prune the tree at the next level. For example,

>>> import cmpy
>>> a = cmpy.BFS(alphabet=['0','1'], depth=3)
>>> a.next()
()
>>> a.next()
('0',)
>>> a.next()
('1',)
>>> a.current_word_is_forbidden = True
>>> a.next()
('0','0')
>>> a.next()
('0','1')
>>> a.next()
('0','0','0')
>>> a.next()
('0','0','1')
>>> a.next()
('0','1','0')
>>> a.next()
('0','1','1')

Notice, even though Pr(1) was forbidden, we still saw the word (‘0’,‘1’). The search algorithm cannot know that Pr(01) will also be zero, as (‘0’,‘1’) is not a child node of (‘1’,).

Methods

contains_word_marked_forbidden(word) Returns True if the word contains a word marked as forbidden.
next() Responsible for returning the next word in the iteration.
next_word() Returns the next word or raised a StopIteration.
update_words_marked_forbidden() Adds the current word to dictionary of words marked forbidden.
next()

Responsible for returning the next word in the iteration.

next_word()

Returns the next word or raised a StopIteration.

cmpy.util.parsetree.simple_bfs(alphabet, depth=None, start=None)

Breadth-first parsing of tree.

Parameters:

alphabet : iterable

The symbols defining the tree.

start : tuple | None

The start word. If None, then we use ().

depth : int | None

The maximum depth of the tree. If None, then iteration continues indefinitely.

Examples

>>> a = simple_bfs(alphabet=['0','1'], depth=2)
>>> a.next()
()
>>> a.next()
('0',)
>>> a.next()
('1',)
>>> a.next()
('0','0')
>>> a.next()
('0','1')
>>> a.next()
('1','0')
>>> a.next()
('1','1')

At any time, call mark_forbidden() on the word, and the algorithm will prune the tree at the next level. For example,

>>> a = simple_bfs(alphabet=['0','1'], depth=3)
>>> a.next()
()
>>> a.next()
('0',)
>>> w = a.next(); w
('1',)
>>> w.mark_forbidden()
>>> a.next()
('0','0')
>>> a.next()
('0','1')
>>> a.next()
('0','0','0')
>>> a.next()
('0','0','1')
>>> a.next()
('0','1','0')
>>> a.next()
('0','1','1')

Notice, even though Pr(1) was forbidden, we still saw the word (‘0’,‘1’). The search algorithm cannot know that Pr(01) will also be zero, as (‘0’,‘1’) is not a child node of (‘1’,), unless it makes expensive checks.

The misc Module

Define miscellaneous utilities.

cmpy.util.misc.Property(fcn)

Simple property decorator.

Usage:

@Property def attr():

doc = ‘’‘The docstring.’‘’ def fget(self):

pass
def fset(self, value):
pass
def fdel(self)
pass

return locals()

cmpy.util.misc.abstract_method(f)

Simple decorator to designate an abstract method.

Examples

class A(object):

@abstract_method def method(self):

pass
cmpy.util.misc.default_opener(filename)

Opens filename using system’s default program.

Parameters:

filename : str

The path of the file to be opened.

class cmpy.util.misc.deprecate(msg='')

Bases: object

Decorator for deprecating functions.

Note: You must decorate with an instance like so:

@deprecate(msg) def func_to_be_decorated:

pass
cmpy.util.misc.get_fobj(fname, mode='w+')

Obtain a proper file object.

Parameters:

fname : string, file object, file descriptor

If a string or file descriptor, then we create a file object. If fname is a file object, then we do nothing and ignore the specified mode parameter.

mode : str

The mode of the file to be opened.

Returns:

fobj : file object

The file object.

close : bool

If fname was a string or file descriptor, then close will be True to signify that the file object should be closed. Otherwise, close will be False signifying that the user has opened the file object and that we should not close it.

cmpy.util.misc.is_string_like(obj)

Returns True if obj is string-like, and False otherwise.

cmpy.util.misc.len_cmp(x, y)

A comparison function which sorts shorter objects first.

cmpy.util.misc.partition_set(elements, relation=None, innerset=False, reflexive=False, transitive=False)

Returns the equivlence classes from elements.

Given relation, we test each element in elements against the other elements and form the equivalence classes induced by relation. By default, we assume the relation is symmetric. Optionally, the relation can be assumed to be reflexive and transitive as well. All three properties are required for relation to be an equivalence relation.

However, there are times when a relation is not reflexive or transitive. For example, floating point comparisons do not have these properties. In this instance, it might be desirable to force reflexivity and transitivity on the elements and then, work with the resulting partition.

Parameters:

elements : iterable

The elements to be partitioned.

relation : function, None

A function accepting two elements, which returns True iff the two elements are related. The relation need not be an equivalence relation, but if reflexive and transitive are not set to False, then the resulting partition will not be unique. If None, then == is used.

innerset : bool

If True, then the equivalence classes will be returned as frozensets. This means that duplicate elements (according to __eq__ not relation) will appear only once in the equivalence class. If False, then the equivalence classes will be returned as lists. This means that duplicate elements will appear multiple times in an equivalence class.

reflexive : bool

If True, then relation is assumed to be reflexive. If False, then reflexivity will be enforced manually. Effectively, a new relation is considered: relation(a,b) AND relation(b,a).

transitive : bool

If True, then relation is assumed to be transitive. If False, then transitivity will be enforced manually. Effectively, a new relation is considered: relation(a,b) for all b in the class.

Returns:

eqclasses : list

The collection of equivalence classes.

lookup : list

A list relating where lookup[i] contains the index of the eqclass that elements[i] was mapped to in eqclasses.

cmpy.util.misc.require_keys(keys, dikt)

Verifies that keys appear in the specified dictionary.

Parameters:

keys : list of str

List of required keys.

dikt : dict

The dictionary that is checked for keys.

Returns:

None :

Raises:

CMPyException :

Raised when a required key is not present.

cmpy.util.misc.xzip(*args)

This is just like the zip function, except it is a generator.

list(xzip(seq1 [, seq2 [...]])) -> [(seq1[0], seq2[0] ...), (...)]

Return a list of tuples, where each tuple contains the i-th element from each of the argument sequences. The returned list is truncated in length to the length of the shortest argument sequence.

The deque Module

Deque object.

cmpy.util.deque.deque_old(iterable, maxlen=None)

Returns a new deque object initialized with data from iterable.

Parameters:

maxlen : {int, None}

The maximum length of the deque.

class cmpy.util.deque.finite_deque(iterable, maxlen)

Bases: collections.deque

Methods

append(item)
appendleft(item)
clear Remove all elements from the deque.
count(...)
extend(iterable)
extendleft(iterable)
pop Remove and return the rightmost element.
popleft Remove and return the leftmost element.
remove D.remove(value) – remove first occurrence of value.
reverse D.reverse() – reverse IN PLACE
rotate Rotate the deque n steps to the right (default n=1).
append(item)
appendleft(item)
extend(iterable)
extendleft(iterable)

The segmentaxis Module

cmpy.util.segmentaxis.segment_axis(a, length, overlap=0, axis=None, end='cut', endvalue=0)

Generate a new array that chops the given array along the given axis into overlapping frames.

Parameters:

a : array-like

The array to segment

length : int

The length of each frame

overlap : int, optional

The number of array elements by which the frames should overlap

axis : int, optional

The axis to operate on; if None, act on the flattened array

end : {‘cut’, ‘wrap’, ‘end’}, optional

What to do with the last frame, if the array is not evenly divisible into pieces.

  • ‘cut’ Simply discard the extra values
  • ‘wrap’ Copy values from the beginning of the array
  • ‘pad’ Pad with a constant value

endvalue : object

The value to use for end=’pad’

Notes

The array is not copied unless necessary (either because it is unevenly strided and being flattened or because end is set to ‘pad’ or ‘wrap’).

use as_strided

Examples

>>> segment_axis(arange(10), 4, 2)
array([[0, 1, 2, 3],
       [2, 3, 4, 5],
       [4, 5, 6, 7],
       [6, 7, 8, 9]])

The subdict Module

Module defining classes with dict functionality.

class cmpy.util.subdict.indexdict(dict=None, **kwargs)

Bases: cmpy.util.subdict.userdict

A two-way dictionary, providing an index() method.

Examples

>>> x = indexdict()
>>> x[3] = 5
>>> x[1] = 5
>>> x[2] = 3
>>> x.index(3)
set([2])
>>> x.index(5)
set([1,3])

Methods

clear()
copy()
get((k[,d]) -> D[k] if k in D, ...)
has_key(key)
index(value, *default) Return set of keys mapping to value.
pop(key, *default)
popitem()
revlen() Returns the number of unique indexed values.
update([dict])
clear()
copy()
index(value, *default)

Return set of keys mapping to value.

If no additional arguments are passed, a ValueError is raised if the value does not exist in the dictionary.

If an additional argument is passed, then it is returned if the value does not exist in the dictionary.

revlen()

Returns the number of unique indexed values.

class cmpy.util.subdict.aliasdict1(dict=None, **kwargs)

Bases: cmpy.util.subdict.userdict

Alias dictionary, where aliases are not explicitly in the dictionary.

Examples

>>> x = aliasdict1()
>>> x.setalias('dog','puppy')
>>> x['puppy'] = 5
>>> x
{'dog': 5}
>>> x['dog'], x['puppy']
5, 5
>>> x['dog'] = 6
>>> x
{'dog': 6}
>>> del x['puppy']
>>> x
{}

Methods

copy()
delalias(alias)
get((k[,d]) -> D[k] if k in D, ...)
has_key(key)
pop(key, *default)
popitem()
setalias(key, alias)
update([dict])
copy()
delalias(alias)
get(k[, d]) → D[k] if k in D, else d. d defaults to None.
setalias(key, alias)
class cmpy.util.subdict.aliasdict2(dict=None, **kwargs)

Bases: cmpy.util.subdict.userdict

Alias dictionary, where aliases are explicitly in the dictionary.

Examples

>>> x = aliasdict2()
>>> x.setalias('dog','puppy')
>>> x['puppy'] = 5
>>> x
{'dog': 5, 'puppy: 5}
>>> x['dog'], x['puppy']
5, 5
>>> x['dog'] = 6
>>> x
{'dog': 6, 'puppy: 6}
>>> del x['puppy']
>>> x
{}

Methods

copy()
delalias(alias)
get((k[,d]) -> D[k] if k in D, ...)
has_key(key)
pop(key, *default)
popitem()
setalias(key, alias)
update([dict])
copy()
delalias(alias)
setalias(key, alias)

The combinatorics Module

Define combinatoric functions.

class cmpy.util.combinatorics.combinations

Bases: object

combinations(iterable, r) –> combinations object

Return successive r-length combinations of elements in the iterable.

combinations(range(4), 3) –> (0,1,2), (0,1,3), (0,2,3), (1,2,3)

Methods

next
next
cmpy.util.combinatorics.flatten(lol)

Flatten one level of nesting

class cmpy.util.combinatorics.permutations

Bases: object

permutations(iterable[, r]) –> permutations object

Return successive r-length permutations of elements in the iterable.

permutations(range(3), 2) –> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

Methods

next
next
cmpy.util.combinatorics.powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)

stolen from itertools docs.

class cmpy.util.combinatorics.product

Bases: object

product(*iterables) –> product object

Cartesian product of input iterables. Equivalent to nested for-loops.

For example, product(A, B) returns the same as: ((x,y) for x in A for y in B). The leftmost iterators are in the outermost for-loop, so the output tuples cycle in a manner similar to an odometer (with the rightmost element changing on every iteration).

To compute the product of an iterable with itself, specify the number of repetitions with the optional repeat keyword argument. For example, product(A, repeat=4) means the same as product(A, A, A, A).

product(‘ab’, range(3)) –> (‘a’,0) (‘a’,1) (‘a’,2) (‘b’,0) (‘b’,1) (‘b’,2) product((0,1), (0,1), (0,1)) –> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...

Methods

next
next
cmpy.util.combinatorics.slots(n, k, normalized=False)

Generates distributions of n identical items into k distinct slots.

A generator over distributions of n indistinguishable items into k distinguishable slots, where each slot can hold up to n items. Selection of items is done without replacement, and the order within the slots cannot matter since the items are indistinguishable.

The number of distributions is (n + k - 1)! / n!

Parameters:

n : int

The number of indistinguishable items.

k : int

The number of distinguishable slots.

normalized : bool

If True, then we divide each term in the tuple by the number of items. The default value is False.

Examples

>>> list(slots(3,2))
[(0, 3), (1, 2), (2, 1), (3, 0)]
cmpy.util.combinatorics.subwords_iter(word)

Generator of all subwords of `word’, beginning with the empty word.

The total number of subwords grows, at most, as L(L+1)/2 where L is the length of the word.

cmpy.util.combinatorics.words_iter(alphabet, L)

Iterator of words of length L, over the specified alphabet.

Parameters:

alphabet : list

This is the alphabet over which we will generate words.

L : int

The desired word length.

The sequences Module

Sequence Tools

Various functions for working with sequences.

cmpy.util.sequences.segment_axis(a, length, overlap=0, axis=None, end='cut', endvalue=0)

Generate a new array that chops the given array along the given axis into overlapping frames.

Parameters:

a : array-like

The array to segment

length : int

The length of each frame

overlap : int, optional

The number of array elements by which the frames should overlap

axis : int, optional

The axis to operate on; if None, act on the flattened array

end : {‘cut’, ‘wrap’, ‘end’}, optional

What to do with the last frame, if the array is not evenly divisible into pieces.

  • ‘cut’ Simply discard the extra values
  • ‘wrap’ Copy values from the beginning of the array
  • ‘pad’ Pad with a constant value

endvalue : object

The value to use for end=’pad’

Notes

The array is not copied unless necessary (either because it is unevenly strided and being flattened or because end is set to ‘pad’ or ‘wrap’).

use as_strided

Examples

>>> segment_axis(arange(10), 4, 2)
array([[0, 1, 2, 3],
       [2, 3, 4, 5],
       [4, 5, 6, 7],
       [6, 7, 8, 9]])
cmpy.util.sequences.take(n, iter)

Take the next n values from iter.

Parameters:

n : int

The number of elements to pull from iter.

iter : iterable

The iterator to take values from.

cmpy.util.sequences.window_iter(seq, L)

Yields windows of length `L’ from the sequence `seq’.

cmpy.util.sequences.windowed(sequence, length)

Iterate over sliding windows of a data sequence.

Parameters:

sequence : iterable

An iterable to take sliding windows from.

length : int

The size of the windows to slide over the data.