Source code for procars.utils.util_classes

# -*- coding: utf-8 -*-:

"""
Copyright © Bonsai - LIFL (Université Lille 1, CNRS UMR 8022) and Inria-Lille Nord Europe

contact: aida.ouangraoua@inria.fr, amandine.perrin@inria.fr

This software is a computer program whose purpose is to progressively reconstruct ancestral
gene orders.

This software is governed by the CeCILL-B license under French law and
abiding by the rules of distribution of free software. You can use,
modify and/or redistribute the software under the terms of the CeCILL-B
license as circulated by CEA, CNRS and Inria at the following URL
http://www.cecill.info, or in the LICENCE file at the root directory of this program.

The fact that you are presently reading this means that you have had
knowledge of the CeCILL-B license and that you accept its terms.

---------------------------------------------------

``util_classes`` **module description**:

This module contains classes used by ProCARs.

    - SparseMatrix: provides a sparse matrix data structure

.. moduleauthor:: Aïda Ouangraoua, Amandine PERRIN

July 2014

"""


class SparseMatrix:
    """ Class providing a sparse matrix data structure, used when a matrix with a lot of zeros
    is needed.

    Attributes
    ----------
    sparse_matrix : dict
        dictionary where keys are IDs of lines containing non-null elements, and values are
        a dictionary with column IDs with non-null elements as keys and value at these
        positions (line_id, column_id) as values.
        **Ex:** *{x1: {y1: 1, y3: 7}, x8: {y4: 4, y3: 5}}*
        All other positions in the matrix are zeros.
    line_nb : int
        sparse matrix x size (number of lines)
    col_nb : int
        sparse matrix y size (number of columns)
    """
    def __init__(self, line_nb, col_nb):
        self.sparse_matrix = {}
        self.line_nb = line_nb
        self.col_nb = col_nb

    def __getitem__(self, index):
        """ Behaviour of sparse matrix when sparsematrix[i, j] or sparse_matrix[i] is called

        Parameters
        ----------
        index : int or tuple
            if int, line number to return. If tuple, value of the (x, y) matrix case to return

        Returns
        -------
        float or list
            If index was a tuple, it returns the value of sparse_matrix[i, j] (0 if (i, j) not in
            sparse_matrix)
            If index was an int, it returns a list of floats corresponding to values of all
            elements of sparse_matrix in line number 'index' (empty list if no non-null element
            in line number 'index')
        """
        if isinstance(index, int):
            if index < 0 or index > self.line_nb:
                raise IndexError('row index out of bounds')
            return self.sparse_matrix.get(index, {}).values()
        else:
            if index[0] < 0 or index[0] > self.line_nb:
                raise IndexError('row index out of bounds')
            if index[1] < 0 or index[1] > self.col_nb:
                raise IndexError('column index out of bounds')
        return self.sparse_matrix.get(index[0], {}).get(index[1], 0)

    def __setitem__(self, index, elem):
        """ Change the value of an element of the matrix

        Parameters
        ----------
        index : tuple
            index of sparse_matrix single element whose value must be changed
        elem : float or int
            new value to give to the given element of sparse_matrix
        """
        if isinstance(index, tuple) and len(index) == 2:
            if index[0] < 0 or index[0] > self.line_nb:
                raise IndexError('row index out of bounds')
            if index[1] < 0 or index[1] > self.col_nb:
                raise IndexError('column index out of bounds')
            self.sparse_matrix.setdefault(index[0], {})
            self.sparse_matrix[index[0]][index[1]] = elem
        else:
            raise IndexError('give (line, col) index')

    def __eq__(self, other_sparsemat):
        """ Define behaviour to compare two sparse_matrices

        Parameters
        ----------
        other_sparsemat : SparseMatrix
            sparse_matrix to compare with the current one

        Returns
        -------
        boolean
            True if the two sparse_matrices are the same, False otherwise.
        """
        return other_sparsemat.sparse_matrix == self.sparse_matrix

    def __repr__(self):
        """ Define what will be printed if print(sparse_matrix) is called

        Returns
        -------
        string
            the string to print in standard output
        """
        res = ""
        for x in self.sparse_matrix:
            for y in self.sparse_matrix[x]:
                res += "(" + str(x) + ", " + str(y) + "): " + str(self.sparse_matrix[x][y]) + "\n"
        return res

    def pairs(self):
        """ Get all pairs *(x, y)* of sparse_matrix = all non-null element indexes of the matrix

        Returns
        -------
        list
            *pairs:* List of tuples (x, y) for which sparse_matrix[x, y] != 0
        """
        pairs = []
        for x in self.sparse_matrix:
            for y in self.sparse_matrix[x]:
                pairs.append((x, y))
        return pairs