1. /*
  2. * @(#)SizeSequence.java 1.13 03/01/23
  3. *
  4. * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package javax.swing;
  8. /**
  9. * A <code>SizeSequence</code> object
  10. * efficiently maintains an ordered list
  11. * of sizes and corresponding positions.
  12. * One situation for which <code>SizeSequence</code>
  13. * might be appropriate is in a component
  14. * that displays multiple rows of unequal size.
  15. * In this case, a single <code>SizeSequence</code>
  16. * object could be used to track the heights
  17. * and Y positions of all rows.
  18. * <p>
  19. * Another example would be a multi-column component,
  20. * such as a <code>JTable</code>,
  21. * in which the column sizes are not all equal.
  22. * The <code>JTable</code> might use a single
  23. * <code>SizeSequence</code> object
  24. * to store the widths and X positions of all the columns.
  25. * The <code>JTable</code> could then use the
  26. * <code>SizeSequence</code> object
  27. * to find the column corresponding to a certain position.
  28. * The <code>JTable</code> could update the
  29. * <code>SizeSequence</code> object
  30. * whenever one or more column sizes changed.
  31. *
  32. * <p>
  33. * The following figure shows the relationship between size and position data
  34. * for a multi-column component.
  35. * <p>
  36. * <center>
  37. * <img src="doc-files/SizeSequence-1.gif" width=384 height = 100
  38. * alt="The first item begins at position 0, the second at the position equal
  39. to the size of the previous item, and so on.">
  40. * </center>
  41. * <p>
  42. * In the figure, the first index (0) corresponds to the first column,
  43. * the second index (1) to the second column, and so on.
  44. * The first column's position starts at 0,
  45. * and the column occupies <em>size<sub>0</sub></em> pixels,
  46. * where <em>size<sub>0</sub></em> is the value returned by
  47. * <code>getSize(0)</code>.
  48. * Thus, the first column ends at <em>size<sub>0</sub></em> - 1.
  49. * The second column then begins at
  50. * the position <em>size<sub>0</sub></em>
  51. * and occupies <em>size<sub>1</sub></em> (<code>getSize(1)</code>) pixels.
  52. * <p>
  53. * Note that a <code>SizeSequence</code> object simply represents intervals
  54. * along an axis.
  55. * In our examples, the intervals represent height or width in pixels.
  56. * However, any other unit of measure (for example, time in days)
  57. * could be just as valid.
  58. *
  59. * <p>
  60. *
  61. * <h4>Implementation Notes</h4>
  62. *
  63. * Normally when storing the size and position of entries,
  64. * one would choose between
  65. * storing the sizes or storing their positions
  66. * instead. The two common operations that are needed during
  67. * rendering are: <code>getIndex(position)</code>
  68. * and <code>setSize(index, size)</code>.
  69. * Whichever choice of internal format is made one of these
  70. * operations is costly when the number of entries becomes large.
  71. * If sizes are stored, finding the index of the entry
  72. * that encloses a particular position is linear in the
  73. * number of entries. If positions are stored instead, setting
  74. * the size of an entry at a particular index requires updating
  75. * the positions of the affected entries, which is also a linear
  76. * calculation.
  77. * <p>
  78. * Like the above techniques this class holds an array of N integers
  79. * internally but uses a hybrid encoding, which is halfway
  80. * between the size-based and positional-based approaches.
  81. * The result is a data structure that takes the same space to store
  82. * the information but can perform most operations in Log(N) time
  83. * instead of O(N), where N is the number of entries in the list.
  84. * <p>
  85. * Two operations that remain O(N) in the number of entries are
  86. * the <code>insertEntries</code>
  87. * and <code>removeEntries</code> methods, both
  88. * of which are implemented by converting the internal array to
  89. * a set of integer sizes, copying it into the new array, and then
  90. * reforming the hybrid representation in place.
  91. *
  92. * @version 1.13 01/23/03
  93. * @author Philip Milne
  94. */
  95. /*
  96. * Each method is implemented by taking the minimum and
  97. * maximum of the range of integers that need to be operated
  98. * upon. All the algorithms work by dividing this range
  99. * into two smaller ranges and recursing. The recursion
  100. * is terminated when the upper and lower bounds are equal.
  101. */
  102. public class SizeSequence {
  103. private static int[] emptyArray = new int[0];
  104. private int a[];
  105. /**
  106. * Creates a new <code>SizeSequence</code> object
  107. * that contains no entries. To add entries, you
  108. * can use <code>insertEntries</code> or <code>setSizes</code>.
  109. *
  110. * @see #insertEntries
  111. * @see #setSizes
  112. */
  113. public SizeSequence() {
  114. a = emptyArray;
  115. }
  116. /**
  117. * Creates a new <code>SizeSequence</code> object
  118. * that contains the specified number of entries,
  119. * all initialized to have size 0.
  120. *
  121. * @param numEntries the number of sizes to track
  122. * @exception NegativeArraySizeException if
  123. * <code>numEntries < 0</code>
  124. */
  125. public SizeSequence(int numEntries) {
  126. this(numEntries, 0);
  127. }
  128. /**
  129. * Creates a new <code>SizeSequence</code> object
  130. * that contains the specified number of entries,
  131. * all initialized to have size <code>value</code>.
  132. *
  133. * @param numEntries the number of sizes to track
  134. * @param value the initial value of each size
  135. */
  136. public SizeSequence(int numEntries, int value) {
  137. this();
  138. insertEntries(0, numEntries, value);
  139. }
  140. /**
  141. * Creates a new <code>SizeSequence</code> object
  142. * that contains the specified sizes.
  143. *
  144. * @param sizes the array of sizes to be contained in
  145. * the <code>SizeSequence</code>
  146. */
  147. public SizeSequence(int[] sizes) {
  148. this();
  149. setSizes(sizes);
  150. }
  151. /**
  152. * Resets this <code>SizeSequence</code> object,
  153. * using the data in the <code>sizes</code> argument.
  154. * This method reinitializes this object so that it
  155. * contains as many entries as the <code>sizes</code> array.
  156. * Each entry's size is initialized to the value of the
  157. * corresponding item in <code>sizes</code>.
  158. *
  159. * @param sizes the array of sizes to be contained in
  160. * this <code>SizeSequence</code>
  161. */
  162. public void setSizes(int[] sizes) {
  163. if (a.length != sizes.length) {
  164. a = new int[sizes.length];
  165. }
  166. setSizes(0, a.length, sizes);
  167. }
  168. private int setSizes(int from, int to, int[] sizes) {
  169. if (to <= from) {
  170. return 0;
  171. }
  172. int m = (from + to)/2;
  173. a[m] = sizes[m] + setSizes(from, m, sizes);
  174. return a[m] + setSizes(m + 1, to, sizes);
  175. }
  176. /**
  177. * Returns the size of all entries.
  178. *
  179. * @return a new array containing the sizes in this object
  180. */
  181. public int[] getSizes() {
  182. int n = a.length;
  183. int[] sizes = new int[n];
  184. getSizes(0, n, sizes);
  185. return sizes;
  186. }
  187. private int getSizes(int from, int to, int[] sizes) {
  188. if (to <= from) {
  189. return 0;
  190. }
  191. int m = (from + to)/2;
  192. sizes[m] = a[m] - getSizes(from, m, sizes);
  193. return a[m] + getSizes(m + 1, to, sizes);
  194. }
  195. /**
  196. * Returns the start position for the specified entry.
  197. * For example, <code>getPosition(0)</code> returns 0,
  198. * <code>getPosition(1)</code> is equal to
  199. * <code>getSize(0)</code>,
  200. * <code>getPosition(2)</code> is equal to
  201. * <code>getSize(0)</code> + <code>getSize(1)</code>,
  202. * and so on.
  203. * <p>Note that if <code>index</code> is greater than
  204. * <code>length</code> the value returned may
  205. * be meaningless.
  206. *
  207. * @param index the index of the entry whose position is desired
  208. * @return the starting position of the specified entry
  209. */
  210. public int getPosition(int index) {
  211. return getPosition(0, a.length, index);
  212. }
  213. private int getPosition(int from, int to, int index) {
  214. if (to <= from) {
  215. return 0;
  216. }
  217. int m = (from + to)/2;
  218. if (index <= m) {
  219. return getPosition(from, m, index);
  220. }
  221. else {
  222. return a[m] + getPosition(m + 1, to, index);
  223. }
  224. }
  225. /**
  226. * Returns the index of the entry
  227. * that corresponds to the specified position.
  228. * For example, <code>getIndex(0)</code> is 0,
  229. * since the first entry always starts at position 0.
  230. *
  231. * @param position the position of the entry
  232. * @return the index of the entry that occupies the specified position
  233. */
  234. public int getIndex(int position) {
  235. return getIndex(0, a.length, position);
  236. }
  237. private int getIndex(int from, int to, int position) {
  238. if (to <= from) {
  239. return from;
  240. }
  241. int m = (from + to)/2;
  242. int pivot = a[m];
  243. if (position < pivot) {
  244. return getIndex(from, m, position);
  245. }
  246. else {
  247. return getIndex(m + 1, to, position - pivot);
  248. }
  249. }
  250. /**
  251. * Returns the size of the specified entry.
  252. * If <code>index</code> is out of the range
  253. * <code>(0 <= index < getSizes().length)</code>
  254. * the behavior is unspecified.
  255. *
  256. * @param index the index corresponding to the entry
  257. * @return the size of the entry
  258. */
  259. public int getSize(int index) {
  260. return getPosition(index + 1) - getPosition(index);
  261. }
  262. /**
  263. * Sets the size of the specified entry.
  264. * Note that if the value of <code>index</code>
  265. * does not fall in the range:
  266. * <code>(0 <= index < getSizes().length)</code>
  267. * the behavior is unspecified.
  268. *
  269. * @param index the index corresponding to the entry
  270. * @param size the size of the entry
  271. */
  272. public void setSize(int index, int size) {
  273. changeSize(0, a.length, index, size - getSize(index));
  274. }
  275. private void changeSize(int from, int to, int index, int delta) {
  276. if (to <= from) {
  277. return;
  278. }
  279. int m = (from + to)/2;
  280. if (index <= m) {
  281. a[m] += delta;
  282. changeSize(from, m, index, delta);
  283. }
  284. else {
  285. changeSize(m + 1, to, index, delta);
  286. }
  287. }
  288. /**
  289. * Adds a contiguous group of entries to this <code>SizeSequence</code>.
  290. * Note that the values of <code>start</code> and
  291. * <code>length</code> must satisfy the following
  292. * conditions: <code>(0 <= start < getSizes().length)
  293. * AND (length >= 0)</code>. If these conditions are
  294. * not met, the behavior is unspecified and an exception
  295. * may be thrown.
  296. *
  297. * @param start the index to be assigned to the first entry
  298. * in the group
  299. * @param length the number of entries in the group
  300. * @param value the size to be assigned to each new entry
  301. * @exception ArrayIndexOutOfBoundsException if the parameters
  302. * are outside of the range:
  303. * (<code>0 <= start < (getSizes().length)) AND (length >= 0)</code>
  304. */
  305. public void insertEntries(int start, int length, int value) {
  306. int sizes[] = getSizes();
  307. int end = start + length;
  308. int n = a.length + length;
  309. a = new int[n];
  310. for (int i = 0; i < start; i++) {
  311. a[i] = sizes[i] ;
  312. }
  313. for (int i = start; i < end; i++) {
  314. a[i] = value ;
  315. }
  316. for (int i = end; i < n; i++) {
  317. a[i] = sizes[i-length] ;
  318. }
  319. setSizes(a);
  320. }
  321. /**
  322. * Removes a contiguous group of entries
  323. * from this <code>SizeSequence</code>.
  324. * Note that the values of <code>start</code> and
  325. * <code>length</code> must satisfy the following
  326. * conditions: <code>(0 <= start < getSizes().length)
  327. * AND (length >= 0)</code>. If these conditions are
  328. * not met, the behavior is unspecified and an exception
  329. * may be thrown.
  330. *
  331. * @param start the index of the first entry to be removed
  332. * @param length the number of entries to be removed
  333. */
  334. public void removeEntries(int start, int length) {
  335. int sizes[] = getSizes();
  336. int end = start + length;
  337. int n = a.length - length;
  338. a = new int[n];
  339. for (int i = 0; i < start; i++) {
  340. a[i] = sizes[i] ;
  341. }
  342. for (int i = start; i < n; i++) {
  343. a[i] = sizes[i+length] ;
  344. }
  345. setSizes(a);
  346. }
  347. }