;
;	array_bounds.pro
;
;	contains definitions for:
;		find_integer_fill
;		array_bounds
;


pro find_integer_fill, arr_ptr_array, smallest, largest, fill
; Search for a useable fill value in an integer array
; within the range smallest to largest

n = n_elements(arr_ptr_array)
fill_ok = 1
; look for a value not in any array
if size(largest, /type) eq 1 then begin
	; try all possible values if a byte type
	try_vals = bindgen(largest-smallest) + smallest
endif else begin
	; try 256 values in the range
	step = (largest - (smallest + 1)) / 255
	try_vals = indgen(256) * step + smallest
endelse
n_try = n_elements(try_vals)
i = 0L
try_ind = 0L
while (i lt n) and (try_ind lt n_try) do begin
	cur_arr = *arr_ptr_array[i]
	try_val = try_vals[try_ind]
	dum = where(cur_arr eq try_val, cnt)
	dum = 0
	while (cnt ne 0) and (try_ind lt n_try-1) do begin
		try_ind = try_ind + 1
		try_val = try_vals[try_ind]
		if try_val eq 0 then continue
		dum = where(cur_arr eq try_val, cnt)
		dum = 0
	endwhile
	if cnt ne 0 then begin
		fill_ok = 0
		break
	endif
	i = i + 1
endwhile
if fill_ok eq 0 then begin
	; all possible values occur in the arrays,
	; or else too many possible values to search
	; find a fill that would at least work
	; try given fill, smallest, largest first
	try_fills = [ smallest, largest, try_vals[1:255] ]
	if size(fill, /type) eq 7 then begin
		try_fills = [ fill, temporary(try_fills) ]
	endif
	for f=0L,n_elements(try_fills)-1 do begin
		try_val = try_fills[f]
		if (f gt 0) and (size(fill, /type) eq 7) $
			and (fill eq try_val) then $
			continue
		if (try_val eq 0) then continue
		fill_ok = 1
		for i=0L,n-1 do begin
			cur_arr = *arr_ptr_array[i]
			if (where(cur_arr eq try_val))[0] ge 0 then begin
				; see if try_val would contract array
				dim_n = size(cur_arr, /n_dimensions)
				would_contract = 0
				while (would_contract eq 0) and $
					(dim_n gt 0) do begin
					shorten_array, cur_arr, dim_n, try_val, would_contract
					dim_n = dim_n - 1
				endwhile
				cur_arr = 0
				if would_contract eq 1 then begin
					fill_ok = 0
					break
				endif
			endif
		endfor
		if fill_ok then begin
			fill = try_val
			break
		endif
	endfor
endif else fill = try_val
end


pro array_bounds, arr_ptr_array, bdim, fill, string_max
; Given an array of pointers to arrays (possibly of variable size),
; find the smallest bounding dimensions to contain every pointer element.
; Also find a good fill value to use (can specify default fill to try.)
; Don't return a valid (string) fill value if one isn't needed
; (i.e. no null pointers and all arrays are the same size.)
; optional variable: find the longest string length (0 if not a string type),
;  return in string_max
; note: arrays must be of the same type

find_strings = 0
if (n_params() eq 4) then begin
	find_strings = 1
	string_max = 0
endif

; vind is the set of non-null indices,
; n is the number of non-null pointers in arr_ptr_array
; n_null is the number of null pointers in arr_ptr_array
vind = where(arr_ptr_array ne ptr_new(), n)
n_null = n_elements(arr_ptr_array) - n

ptr_arr_size = size(arr_ptr_array, /dimensions)

if (n eq 0) then begin
	; nothing but null-pointers; return
	bdim = [1]
	fill = '1'
	return
endif

btype = size(*arr_ptr_array[vind[0]], /type)

if ((where(btype eq [0,8,10,11]))[0] ge 0) then begin
	; don't deal with undefined, struct, pointer, objref array types
	bdim = 0
	return
endif

need_fill = 0
zero_dims = lonarr(8)
bdim = zero_dims

; check array sizes & types
for i=0,n-1 do begin
	cind = vind[i]
       	if (size(*arr_ptr_array[cind], /type) ne btype) then begin
		bdim = 0
		return
	endif
	; find the largest space needed
	tmpdim = zero_dims
	tmpdim[0] = size(*arr_ptr_array[cind], /dimensions)
		if (not array_equal(bdim,tmpdim)) then $
			need_fill = 1
	bdim = bdim > tmpdim
	; check for string lengths
	if (find_strings and (btype eq 7)) then $
		string_max = string_max > max(strlen(*arr_ptr_array[cind]))
endfor
if bdim[0] eq 0 then begin
	n_dim = 0
	bdim = [ ptr_arr_size ]
endif else begin
	n_dim = max(where(bdim ne 0)) + 1
	if ptr_arr_size[0] gt 0 then $
		bdim = [ bdim[0:n_dim-1], ptr_arr_size ] $
	else $
		bdim = bdim[0:n_dim-1]
endelse

; remember if the array will contain floating-point values
float_or_complex = (where(btype eq [4,5,6,9]))[0] ge 0

if (n_null gt 0) then $
	need_fill = 1
if (need_fill eq 0) then $
	fill = 0 $
else begin
	if (size(fill, /type) eq 7) then begin
		; a given fill value; see if it would work
		on_ioerror, bad_type
		fval = fix(fill, type=btype, /print)
		fval_ok = 1
		goto, ok_type
		bad_type:
			fill = 1
			fval = fix(fill, type=btype, /print)
			fval_ok = 0

		ok_type:
		if fval_ok eq 1 then begin
			if float_or_complex then begin
				; float/complex type
				for i=0,n-1 do begin
					vinds = vind[i]
					if finite(fval, /nan) then $
						match_ind = (where(finite(*arr_ptr_array[vinds], /nan)))[0] $
					else if finite(fval, /infinity) then begin
						match_ind = where(finite(*arr_ptr_array[vinds], /infinity))
						if match_ind[0] ge 0 then begin
							if (fval gt 0) then match_ind = $
								(where(*arr_ptr_array[vinds[match_ind]] gt 0))[0] $
							else match_ind = $
								(where(*arr_ptr_array[vinds[match_ind]] lt 0))[0]
						endif
					endif else case btype of
						6: match_ind = (where(float(*arr_ptr_array[vinds]) eq fval))[0]
						9: match_ind = (where(double(*arr_ptr_array[vinds]) eq fval))[0]
						else: match_ind = (where(*arr_ptr_array[vinds] eq fval))[0]
					endcase
					if (match_ind ge 0) then begin
						fval_ok = 0
						break
					endif
				endfor
			endif else begin
				for i=0,n-1 do begin
					match_ind = (where(*arr_ptr_array[vind[i]] eq fval))[0]
					if (match_ind ge 0) then begin
						fval_ok = 0
						break
					endif
				endfor
			endelse
		endif
		if (fval_ok eq 1) then return
	endif

	; strings: try space, other single-character strings for fill
	if (btype eq 7) then begin
		try_fills = [ ' ', '!', '?', '&', '#', '%', '+', '-', $
			'(', ')', '[', ']', '{', '}', '<', '>', '.', ',' ]
		fill_ok = 0
		for f=0,n_elements(try_fills)-1 do begin
			fill = try_fills[f]
			fill_ok = 1
			for i=0,n-1 do begin
				if (where(*arr_ptr_array[vind[i]] eq fill))[0] $
					ge 0 then begin
					fill_ok = 0
					break
				endif
			endfor
			if fill_ok then return
		endfor
		return 	; just use the comma as fill if everything else in array
	endif

	; need to find a decent fill value
	fval = 1

	; check min/max values
	all_max = !values.f_nan
	d_all_max = !values.d_nan
	all_min = all_max
	d_all_min = d_all_max
	for i=0L,n-1 do begin
		cur_arr = 0
		cur_arr = *arr_ptr_array[vind[i]]
		if (btype eq 6) or (btype eq 9) then begin
			; complex types - only use real part for fill
			fin_ind = where(finite(cur_arr))
			if fin_ind[0] ge 0 then begin
				fin_vals = cur_arr[fin_ind]
				d_fin_vals = double(fin_vals)
				dum = max(d_fin_vals, cind)
				cur_max = fin_vals[cind]
				d_cur_max = d_fin_vals[cind]
				dum = min(d_fin_vals, cind)
				cur_min = fin_vals[cind]
				d_cur_min = d_fin_vals[cind]
				d_fin_vals = 0
				fin_vals = 0
				if finite(all_max) and finite(cur_max) then begin
					if (d_cur_max gt d_all_max) then begin
						all_max = cur_max
						d_all_max = d_cur_max
					endif
					if (d_cur_min lt d_all_min) then begin
						all_min = cur_min
						d_all_min = d_cur_min
					endif
				endif else if not finite(all_max) then begin
					all_max = cur_max
					d_all_max = d_cur_max
					all_min = cur_min
					d_all_min = d_cur_min
				endif
			endif
		endif else if float_or_complex then begin
			; this handles float, but not complex
			dum = where(not finite(cur_arr), cnt)
			dum = 0
			if (cnt ne 0) then begin
				cur_max = max(cur_arr, /NAN, min=cur_min)
			endif else $
				cur_max = max(cur_arr, min=cur_min)
			if finite(all_max) and finite(cur_max) then begin
				all_max = all_max > cur_max
				all_min = all_min < cur_min
			endif else if not finite(all_max) then begin
				all_max = cur_max
				all_min = cur_min
			endif
			d_all_max = double(all_max)
			d_all_min = double(all_min)
		endif else begin
			cur_max = max(cur_arr, min=cur_min)
			if not finite(all_max) then begin
				all_max = cur_max
				all_min = cur_min
			endif else begin
				all_max = all_max > cur_max
				all_min = all_min < cur_min
			endelse
		endelse
		cur_arr = 0
	endfor
	;print, 'min/max: ', d_all_min, d_all_max
	if ((where(btype eq [1,12,13,15]))[0] ge 0) then begin
		; unsigned types: try max/min possible values
		largest = not fix(0, type=btype, /print)
		if (all_max lt largest) then $
			fval = largest $
		else if (all_min gt 1) then $
			fval = 1 $
		else begin
			fval = fill
			find_integer_fill, arr_ptr_array[vind], $
				(largest * 0) + 1, largest, fval
		endelse
	endif else if float_or_complex then begin
		; floating point or complex type
		; prefer fill values of 1 or -1
		fval = 0
		if not finite(all_max) then $
			fval = 1 $
		else if (d_all_min ge 0) then $
			fval = -1 $
		else if (d_all_max le 0) then $
			fval = 1
		; we could try NaN, +/- Inf for fill values, but it takes a long time to check
		if fval eq 0 then begin
			;print, all_max, all_min
			if (d_all_max le abs(d_all_min)) then $
				fval = floor(d_all_max, /L64) + 1 $
			else $
				fval = ceil(d_all_min, /L64) - 1
		endif
	endif else begin
		; signed integer types
		; prefer fill values of 0, 1, or -1
		if (all_min ge 0) then $
			fval = -1 $
		else if (all_max le 0) then $
			fval = 1 $
		else begin
			case btype of
				2: largest = (not uint(0)) / 2
				3: largest = (not ulong(0)) / 2
				14: largest = (not ulong64(0)) / 2
				else: largest = 0
			endcase
			if (all_max lt largest) then $
				fval = largest $
			else if (all_min ge -largest) then $
				fval = -(long64(largest) + 1) $
			else begin
				fval = fill
				find_integer_fill, arr_ptr_array[vind], $
					-1 - largest, largest, fval
			endelse
		endelse
	endelse
	fill = strtrim(fval,2)
	;help, fill
endelse

end