Built in data structures

mutable struct FPTree
    content::Union{Nothing,Item}        # Item contained in this node (nothing if root)

    parent::Union{Nothing,FPTree}       # parent node
    const children::Vector{FPTree}      # children nodes

    count::Int64                        # number of equal Items this node represents

    link::Union{Nothing,FPTree}         # link to another FPTree root
end

Fundamental data structure used in FP-Growth algorithm. Essentialy, an FPTree is a prefix tree where a root-leaf path represent an Itemset.

Consider the Itemsets sorted by gsupport of their items. An FPTree is such that the common Items-prefix shared by different Itemsets is not stored multiple times.

This implementation generalizes the propositional logic case scenario to modal logic; given two Itemsets sharing a Item prefix, the worlds in which they are true is accumulated.

See also EnhancedItemset, fpgrowth, gsupport, Item, Itemset, WorldMask.

content(fptree::FPTree)::Union{Nothing,Item}

Getter for the Item (possibly empty) wrapped by fptree.

See also content!, FPTree.

content!(fptree::FPTree, item::Union{Nothing,Item})

Setter for fptree's content (the wrapped item).

See also content, FPTree.

parent(fptree::FPTree)::Union{Nothing,FPTree}

Getter for the parent FPTrees of fptree.

See also FPTree, parent!.

parent!(fptree::FPTree, item::Union{Nothing,FPTree})

Setter for fptree's parent FPTree.

See also FPTree, parent.

children(fptree::FPTree)::Vector{FPTree}

Getter for the list of children FPTrees of fptree.

See also children!, FPTree.

children!(fptree::FPTree, child::FPTree)

Add a new FPTree to fptree's children vector.

See also children, FPTree.

Base.count(fptree::FPTree)::Int64

Getter for the fptree internal counter. Essentially, it represents the number of overlappings Item which ended up in fptree node during the building process of the tree itself.

See also count!, FPTree, Item.

count!(fptree::FPTree, newcount::Int64)

Setter for fptree's internal counter to a fixed value newcount.

See also count, FPTree.

addcount!(fptree::FPTree, newcount::Int64)

Add newcount to fptree's internal counter.

See also count, FPTree.

link(fptree::FPTree)::Union{Nothing,FPTree}

Getter for fptree's next brother FPTree. fptree's brotherhood is the set of all the FPTree whose content is exactly fptree.content.

See also content, FPTree.

function link!(from::FPTree, to::FPTree)

Establish a link between two FPTrees. If the starting tree is already linked with something, the already existing link are followed until a new "empty-linked" FPTree is found.

See also follow, FPTree, HeaderTable.

function follow(fptree::FPTree)::Union{Nothing,FPTree}

Follow fptree link to (an internal node of) another FPTree.

See also FPTree, HeaderTable.

islist(fptree::FPTree)::Bool

Return true if every subtree in fptree has exactly 0 or 1 children.

See also FPTree

struct HeaderTable
    items::Vector{Item}
    link::Dict{Item,Union{Nothing,FPTree}}
end

Utility data structure used to fastly access FPTree internal nodes.

items(htable::HeaderTable)::Vector{Item}

Getter for the Items loaded inside htable.

See also HeaderTable, Item.

link(htable::HeaderTable)
link(htable::HeaderTable, item::Item)

Getter for the link structure wrapped by htable, or one of its specific entry.

The link structure is, essentially, a dictionary associating an Item to a specific FPTree.

See also FPTree, HeaderTable, Item, link!.

function follow(htable::HeaderTable, item::Item)::Union{Nothing,FPTree}

Follow htable link to (an internal node of) a FPTree.

See also FPTree, HeaderTable, Item, link, link!.

function link!(htable::HeaderTable, fptree::FPTree)

Establish a link towards fptree, following the entry in htable corresponding to the content of fptree.

See also content, FPTree, HeaderTable.

function checksanity!(htable::HeaderTable, miner::Miner)::Bool

Check if htable internal state is correct, that is, its items are sorted decreasingly by global support. If items are already sorted, return true; otherwise, sort them and return false.

See also Miner, gsupport, HeaderTable, items.

Base.reverse(htable::HeaderTable)

Iterator on htable wrapped Items, in reverse order.

See also HeaderTable, Item.