################################################################################

import itertools as it

################################################################################

def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(it.islice(iterable, n))

def consume(iterator, n):
    "Advance the iterator n-steps ahead. If n is none, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(it.islice(iterator, n, n), None)
    return iterator

################################################################################

class SequenceException(Exception):
    """Exception class for Sequence object"""
    pass

################################################################################

class Sequence(object):
    "A integer sequence"

    def __init__(self, description, generator, rep_len = 5):
        """create an integer sequence from a string description,
        a generator describing its elements, and an optional integer
        specfying how many elements are printed in a string representation
        (default is 5)"""
        self._check_rep_len(rep_len)
        self._description = description
        self._generator   = generator  
        self._rep_len     = rep_len    

    def __str__(self):
        """string representation of an integer sequence: description +
        the first rep_len elements"""
        str_rep = ', '.join((str(i) for i in take(self._rep_len, self._generator())))
        return '%s: %s' % (self._description, str_rep)

    def __iter__(self):
        """return a generator to iterate over the elements of this
        integer sequence"""
        return self._generator()

    @staticmethod
    def _check_rep_len(rep_len):
        """check that rep_len is at least 1, raise SequenceException otherwise"""
        if rep_len < 1:
            raise SequenceException("Rep len must be at least 1")

    def get_rep_len(self):
        """how many elements of this integer sequence are printed in
        a string representation?"""
        return self._rep_len

    def set_rep_len(self, rep_len):
        """set how many elements of this integer sequence are printed in
        a string representation"""
        self._check_rep_len(rep_len)
        self._rep_len = rep_len

    rep_len = property(get_rep_len, set_rep_len, None, 
                       "I'm the 'rep_len' property.")

    def get_description(self):
        """return the description of this sequence"""
        return self._description

    def set_description(self, new_description):
        """define a new description for this sequence"""
        self._description = new_description
    
    description = property(get_description, set_description, None, 
                           "I'm the 'description' property.")


################################################################################

class Database(object):
    """A database to store and query integer sequences"""

    def __init__(self, rep_len):
        """create an empty database (when asked, print the first
        rep_len elements of each sequence"""
        self._catalogue = []
        self._rep_len = rep_len

    def __len__(self):
        """return the number of integer sequences in the database"""
        return len(self._catalogue)

    def __iter__(self):
        """return an iterator over this database, i.e., all the
        integer sequences stored in the database"""
        return (sequence for sequence in self._catalogue)

    def add_sequence(self, sequence):
        """add an integer sequence (object Sequence) to the database"""
        sequence.set_rep_len(self._rep_len)
        self._catalogue.append(sequence)

    def delete_sequences(self, ints):
        """delete every sequence in the database that begin as ints"""
        sequences_to_delete = []
        for sequence in self._catalogue:
            if take(len(ints), sequence) == ints:
                sequences_to_delete.append(sequence)
        for sequence in sequences_to_delete:
            self._catalogue.remove(sequence)
        return len(sequences_to_delete)
            
    def search_by_name(self, name):
        """return a generator over all sequences that contain name
        in their description"""
        return (sequence 
                for sequence in self._catalogue 
                if name in sequence.description)
    
    def search_by_seq(self, ints):
        """return a generator over all sequences that begin as ints"""
        return (sequence 
                for sequence in self._catalogue 
                if take(len(ints), sequence) == ints)		

    def search_by_seq_with_shift(self, ints, shift):
        """return a generator over all sequences that begin + shift as ints"""
        return (sequence 
                for sequence in self._catalogue 
                for i in range(shift) 
                if take(len(ints), consume(iter(sequence), i)) == ints)	

    def find_duplicates(self, test_len = None):
        """return a generator over all pairs of sequences that begin with
        the same integers. The test is for test_len integer if it is not
        None, and self._rep_len otherwise"""
        test_len = test_len if test_len is not None else self._rep_len
        return ((sequence1, sequence2)
                for sequence1 in self._catalogue
                for sequence2 in self._catalogue
                if sequence1 < sequence2
                if take(test_len, sequence1) == take(test_len, sequence2))

################################################################################