商品分类以及统计

     在卓越网首页的左边,或者当当网的左边，都有商品分类列表，并会显示旗下的商品有多少种。如何在计算机中描述？那可定是用树来表示。但要高效地完成这个功能会面临哪些问题？

    1、怎么统计某一分类的商品种类

    2、如果更改某一分类商品种类数量，怎么通知其他节点

    3、对于非叶子节，是否要记录商品数，

    4、如果增加新的商品类型，又怎么做

 

    对于这些问题，我认为关键的一点是：一旦有数据变化，就要通知双亲，直到根节点。这样一来，每当获取某一中分类的商品种类数时，它会检测是否收到通知，如果收到，则重新计算；否则直接返回数量。

    2011年9月，引入CommodityVisitor和CommoditySearcher，用来处理遍历和检索两种情况；重写计算商品分类数量的相关函数；删除多余函数。

   废话不多说，直接贴代码，欢迎拍砖。

 

 

/**
 * 商品分类
 */
public class CommodityClassify implements Cloneable {
    private static final int ZERO = 0;
    //*************************  节点属性  ******************************
    /**
     * 该分类名称
     */
    private String name;
    /**
     * 商品分数码
     */
    private String code;
    /**
     * 该分类下的商品种类数
     */
    private int amount = ZERO;
    /**
     * 是否要计算商品种类
     */
    private boolean needRecount = true;

    //*************************** 树形关系  *********************************
    /**
     * 双亲结点
     */
    private CommodityClassify parent;
    /**
     * 孩子结点
     */
    private List<CommodityClassify> children = Collections.synchronizedList(new LinkedList<CommodityClassify>());

    public CommodityClassify(String name, String code) {
        this(name, code, ZERO);
    }

    public CommodityClassify(String name, String code, int amount) {
        this.name = name;
        this.code = code;
        this.amount = amount;
    }

    /**
     * 调整节点的amount
     *
     * @param amount
     */
    public synchronized void adjustAmount(int amount) {
        //1、如果是叶子节点，则传入amount，否则跳过
        if (isLeafy() && this.amount != amount) {
            this.amount = amount;
            onAmountChange();
        }
    }

    /**
     * 判断是否为叶子节点
     */
    public boolean isLeafy() {
        return 0 == children.size();
    }

    /**
     * 计算当前节点的商品种类
     */
    public int calcAmount() {
        if (needRecount && !isLeafy()) {
            amount = ZERO;
            for (CommodityClassify cc : children) {
                amount += cc.calcAmount();
            }
            needRecount = false;
        }
        return amount;
    }

    /**
     * 返回深度
     *
     * @return
     */
    public int getDepth() {
        int depth = 1;
        CommodityClassify root = parent;
        while (root != null) {
            depth += 1;
            root = root.getParent();

        }
        return depth;
    }

    //*************************  getter/setter  ******************************
    protected void setChildren(List<CommodityClassify> children) {
        this.children = children;
    }

    public boolean isNeedRecount() {
        return needRecount;
    }

    private void setNeedRecount(boolean needRecount) {
        this.needRecount = needRecount;
    }

    public CommodityClassify getParent() {
        return parent;
    }

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

    public String getName() {
        return name;
    }

    public String getCode() {
        return code;
    }

    public List<CommodityClassify> getChildren() {
        return children;
    }

    public int getAmount() {
        return amount;
    }
    //*********************  节点操作  **********************

    /**
     * 增加孩子结点
     * 需要同步
     *
     * @param cc
     */
    private void addChild(CommodityClassify cc) {
        //1、设置双亲节点
        cc.setParent(this);
        //2、增加叶子节点
        children.add(cc);
        onAmountChange();
    }
    /**
     * 删除孩子节点
     *
     * @param cc
     */
    private void removeChild(CommodityClassify cc) {
        //1、待删除的节点清空双亲
        cc.setParent(null);
        //2、删除节点
        children.remove(cc);
        //3、通知变化
        onAmountChange();
    }
    /**
     * 返回根节点
     *
     * @return
     */
    private CommodityClassify getRoot() {
        CommodityClassify root = this;
        while (root.parent != null) {
            root = root.parent;
        }
        return root;
    }

    /**
     * 商品分类的数量变化时，重新计算
     */
    private void onAmountChange() {
        notifyParentChange();
        recountTotal();
    }

    /**
     * 通知双亲结点:数据已经改变
     */
    private void notifyParentChange() {
        //通知当前当前结点数据变化
        this.setNeedRecount(true);
        //通知双亲结点数据已经变化
        CommodityClassify parents = this.parent;
        while (parents != null) {
            parents.setNeedRecount(true);
            parents = parents.parent;
        }
    }

    /**
     * 重新计算 商品 总数
     */
    private void recountTotal() {
        this.getRoot().calcAmount();
    }


    //*************************  遍历 **************************

    /**
     * 广度优先遍历
     */
    public void breadthFirstTraversal(CommodityVisitor visitor) {
        Queue<CommodityClassify> queue = new LinkedList<CommodityClassify>();
        queue.add(this);
        while (!queue.isEmpty()) {
            CommodityClassify c = queue.poll();
            visitor.visit(c);
            queue.addAll(c.getChildren());
        }
    }

    /**
     * 返回层次遍历的的链表
     *
     * @return
     */
    public List<CommodityClassify> getBFTList() {
        List<CommodityClassify> list = new LinkedList<CommodityClassify>();
        int currentIndex = 0;
        list.add(this);
        while (currentIndex < list.size()) {
            if (!list.get(currentIndex).isLeafy()) {
                list.addAll(list.get(currentIndex).getChildren());    ///将子节点添加的list中
            }
            currentIndex++;
        }
        return list;
    }

    /**
     * 深度优先遍历 非递归算法   方向 ：从右到左
     */
    public void depthFirstTraversal(CommodityVisitor visitor) {
        Stack<CommodityClassify> stack = new Stack<CommodityClassify>();
        stack.push(this);
        while (!stack.isEmpty()) {
            CommodityClassify c = stack.pop();
            visitor.visit(c);
            if (!c.isLeafy()) {
                stack.addAll(c.getChildren());
            }
        }
    }

    //*************************  检索 **************************

    /**
     * 广度优先检索
     */
    public CommodityClassify breadthFirstSearch(CommoditySearcher searcher) {
        Queue<CommodityClassify> queue = new LinkedList<CommodityClassify>();
        queue.add(this);
        while (!queue.isEmpty()) {
            CommodityClassify c = queue.poll();
            if (searcher.search(c)) {
                return c;
            }
            queue.addAll(c.getChildren());
        }
        return null;
    }

    /**
     * 深度优先检索
     */
    public CommodityClassify depthFirstSearch(CommoditySearcher searcher) {
        Stack<CommodityClassify> stack = new Stack<CommodityClassify>();
        stack.push(this);
        while (!stack.isEmpty()) {
            CommodityClassify c = stack.pop();
            if (searcher.search(c)) {
                return c;
            }
            if (!c.isLeafy()) {
                stack.addAll(c.getChildren());
            }
        }
        return null;
    }


    //***************************  常见操作 函数*******************************
    /**
     * 添加子商品分类
     * @param name   分类名称
     * @param code   分类编码
     * @param amount 数量
     * @return
     */
    public CommodityClassify addChild(String name, String code, int amount) {
        CommodityClassify c = new CommodityClassify(name, code, amount);
        addChild(c);
        return c;
    }

    public CommodityClassify addChild(String name, String code) {
        CommodityClassify c = new CommodityClassify(name, code);
        addChild(c);
        return c;
    }

    public CommodityClassify getByCode(final String code) {
        CommoditySearcher vs = new CommoditySearcher() {
            public boolean search(CommodityClassify c) {
                return (c.getCode().equals(code));
            }
        };
        return depthFirstSearch(vs);
    }
    /**
     * 把 当前树 从 整棵树中 剥离出来；
     */
    public void remove() throws Exception {
        if (this.getParent() == null) throw new Exception("根节点不能删除");
        //1、找到双亲
        parent = this.getParent();
        //2、删除当前树
        parent.removeChild(this);
    }

    /**
     * 删除商品分类
     * @param cc
     * @throws Exception
     */
    public void remove(CommodityClassify cc) throws Exception {
        if (this.getParent() == null) throw new Exception("根节点不能删除");
        if (this.equals(cc)) throw new Exception("不能删除自身");
        if (!this.children.contains(cc)) throw new Exception("不包含子节点");
        removeChild(cc);
    }
    //************************  其他 ********************************************
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (obj.getClass() != this.getClass()) return false;
        CommodityClassify c = (CommodityClassify) obj;
        return c.getCode().equals(this.getCode());
    }

    public Object clone() throws CloneNotSupportedException {
        super.clone();
        CommodityClassify c = new CommodityClassify(name, code, amount);
        List<CommodityClassify> ccList = Collections.synchronizedList(new LinkedList<CommodityClassify>());
        for (CommodityClassify cc : children) {
            CommodityClassify newCC = (CommodityClassify) cc.clone();
            newCC.setParent(c);
            ccList.add(newCC);
        }

        c.setChildren(ccList);
        return c;
    }
}  

  

 

 

public interface CommoditySearcher {
    public boolean search(CommodityClassify c);
}

 

 

 

public interface CommodityVisitor {
    public void visit(CommodityClassify cc);
}