1 // Copyright (c) 2002, 2003, 2016  Per M.A. Bothner and Brainfood Inc.
2 // This is free software;  for terms and warranty disclaimer see ./COPYING.
3 
4 package gnu.kawa.functions;
5 import gnu.bytecode.PrimType;
6 import gnu.lists.*;
7 import gnu.mapping.*;
8 import gnu.math.IntNum;
9 
10 /** Static methods for implementing Scheme (SRFI-25) arrays. */
11 
12 public class Arrays
13 {
14   static final int[] shapeStrides = { 2, 1} ;
15   static final int[] zeros2 = new int[2];
16 
17   /** Convert a sequence of (lower,upper) bounds to a SRFI-25 shape.
18     */
shape(Object[] vals)19   public static Array shape (Object[] vals)
20   {
21     int len = vals.length;
22     if ((len & 1) != 0)
23       throw new RuntimeException("shape: not an even number of arguments");
24     int d = len >> 1;
25     int[] dims = { d, 2 };
26     return new GeneralArray(new FVector(vals), dims, null, shapeStrides, 0);
27   }
28 
29     /** Process a shape specifier.
30      * @param shape A canonical shape (rank*2 array)
31      * or a shape specifier (vector whose length is the rank).
32      * @param rank The rank of arrays of that shape.
33      * @param dimensions Ignored if toShape.  Otherwise,
34      *   must have length==rank, and is modified with (hi-lo).
35      * @param toShape: True if used by {@code ->shape}.
36      * @return If toShape: a rank*2 shape array as an int[];
37      *   otherwise: vector of low-bounds (or null if all zero).
38      */
handleShapeSpecifier(Array shape, int rank, int[] dimensions, boolean toShape)39     public static int[] handleShapeSpecifier(Array shape, int rank,
40                                              int[] dimensions,
41                                              boolean toShape) {
42         int srank = shape.rank();
43         int[] result = toShape ? new int[2 * rank] : null;
44         for (int i = rank;  --i >= 0; ) {
45             int lo, hi;
46             if (srank == 2) {
47                 lo = shape.getInt(i, 0);
48                 hi = shape.getInt(i, 1);
49             } else if (shape instanceof IntSequence) {
50                 lo = 0;
51                 hi = ((IntSequence) shape).getInt(i);
52             } else {
53                 Object dim = shape.get(i);
54                 Sequence sdim;
55                 if (LList.listLength(dim, false) == 2) {
56                     Pair p0 = (Pair) dim;
57                     lo = ((Number) p0.getCar()).intValue();
58                     Pair p1 = (Pair) p0.getCdr();
59                     hi = ((Number) p1.getCar()).intValue();
60                 } else
61                 if (dim instanceof Range.IntRange) {
62                     Range.IntRange range = (Range.IntRange) dim;
63                     if (range.getStepInt() != 1)
64                         ; // ERROR
65                     lo = range.getStartInt();
66                     hi = range.size() + lo;
67                 } else {
68                     lo = 0;
69                     hi = ((Number) dim).intValue();
70                 }
71             }
72             if (lo > hi)
73                 throw new RuntimeException("array dimension "+i+" has negative size");
74             if (toShape) {
75                 result[2*i] = lo;
76                 result[2*i+1] = hi;
77             } else {
78                 dimensions[i] = hi - lo;
79                 if (lo != 0) {
80                     if (result == null)
81                         result = new int[rank];
82                     result[i] = lo;
83                 }
84             }
85         }
86         return result;
87     }
88 
89     /** Convenience method for resolving shape specifiers.
90      */
allocateArray(Array shape)91     public static GeneralArray allocateArray(Array shape) {
92         int srank = shape.rank();
93         int rank = shape.getSize(0);
94         if (srank != 1
95             && ! (srank == 2 && shape.getSize(1) == 2))
96             throw new RuntimeException("array shape must be a sequence or a rank*2 array");
97         int[] dimensions = new int[rank];
98         int[] lowBounds = handleShapeSpecifier(shape, rank, dimensions, false);
99         return GeneralArray.make(null, dimensions, lowBounds, null, 0);
100     }
101 
makeFromValues(Array shape, Object[] values)102     public static Array makeFromValues(Array shape, Object[] values) {
103         GeneralArray array = allocateArray(shape);
104         int total = array.getSize();
105         Object[] data = new Object[total];
106         if (values != null && values.length > 0) {
107             int j = 0;
108             for (int i = 0;  i < total; ++i) {
109                 data[i] = values[j];
110                 if (++j == values.length)
111                     j = 0;
112             }
113         }
114         array.setBase(data);
115         return array;
116     }
117 
makeFromSimple(int [] dimensions, int[] lowBounds, Object buffer, PrimType elementType)118     public static Array makeFromSimple(int [] dimensions, int[] lowBounds,
119                                        Object buffer,
120                                        PrimType elementType) {
121         char sig1;
122         if (elementType == null)
123             sig1 = 'L';
124         else {
125             sig1 = elementType.getSignature().charAt(0);
126             if (elementType.isUnsigned())
127                 sig1 = Character.toLowerCase(sig1);
128         }
129         int rank = dimensions.length;
130         SimpleVector base;
131         switch (sig1) {
132         case 'L':
133             base = new FVector((Object[]) buffer);
134             break;
135         case 'B':
136             base = new S8Vector((byte[]) buffer);
137             break;
138         case 'b':
139             base = new U8Vector((byte[]) buffer);
140             break;
141         case 'I':
142             base = new S32Vector((int[]) buffer);
143             break;
144         case 'i':
145             base = new U32Vector((int[]) buffer);
146             break;
147         case 'J':
148             base = new S64Vector((long[]) buffer);
149             break;
150         case 'j':
151             base = new U64Vector((long[]) buffer);
152             break;
153         case 'S':
154             base = new S16Vector((short[]) buffer);
155             break;
156         case 's':
157             base = new U16Vector((short[]) buffer);
158             break;
159         case 'D':
160             base = new F64Vector((double[]) buffer);
161             break;
162         case 'F':
163             base = new F32Vector((float[]) buffer);
164             break;
165         default:
166             throw new Error("bad type for makeFromSimple");
167         }
168         if (rank == 1 && (lowBounds == null || lowBounds[0] == 0))
169             return base;
170         else
171             return GeneralArray.makeSimple(lowBounds, dimensions, base);
172     }
173 
makeSimple(Array shape, SimpleVector base)174     public static Array makeSimple(Array shape, SimpleVector base) {
175         GeneralArray array = allocateArray(shape);
176         array.setBase(base);
177         return array;
178   }
179 
effectiveIndex(Array array, Procedure proc, Object[] args, int[] work)180   private static int effectiveIndex(Array array, Procedure proc,
181 				    Object[] args, int[] work)
182     throws Throwable
183   {
184     Object mapval = proc.applyN(args);
185     if (mapval instanceof Values)
186       {
187 	Values mapvals = (Values) mapval;
188 	for (int i = 0, j = 0;  (i = mapvals.nextPos(i)) != 0;  j++)
189 	  {
190 	    work[j] = ((Number) mapvals.getPosPrevious(i)).intValue();
191 	  }
192       }
193     else
194       work[0] = ((Number) mapval).intValue();
195     if (array instanceof GeneralArray)
196         return ((GeneralArray) array).resolve(work);
197     else
198         return work[0];
199   }
200 
201   /* Create a view of a simple-array that is an affine index transform.
202    */
shareArray(Array array, Array shape, Procedure proc)203   public static Array shareArray(Array array, Array shape,
204 				 Procedure proc)
205     throws Throwable
206   {
207     GeneralArray result = allocateArray(shape);
208     int rank = result.rank();
209     Object[] args = new Object[rank];
210     int[] dimensions = result.getDimensions();
211     int[] lowBounds = result.getLowBounds();
212     boolean empty = result.getSize() == 0;
213     for (int i = rank;  --i >= 0; )
214         args[i] = Integer.valueOf(result.getLowBound(i));
215     int arank = array.rank();
216     int[] offsets = new int[rank];
217     int offset0;
218     if (empty)
219       offset0 = 0;
220     else
221       {
222 	int[] work = new int[arank];
223 	offset0 = effectiveIndex (array, proc, args, work);
224 	for (int i = rank;  --i >= 0; )
225 	  {
226 	    int size = dimensions[i];
227 	    int lo = lowBounds == null ? 0 : lowBounds[i];
228 	    if (size <= 1)
229 	      offsets[i] = 0;
230 	    else
231 	      {
232 		Object low = args[i];
233 		args[i] = IntNum.make(lo + 1);
234 		offsets[i] = (effectiveIndex (array, proc, args, work)
235 			      - offset0);
236 		args[i] = low;
237 	      }
238 	  }
239       }
240     AVector base = array instanceof GeneralArray
241         ? ((GeneralArray) array).getBase()
242         : (AVector) array;
243     result.setBase(base);
244     result.setStrides(offsets, offset0);
245     return result;
246   }
247 
248     /** Class for implementing computed (virtual) array.
249      * Used by build-array procedure.
250      */
251     public static class BuiltArray<E> extends AbstractSequence<E>
252         implements Array<E> {
253         Procedure getter;
254         Procedure setter;
255         int[] dims;
256         int[] lowBounds;
checkCanWrite()257         protected void checkCanWrite () {
258             if (setter == null)
259                 throw new UnsupportedOperationException("write not allowed to read-only "+(rank()==1 ? "sequence" : "array"));
260         }
BuiltArray(Procedure getter, int[] dimensions, int[] lowBounds)261         public BuiltArray(Procedure getter,
262                           int[] dimensions, int[] lowBounds) {
263             this.getter = getter;
264             this.dims = dimensions;
265             this.lowBounds = lowBounds;
266         }
BuiltArray(Procedure getter, Procedure setter, int[] dimensions, int[] lowBounds)267         public BuiltArray(Procedure getter, Procedure setter,
268                           int[] dimensions, int[] lowBounds) {
269 
270             this.getter = getter;
271             this.setter = setter;
272             this.dims = dimensions;
273             this.lowBounds = lowBounds;
274         }
275         @Override
rank()276         public int rank() { return dims.length; }
277         @Override
getLowBound(int dim)278         public int getLowBound(int dim) { return lowBounds[dim]; }
279         @Override
getSize(int dim)280         public int getSize(int dim) { return dims[dim]; }
281 
get()282         public E get() { return get(AbstractSequence.noInts); }
get(int i)283         public E get(int i) { return get(new int[] {i}); }
get(int i, int j)284         public E get(int i, int j) { return get(new int[] {i, j}); }
get(int i, int j, int k, int... rest)285         public E get(int i, int j, int k, int... rest) {
286             if (rest.length == 0)
287                 return get(new int[]{i, j, k});
288             int[] indexes = new int[rest.length+3];
289             indexes[0] = i;
290             indexes[1] = j;
291             indexes[2] = k;
292             System.arraycopy(rest, 0, indexes, 0, rest.length-3);
293             return get(indexes);
294         }
295 
get(int[] indexes)296         public E get(int[] indexes) {
297             try {
298                 return (E) getter.apply1(new S32Vector(indexes));
299             } catch (Throwable ex) {
300                 throw new RuntimeException("caught "+ex+" evaluating array procedure", ex);
301             }
302         }
getRaw(int effi)303         public E getRaw(int effi) {
304             int[] indexes = new int[rank()];
305             for (int i = rank(); --i >= 0; ) {
306                 int d = dims[i];
307                 indexes[i] = (effi % d) + lowBounds[i];
308                 effi = effi / d;
309             }
310             return get(indexes);
311         }
set(int[] indexes, E value)312         public void set(int[] indexes, E value) {
313             checkCanWrite();
314             try {
315                 setter.apply2(new S32Vector(indexes), value);
316             } catch (Throwable ex) {
317                 throw new RuntimeException("caught "+ex+" evaluating array procedure", ex);
318             }
319         }
setRaw(int effi, E value)320         public void setRaw(int effi, E value) {
321             int[] indexes = new int[rank()];
322             for (int i = rank(); --i >= 0; ) {
323                 int d = dims[i];
324                 indexes[i] = (effi % d) + lowBounds[i];
325                 effi = effi / d;
326             }
327             set(indexes, value);
328         }
329     }
getBuiltArray(Array shape, Procedure getter)330     public static <E> Array<E> getBuiltArray(Array shape, Procedure getter) {
331         GeneralArray ashape = allocateArray(shape);
332         return new BuiltArray(getter,
333                               ashape.getDimensions(), ashape.getLowBounds());
334     }
getBuiltArray(Array shape, Procedure getter, Procedure setter)335     public static <E> Array<E> getBuiltArray(Array shape,
336                                              Procedure getter,
337                                              Procedure setter) {
338         GeneralArray ashape = allocateArray(shape);
339         return new BuiltArray(getter, setter,
340                               ashape.getDimensions(), ashape.getLowBounds());
341     }
342 
343     /** General array "view" class using a Procedure index transformer.
344      * Used by array-transform procedure.
345      */
346     public static class ProcTransformedArray<E> extends TransformedArray<E> {
347         Procedure proc;
348         int[] dims;
349         int[] lowBounds;
ProcTransformedArray(Array<E> base, Procedure transformer, int[] dimensions, int[] lowBounds)350         public ProcTransformedArray(Array<E> base, Procedure transformer,
351                                     int[] dimensions, int[] lowBounds) {
352             super(base);
353             this.proc = transformer;
354             this.dims = dimensions;
355             this.lowBounds = lowBounds;
356         }
357         @Override
rank()358         public int rank() { return dims.length; }
359         @Override
getLowBound(int dim)360         public int getLowBound(int dim) { return lowBounds[dim]; }
361         @Override
getSize(int dim)362         public int getSize(int dim) { return dims[dim]; }
363 
effectiveIndex(int i, int j)364         public final int effectiveIndex(int i, int j) {
365             return effectiveIndex(new int[] {i, j});
366         }
effectiveIndex(int[] indexes)367         public int effectiveIndex(int[] indexes) {
368             Object obj;
369             try {
370                 obj = proc.apply1(indexes);
371             } catch (Throwable ex) {
372                 throw new RuntimeException("index transformer throw "+ex, ex);
373             }
374             if (obj instanceof int[])
375                 return base.effectiveIndex((int[]) obj);
376             IntSequence ind = Sequences.asIntSequenceOrNull(obj);
377             if (ind == null)
378                 throw new ClassCastException("not an integer sequence");
379             if (ind instanceof S32Vector)
380                 return base.effectiveIndex(((S32Vector) ind).getBuffer());
381             else {
382                 int rank = ind.size();
383                 switch (rank) {
384                 case 0:
385                     return base.effectiveIndex();
386                 case 1:
387                     return base.effectiveIndex(ind.getInt(0));
388                 case 2:
389                     return base.effectiveIndex(ind.getInt(0), ind.getInt(1));
390                 default:
391                     int[] rest = rank == 3 ? AbstractSequence.noInts
392                         : new int[rank-3];
393                     for (int i = 3; i < rank; i++)
394                         rest[i-3] = ind.getInt(i);
395                     return base.effectiveIndex(ind.getInt(0), ind.getInt(1),
396                                                ind.getInt(2), rest);
397                 }
398             }
399         }
400     }
getTransformed(Array<E> base, Procedure transformer, Array shape)401     public static <E> Array<E> getTransformed(Array<E> base, Procedure transformer, Array shape) {
402         GeneralArray ashape = allocateArray(shape);
403         return new ProcTransformedArray(base, transformer,
404                                         ashape.getDimensions(),
405                                         ashape.getLowBounds());
406     }
407 }
408