001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.editor;
022:
023: /**
024: * Switch is used to hold the lookup values and branch targets of a tableswitch
025: * or lookup switch instruction.
026: * <p>
027: * The tableswitch low-to-high range of values is represented by storing each
028: * lookup value in the range. This allows the tableswitch to be replaced with a
029: * lookupswitch if branches are deleted.
030: *
031: * @author Nate Nystrom (<a
032: * href="mailto:nystrom@cs.purdue.edu">nystrom@cs.purdue.edu</a>)
033: */
034: public class Switch {
035: private Label defaultTarget;
036:
037: private Label[] targets;
038:
039: private int[] values;
040:
041: /**
042: * Constructor.
043: *
044: * @param defaultTarget
045: * The default target of the switch.
046: * @param targets
047: * The non-default branch targets of the switch.
048: * @param values
049: * The lookup values of the switch. This array must be the same
050: * size as the targets array.
051: */
052: public Switch(final Label defaultTarget, final Label[] targets,
053: final int[] values) {
054: this .defaultTarget = defaultTarget;
055: this .targets = targets;
056: this .values = values;
057: sort();
058: uniq();
059: }
060:
061: /**
062: * Set the default target of the switch.
063: *
064: * @param target
065: * The default target of the switch.
066: */
067: public void setDefaultTarget(final Label target) {
068: defaultTarget = target;
069: }
070:
071: /**
072: * Get the default target of the switch.
073: *
074: * @return The default target of the switch.
075: */
076: public Label defaultTarget() {
077: return defaultTarget;
078: }
079:
080: /**
081: * Get the non-default branch targets of the switch. The targets are sorted
082: * by the corresponding lookup value.
083: *
084: * @return The non-default branch targets of the switch.
085: */
086: public Label[] targets() {
087: return targets;
088: }
089:
090: /**
091: * Get the lookup values of the switch, sorted low to high.
092: *
093: * @return The lookup values of the switch.
094: */
095: public int[] values() {
096: return values;
097: }
098:
099: /**
100: * Check if the all the values in the range of lookup values are contiguous.
101: * If they are, a table switch can be used. If not a lookupswitch can be
102: * used.
103: *
104: * @return true if contiguous, false if not.
105: */
106: public boolean hasContiguousValues() {
107: return values.length == highValue() - lowValue() + 1;
108: }
109:
110: /**
111: * Get the low value in the range the lookup values.
112: *
113: * @return The low value.
114: */
115: public int lowValue() {
116: return values[0];
117: }
118:
119: /**
120: * Get the high value in the range the lookup values.
121: *
122: * @return The high value.
123: */
124: public int highValue() {
125: return values[values.length - 1];
126: }
127:
128: /**
129: * Sort the targets and values arrays so that values is sorted low to high.
130: */
131: private void sort() {
132: quicksort(0, values.length - 1);
133: }
134:
135: /**
136: * Utility function to sort the targets and values arrays so that values is
137: * sorted low to high.
138: *
139: * @param p
140: * The low index of the portion of the array to sort.
141: * @param r
142: * The high index of the portion of the array to sort.
143: */
144: private void quicksort(final int p, final int r) {
145: if (p < r) {
146: final int q = partition(p, r);
147: quicksort(p, q);
148: quicksort(q + 1, r);
149: }
150: }
151:
152: /**
153: * Utility function to sort the targets and values arrays so that values is
154: * sorted low to high.
155: * <p>
156: * Partition the arrays so that the values less than values[p] are to the
157: * left.
158: *
159: * @param p
160: * The low index of the portion of the array to sort.
161: * @param r
162: * The high index of the portion of the array to sort.
163: * @return The index at which the partition finished.
164: */
165: private int partition(final int p, final int r) {
166: final int x = values[p];
167: int i = p - 1;
168: int j = r + 1;
169:
170: while (true) {
171: do {
172: j--;
173: } while (values[j] > x);
174:
175: do {
176: i++;
177: } while (values[i] < x);
178:
179: if (i < j) {
180: final int v = values[i];
181: values[i] = values[j];
182: values[j] = v;
183:
184: final Label t = targets[i];
185: targets[i] = targets[j];
186: targets[j] = t;
187: } else {
188: return j;
189: }
190: }
191: }
192:
193: /**
194: * Remove duplicates from the values and targets arrays.
195: */
196: private void uniq() {
197: if (values.length == 0) {
198: return;
199: }
200:
201: final int[] v = new int[values.length];
202: final Label[] t = new Label[values.length];
203:
204: v[0] = values[0];
205: t[0] = targets[0];
206:
207: int j = 1;
208:
209: for (int i = 1; i < values.length; i++) {
210: if (v[j - 1] != values[i]) {
211: v[j] = values[i];
212: t[j] = targets[i];
213: j++;
214: }
215: }
216:
217: values = new int[j];
218: System.arraycopy(v, 0, values, 0, j);
219:
220: targets = new Label[j];
221: System.arraycopy(t, 0, targets, 0, j);
222: }
223:
224: /**
225: * Convert the operand to a string.
226: *
227: * @return A string representation of the operand.
228: */
229: public String toString() {
230: return "" + values.length + " pairs";
231: }
232: }
|