1 19 package bak.pcj.list; 20 21 import bak.pcj.ByteIterator; 22 import bak.pcj.ByteCollection; 23 import bak.pcj.hash.DefaultByteHashFunction; 24 import bak.pcj.util.Exceptions; 25 26 import java.io.Serializable ; 27 import java.io.IOException ; 28 import java.io.ObjectInputStream ; 29 import java.io.ObjectOutputStream ; 30 31 41 public class ByteArrayDeque extends AbstractByteList implements ByteDeque, Cloneable , Serializable { 42 43 44 private static final int GROWTH_POLICY_RELATIVE = 0; 45 46 47 private static final int GROWTH_POLICY_ABSOLUTE = 1; 48 49 54 private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE; 55 56 57 public static final double DEFAULT_GROWTH_FACTOR = 1.0; 58 59 60 public static final int DEFAULT_GROWTH_CHUNK = 10; 61 62 63 public static final int DEFAULT_CAPACITY = 10; 64 65 66 private transient byte[] data; 67 68 72 private int size; 73 74 75 private transient int first; 76 77 78 private transient int last; 79 80 84 private int growthPolicy; 85 86 91 private double growthFactor; 92 93 98 private int growthChunk; 99 100 private ByteArrayDeque(int capacity, int growthPolicy, double growthFactor, int growthChunk) { 101 if (capacity < 0) 102 Exceptions.negativeArgument("capacity", String.valueOf(capacity)); 103 if (growthFactor < 0.0) 104 Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor)); 105 if (growthChunk < 0) 106 Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk)); 107 data = new byte[capacity]; 108 size = 0; 109 this.growthPolicy = growthPolicy; 110 this.growthFactor = growthFactor; 111 this.growthChunk = growthChunk; 112 this.first = 0; 113 this.last = 0; 114 } 115 116 122 public ByteArrayDeque() { 123 this(DEFAULT_CAPACITY); 124 } 125 126 139 public ByteArrayDeque(ByteCollection c) { 140 this(c.size()); 141 addAll(c); 142 } 143 144 159 public ByteArrayDeque(byte[] a) { 160 this(a.length); 161 System.arraycopy(a, 0, data, 0, a.length); 162 size = a.length; 163 first = 0; 164 last = a.length-1; 165 } 166 167 179 public ByteArrayDeque(int capacity) { 180 this(capacity, DEFAULT_GROWTH_FACTOR); 181 } 182 183 202 public ByteArrayDeque(int capacity, double growthFactor) { 203 this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK); 204 } 205 206 225 public ByteArrayDeque(int capacity, int growthChunk) { 226 this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk); 227 } 228 229 233 242 private int computeCapacity(int capacity) { 243 int newcapacity; 244 if (growthPolicy == GROWTH_POLICY_RELATIVE) 245 newcapacity = (int)(data.length * (1.0 + growthFactor)); 246 else 247 newcapacity = data.length + growthChunk; 248 if (newcapacity < capacity) 249 newcapacity = capacity; 250 return newcapacity; 251 } 252 253 265 public int ensureCapacity(int capacity) { 266 if (capacity > data.length) { 267 byte[] newdata = new byte[capacity = computeCapacity(capacity)]; 268 toArray(newdata); 269 first = 0; 270 last = size; 271 data = newdata; 272 } 273 return capacity; 274 } 275 276 285 public int capacity() 286 { return data.length; } 287 288 292 public void add(int index, byte v) { 293 if (index == 0) 294 addFirst(v); 295 else if (index == size) 296 addLast(v); 297 else { 298 if (index < 0 || index > size) 299 Exceptions.indexOutOfBounds(index, 0, size); 300 ensureCapacity(size+1); 301 if (first < last || last == 0) { int iidx = index+first; 303 int end = last == 0 ? data.length : last; 304 int block = end-iidx; 305 if (last == 0) { data[0] = data[data.length-1]; 307 System.arraycopy(data, iidx, data, iidx+1, block-1); 308 last = 1; 309 } else { 310 System.arraycopy(data, iidx, data, iidx+1, block); 311 if (++last == data.length) 312 last = 0; 313 } 314 data[iidx] = v; 315 } else { int iidx = (first+index) % data.length; 317 if (iidx <= last) { int block = last-iidx; 319 System.arraycopy(data, iidx, data, iidx+1, block); 320 last++; 321 data[iidx] = v; 322 } else { int block = iidx-first; 324 System.arraycopy(data, first, data, first-1, block); 325 first--; 326 data[iidx-1] = v; 327 } 328 } 329 size++; 330 } 331 } 332 333 public byte get(int index) { 334 if (index < 0 || index >= size) 335 Exceptions.indexOutOfBounds(index, 0, size-1); 336 return data[(first+index) % data.length]; 337 } 338 339 public byte set(int index, byte v) { 340 if (index < 0 || index >= size) 341 Exceptions.indexOutOfBounds(index, 0, size-1); 342 int idx = (first+index) % data.length; 343 byte result = data[idx]; 344 data[idx] = v; 345 return result; 346 } 347 348 public byte removeElementAt(int index) { 349 byte result; 350 if (index == 0) 351 result = removeFirst(); 352 else if (index == size-1) 353 result = removeLast(); 354 else { 355 if (index < 0 || index >= size) 356 Exceptions.indexOutOfBounds(index, 0, size-1); 357 int ridx = (first+index) % data.length; 358 result = data[ridx]; 359 if (first < last || last == 0) { int block1 = ridx-first; 362 int block2 = size-block1-1; 363 if (block1 < block2) { System.arraycopy(data, first, data, first+1, block1); 365 first++; 366 } else { System.arraycopy(data, ridx+1, data, ridx, block2); 368 if (--last < 0) 369 last = data.length-1; 370 } 371 } else { if (ridx < last) { int block = last-ridx-1; 374 System.arraycopy(data, ridx+1, data, ridx, block); 375 last--; 376 } else { int block = ridx-first; 378 System.arraycopy(data, first, data, first+1, block); 379 if (++first == data.length) 380 first = 0; 381 } 382 } 383 size--; 384 } 385 return result; 386 } 387 388 394 public void trimToSize() { 395 if (data.length > size) { 396 byte[] newdata = toArray(); 397 first = 0; 398 last = 0; 399 data = newdata; 400 } 401 } 402 403 410 public Object clone() { 411 try { 412 ByteArrayDeque c = (ByteArrayDeque)super.clone(); 413 c.data = new byte[data.length]; 414 System.arraycopy(data, 0, c.data, 0, data.length); 416 return c; 417 } catch (CloneNotSupportedException e) { 418 Exceptions.cloning(); return null; 419 } 420 } 421 422 426 public byte getFirst() { 427 if (size == 0) 428 Exceptions.dequeNoFirst(); 429 return data[first]; 430 } 431 432 public byte getLast() { 433 if (size == 0) 434 Exceptions.dequeNoLast(); 435 return data[last == 0 ? data.length-1 : last-1]; 436 } 437 438 public void addFirst(byte v) { 439 ensureCapacity(size+1); 440 if (--first < 0) 441 first = data.length-1; 442 data[first] = v; 443 size++; 444 } 445 446 public void addLast(byte v) { 447 ensureCapacity(size+1); 448 data[last] = v; 449 if (++last == data.length) 450 last = 0; 451 size++; 452 } 453 454 public byte removeFirst() { 455 if (size == 0) 456 Exceptions.dequeNoFirstToRemove(); 457 byte result = data[first]; 458 if (++first == data.length) 459 first = 0; 460 size--; 461 return result; 462 } 463 464 public byte removeLast() { 465 if (size == 0) 466 Exceptions.dequeNoLastToRemove(); 467 if (--last < 0) 468 last = data.length-1; 469 size--; 470 return data[last]; 471 } 472 473 477 public int size() 478 { return size; } 479 480 public boolean isEmpty() 481 { return size == 0; } 482 483 public void clear() { 484 size = 0; 485 first = 0; 486 last = 0; 487 } 488 489 public boolean contains(byte v) { 490 for (int i = 0, idx = first; i < size; i++) { 491 if (data[idx] == v) 492 return true; 493 if (++idx == data.length) 494 idx = 0; 495 } 496 return false; 497 } 498 499 public int indexOf(byte c) { 500 for (int i = 0, idx = first; i < size; i++) { 501 if (data[idx] == c) 502 return i; 503 if (++idx == data.length) 504 idx = 0; 505 } 506 return -1; 507 } 508 509 public int lastIndexOf(byte c) { 510 for (int i = size-1, idx = last-1; i >= 0; i--) { 511 if (idx < 0) 512 idx = data.length-1; 513 if (data[idx] == c) 514 return i; 515 idx--; 516 } 517 return -1; 518 } 519 520 public boolean remove(byte v) { 521 int index = indexOf(v); 522 if (index != -1) { 523 removeElementAt(index); 524 return true; 525 } 526 return false; 527 } 528 529 public byte[] toArray(byte[] a) { 530 if (a == null || a.length < size) 531 a = new byte[size]; 532 if (last <= first) { 533 if (last == 0) { System.arraycopy(data, first, a, 0, size); 535 } else { int block1 = data.length-first; 537 int block2 = size-block1; 538 System.arraycopy(data, first, a, 0, block1); 540 System.arraycopy(data, 0, a, block1, block2); 542 } 543 } else { System.arraycopy(data, first, a, 0, size); 545 } 546 return a; 547 } 548 549 public boolean equals(Object obj) { 550 if (this == obj) 551 return true; 552 if (!(obj instanceof ByteDeque)) 553 return false; 554 ByteDeque s = (ByteDeque)obj; 555 if (size != s.size()) 556 return false; 557 ByteListIterator i2 = s.listIterator(); 558 for (int i = 0, idx = first; i < size; i++) { 559 if (data[idx] != i2.next()) 560 return false; 561 if (++idx == data.length) 562 idx = 0; 563 } 564 return true; 565 } 566 567 public int hashCode() { 568 int h = 1; 569 for (int i = 0, idx = first; i < size; i++) { 570 h = (int)(31*h + DefaultByteHashFunction.INSTANCE.hash(data[idx])); 571 if (++idx == data.length) 572 idx = 0; 573 } 574 return h; 575 } 576 577 581 588 private void writeObject(ObjectOutputStream s) throws IOException { 589 s.defaultWriteObject(); 590 s.writeInt(data.length); 591 ByteIterator i = iterator(); 592 while (i.hasNext()) 593 s.writeByte(i.next()); 594 } 595 596 599 private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException { 600 s.defaultReadObject(); 601 data = new byte[s.readInt()]; 602 first = 0; 603 last = size; 604 for (int i = 0; i < size; i++) 605 data[i] = s.readByte(); 606 } 607 608 } | Popular Tags |