'''FRENO'''
from time import time
import sys
import csv

def scanDB(path, separator):
	db = {}
	f = open(path, 'r')
	for line in f:
		if line:
			trx = line.rstrip().split(separator)
			db[trx] = db.get(trx, 0) + 1
	f.close()
	return db

def output_perf(fpath, minsup, perf):
	with open(fpath, 'a') as fperf:
		writer = csv.writer(fperf)
		#writer.writerow([minsup, perf])
		for item in perf:
			writer.writerow(item)

def isSubSequence(l1, l2):
    i = 0
    for j in range(len(l2)):
        if l1[i] == l2[j]:
            i += 1
        if i >= len(l1):
            return j
    return False

class TreeNode():
    def __init__(self, key = None, parent = None, count = 0):
        self._key = key
        self._parent = parent
        self._count = count
        self._children = {}
        self._item_table = {}

    def addChild(self, node):
        self._children[node._key] = node


class Tree():
	def __init__(self, minsup, db={}):
		self._db = db
		self._root = TreeNode()
		self._size = 0
		self.minsup = minsup
		self._times = []

    #-------------------------- public accessors -------------------
	def size(self):
		return self._size

	def is_empty(self):
		return self.size() == 0

	#iterators
	def __iter__(self):
		for node in self.preorder():
			yield node

	def nodes(self):
		for node in self.preorder():
			yield node

	def keys(self):
		for node in self.preorder():
			yield node._key

	def counts(self):
		for node in self.preorder():
			yield node._count

	def children(self, node):
		for child in node._children.keys():
			yield child

	def preorder(self):
		if not self.is_empty():
			for node in self._subtree_preorder(self._root):
				yield node

	def _subtree_preorder(self, node):
		yield node
		for c in node._children.values():
			for other in self._subtree_preorder(c):
				yield other

	def toList(self):
		ret = []
		for item in self.preorder():
			if item._count >= self.minsup:
				ret.append(str(item._key))
		return ret

	def __repr__(self):
		ret = []
		for item in self.preorder():
			if item._count >= self.minsup:
				ret.append(str(item._key))
		return str(sorted(ret))

	def _addNode(self, parent, value, count=0):
		newNode = TreeNode(value, parent, count)
		parent.addChild(newNode)
		self._size += 1
		return newNode

	def _recordAccess(self, node):
		node._count += 1

	def _recordInfo(self, node, comb, count=1):
		combStr = (",").join(comb)
		new_freq_items = []
		for item in comb:
			old_count = node._item_table.get(item, 0)
			new_count = old_count + count
			node._item_table[item] = new_count
			# item just became frequent
			if old_count < self.minsup and new_count >= self.minsup:
				new_freq_items.append(item)
		for item in new_freq_items:
			# add node
			newNode = self._addNode(node, node._key + "," + item, node._item_table[item])
			# transfer patterns to newNode
			for ptnStr, c in self._db.items():
				ptn = ptnStr.split(",")
				i = isSubSequence(node._key.split(",") + [item], ptn)
				if i:
					if i < len(ptn) - 1:
						suffix = ptn[i + 1:]
						self._recordInfo(newNode, suffix, c)


	def insertAndRecord(self, node, comb):
		# not root
		self._recordAccess(node)
		# reached the end
		if not comb:
			return
		self._recordInfo(node, comb)
		for i in range(len(comb)):
			if node._key + "," + comb[i] in node._children:
				self.insertAndRecord(node._children[node._key + "," + comb[i]], comb[i+1:])

	def myinsert(self, node, trx):
		trxStr = ",".join(trx)
		self._db[trxStr] = self._db.get(trxStr, 0) + 1
		for i in range(len(trx)):
			if trx[i] not in node._children:
				newNode = self._addNode(node, trx[i])
			self.insertAndRecord(node._children[trx[i]], trx[i+1:])

	def insert(self, node, trx, pointers):
		trxStr = ",".join(trx)
		self._db[trxStr] = self._db.get(trxStr, 0) + 1
		for i in pointers:
			if trx[i] not in node._children:
				newNode = self._addNode(node, trx[i])
			self.insertAndRecord(node._children[trx[i]], trx[i+1:])


