using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace FPTree
{
    /// <summary>
    /// FPGrowth操作類
    /// </summary>
    public class FPGrowthFacade 
    {
        /// <summary>
        /// 計(jì)算頻繁K項(xiàng)集的大小
        /// </summary>
        Hashtable _frequentPattern = new Hashtable();
        /// <summary>
        /// 計(jì)算頻繁K項(xiàng)集的大小
        /// </summary>
        public Hashtable FrequentPattern
        {
            get { return _frequentPattern; }            
        }
        
        
        /// <summary>
        /// 在頻繁一項(xiàng)集表中,從后到前遍歷
        /// 生成條件FPTree
        /// </summary>
        /// <param name="_frequentItemList"></param>
        public void FPGrowth(FPTree _fpTree, List<TreeNodeItem> _itemSet)
        {
            if (_fpTree.SinglePath)
            {  
                //返回所有組合,用_itemSetList保存
                List<ItemSet> _itemSetList = new List<ItemSet>();
                CombineNodes(_fpTree, _itemSetList);
                //產(chǎn)生模式 β∪α,_itemSetList是β的集合                
                AddPattern(_itemSet, _itemSetList);
                
                _itemSet.Clear();
            }
            else
            {
                for (int i = _fpTree.FrequentItemCount - 1; i > -1; i--)
                {                    
                    //頭表中的每個(gè)a(i)
                    TreeNodeItem _treeNodeItem = _fpTree.GetLinkNode(i);                    
                    //產(chǎn)生模式β = a(i)∪α
                    List<TreeNodeItem> _itemSetConbine = new List<TreeNodeItem>();
                    if (_treeNodeItem != null)
                    {
                        if (_itemSet == null)
                            _itemSet = new List<TreeNodeItem>();
                        TreeNodeItem[] _arrTreeNodeItem = new TreeNodeItem[_itemSet.Count];
                        _itemSet.CopyTo(_arrTreeNodeItem);
                        _itemSetConbine.AddRange(_arrTreeNodeItem);
                        _itemSetConbine.Insert(0,_treeNodeItem);                        
                    }
                    //構(gòu)造條件FPTree(1)
                    FPTree _conditionFPTree = new FPTree();
                    _conditionFPTree.MinSupCount = _fpTree.MinSupCount;
                    List<List<TreeNodeItem>> _listStrList = new List<List<TreeNodeItem>>();                    
                    Hashtable _hashTable = new Hashtable();  

                    bool _doLoop = (_treeNodeItem != null);
                    while (_doLoop)
                    {
                        //構(gòu)造條件模式基,支持度計(jì)數(shù)由小到大放入List
                        List<TreeNodeItem> _treeNodeItemList = new List<TreeNodeItem>();
                        GetParentPath(_treeNodeItem.CloneNode(), _treeNodeItemList, _hashTable, _conditionFPTree);

                        //如果模式已經(jīng)產(chǎn)生并且不是頻繁一項(xiàng)集
                        if (_treeNodeItemList.Count == 0 && _itemSetConbine.Count >1)                        
                            //產(chǎn)生模式 
                            AddPattern(_itemSetConbine,_fpTree);                            
                        
                        //構(gòu)造條件FPTree(2)
                        if(_treeNodeItemList.Count>0)                            
                        _listStrList.Add(_treeNodeItemList);                    
                        
                        //多個(gè)條件模式基
                        if (_treeNodeItem.NextNode != null)
                            _treeNodeItem = _treeNodeItem.NextNode;
                        else
                            _doLoop = false;
                    }                   
                    //構(gòu)造條件FPTree(3)
                    if(_listStrList.Count >0)
                    _conditionFPTree.InitializeConditionFPTree(_listStrList);
                
                    //檢查樹(shù)是否為空
                    if (_conditionFPTree.TopNode.Nodes.Count > 0)
                        FPGrowth(_conditionFPTree, _itemSetConbine);   
                    else
                        _itemSetConbine = _itemSet;
                }                
            }
        }
        /// <summary>
        /// 樹(shù)為空時(shí)產(chǎn)生模式
        /// </summary>
        /// <param name="_itemSetConbine">傳入的β = a(i)∪α</param>
        private void AddPattern(List<TreeNodeItem> _itemSetConbine,FPTree _fpTree)
        {
            //產(chǎn)生模式 
            if (!_frequentPattern.ContainsKey(_itemSetConbine.Count))
            {
                List<ItemSet> _tmpItemSetList = new List<ItemSet>();
                ItemSet _tmpItemSet = new ItemSet();
                //產(chǎn)生模式              
                foreach (TreeNodeItem _nodes in _itemSetConbine)
                {
                    _tmpItemSet.Content.Add(_nodes.ItemName);                    
                }
                _tmpItemSet.Count =
                        _fpTree.GetSupCountByID(
                        _itemSetConbine[0].ItemName);
                _tmpItemSetList.Add(_tmpItemSet);
                _frequentPattern.Add(_itemSetConbine.Count, _tmpItemSetList);
            }
            else
            {
                List<ItemSet> _tmpItemSetList = (List<ItemSet>)_frequentPattern[_itemSetConbine.Count];
                ItemSet _tmpItemSet = new ItemSet();
                //增加/設(shè)置α的內(nèi)容           
                foreach (TreeNodeItem _nodes in _itemSetConbine)
                {
                    _tmpItemSet.Content.Add(_nodes.ItemName);                    
                }
                _tmpItemSet.Count =
                        _fpTree.GetSupCountByID(
                        _itemSetConbine[0].ItemName);
                _tmpItemSetList.Add(_tmpItemSet);
                //_frequentPattern[_itemSetConbine.Count] = _tmpItemSetList;
            }
        }
        /// <summary>
        /// 樹(shù)為單一路徑時(shí)產(chǎn)生模式
        /// </summary>
        /// <param name="_itemSet">傳入的α</param>
        /// <param name="_itemSetList">節(jié)點(diǎn)的組合β'</param>
        private void AddPattern(List<TreeNodeItem> _itemSet, List<ItemSet> _itemSetList)
        {
            for (int i = 0; i < _itemSetList.Count; i++)
            {
                //每個(gè)組合β
                ItemSet _tmpItemSet = _itemSetList[i];

                int _count = _itemSet.Count + _tmpItemSet.Content.Count;
                if (!_frequentPattern.ContainsKey(_count))
                {
                    List<ItemSet> _tmpItemSetList = new List<ItemSet>();
                    //增加α的內(nèi)容          
                    foreach (TreeNodeItem _nodes in _itemSet)
                    {
                        //β∪α最小支持度為β(在Combine中已經(jīng)設(shè)置節(jié)點(diǎn)最小的)
                        _tmpItemSet.Content.Add(_nodes.ItemName);
                        //_tmpItemSet.Count = _tmpItemSet.Count;
                    }
                    _tmpItemSetList.Add(_tmpItemSet);
                    _frequentPattern.Add(_count, _tmpItemSetList);
                }
                else
                {
                    List<ItemSet> _tmpItemSetList = (List<ItemSet>)_frequentPattern[_count];
                    //增加α的內(nèi)容
                    foreach (TreeNodeItem _nodes in _itemSet)
                    {
                        //β∪α最小支持度為β(在Combine中已經(jīng)設(shè)置節(jié)點(diǎn)最小的)
                        _tmpItemSet.Content.Add(_nodes.ItemName);
                        //_tmpItemSet.Count = _tmpItemSet.Count;
                    }
                    _tmpItemSetList.Add(_tmpItemSet);
                    //_frequentPattern[_count] = _tmpItemSetList;
                }
            }
        }

        /// <summary>
        /// 返回一個(gè)包含子節(jié)點(diǎn)的父結(jié)點(diǎn)
        /// 設(shè)置父結(jié)點(diǎn)的計(jì)數(shù)為葉子結(jié)點(diǎn)計(jì)數(shù)
        /// 復(fù)制樹(shù)
        /// </summary>
        /// <param name="_treeNodeItem"></param>
        /// <param name="_treeNodeItemList"></param>
        public void GetParentPath(TreeNodeItem _treeNodeItem, List<TreeNodeItem> _treeNodeItemList, Hashtable _hashTable,FPTree _fpTree)
        {
            while (_treeNodeItem.Parent != null && _treeNodeItem.Parent.ItemName != null)
            {
                //條件模式基所有的節(jié)點(diǎn)的支持度計(jì)數(shù)都為葉子計(jì)數(shù)
                TreeNodeItem _newTreeNodeItem = _treeNodeItem.Parent.CloneNode();
                _newTreeNodeItem.Count = _treeNodeItem.Count;
                
                _treeNodeItemList.Insert(0, _newTreeNodeItem);
                //建立頻繁一項(xiàng)集
                if (_hashTable.ContainsKey(_newTreeNodeItem.ItemName))
                    _hashTable[_newTreeNodeItem.ItemName] = Convert.ToInt32(_hashTable[_newTreeNodeItem.ItemName]) +
                        _newTreeNodeItem.Count;
                else
                    _hashTable.Add(_newTreeNodeItem.ItemName, _newTreeNodeItem.Count);
                //頻繁
                if (Convert.ToInt32(_hashTable[_newTreeNodeItem.ItemName]) > _fpTree.MinSupCount - 1)
                {
                    _fpTree.BuildFrequentItemList(_newTreeNodeItem.ItemName,
                        Convert.ToInt32(_hashTable[_newTreeNodeItem.ItemName]));
                }
                _treeNodeItem = _newTreeNodeItem;
            } 
        }
        
        /// <summary>
        /// 獲得所有的模式
        /// 獲取子集算法
        /// </summary>
        /// <param name="_treeNodeItemList"></param>
        public void CombineNodes(FPTree _fpTree, List<ItemSet> _itemSetList)
        {
            //獲取所有結(jié)點(diǎn)
            List<TreeNodeItem> _treeNodeItemList = new List<TreeNodeItem>();
            TreeNodeItem _treeNodeItem = _fpTree.TopNode;
            bool _hasNext = (_treeNodeItem.Nodes.Count > 0);
            _treeNodeItem = _treeNodeItem.Nodes[0];
            while (_hasNext)
            {
                _treeNodeItemList.Add(_treeNodeItem);
                if (_treeNodeItem.Nodes.Count > 0)
                    _treeNodeItem = _treeNodeItem.Nodes[0];
                else
                    _hasNext = false;
            }

            int _length = _treeNodeItemList.Count;
            //從1開(kāi)始,因?yàn)椴蝗】占?            for (int i = 1; i < Math.Pow(2, _length); i++)
            {
                String str = Convert.ToString(int.Parse(i.ToString()), 2);
                str = str.PadLeft(_length, '0');
                char[] _arrChr = str.ToCharArray();             
                ItemSet _itemSet = new ItemSet();
                for (int j = _arrChr.Length-1; j >-1; j--)
                {
                    if (_arrChr[j] == '1')
                    {
                        _itemSet.Content.Add(_treeNodeItemList[j].ItemName);
                        if (_itemSet.Count == 0)
                            _itemSet.Count = _treeNodeItemList[j].Count;
                        else
                        {
                            //支持度等于β中結(jié)點(diǎn)最小的支持度計(jì)數(shù)
                            if(_treeNodeItemList[j].Count < _itemSet.Count)
                            _itemSet.Count = _treeNodeItemList[j].Count;
                        }
                    }
                }
                if(_itemSet.Content.Count!=0)
                    _itemSetList.Add(_itemSet);               
            }
        }

        /// <summary>
        /// 清空所有的數(shù)據(jù)集
        /// </summary>
        public void DisposeAll()
        {
            _frequentPattern.Clear();           
        }       

    }
}