1 /*
2 * ObjectLab, http://www.objectlab.co.uk/open is supporting JTreeMap.
3 *
4 * Based in London, we are world leaders in the design and development
5 * of bespoke applications for the securities financing markets.
6 *
7 * <a href="http://www.objectlab.co.uk/open">Click here to learn more</a>
8 * ___ _ _ _ _ _
9 * / _ \| |__ (_) ___ ___| |_| | __ _| |__
10 * | | | | '_ \| |/ _ \/ __| __| | / _` | '_ \
11 * | |_| | |_) | | __/ (__| |_| |__| (_| | |_) |
12 * \___/|_.__// |\___|\___|\__|_____\__,_|_.__/
13 * |__/
14 *
15 * www.ObjectLab.co.uk
16 *
17 * $Id: SplitBySortedWeight.java 75 2006-10-24 23:00:51Z benoitx $
18 *
19 * Copyright 2006 the original author or authors.
20 *
21 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
22 * use this file except in compliance with the License. You may obtain a copy of
23 * the License at
24 *
25 * http://www.apache.org/licenses/LICENSE-2.0
26 *
27 * Unless required by applicable law or agreed to in writing, software
28 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
29 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
30 * License for the specific language governing permissions and limitations under
31 * the License.
32 */
33 package net.sf.jtreemap.ktreemap;
34
35 import java.util.ArrayList;
36 import java.util.Iterator;
37 import java.util.List;
38
39 /**
40 * Strategy who split the elements in 2 groups of equivalent weight.
41 * <p>
42 * The elements are first sorted by descending weight. Then they are splitted in
43 * 2 groups of equivalent weight.
44 * <p>
45 * The heaviest elements are on the top left of the KTreeMap. The lightest
46 * elements are on the bottom right of the KTreeMap
47 *
48 * @author Laurent Dutheil
49 */
50
51 public class SplitBySortedWeight extends SplitStrategy {
52
53 @Override
54 public void splitElements(List<TreeMapNode> list, List<TreeMapNode> group1,
55 List<TreeMapNode> group2) {
56 List<TreeMapNode> listClone = new ArrayList<TreeMapNode>(list);
57 double memWeight = 0.0;
58 double sumWeight = sumWeight(list);
59 double elemWeight = 0.0;
60
61 sortList(listClone);
62
63 for (Iterator<TreeMapNode> i = listClone.iterator(); i.hasNext();) {
64 TreeMapNode tmn = i.next();
65 elemWeight = tmn.getWeight();
66 // if adding the current element pass the middle of total weight
67 if (memWeight + elemWeight >= sumWeight / 2) {
68 // we look at the finest split (the nearest of the middle of weight)
69 if (((sumWeight / 2) - memWeight) > ((memWeight + elemWeight) - (sumWeight / 2))) {
70 // if it is after the add, we add the element to the first Vector
71 memWeight += elemWeight;
72 group1.add(tmn);
73 } else {
74 // we must have at least 1 element in the first vector
75 if (group1.isEmpty()) {
76 group1.add(tmn);
77 } else {
78 // if it is before the add, we add the element to the second Vector
79 group2.add(tmn);
80 }
81 }
82 // then we fill the second Vector qith the rest of elements
83 while (i.hasNext()) {
84 tmn = i.next();
85 group2.add(tmn);
86 }
87 } else {
88 // we add in the first vector while we don't reach the middle of weight
89 memWeight += elemWeight;
90 group1.add(tmn);
91 }
92 }
93 }
94 }
95 /*
96 * ObjectLab is supporing JTreeMap
97 *
98 * Based in London, we are world leaders in the design and development
99 * of bespoke applications for the securities financing markets.
100 *
101 * <a href="http://www.objectlab.co.uk/open">Click here to learn more about us</a>
102 * ___ _ _ _ _ _
103 * / _ \| |__ (_) ___ ___| |_| | __ _| |__
104 * | | | | '_ \| |/ _ \/ __| __| | / _` | '_ \
105 * | |_| | |_) | | __/ (__| |_| |__| (_| | |_) |
106 * \___/|_.__// |\___|\___|\__|_____\__,_|_.__/
107 * |__/
108 *
109 * www.ObjectLab.co.uk
110 */