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}