java实现fp-growth算法

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：fpTree树节点
 * 
 * @param 
 *
 * @author xiaomingyang
 * @created on 2019年5月23日，下午8:01:46
 */
public class FpTreeNode {
    /**
     * 当前节点频繁度
     */
    private long count = 0;
    
    /**
     * 节点内容值
     */
    private T nodeVal;
    
    /**
     * 父类节点
     */
    private FpTreeNode parent = null;
    
    /**
     * 当前节点子节点
     */
    private List> children = null;
    
    /**
     * helper
     */
    private FpTreeHelper helper = null;
    
    public FpTreeNode(long count, T nodeVal, FpTreeNode parent, List> children,
            FpTreeHelper helper) {
        super();
        this.count = count;
        this.nodeVal = nodeVal;
        this.parent = parent;
        this.children = children;
        this.helper = helper;
    }

    /**
     * 描述：添加子节点
     *
     * @param child
     * @return 被添加的子节点
     * @author xiaomingyang
     * @created on 2019年5月23日，下午7:33:13
     */
    public FpTreeNode addChild(FpTreeNode child) {
        if (this.getChildren() == null) {
            children = new ArrayList>();
        }
        child.setParent(this);
        this.children.add(child);
        return child;
    }
    
    /**
     * 描述：向当前节点添加路径
     * 

     * List结构数据前一项为后一项数据父节点，例：

     * a,b,c,d
     * 
     * 
     * 
     * 
     * 
     * 
     * 

节点
父节点

a
null

b
a

c
b

d
c

     * 
     * @param path 树的一条路径，是某个事物下的数据记录列表
     * @param parentNode 路径第一个节点的父节点
     * @return 
     * @author xiaomingyang
     * @created on 2019年5月25日，下午9:42:41
     */
    public void addPath(List path, FpTreeNode parentNode) {
        if (path == null || path.size() == 0) {
            return ;
        }
        
        T firstEl = path.get(0);
        if (parentNode != null 
                && helper.nodeCompare(firstEl, parentNode.getNodeVal())) {
            parentNode.increaseCountOne();
            parentNode.addPath(path.subList(1, path.size()), parentNode);
        } else {
            FpTreeNode fnode = new FpTreeNode(1, firstEl, null, null, this.getHelper()); 
            
            FpTreeNode exsistChild = this.findChild(fnode.getNodeVal());
            if (exsistChild != null) {
                exsistChild.increaseCountOne();
                exsistChild.addPath(path.subList(1, path.size()), exsistChild);
            } else {
                FpTreeNode node = this.addChild(fnode);
                node.addPath(path.subList(1, path.size()), node);
            }
        }
    }
    
    /**
     * 描述：计数器加一
     *
     * @return 当前节点计数器
     * @author xiaomingyang
     * @created on 2019年5月23日，下午7:36:21
     */
    public long increaseCountOne() {
        return this.increaseCount(1);
    }
    
    /**
     * 描述：
     *
     * @param increasement
     * @return 当前节点计数器
     * @author xiaomingyang
     * @created on 2019年5月23日，下午7:37:16
     */
    public long increaseCount(long increasement) {
        this.count += increasement;
        return this.count;
    }
    
    /**
     * 描述： 当前节点寻找指定子节点,有，则返回节点，无则返回null
     *
     * @param childVal
     * @return
     * @author xiaomingyang
     * @created on 2019年5月23日，下午7:41:42
     */
    public FpTreeNode findChild(T childVal) {
        if (children == null) {
            return null;
        }
        for (FpTreeNode child : children) {
            if (helper.nodeCompare(child.getNodeVal(), childVal)) {
                return child;
            }
        }
        return null;
    }

    @Override
    public String toString() {
        return super.toString() + "-node (val:" + this.getNodeVal() + ", count: " + this.getCount() + ")";
    }

    public long getCount() {
        return count;
    }

    public void setCount(long count) {
        this.count = count;
    }

    public T getNodeVal() {
        return nodeVal;
    }

    public void setNodeVal(T nodeVal) {
        this.nodeVal = nodeVal;
    }

    public FpTreeNode getParent() {
        return parent;
    }

    public void setParent(FpTreeNode parent) {
        this.parent = parent;
    }

    public List> getChildren() {
        return children;
    }

    public void setChildren(List> children) {
        this.children = children;
    }

    public FpTreeHelper getHelper() {
        return helper;
    }

    public void setHelper(FpTreeHelper helper) {
        this.helper = helper;
    }
}

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.util.Assert;

import com.slyk.sdp.algorithms.externalAlgorithms.fpTree.util.ListSortUtils;

/**
 * 描述：fptree项头表
 * 
 * @param 
 *
 * @author xiaomingyang
 * @created on 2019年5月23日，下午8:05:14
 */
@SuppressWarnings("hiding")
public class FpTreeHeaderextends LinkedHashMap  {
    private static Logger logger = LoggerFactory.getLogger(FpTreeHeader.class);
    
    private static final long serialVersionUID = 1L;
    
    /**
     * 过滤、排序后的原始数据,用以做构建fptree输入数据
     */
    private List> inputData = new LinkedList>();
    
    /**
     * helper
     */
    private FpTreeHelper helper;
    
    /**
     * 节点链,fptree构建后依据项头表建立的节点链列表
     */
    private Map>> treeNodeMap = new LinkedHashMap>>();
    
    /**
     * 描述：添加helper
     *
     * @param helper
     * @return
     * @author xiaomingyang
     * @created on 2019年5月29日，上午10:54:18
     */
    public FpTreeHeader addHelper( FpTreeHelper helper) {
        this.setHelper(helper);
        return this;
    }
    
    /**
     * 描述: 构建节点链列表
     *
     * @param node
     * @author xiaomingyang
     * Created On 2019年5月29日, 上午1:13:27
     */
    protected void buildNodeEntryList(FpTreeNode node) {
        if (node.getCount() != -1) {
            List> nodeList = treeNodeMap.get(node.getNodeVal());
            if (nodeList == null) {
                nodeList = new ArrayList>();
                nodeList.add(node);
                treeNodeMap.put(node.getNodeVal(), nodeList);
            } else {
                nodeList.add(node);
            }
        }
        
        if (node.getChildren() == null) {
            return ;
        }
        
        for (FpTreeNode child : node.getChildren()) {
            buildNodeEntryList(child);
        }
    }
    
    /**
     * 描述：构建项头表
     *
     * @param sourceData
     * @param absSupport
     * @return
     * @author xiaomingyang
     * @created on 2019年5月23日，下午8:36:58
     */
    @SuppressWarnings("unchecked")
    public FpTreeHeader buildTable(List> sourceData, int absSupport) {
        Assert.notNull(this.helper, "helper cannot be null, Set helper first!");
        
        logger.debug("构建项头表.");
        for (List data : sourceData) {
            for (K k : data) {
                if (this.get(k) == null) {
                    this.put(k, 1);
                } else {
                    this.put(k, this.get(k) + 1);
                }
            }
        }
        
        // 过滤不满足项目
        Set> set = this.entrySet();
        Iterator> ite = set.iterator();
        while (ite.hasNext()) {
            java.util.Map.Entry entry = ite.next();
            if (entry.getValue()  absSupport) {
                ite.remove();
            }
        }
        
        // 项头表排序
        List keylist = new ArrayList(this.keySet());
        Map thisRef = (Map) new LinkedHashMap();
        ListSortUtils.sort(keylist, this.getHelper().nodeEleCompare((FpTreeHeader) this));
        for (K k : keylist) {
            thisRef.put(k, (Integer) this.get(k));
        }
        this.clear();
        this.putAll((Map extends K, ? extends java.lang.Integer>) thisRef);
        
        // 对原始输入数据过滤并排序
        for (List data : sourceData) {
            for (Iterator itr = data.iterator(); itr.hasNext(); ) {
                K k = itr.next();
                if (!this.containsKey(k)) {
                    itr.remove();
                }
            }
            FpTreeHeader _this = (FpTreeHeader) this;
            ListSortUtils.sort(data, new Comparator() {
                @Override
                public int compare(K o1, K o2) {
                    int i = _this.get(o2) - _this.get(o1);
                    if (i == 0) {
                        Iterator> itr = _this.entrySet().iterator();
                        int index1 = 0;
                        int index2 = 0;
                        for (int a = 0,b = 0; itr.hasNext(); ) {
                            a = a + 1;
                            b = b + 1;
                            java.util.Map.Entry entry = itr.next();
                            if (helper.nodeCompare(entry.getKey(), o1)) {
                                index1 = a;
                            } else if (helper.nodeCompare(entry.getKey(), o2)) {
                                index2 = b;
                            }
                        }
                        i = index1 - index2;
                    }
                    return i;
                }
                
            });
            if (!data.isEmpty()) {
                inputData.add(data);
            }
        }
        sourceData = null;
        logger.debug("构建项头表完成.");
        return this;
    }

    public List> getInputData() {
        return inputData;
    }

    public void setInputData(List> inputData) {
        this.inputData = inputData;
    }

    public FpTreeHelper getHelper() {
        return helper;
    }

    public void setHelper(FpTreeHelper helper) {
        this.helper = helper;
    }

    public Map>> getTreeNodeMap() {
        return treeNodeMap;
    }

    public void setTreeNodeMap(Map>> treeNodeMap) {
        this.treeNodeMap = treeNodeMap;
    }
}

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.util.Assert;

import com.slyk.sdp.algorithms.externalAlgorithms.fpTree.util.DoubleKeyMap;

/**
 * FPtree
 * 
 * 描述：@param 
 *
 * @author xiaomingyang
 * @created on 2019年6月3日，下午1:34:22
 */
public class FpTree {
    private static Logger logger = LoggerFactory.getLogger(FpTree.class);
    
    /**
     * 项头表
     */
    private FpTreeHeader fpTreeHeader;
    
    /**
     * helper
     */
    private FpTreeHelper helper;
    
    /**
     * root node
     */
    private FpTreeNode root;
    
    /**
     * 默认频繁度阈值
     */
    protected static final int DEFAULT_ABS_SUPPORT = 0xf;
    
    private int absSupport = DEFAULT_ABS_SUPPORT;
    
    /**
     * 默认置信度
     */
    private static final int DEFAULT_CONFIDENT = 3;
    
    /**
     * 置信度
     */
    private int confident = DEFAULT_CONFIDENT;
    
    /**
     * 描述：挖掘树
     * 
代码参考自《机器学习实战》
     *
     * @param outList
     * @param tree
     * @param basePat
     * @return
     * @throws ClassNotFoundException
     * @throws IOException
     * @author xiaomingyang
     * @created on 2019年5月31日，下午5:50:45
     */
    public List> fpGrowth(List> outList, FpTree tree, List prefix) throws ClassNotFoundException, IOException {
        logger.debug("开始conditionFpTree数据挖掘计算.");
        //
        // 挖掘频繁项集的步骤如下：
        // 1 从FP树提取条件模式基
        // 2 用条件模式基构造FP树
        // 3 重复1和2直到树只包含一个元素
        //
        DoubleKeyMap, Integer> cpbs = tree.buildPrefixPath();
        
        // 从项头表逆序访问
        ListIterator> li =
                new ArrayList>(
                        this.fpTreeHeader.entrySet()).listIterator(this.fpTreeHeader.size()); 
        for ( ;li.hasPrevious(); ) {
            Map.Entry entry = li.previous(); 
            T fpHeaderItem = entry.getKey();
                       
            List newBasePat = new ArrayList(prefix);
            newBasePat.add(fpHeaderItem);
            
            this.getHelper().resultHandler(newBasePat, confident, entry.getValue());
            logger.debug("发现频繁项集：" + newBasePat.toString());
            
            Set> set = cpbs.get(fpHeaderItem).keySet();
            Iterator> setItr = set.iterator();
            Map> cpbInputData = new LinkedHashMap>();
            for ( ; setItr.hasNext(); ) {
                List cpb = setItr.next();
                Integer count = cpbs.get(fpHeaderItem, cpb);
                for (int repeat = 0; repeat ) {
                    if (!cpb.isEmpty()) {
                        cpbInputData.put(cpb.toString() + "-" + repeat, cpb);
                    }
                }
            }
            FpTree cpbTree = new FpTree();
            cpbTree.setHelper(this.getHelper());
            cpbTree = cpbTree.init(this.getAbsSupport(), this.getConfident(), cpbInputData);
            if (!cpbTree.getFpTreeHeader().keySet().isEmpty()) {
                cpbTree.fpGrowth(outList, cpbTree, newBasePat);
            }
            
            cpbTree = null;
            cpbInputData = null;
        }
        logger.debug("完成conditionFpTree数据挖掘计算.");
        return outList;
    }
    
    /**
     * 描述：初始、构建fptree，为数据挖掘做准备
     * 

     * 
     * 输入sourceMap数据结构：
     * KEY              LIST
     * T0               1,2,3,4
     * T1               1
     * T2               3,4
     * T3               2,3
     * 
     * 
     * @param absSupport
     * @param sourceMap
     * @return
     * @author xiaomingyang
     * @created on 2019年5月29日，上午11:53:11
     */
    public FpTree init(Integer absSupport, Integer confident, Map> sourceMap) {
        logger.debug("开始fptree构建.");
        this.absSupport = absSupport == null ? this.getAbsSupport() : absSupport;
        this.confident = confident == null ? this.getConfident() : confident;
        
        List> sourceData = new ArrayList>();
        Set keys = sourceMap.keySet();
        for (String key : keys) {
            List inList = sourceMap.get(key);
            sourceData.add(inList);
        }
        
        this.fpTreeHeader = new FpTreeHeader().addHelper(helper)
                .buildTable(sourceData, absSupport);
        sourceData = null;
        
        root = buildTree();
        
//        logger.info("构建构建节点链.");
        this.fpTreeHeader.buildNodeEntryList(root);
//        logger.info("构建构建节点链完成.");
        logger.debug("完成fptree构建..");
        return this;
    } 
    
    /**
     * 描述：构建条件模式基
     *
     * @return
     * @author xiaomingyang
     * @created on 2019年5月29日，下午2:37:47
     */
    public DoubleKeyMap, Integer> buildPrefixPath() {
        Assert.notNull(this.fpTreeHeader, "fpTreeHeader cannot be null, Set helper first!");
        logger.debug("构建条件模式基");
        DoubleKeyMap, Integer> cpb = new DoubleKeyMap, Integer>();
        // 从项头表逆序寻找条件模式集
        ListIterator> li =
                new ArrayList>(
                        this.fpTreeHeader.entrySet()).listIterator(this.fpTreeHeader.size()); 
        for ( ;li.hasPrevious(); ) {
            Map.Entry entry = li.previous(); 
            T fpHeaderItem = entry.getKey();
            List> nodeList = this.getFpTreeHeader().getTreeNodeMap().get(fpHeaderItem);
            for (FpTreeNode node : nodeList) {
                cpb = findPrefixPath(node, cpb);
            }
        }
        logger.debug("完成构建条件模式基");
        return cpb;
    }
    
    /**
     * 描述：寻找条件模式基
     *
     * @param node 节点链中的节点
     * @return
     * @author xiaomingyang
     * @created on 2019年5月27日，上午1:05:45
     */
    private DoubleKeyMap, Integer> findPrefixPath(FpTreeNode node, DoubleKeyMap, Integer> cpb) {
        Assert.notNull(this.fpTreeHeader, "fpTreeHeader cannot be null, Set helper first!");
        List prefixPath = new ArrayList();
        FpTreeNode up = node.getParent();
        while (up.getParent() != null) {
            prefixPath.add(up.getNodeVal());
            up = up.getParent();
        }
        Collections.reverse(prefixPath);
        cpb.put(node.getNodeVal(), prefixPath, (int) node.getCount());
        return cpb;
    }
    
    /**
     * 描述：构建fptree
     *
     * @return
     * @author xiaomingyang
     * @created on 2019年5月24日，上午11:45:34
     */
    private FpTreeNode buildTree() {
        Assert.notNull(this.helper, "helpser cannot be null, Set helper first!");
        Assert.notNull(this.fpTreeHeader, "fpTreeHeader cannot be null, Set helper first!");
        
        FpTreeNode rootNode = new FpTreeNode(-1, null, null, null, helper);
        
        int index = 0;
        for (List path : this.fpTreeHeader.getInputData()) {
            rootNode.addPath(path, rootNode);
            index += 1;
            logger.debug("fptree完成进度:" + index + "/" + this.fpTreeHeader.getInputData().size());
        }
        
        return rootNode;
    }
    
    /**
     * 描述: 打印树,以便直观观察
     *
     * @param node
     * @param ins
     * @author xiaomingyang
     * Created On 2019年5月29日, 上午12:27:43
     */
    public void display(FpTreeNode node, int ins) {
        if (node.getParent() == null) {
            logger.info("打印树形结构如下：");
        }
        System.out.print(StringUtils.repeat("  ", ins) + node.getNodeVal() + "  " + node.getCount() + "\n");
        if (node.getChildren() == null) {
            return ;
        }
        ins = ins + 1;
        for (FpTreeNode subNode : node.getChildren()) {
            display(subNode, ins);
        }
    }
    
    /**
     * 描述：deepCopy
     *
     * @param src
     * @return
     * @throws IOException
     * @throws ClassNotFoundException
     * @author xiaomingyang
     * @created on 2019年5月30日，下午5:28:26
     */
    @SuppressWarnings("unchecked")
    public static  List deepCopy(List src) throws IOException, ClassNotFoundException {  
        ByteArrayOutputStream byteOut = new ByteArrayOutputStream();  
        ObjectOutputStream out = new ObjectOutputStream(byteOut);  
        out.writeObject(src); 
        ByteArrayInputStream byteIn = new ByteArrayInputStream(byteOut.toByteArray());  
        ObjectInputStream in = new ObjectInputStream(byteIn);  
        List dest = (List) in.readObject();  
        return dest;  
    }  

    public FpTreeHeader getFpTreeHeader() {
        return fpTreeHeader;
    }

    public void setFpTreeHeader(FpTreeHeader fpTreeHeader) {
        this.fpTreeHeader = fpTreeHeader;
    }

    public FpTreeHelper getHelper() {
        return helper;
    }

    public void setHelper(FpTreeHelper helper) {
        this.helper = helper;
    }

    public FpTreeNode getRoot() {
        return root;
    }

    public void setRoot(FpTreeNode root) {
        this.root = root;
    }

    public int getAbsSupport() {
        return absSupport;
    }

    public void setAbsSupport(int absSupport) {
        this.absSupport = absSupport;
    }

    public int getConfident() {
        return confident;
    }

    public void setConfident(int confident) {
        this.confident = confident;
    }
}

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree;

import java.util.Comparator;
import java.util.List;

/**
 * 描述：fptree helper class
 * 
 * @param 
 *
 * @author xiaomingyang
 * @created on 2019年5月23日，下午7:49:46
 */
public interface FpTreeHelper {
    /**
     * 描述：比较目标节点和源节点是否相等，等返回true,否则false
     *
     * @param target
     * @param source
     * @return
     * @author xiaomingyang
     * @created on 2019年5月23日，下午7:52:35
     */
    boolean nodeCompare(T target, T source);
    
    /**
     * 描述：比较节点内容
     *
     * @return
     * @author xiaomingyang
     * @created on 2019年5月29日，上午10:42:35
     */
    Comparator nodeEleCompare(FpTreeHeader header);
    
    /**
     * 描述: 找到的结果处理
     *
     * @param result 单条记录
     * @param extArgs 附加参数
     * @author xiaomingyang
     * Created On 2019年6月2日, 上午1:36:35
     */
    void resultHandler(List result, Object ...extArgs);
}

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree.util;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class DoubleKeyMap {
    Map> data = new LinkedHashMap>();

    public Value put(Key1 k1, Key2 k2, Value v) {
        Map data2 = data.get(k1);
        Value prev = null;
        if ( data2==null ) {
            data2 = new LinkedHashMap();
            data.put(k1, data2);
        }
        else {
            prev = data2.get(k2);
        }
        data2.put(k2, v);
        return prev;
    }

    public Value get(Key1 k1, Key2 k2) {
        Map data2 = data.get(k1);
        if ( data2==null ) return null;
        return data2.get(k2);
    }

    public Map get(Key1 k1) { return data.get(k1); }

    /** Get all values associated with primary key */
    public Collection values(Key1 k1) {
        Map data2 = data.get(k1);
        if ( data2==null ) return null;
        return data2.values();
    }

    /** get all primary keys */
    public Set keySet() {
        return data.keySet();
    }

    /** get all secondary keys associated with a primary key */
    public Set keySet(Key1 k1) {
        Map data2 = data.get(k1);
        if ( data2==null ) return null;
        return data2.keySet();
    }

    public Collection values() {
        Set s = new HashSet();
        for (Map k2 : data.values()) {
            for (Value v : k2.values()) {
                s.add(v);
            }
        }
        return s;
    }
    
    @SuppressWarnings("unchecked")
    public void print() {
        System.out.println("条件模式基集合:");
        Set kset = this.keySet();
        for (Iterator itrKey1 = kset.iterator(); itrKey1.hasNext();) {
            Key1 key1 = itrKey1.next();
            for (Iterator itrKey2 = this.get(key1).keySet().iterator(); itrKey2.hasNext();) {
                Object key2 = itrKey2.next();
                System.out.println(key1 + ":" + key2 + "(" + this.get(key1, (Key2) key2) + ")");
            }
        }
    }
}

package com.slyk.sdp.algorithms.externalAlgorithms.fpTree.util;

import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;

/**
 * 描述: 求集合排序，原本集合collections包有排序功能，但是jdk7后改为 timsort排序实现，此类实现存在问题，例如： int[]
 * sample = new int[]
 * {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 * ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-2,1,0,-2,0,0,0,0};
 * 如上例子数据在timsort排序将会报错，因此排序算法将参考JDK5的LegacyMergeSort算法封装排序。
 *
 * @author xiaomingyang
 *         2019年6月2日,下午11:35:16
 * @version v0.1
 */
public class ListSortUtils {
    /**
     * 描述：参考Collections.sort()方法
     *
     * @param list
     * @param c
     * @author xiaomingyang
     * @created on 2019年6月3日，下午1:35:04
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void sort(List list, Comparator super T> c) {
        Object[] a = list.toArray();
        sort(a, (Comparator) c);
        ListIterator i = list.listIterator();
        for (int j = 0; j ) {
            i.next();
            i.set(a[j]);
        }
    }

    public static void sort(T[] a, Comparator super T> c) {
        T[] aux = (T[]) a.clone();
        if (c == null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

    private static final int INSERTIONSORT_THRESHOLD = 7;

    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static void mergeSort(Object[] src, Object[] dest, int low,
            int high, int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length  INSERTIONSORT_THRESHOLD) {
            for (int i = low; i )
                for (int j = i; j > low
                        && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable) src[mid - 1]).compareTo(src[mid]) ) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (int i = destLow, p = low, q = mid; i ) {
            if (q >= high || p  mid
                    && ((Comparable) src[p]).compareTo(src[q]) )
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static void mergeSort(Object[] src, Object[] dest, int low,
            int high, int off, Comparator c) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length  INSERTIONSORT_THRESHOLD) {
            for (int i = low; i )
                for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid - 1], src[mid]) ) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (&lt