#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
===============================================
GSP (Generalized Sequential Pattern) algorithm
===============================================

GSP algorithm made with Python3 to deal with arrays as transactions.

Example:

transactions = [
				['Bread', 'Milk'],
				['Bread', 'Diaper', 'Beer', 'Eggs'],
				['Milk', 'Diaper', 'Beer', 'Coke'],
				['Bread', 'Milk', 'Diaper', 'Beer'],
				['Bread', 'Milk', 'Diaper', 'Coke']
			]
"""

import logging
import numpy as np

from itertools import combinations

__author__ = "Jackson Antonio do Prado Lima"
__email__ = "jacksonpradolima@gmail.com"
__license__ = "GPL"
__version__ = "1.0"

class GSP:
	def __init__(self, raw_transactions):
		self.freq_patterns = []
		self._pre_processing(raw_transactions)

	def _pre_processing(self, raw_transactions):
		'''
		Prepare the data

		Parameters:
			raw_transactions: the data that it will be analysed
		'''
		# each item is parsed to a set type
		self.transactions = [set(np.array(i)) for i in raw_transactions]

		# different items in the base
		self.unique_candidates = [set([item]) for item in set(x for l in self.transactions for x in l)]

		# the total of different items in the base
		self.t_size = len(self.unique_candidates)

	def _support(self, items, minsup = 0):
		'''
		The support is the probability that the antecedent of the rule is present in the base (transactions) in relation to the total amount of records in the base.

		Parameters
			items: set of items that will be evaluated
			minsup: minimum support
		'''
		results = {}
		for item in items:
			# The number of times the item appears in the base
			frequency = len([t for t in self.transactions if item.issubset(t)])

			# ratio between the frequency and the total of different items in the base
			support = round(frequency / self.t_size, 3)

			if support >= minsup:
				results[tuple(item)] = [frequency, support]
		return results

	def _print_status(self, run, candidates):
		logging.debug("Run {}\nThere are {} candidates.\nThe candidates have been filtered down to {}.\n".format(run, len(candidates), len(self.freq_patterns[run-1])))

	def search(self, minsup = 0.2):
		'''
		Run GSP mining algorithm 

		Parameters
			minsup: minimum support
		'''
		assert (0.0 < minsup) and (minsup <= 1.0)

		# the set of frequent 1-sequence: all singleton sequences (k-itemsets/k-sequence = 1) - Initially, every item in DB is a candidate
		candidates = self.unique_candidates

		# scan transactions to collect support count for each candidate sequence & filter
		self.freq_patterns.append(self._support(candidates, minsup))

		# (k-itemsets/k-sequence = 1)
		k_items = 1

		self._print_status(k_items, candidates)

		# repeat until no frequent sequence or no candidate can be found
		while len(self.freq_patterns[k_items - 1]):
			k_items += 1

			# Generate candidate sets Ck (set of candidate k-sequences) - generate new candidates from the last "best" candidates filtered by minimum support
			candidates = [set(c) for c in combinations(set(x for l in self.freq_patterns[k_items - 2].keys() for x in l), k_items)]

			# candidate pruning - eliminates candidates who are not potentially frequent (using support as threshold)
			self.freq_patterns.append(self._support(candidates, minsup))

			self._print_status(k_items, candidates)
		return self.freq_patterns[:-1]
@@ -1219,24 +1219,25 @@
  the base%0A%09%09
+#
 self.t_size 
@@ -1266,16 +1266,16 @@
 idates)%0A
-
 %0A%09def _s
@@ -1331,152 +1331,321 @@
 ort 
-is the probability that the antecedent of the rule is present 
+count (or simply support) for a sequence is defined as the fraction of total data-sequences that %22conta
 in
+%22
  th
-e base (transactions) in relation to the total amount of records in the base.
+is sequence. %0A%09%09(Although the word %22contains%22 is not strictly accurate once we incorporate taxonomies, %0A%09%09it captures the spirt of when a data-sequence contributes to the support of a sequential pattern.)
 %0A%0A%09%09
@@ -1815,28 +1815,37 @@
 ears in the 
-base
+transactions 
 %0A%09%09%09frequenc
@@ -1912,144 +1912,20 @@
 %0A%09%09%09
-# ratio between the frequency and the total of different items in the base%0A%09%09%09support = round(frequency / self.t_size, 3)%0A%0A%09%09%09if support
+if frequency
  %3E= 
@@ -1973,17 +1973,8 @@
 ency
-, support
 %5D%0A%09%09
@@ -2309,16 +2309,16 @@
 t%0A%09%09'''%0A
-
 %09%09assert
@@ -2352,16 +2352,59 @@
  %3C= 1.0)
+%0A%09%09minsup = len(self.transactions) * minsup
 %0A%0A%09%09# th

update gsp