001/** 002 * 003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved. 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, see <http://www.gnu.org/licenses/>. 017 * 018 **/ 019package lucee.runtime.type; 020 021import java.util.ArrayList; 022import java.util.Arrays; 023import java.util.Comparator; 024import java.util.Iterator; 025import java.util.Map.Entry; 026 027import lucee.commons.lang.SizeOf; 028import lucee.runtime.PageContext; 029import lucee.runtime.config.NullSupportHelper; 030import lucee.runtime.dump.DumpData; 031import lucee.runtime.dump.DumpProperties; 032import lucee.runtime.dump.DumpTable; 033import lucee.runtime.dump.DumpUtil; 034import lucee.runtime.dump.SimpleDumpData; 035import lucee.runtime.exp.ExpressionException; 036import lucee.runtime.exp.PageRuntimeException; 037import lucee.runtime.op.Caster; 038import lucee.runtime.op.Duplicator; 039import lucee.runtime.op.ThreadLocalDuplication; 040import lucee.runtime.type.it.EntryIterator; 041import lucee.runtime.type.it.KeyIterator; 042import lucee.runtime.type.it.StringIterator; 043import lucee.runtime.type.util.ArraySupport; 044import lucee.runtime.type.util.ArrayUtil; 045import lucee.runtime.type.util.ListIteratorImpl; 046 047 048 049/** 050 * CFML array object 051 */ 052public class ArrayImpl extends ArraySupport implements Sizeable { 053 054 private static final long serialVersionUID = -6187994169003839005L; 055 private static final int DEFAULT_CAPACITY=32; 056 057 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 058 059 private Object[] arr; 060 private int dimension=1; 061 062 063 private final int cap=DEFAULT_CAPACITY; 064 private int size=0; 065 private int offset=0; 066 private int offCount=0; 067 068 /** 069 * constructor with definiton of the dimension 070 * @param dimension dimension goes from one to 3 071 * @throws ExpressionException 072 */ 073 public ArrayImpl(int dimension) throws ExpressionException { 074 this(dimension,DEFAULT_CAPACITY); 075 } 076 077 public ArrayImpl(int dimension, int initalCapacity) throws ExpressionException { 078 if(dimension>3 || dimension<1) 079 throw new ExpressionException("Array Dimension must be between 1 and 3"); 080 this.dimension=dimension; 081 arr=new Object[offset+initalCapacity]; 082 } 083 084 protected ArrayImpl(int dimension, int initalCapacity, int noFunctionality) { 085 this.dimension=dimension; 086 arr=new Object[offset+initalCapacity]; 087 } 088 089 /** 090 * constructor with default dimesnion (1) 091 */ 092 public ArrayImpl() { 093 arr=new Object[offset+cap]; 094 } 095 096 /** 097 * constructor with to data to fill 098 * @param objects Objects array data to fill 099 */ 100 public ArrayImpl(Object[] objects) { 101 size=objects.length; 102 103 arr=new Object[ Math.max(size, cap) ]; 104 105 if (size > 0) 106 arr = ArrayUtil.mergeNativeArrays(arr, objects, 0, false); 107 108 offset=0; 109 } 110 111 /** 112 * return dimension of the array 113 * @return dimension of the array 114 */ 115 public int getDimension() { 116 return dimension; 117 } 118 119 @Override 120 public Object get(String key) throws ExpressionException { 121 return getE(Caster.toIntValue(key)); 122 } 123 124 @Override 125 public Object get(Collection.Key key) throws ExpressionException { 126 return getE(Caster.toIntValue(key.getString())); 127 } 128 129 @Override 130 public Object get(String key, Object defaultValue) { 131 double index=Caster.toIntValue(key,Integer.MIN_VALUE); 132 if(index==Integer.MIN_VALUE) return defaultValue; 133 return get((int)index,defaultValue); 134 } 135 136 @Override 137 public Object get(Collection.Key key, Object defaultValue) { 138 double index=Caster.toIntValue(key.getString(),Integer.MIN_VALUE); 139 if(index==Integer.MIN_VALUE) return defaultValue; 140 return get((int)index,defaultValue); 141 } 142 143 @Override 144 public synchronized Object get(int key, Object defaultValue) { 145 if(key>size || key<1) { 146 if(dimension>1) { 147 ArrayImpl ai = new ArrayImpl(); 148 ai.dimension=dimension-1; 149 return setEL(key,ai); 150 } 151 return defaultValue; 152 } 153 Object o=arr[(offset+key)-1]; 154 155 if(o==null) { 156 if(dimension>1) { 157 ArrayImpl ai = new ArrayImpl(); 158 ai.dimension=dimension-1; 159 return setEL(key,ai); 160 } 161 if(!NullSupportHelper.full()) return defaultValue; 162 } 163 return o; 164 } 165 166 @Override 167 public synchronized Object getE(int key) throws ExpressionException { 168 if(key<1) { 169 throw invalidPosition(key); 170 } 171 else if(key>size) { 172 if(dimension>1)return setE(key,new ArrayImpl(dimension-1)); 173 throw invalidPosition(key); 174 } 175 176 Object o=arr[(offset+key)-1]; 177 178 if(NullSupportHelper.full()) { 179 if(o==null && dimension>1) return setE(key,new ArrayImpl(dimension-1)); 180 return o; 181 } 182 183 if(o==null) { 184 if(dimension>1) return setE(key,new ArrayImpl(dimension-1)); 185 throw invalidPosition(key); 186 } 187 return o; 188 } 189 190 /** 191 * Exception method if key doesn't exist at given position 192 * @param pos 193 * @return exception 194 */ 195 private ExpressionException invalidPosition(int pos) { 196 return new ExpressionException("Element at position ["+pos+"] doesn't exist in array"); 197 } 198 199 @Override 200 public Object setEL(String key, Object value) { 201 try { 202 return setEL(Caster.toIntValue(key), value); 203 } catch (ExpressionException e) { 204 return null; 205 } 206 } 207 208 @Override 209 public Object setEL(Collection.Key key, Object value) { 210 try { 211 return setEL(Caster.toIntValue(key.getString()), value); 212 } catch (ExpressionException e) { 213 return null; 214 } 215 } 216 217 @Override 218 public Object set(String key, Object value) throws ExpressionException { 219 return setE(Caster.toIntValue(key),value); 220 } 221 222 @Override 223 public Object set(Collection.Key key, Object value) throws ExpressionException { 224 return setE(Caster.toIntValue(key.getString()),value); 225 } 226 227 @Override 228 public synchronized Object setEL(int key, Object value) { 229 if(offset+key>arr.length)enlargeCapacity(key); 230 if(key>size)size=key; 231 arr[(offset+key)-1]=checkValueEL(value); 232 return value; 233 } 234 235 /** 236 * set value at defined position 237 * @param key 238 * @param value 239 * @return defined value 240 * @throws ExpressionException 241 */ 242 public synchronized Object setE(int key, Object value) throws ExpressionException { 243 if(key<1)throw new ExpressionException("Invalid index ["+key+"] for array. Index must be a positive integer (1, 2, 3, ...)"); 244 if(offset+key>arr.length)enlargeCapacity(key); 245 if(key>size)size=key; 246 arr[(offset+key)-1]=checkValue(value); 247 return value; 248 } 249 // same as "setE" bit not synchronized 250 private Object _setE(int key, Object value) throws ExpressionException { 251 if(key<1)throw new ExpressionException("Invalid index ["+key+"] for array. Index must be a positive integer (1, 2, 3, ...)"); 252 if(offset+key>arr.length)enlargeCapacity(key); 253 if(key>size)size=key; 254 arr[(offset+key)-1]=checkValue(value); 255 return value; 256 } 257 258 public synchronized int ensureCapacity(int cap) { 259 if (cap > arr.length) 260 enlargeCapacity(cap); 261 return arr.length; 262 } 263 264 /** 265 * !!! all methods that use this method must be sync 266 * enlarge the inner array to given size 267 * @param key min size of the array 268 */ 269 private void enlargeCapacity(int key) { 270 int diff=offCount-offset; 271 int minCapacity = Math.max(arr.length, key + offset + diff + 1); 272 273 if(minCapacity>arr.length) { 274 int oldCapacity = arr.length; 275 int newCapacity = oldCapacity + (oldCapacity >> 1); 276 if (newCapacity - minCapacity < 0) 277 newCapacity = minCapacity; 278 if (newCapacity - MAX_ARRAY_SIZE > 0) 279 newCapacity = hugeCapacity(minCapacity); 280 // minCapacity is usually close to size, so this is a win: 281 arr = Arrays.copyOf(arr, newCapacity); 282 } 283 } 284 285 private static int hugeCapacity(int minCapacity) { 286 if (minCapacity < 0) // overflow 287 throw new OutOfMemoryError(); 288 return (minCapacity > MAX_ARRAY_SIZE) ? 289 Integer.MAX_VALUE : 290 MAX_ARRAY_SIZE; 291 } 292 293 /** 294 * !!! all methods that use this method must be sync 295 * enlarge the offset if 0 296 */ 297 private void enlargeOffset() { 298 if(offset==0) { 299 offCount=offCount==0?1:offCount*2; 300 offset=offCount; 301 Object[] narr=new Object[arr.length+offset]; 302 for(int i=0;i<size;i++) { 303 narr[offset+i]=arr[i]; 304 } 305 arr=narr; 306 } 307 } 308 309 /** 310 * !!! all methods that use this method must be sync 311 * check if value is valid to insert to array (to a multidimesnional array only array with one smaller dimension can be inserted) 312 * @param value value to check 313 * @return checked value 314 * @throws ExpressionException 315 */ 316 private Object checkValue(Object value) throws ExpressionException { 317 // is a 1 > Array 318 if(dimension>1) { 319 if(value instanceof Array) { 320 if(((Array)value).getDimension()!=dimension-1) 321 throw new ExpressionException("You can only Append an Array with "+(dimension-1)+" Dimension","array has wrong dimension, now is "+(((Array)value).getDimension())+ " but it must be "+(dimension-1)); 322 } 323 else 324 throw new ExpressionException("You can only Append an Array with "+(dimension-1)+" Dimension","now is a object of type "+Caster.toClassName(value)); 325 } 326 return value; 327 } 328 329 /** 330 * !!! all methods that use this method must be sync 331 * check if value is valid to insert to array (to a multidimesnional array only array with one smaller dimension can be inserted), if value is invalid return null; 332 * @param value value to check 333 * @return checked value 334 */ 335 private Object checkValueEL(Object value) { 336 // is a 1 > Array 337 if(dimension>1) { 338 if(value instanceof Array) { 339 if(((Array)value).getDimension()!=dimension-1) 340 return null; 341 } 342 else 343 return null; 344 } 345 return value; 346 } 347 348 @Override 349 public int size() { 350 return size; 351 } 352 353 @Override 354 public synchronized Collection.Key[] keys() { 355 356 ArrayList<Collection.Key> lst=new ArrayList<Collection.Key>(); 357 int count=0; 358 for(int i=offset;i<offset+size;i++) { 359 Object o=arr[i]; 360 count++; 361 if(o!=null) lst.add(KeyImpl.getInstance(count+"")); 362 } 363 return lst.toArray(new Collection.Key[lst.size()]); 364 } 365 366 @Override 367 public synchronized int[] intKeys() { 368 ArrayList<Integer> lst=new ArrayList<Integer>(); 369 int count=0; 370 for(int i=offset;i<offset+size;i++) { 371 Object o=arr[i]; 372 count++; 373 if(o!=null) lst.add(Integer.valueOf(count)); 374 } 375 376 int[] ints=new int[lst.size()]; 377 378 for(int i=0;i<ints.length;i++){ 379 ints[i]=lst.get(i).intValue(); 380 } 381 return ints; 382 } 383 384 @Override 385 public Object remove(Collection.Key key) throws ExpressionException { 386 return removeE(Caster.toIntValue(key.getString())); 387 } 388 389 public Object removeEL(Collection.Key key) { 390 return removeEL(Caster.toIntValue(key.getString(),-1)); 391 } 392 393 @Override 394 public synchronized Object removeE(int key) throws ExpressionException { 395 if(key>size || key<1) throw invalidPosition(key); 396 Object obj=get(key,null); 397 for(int i=(offset+key)-1;i<(offset+size)-1;i++) { 398 arr[i]=arr[i+1]; 399 } 400 size--; 401 return obj; 402 } 403 404 @Override 405 public synchronized Object removeEL(int key) { 406 if(key>size || key<1) return null; 407 Object obj=get(key,null); 408 409 for(int i=(offset+key)-1;i<(offset+size)-1;i++) { 410 arr[i]=arr[i+1]; 411 } 412 size--; 413 return obj; 414 } 415 416 @Override 417 public synchronized void clear() { 418 if(size()>0) { 419 arr=new Object[cap]; 420 size=0; 421 offCount=1; 422 offset=0; 423 } 424 } 425 426 @Override 427 public synchronized boolean insert(int key, Object value) throws ExpressionException { 428 if(key<1 || key>size+1) { 429 throw new ExpressionException("can't insert value to array at position "+key+", array goes from 1 to "+size()); 430 } 431 // Left 432 if((size/2)>=key) { 433 enlargeOffset(); 434 for(int i=offset;i<(offset+key)-1;i++) { 435 arr[i-1]=arr[i]; 436 } 437 offset--; 438 arr[(offset+key)-1]=checkValue(value); 439 size++; 440 } 441 // Right 442 else { 443 if((offset+key)>arr.length || size+offset>=arr.length)enlargeCapacity(arr.length+2); 444 for(int i=size+offset;i>=key+offset;i--) { 445 arr[i]=arr[i-1]; 446 } 447 arr[(offset+key)-1]=checkValue(value); 448 size++; 449 450 } 451 return true; 452 } 453 454 @Override 455 public synchronized Object append(Object o) throws ExpressionException { 456 if(offset+size+1>arr.length)enlargeCapacity(size+1); 457 arr[offset+size]=checkValue(o); 458 size++; 459 return o; 460 } 461 462 /** 463 * append a new value to the end of the array 464 * @param o value to insert 465 * @return inserted value 466 */ 467 public synchronized Object appendEL(Object o) { 468 469 if(offset+size+1>arr.length)enlargeCapacity(size+1); 470 arr[offset+size]=o; 471 size++; 472 return o; 473 } 474 475 /** 476 * append a new value to the end of the array 477 * @param str value to insert 478 * @return inserted value 479 */ 480 public synchronized String _append(String str) { 481 if(offset+size+1>arr.length)enlargeCapacity(size+1); 482 arr[offset+size]=str; 483 size++; 484 return str; 485 } 486 487 /** 488 * add a new value to the begin of the array 489 * @param o value to insert 490 * @return inserted value 491 * @throws ExpressionException 492 */ 493 public Object prepend(Object o) throws ExpressionException { 494 insert(1,o); 495 return o; 496 } 497 498 /** 499 * resize array to defined size 500 * @param to new minimum size of the array 501 */ 502 public synchronized void resize(int to) { 503 if(to>size) { 504 enlargeCapacity(to); 505 size=to; 506 } 507 } 508 509 public synchronized void sort(Comparator comp) { 510 if(getDimension()>1) 511 throw new PageRuntimeException("only 1 dimensional arrays can be sorted"); 512 Arrays.sort(arr,offset,offset+size,comp); 513 } 514 515 /** 516 * @return return arra as native (Java) Object Array 517 */ 518 public synchronized Object[] toArray() { 519 Object[] rtn=new Object[size]; 520 int count=0; 521 for(int i=offset;i<offset+size;i++) { 522 rtn[count++]=arr[i]; 523 } 524 525 return rtn; 526 } 527 528 @Override 529 public DumpData toDumpData(PageContext pageContext, int maxlevel, DumpProperties dp) { 530 DumpTable table = new DumpTable("array","#99cc33","#ccff33","#000000"); 531 table.setTitle("Array"); 532 533 int top = dp.getMaxlevel(); 534 535 if( size() > top ) 536 table.setComment("Rows: " + size() + " (showing top " + top + ")"); 537 else if(size()>10 && dp.getMetainfo()) 538 table.setComment("Rows: "+size()); 539 540 541 542 int length=size(); 543 544 for(int i=1;i<=length;i++) { 545 Object o=null; 546 try { 547 o = getE(i); 548 } 549 catch (Exception e) {} 550 551 table.appendRow( 1, new SimpleDumpData(i), DumpUtil.toDumpData(o, pageContext, maxlevel, dp) ); 552 553 if ( i == top ) 554 break; 555 } 556 557 return table; 558 } 559 560 /** 561 * return code print of the array as plain text 562 * @return content as string 563 */ 564 public synchronized String toPlain() { 565 566 StringBuffer sb=new StringBuffer(); 567 int length=size(); 568 for(int i=1;i<=length;i++) { 569 sb.append(i); 570 sb.append(": "); 571 sb.append(get(i-1,null)); 572 sb.append("\n"); 573 } 574 return sb.toString(); 575 } 576 577 @Override 578 public synchronized Collection duplicate(boolean deepCopy) { 579 return duplicate(new ArrayImpl(dimension,size(),0),deepCopy); 580 } 581 582 protected Collection duplicate(ArrayImpl arr,boolean deepCopy) { 583 arr.dimension=dimension; 584 585 Iterator<Entry<Key, Object>> it = entryIterator(); 586 boolean inside=deepCopy?ThreadLocalDuplication.set(this, arr):true; 587 Entry<Key, Object> e; 588 try { 589 while(it.hasNext()){ 590 e = it.next(); 591 if(deepCopy)arr.set(e.getKey(),Duplicator.duplicate(e.getValue(),deepCopy)); 592 else arr._setE(Caster.toIntValue(e.getKey().getString()),e.getValue()); 593 } 594 } 595 catch (ExpressionException ee) {} 596 finally{ 597 if(!inside)ThreadLocalDuplication.reset(); 598 } 599 return arr; 600 } 601 602 @Override 603 public Iterator<Collection.Key> keyIterator() { 604 return new KeyIterator(keys()); 605 } 606 607 @Override 608 public Iterator<String> keysAsStringIterator() { 609 return new StringIterator(keys()); 610 } 611 612 @Override 613 public Iterator<Entry<Key, Object>> entryIterator() { 614 return new EntryIterator(this, keys()); 615 } 616 617 618 @Override 619 public Iterator iterator() { 620 return new ListIteratorImpl(this,0); 621 } 622 623 @Override 624 public long sizeOf() { 625 return SizeOf.size(arr) 626 +SizeOf.size(dimension) 627 +SizeOf.size(cap) 628 +SizeOf.size(size) 629 +SizeOf.size(offset) 630 +SizeOf.size(offCount) 631 +SizeOf.REF_SIZE; 632 } 633}