01: /*
02: *
03: *
04: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
05: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
06: *
07: * This program is free software; you can redistribute it and/or
08: * modify it under the terms of the GNU General Public License version
09: * 2 only, as published by the Free Software Foundation.
10: *
11: * This program is distributed in the hope that it will be useful, but
12: * WITHOUT ANY WARRANTY; without even the implied warranty of
13: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: * General Public License version 2 for more details (a copy is
15: * included at /legal/license.txt).
16: *
17: * You should have received a copy of the GNU General Public License
18: * version 2 along with this work; if not, write to the Free Software
19: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20: * 02110-1301 USA
21: *
22: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
23: * Clara, CA 95054 or visit www.sun.com if you need additional
24: * information or have any questions.
25: */
26:
27: package com.sun.kvem.midp.pim;
28:
29: import java.util.Vector;
30:
31: /**
32: * Class KeySortUtility contains static method "store" only.
33: * @see store
34: *
35: */
36: class KeySortUtility {
37:
38: /**
39: * Support method. Maintains a list, valueList, where each element in
40: * the list has a corresponding key (of type Long) stored in keyList.
41: * This method inserts "value" into "valueList" with the following
42: * postconditions:
43: * <ul>
44: * <li> keyList.size() == valueList.size()
45: * <li> keyList[i] corresponds to valueList[i] (0 <= i < keyList.size())
46: * <li> keyList is in ascending order of keys
47: * <li> keyList contains key
48: * <li> valueList contains value
49: * <li> key corresponds to value
50: * </ul>
51: * The following are preconditions:
52: * <ul>
53: * <li> keyList.size() == valueList.size()
54: * <li> keyList[i] corresponds to valueList[i] (0 <= i < keyList.size())
55: * <li> keyList is in ascending order of keys
56: * </ul>
57: * In order to maintain the arrays correctly, the objects passed as keyList
58: * and valueList should <i>only</i> be modified by this method.
59: * <p>Preconditions are not verified by this method.
60: * @param keyList array or property names
61: * @param valueList array of property values
62: * @param key identifier for this list
63: * @param value target object to store the list
64: */
65: static void store(Vector keyList, Vector valueList, long key,
66: Object value) {
67: // do a binary chop search for the index before which to
68: // insert value
69: int lowerBound = 0;
70: int upperBound = keyList.size();
71: while (lowerBound != upperBound) {
72: int index = lowerBound + (upperBound - lowerBound) / 2;
73: long indexKey = ((Long) keyList.elementAt(index))
74: .longValue();
75: if (indexKey > key) {
76: if (index == upperBound) {
77: upperBound--;
78: } else {
79: upperBound = index;
80: }
81: } else {
82: if (index == lowerBound) {
83: lowerBound++;
84: } else {
85: lowerBound = index;
86: }
87: }
88: }
89: keyList.insertElementAt(new Long(key), lowerBound);
90: valueList.insertElementAt(value, lowerBound);
91: }
92: }
|