001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: /**
019: * @author Dennis Ushakov
020: * @version $Revision$
021: */package javax.swing;
022:
023: public class SizeSequence {
024: private int[] tree;
025: private int sizesCount;
026:
027: public SizeSequence() {
028: this (new int[0]);
029: }
030:
031: public SizeSequence(final int numEntries) {
032: this (numEntries, 0);
033: }
034:
035: public SizeSequence(final int numEntries, final int value) {
036: int[] sizes = new int[numEntries];
037: for (int i = 0; i < numEntries; i++) {
038: sizes[i] = value;
039: }
040: setSizes(sizes);
041: }
042:
043: public SizeSequence(final int[] sizes) {
044: setSizes(sizes);
045: }
046:
047: public void setSizes(final int[] sizes) {
048: if (sizes.length == 0) {
049: tree = new int[0];
050: sizesCount = 0;
051: return;
052: }
053: int upper = 1;
054: while (upper - 1 < sizes.length) {
055: upper <<= 1;
056: }
057: tree = new int[upper - 1];
058: sizesCount = sizes.length;
059: setSizesImpl(sizes, 0, upper - 1, 0);
060: }
061:
062: public int[] getSizes() {
063: if (sizesCount == 0) {
064: return new int[0];
065: }
066: int[] allSizes = new int[tree.length];
067: getSizesImpl(allSizes, 0, tree.length - 1);
068: int[] result = new int[sizesCount];
069: System.arraycopy(allSizes, 0, result, 0, sizesCount);
070: return result;
071: }
072:
073: public int getPosition(final int index) {
074: if (index < 0 || sizesCount == 0) {
075: return 0;
076: }
077: if (index >= sizesCount) {
078: return tree[(tree.length - 1) / 2];
079: }
080: int position = 0;
081: int left = 0;
082: int right = tree.length - 1;
083: int cur = (left + right) / 2;
084:
085: do {
086: if (cur > index) {
087: right = cur - 1;
088: } else if (cur < index) {
089: position += tree[cur];
090: position -= (right + cur + 1) / 2 == cur ? 0
091: : tree[(right + cur + 1) / 2];
092: left = cur + 1;
093: }
094: cur = (left + right) / 2;
095: } while (cur != index);
096: position += (cur + left) / 2 == cur ? 0
097: : tree[(cur + left) / 2];
098: return position;
099: }
100:
101: public int getIndex(final int position) {
102: if (position < 0 || sizesCount == 0) {
103: return 0;
104: }
105: if (position >= tree[(tree.length - 1) / 2]) {
106: return sizesCount;
107: }
108:
109: int pos = position;
110: int left = 0;
111: int right = tree.length - 1;
112: int cur = (left + right) / 2;
113:
114: while (left != right) {
115: if (pos - tree[(cur + left) / 2] < 0) {
116: right = cur - 1;
117: } else {
118: pos -= tree[(cur + left) / 2];
119: int size = tree[cur];
120: size -= (right + cur + 1) / 2 == cur ? 0 : tree[(right
121: + cur + 1) / 2];
122: size -= (cur + left) / 2 == cur ? 0
123: : tree[(cur + left) / 2];
124: if (pos < size) {
125: return cur < sizesCount ? cur : sizesCount;
126: } else {
127: pos -= size;
128: left = cur + 1;
129: }
130: }
131: cur = (left + right) / 2;
132: }
133: return cur < sizesCount ? cur : sizesCount;
134: }
135:
136: public int getSize(final int index) {
137: if (!isValidIndex(index)) {
138: return 0;
139: }
140: int result = tree[index];
141: int left = 0;
142: int right = tree.length - 1;
143: int cur = (left + right) / 2;
144: while (cur != index) {
145: if (cur < index) {
146: left = cur + 1;
147: }
148: if (cur > index) {
149: right = cur - 1;
150: }
151: cur = (left + right) / 2;
152: }
153: result -= (right + cur + 1) / 2 == cur ? 0
154: : tree[(right + cur + 1) / 2];
155: result -= (cur + left) / 2 == cur ? 0 : tree[(cur + left) / 2];
156: return result;
157: }
158:
159: public void setSize(final int index, final int size) {
160: if (!isValidIndex(index)) {
161: return;
162: }
163: int delta = size - getSize(index);
164: int left = 0;
165: int right = tree.length - 1;
166: int cur = (left + right) / 2;
167: tree[cur] += delta;
168: while (cur != index) {
169: if (cur < index) {
170: left = cur + 1;
171: }
172: if (cur > index) {
173: right = cur - 1;
174: }
175: cur = (left + right) / 2;
176: tree[cur] += delta;
177: }
178: }
179:
180: public void insertEntries(final int start, final int length,
181: final int value) {
182: int[] newSizes = new int[sizesCount + length];
183: int[] sizes = getSizes();
184: System.arraycopy(sizes, 0, newSizes, 0, start);
185: for (int i = start; i < start + length; i++) {
186: newSizes[i] = value;
187: }
188: System.arraycopy(sizes, start, newSizes, start + length,
189: sizes.length - start);
190: setSizes(newSizes);
191: }
192:
193: public void removeEntries(final int start, final int length) {
194: int[] newSizes = new int[sizesCount - length];
195: int[] sizes = getSizes();
196: System.arraycopy(sizes, 0, newSizes, 0, start);
197: System.arraycopy(sizes, start + length, newSizes, start,
198: sizes.length - start - length);
199: setSizes(newSizes);
200: }
201:
202: private boolean isValidIndex(final int index) {
203: return (index >= 0 && index < sizesCount);
204: }
205:
206: private int setSizesImpl(final int[] sizes, final int left,
207: final int right, final int depth) {
208: int cur = (right + left) / 2;
209: int size = (cur < sizes.length) ? sizes[cur] : 0;
210: if ((right - left) / 2 > 0) {
211: tree[cur] = size
212: + setSizesImpl(sizes, left, cur - 1, depth + 1)
213: + setSizesImpl(sizes, cur + 1, right, depth + 1);
214: } else if ((right - left) / 2 == 0) {
215: tree[cur] = size;
216: } else {
217: return 0;
218: }
219: return tree[cur];
220: }
221:
222: private int getSizesImpl(final int[] sizes, final int left,
223: final int right) {
224: int cur = (right + left) / 2;
225: int length = tree[cur];
226: if ((right - left) / 2 > 0) {
227: sizes[cur] = length - getSizesImpl(sizes, left, cur - 1)
228: - getSizesImpl(sizes, cur + 1, right);
229: } else if ((right - left) / 2 == 0) {
230: sizes[cur] = length;
231: }
232: return (right - left) / 2 < 0 ? 0 : length;
233: }
234: }
|