001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2003 Søren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package bak.pcj.list;
020:
021: import bak.pcj.CharIterator;
022: import bak.pcj.CharCollection;
023: import bak.pcj.hash.DefaultCharHashFunction;
024: import bak.pcj.util.Exceptions;
025:
026: import java.io.Serializable;
027: import java.io.IOException;
028: import java.io.ObjectInputStream;
029: import java.io.ObjectOutputStream;
030:
031: /**
032: * This class represents an array implementaion of deques of
033: * char values.
034: *
035: * @see java.util.LinkedList
036: *
037: * @author Søren Bak
038: * @version 1.3 21-08-2003 19:25
039: * @since 1.0
040: */
041: public class CharArrayDeque extends AbstractCharList implements
042: CharDeque, Cloneable, Serializable {
043:
044: /** Constant indicating relative growth policy. */
045: private static final int GROWTH_POLICY_RELATIVE = 0;
046:
047: /** Constant indicating absolute growth policy. */
048: private static final int GROWTH_POLICY_ABSOLUTE = 1;
049:
050: /**
051: * The default growth policy of this deque.
052: * @see #GROWTH_POLICY_RELATIVE
053: * @see #GROWTH_POLICY_ABSOLUTE
054: */
055: private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
056:
057: /** The default factor with which to increase the capacity of this deque. */
058: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
059:
060: /** The default chunk size with which to increase the capacity of this deque. */
061: public static final int DEFAULT_GROWTH_CHUNK = 10;
062:
063: /** The default capacity of this deque. */
064: public static final int DEFAULT_CAPACITY = 10;
065:
066: /** The elements of this deque (indices <tt>0</tt> to <tt>size-1</tt>). */
067: private transient char[] data;
068:
069: /**
070: * The current size of this deque.
071: * @serial
072: */
073: private int size;
074:
075: /** The index of the first element in this deque. */
076: private transient int first;
077:
078: /** The index of the last element in this deque. */
079: private transient int last;
080:
081: /**
082: * The growth policy of this deque (0 is relative growth, 1 is absolute growth).
083: * @serial
084: */
085: private int growthPolicy;
086:
087: /**
088: * The growth factor of this deque, if the growth policy is
089: * relative.
090: * @serial
091: */
092: private double growthFactor;
093:
094: /**
095: * The growth chunk size of this deque, if the growth policy is
096: * absolute.
097: * @serial
098: */
099: private int growthChunk;
100:
101: private CharArrayDeque(int capacity, int growthPolicy,
102: double growthFactor, int growthChunk) {
103: if (capacity < 0)
104: Exceptions.negativeArgument("capacity", String
105: .valueOf(capacity));
106: if (growthFactor < 0.0)
107: Exceptions.negativeArgument("growthFactor", String
108: .valueOf(growthFactor));
109: if (growthChunk < 0)
110: Exceptions.negativeArgument("growthChunk", String
111: .valueOf(growthChunk));
112: data = new char[capacity];
113: size = 0;
114: this .growthPolicy = growthPolicy;
115: this .growthFactor = growthFactor;
116: this .growthChunk = growthChunk;
117: this .first = 0;
118: this .last = 0;
119: }
120:
121: /**
122: * Creates a new array deque with capacity 10 and a relative
123: * growth factor of 1.0.
124: *
125: * @see #CharArrayDeque(int,double)
126: */
127: public CharArrayDeque() {
128: this (DEFAULT_CAPACITY);
129: }
130:
131: /**
132: * Creates a new array deque with the same elements as a
133: * specified collection. The elements of the specified collection
134: * are added to the end of the deque in the collection's iteration
135: * order.
136: *
137: * @param c
138: * the collection whose elements to add to the new
139: * deque.
140: *
141: * @throws NullPointerException
142: * if <tt>c</tt> is <tt>null</tt>.
143: */
144: public CharArrayDeque(CharCollection c) {
145: this (c.size());
146: addAll(c);
147: }
148:
149: /**
150: * Creates a new array deque with the same elements as a
151: * specified array. The elements of the specified array
152: * are added the end of the deque in the order in which they
153: * appear in the array.
154: *
155: * @param a
156: * the array whose elements to add to the new
157: * deque.
158: *
159: * @throws NullPointerException
160: * if <tt>a</tt> is <tt>null</tt>.
161: *
162: * @since 1.1
163: */
164: public CharArrayDeque(char[] a) {
165: this (a.length);
166: System.arraycopy(a, 0, data, 0, a.length);
167: size = a.length;
168: first = 0;
169: last = a.length - 1;
170: }
171:
172: /**
173: * Creates a new array deque with a specified capacity and a
174: * relative growth factor of 1.0.
175: *
176: * @param capacity
177: * the initial capacity of the deque.
178: *
179: * @see #CharArrayDeque(int,double)
180: *
181: * @throws IllegalArgumentException
182: * if <tt>capacity</tt> is negative.
183: */
184: public CharArrayDeque(int capacity) {
185: this (capacity, DEFAULT_GROWTH_FACTOR);
186: }
187:
188: /**
189: * Creates a new array deque with a specified capacity and
190: * relative growth factor.
191: *
192: * <p>The array capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
193: * This strategy is good for avoiding many capacity increases, but
194: * the amount of wasted memory is approximately the size of the deque.
195: *
196: * @param capacity
197: * the initial capacity of the deque.
198: *
199: * @param growthFactor
200: * the relative amount with which to increase the
201: * the capacity when a capacity increase is needed.
202: *
203: * @throws IllegalArgumentException
204: * if <tt>capacity</tt> is negative;
205: * if <tt>growthFactor</tt> is negative.
206: */
207: public CharArrayDeque(int capacity, double growthFactor) {
208: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
209: DEFAULT_GROWTH_CHUNK);
210: }
211:
212: /**
213: * Creates a new array deque with a specified capacity and
214: * absolute growth factor.
215: *
216: * <p>The array capacity increases to <tt>capacity()+growthChunk</tt>.
217: * This strategy is good for avoiding wasting memory. However, an
218: * overhead is potentially introduced by frequent capacity increases.
219: *
220: * @param capacity
221: * the initial capacity of the deque.
222: *
223: * @param growthChunk
224: * the absolute amount with which to increase the
225: * the capacity when a capacity increase is needed.
226: *
227: * @throws IllegalArgumentException
228: * if <tt>capacity</tt> is negative;
229: * if <tt>growthChunk</tt> is negative.
230: */
231: public CharArrayDeque(int capacity, int growthChunk) {
232: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
233: growthChunk);
234: }
235:
236: // ---------------------------------------------------------------
237: // Array management
238: // ---------------------------------------------------------------
239:
240: /**
241: * Computes the new capacity of the deque based on a needed
242: * capacity and the growth policy.
243: *
244: * @param capacity
245: * the needed capacity of the deque.
246: *
247: * @return the new capacity of the deque.
248: */
249: private int computeCapacity(int capacity) {
250: int newcapacity;
251: if (growthPolicy == GROWTH_POLICY_RELATIVE)
252: newcapacity = (int) (data.length * (1.0 + growthFactor));
253: else
254: newcapacity = data.length + growthChunk;
255: if (newcapacity < capacity)
256: newcapacity = capacity;
257: return newcapacity;
258: }
259:
260: /**
261: * Ensures that this deque has at least a specified capacity.
262: * The actual capacity is calculated from the growth factor
263: * or growth chunk specified to the constructor.
264: *
265: * @param capacity
266: * the minimum capacity of this deque.
267: *
268: * @return the new capacity of this deque.
269: *
270: * @see #capacity()
271: */
272: public int ensureCapacity(int capacity) {
273: if (capacity > data.length) {
274: char[] newdata = new char[capacity = computeCapacity(capacity)];
275: toArray(newdata);
276: first = 0;
277: last = size;
278: data = newdata;
279: }
280: return capacity;
281: }
282:
283: /**
284: * Returns the current capacity of this deque. The capacity is the
285: * number of elements that the deque can contain without having to
286: * increase the amount of memory used.
287: *
288: * @return the current capacity of this deque.
289: *
290: * @see #ensureCapacity(int)
291: */
292: public int capacity() {
293: return data.length;
294: }
295:
296: // ---------------------------------------------------------------
297: // Operations not supported by abstract list implementation
298: // ---------------------------------------------------------------
299:
300: public void add(int index, char v) {
301: if (index == 0)
302: addFirst(v);
303: else if (index == size)
304: addLast(v);
305: else {
306: if (index < 0 || index > size)
307: Exceptions.indexOutOfBounds(index, 0, size);
308: ensureCapacity(size + 1);
309: if (first < last || last == 0) { // data is in one block
310: int iidx = index + first;
311: int end = last == 0 ? data.length : last;
312: int block = end - iidx;
313: if (last == 0) { // wrap one element around end
314: data[0] = data[data.length - 1];
315: System.arraycopy(data, iidx, data, iidx + 1,
316: block - 1);
317: last = 1;
318: } else {
319: System.arraycopy(data, iidx, data, iidx + 1, block);
320: if (++last == data.length)
321: last = 0;
322: }
323: data[iidx] = v;
324: } else { // data is split
325: int iidx = (first + index) % data.length;
326: if (iidx <= last) { // element is in left block
327: int block = last - iidx;
328: System.arraycopy(data, iidx, data, iidx + 1, block);
329: last++;
330: data[iidx] = v;
331: } else { // element is in right block
332: int block = iidx - first;
333: System.arraycopy(data, first, data, first - 1,
334: block);
335: first--;
336: data[iidx - 1] = v;
337: }
338: }
339: size++;
340: }
341: }
342:
343: public char get(int index) {
344: if (index < 0 || index >= size)
345: Exceptions.indexOutOfBounds(index, 0, size - 1);
346: return data[(first + index) % data.length];
347: }
348:
349: public char set(int index, char v) {
350: if (index < 0 || index >= size)
351: Exceptions.indexOutOfBounds(index, 0, size - 1);
352: int idx = (first + index) % data.length;
353: char result = data[idx];
354: data[idx] = v;
355: return result;
356: }
357:
358: public char removeElementAt(int index) {
359: char result;
360: if (index == 0)
361: result = removeFirst();
362: else if (index == size - 1)
363: result = removeLast();
364: else {
365: if (index < 0 || index >= size)
366: Exceptions.indexOutOfBounds(index, 0, size - 1);
367: int ridx = (first + index) % data.length;
368: result = data[ridx];
369: if (first < last || last == 0) { // data is in one block
370: // move the shorter block
371: int block1 = ridx - first;
372: int block2 = size - block1 - 1;
373: if (block1 < block2) { // move first block
374: System.arraycopy(data, first, data, first + 1,
375: block1);
376: first++;
377: } else { // move last block
378: System
379: .arraycopy(data, ridx + 1, data, ridx,
380: block2);
381: if (--last < 0)
382: last = data.length - 1;
383: }
384: } else { // data is split
385: if (ridx < last) { // element is in left block
386: int block = last - ridx - 1;
387: System.arraycopy(data, ridx + 1, data, ridx, block);
388: last--;
389: } else { // element is in right block
390: int block = ridx - first;
391: System.arraycopy(data, first, data, first + 1,
392: block);
393: if (++first == data.length)
394: first = 0;
395: }
396: }
397: size--;
398: }
399: return result;
400: }
401:
402: /**
403: * Minimizes the memory used by this array deque. The underlying
404: * array is replaced by an array whose size is exactly the number
405: * of elements in this array deque. The method can be used to
406: * free up memory after many removals.
407: */
408: public void trimToSize() {
409: if (data.length > size) {
410: char[] newdata = toArray();
411: first = 0;
412: last = 0;
413: data = newdata;
414: }
415: }
416:
417: /**
418: * Returns a clone of this array deque.
419: *
420: * @return a clone of this array deque.
421: *
422: * @since 1.1
423: */
424: public Object clone() {
425: try {
426: CharArrayDeque c = (CharArrayDeque) super .clone();
427: c.data = new char[data.length];
428: // This could be improved to only copying the blocks in use.
429: System.arraycopy(data, 0, c.data, 0, data.length);
430: return c;
431: } catch (CloneNotSupportedException e) {
432: Exceptions.cloning();
433: return null;
434: }
435: }
436:
437: // ---------------------------------------------------------------
438: // Operations declared by CharDeque
439: // ---------------------------------------------------------------
440:
441: public char getFirst() {
442: if (size == 0)
443: Exceptions.dequeNoFirst();
444: return data[first];
445: }
446:
447: public char getLast() {
448: if (size == 0)
449: Exceptions.dequeNoLast();
450: return data[last == 0 ? data.length - 1 : last - 1];
451: }
452:
453: public void addFirst(char v) {
454: ensureCapacity(size + 1);
455: if (--first < 0)
456: first = data.length - 1;
457: data[first] = v;
458: size++;
459: }
460:
461: public void addLast(char v) {
462: ensureCapacity(size + 1);
463: data[last] = v;
464: if (++last == data.length)
465: last = 0;
466: size++;
467: }
468:
469: public char removeFirst() {
470: if (size == 0)
471: Exceptions.dequeNoFirstToRemove();
472: char result = data[first];
473: if (++first == data.length)
474: first = 0;
475: size--;
476: return result;
477: }
478:
479: public char removeLast() {
480: if (size == 0)
481: Exceptions.dequeNoLastToRemove();
482: if (--last < 0)
483: last = data.length - 1;
484: size--;
485: return data[last];
486: }
487:
488: // ---------------------------------------------------------------
489: // Operations overwritten for efficiency
490: // ---------------------------------------------------------------
491:
492: public int size() {
493: return size;
494: }
495:
496: public boolean isEmpty() {
497: return size == 0;
498: }
499:
500: public void clear() {
501: size = 0;
502: first = 0;
503: last = 0;
504: }
505:
506: public boolean contains(char v) {
507: for (int i = 0, idx = first; i < size; i++) {
508: if (data[idx] == v)
509: return true;
510: if (++idx == data.length)
511: idx = 0;
512: }
513: return false;
514: }
515:
516: public int indexOf(char c) {
517: for (int i = 0, idx = first; i < size; i++) {
518: if (data[idx] == c)
519: return i;
520: if (++idx == data.length)
521: idx = 0;
522: }
523: return -1;
524: }
525:
526: public int lastIndexOf(char c) {
527: for (int i = size - 1, idx = last - 1; i >= 0; i--) {
528: if (idx < 0)
529: idx = data.length - 1;
530: if (data[idx] == c)
531: return i;
532: idx--;
533: }
534: return -1;
535: }
536:
537: public boolean remove(char v) {
538: int index = indexOf(v);
539: if (index != -1) {
540: removeElementAt(index);
541: return true;
542: }
543: return false;
544: }
545:
546: public char[] toArray(char[] a) {
547: if (a == null || a.length < size)
548: a = new char[size];
549: if (last <= first) {
550: if (last == 0) { // one block at end
551: System.arraycopy(data, first, a, 0, size);
552: } else { // two blocks
553: int block1 = data.length - first;
554: int block2 = size - block1;
555: // copy block at end
556: System.arraycopy(data, first, a, 0, block1);
557: // copy block at start
558: System.arraycopy(data, 0, a, block1, block2);
559: }
560: } else { // one block in middle
561: System.arraycopy(data, first, a, 0, size);
562: }
563: return a;
564: }
565:
566: public boolean equals(Object obj) {
567: if (this == obj)
568: return true;
569: if (!(obj instanceof CharDeque))
570: return false;
571: CharDeque s = (CharDeque) obj;
572: if (size != s.size())
573: return false;
574: CharListIterator i2 = s.listIterator();
575: for (int i = 0, idx = first; i < size; i++) {
576: if (data[idx] != i2.next())
577: return false;
578: if (++idx == data.length)
579: idx = 0;
580: }
581: return true;
582: }
583:
584: public int hashCode() {
585: int h = 1;
586: for (int i = 0, idx = first; i < size; i++) {
587: h = (int) (31 * h + DefaultCharHashFunction.INSTANCE
588: .hash(data[idx]));
589: if (++idx == data.length)
590: idx = 0;
591: }
592: return h;
593: }
594:
595: // ---------------------------------------------------------------
596: // Serialization
597: // ---------------------------------------------------------------
598:
599: /**
600: * @serialData Default fields; the capacity of the
601: * deque (<tt>int</tt>); the deques's elements
602: * (<tt>char</tt>).
603: *
604: * @since 1.1
605: */
606: private void writeObject(ObjectOutputStream s) throws IOException {
607: s.defaultWriteObject();
608: s.writeInt(data.length);
609: CharIterator i = iterator();
610: while (i.hasNext())
611: s.writeChar(i.next());
612: }
613:
614: /**
615: * @since 1.1
616: */
617: private void readObject(ObjectInputStream s) throws IOException,
618: ClassNotFoundException {
619: s.defaultReadObject();
620: data = new char[s.readInt()];
621: first = 0;
622: last = size;
623: for (int i = 0; i < size; i++)
624: data[i] = s.readChar();
625: }
626:
627: }
|