1: /*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16: package com.jybat.dp;
17:
18: import java.util.SortedSet;
19: import java.util.TreeSet;
20:
21: public class BST { 22:
23: private int[] data = { 0, 1, 2, 3, 4 };// assume the n data items are 24: // the ints {0,1,..,n-1} 25: // corresponding to strings
26: // { "A", "B", "C", "D", 27: // "E"}
28: private double[] probability = { 0.25, 0.05, 0.2, 0.4, 0.1 }; 29:
30: private static SortedSet<Integer> setOfAllItems = new TreeSet<Integer>();
31:
32: public BST() { 33: for (int i = 0; i < data.length; i++)
34: setOfAllItems.add(data[i]);
35: }
36:
37: private double sumOfProbabilitiesOfItems(SortedSet items) { 38: double result = 0.0;
39: for (int i = ((Integer) items.first()).intValue(); i <= ((Integer) items
40: .last()).intValue(); i++) { 41: result += probability[i];
42: }
43: return result;
44: }
45:
46: private SortedSet setOfItemsLessThanPivot(SortedSet items, int alpha) { 47: // conveniently use method headSet() from SortedSet
48: // headSet() DOES NOT include alpha
49: return new TreeSet(items.headSet(new Integer(alpha)));
50: }
51:
52: private SortedSet setOfItemsGreaterThanPivot(SortedSet items, int alpha) { 53: // conveniently use method tailSet() from SortedSet
54: // headSet() DOES include alpha
55: SortedSet ss = new TreeSet(items.tailSet(new Integer(alpha)));
56: ss.remove(alpha);
57: return ss;
58: }
59:
60: public double f(SortedSet<Integer> items) { 61: if (items.size() == 0)
62: return 0.0;
63: double min = Double.MAX_VALUE;
64: for (int a : items) { 65: double t = sumOfProbabilitiesOfItems(items)
66: + f(setOfItemsLessThanPivot(items, a))
67: + f(setOfItemsGreaterThanPivot(items, a));
68: if (t < min)
69: min = t;
70: }
71: return min;
72: }
73:
74: /**
75: * @param args
76: */
77: public static void main(String[] args) { 78: BST bst = new BST();
79: System.out.println(bst.f(setOfAllItems));
80: }
81:
82: }