Algorithm for Ruby flatten () method implemented in Java
I was reading a ruby book and came across the .flatten function. As the name suggests, it aligns the array as shown below:
a = [ 1, 2, 3 ] #=> [1, 2, 3]
b = [ 4, 5, 6, [7, 8] ] #=> [4, 5, 6, [7, 8]]
c = [ a, b, 9, 10 ] #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
c.flatten #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
My question is: I am trying to implement, see if I can come up with an algorithm in Java so that when passing an array (which could contain) other arrays, it will return an array. I don't know, maybe there is an easier way to do this, or maybe implementation of it already in Java. Regardless, I know I didn't wait for my time to do it today :)
Here's my algorithm to start with: Create an arrayList.
for each element in array as x,
if x element, add to arrayList
else
do a recurse(pass x as arg)
Once done, create a int array with size = arrayList.
Loop arrayList and add each element
Here's my code:
public class Flatten {
public static void main(String[] args){
a = [ 1, 2, 3 ]
b = [ 4, 5, 6, [7, 8] ]
c = [ a, b, 9, 10 ]
flatten(c);
}
public static int[] flatten(int[] a){
ArrayList<Integer> ar = new ArrayList<Integer>();
for(int i=0; i<a.; i
Object o = a[i];
if(!obj instanceof Object[])){
arr.add(a[i]);
}
else {
int[] newArray = nR
flatten(nR);
}
}
}
int[] results = new int[ar.size()];
for(int i=0; i<ar.size(); i++){
int x = ar.get(i);
int[i] = x;
}
return results;
}
}
The tricky part of this algorithm is checking if an element is an array. Also the problem is that arrays in Java must be declared with their size.
source to share
You can write a method that will flatten many types Object
in List<Integer>
no matter how deeply nested. The method below will work for int[]
, int[][]
, Integer
, Integer[]
, Integer[][]
, List<Integer>
, List<List<Integer>>
, List<int[]>
, etc. (You can easily force it to return int[]
instead).
public static List<Integer> flatten(Object object) {
List<Integer> list = new ArrayList<>();
helper(object, list);
return list;
}
private static void helper(Object object, List<Integer> list) {
if (object instanceof Integer) {
list.add((Integer) object);
} else if (object instanceof int[]) {
for (int a : (int[]) object)
list.add(a);
} else if (object instanceof Object[]) {
for (Object obj : (Object[]) object)
helper(obj, list);
} else if (object instanceof Iterable) {
for (Object obj : (Iterable) object)
helper(obj, list);
} else {
throw new IllegalArgumentException();
}
}
However, such a thing is a really scary idea . If you find yourself writing a checkout load instanceof
and then doing different things based on the result, you've most likely made some bad design decisions.
source to share
You might find it easier to implement Iterator flatten(Object ... items)
- returning an array of the correct size will involve walking through all the records twice (once to count and once to fill). Iterator
can use stack
and smooth everything Iterable
even though they are deeply nested. This way, all arrays and everything would Collection
also be flattened naturally. Also, arrays are so 2014!
It seems to work. It uses the apache.IteratorUtils collections to create an Iterator over primitive arrays.
private static class FlatteningIterator implements Iterator {
// All fall to null at end.
Object o;
// It is an iterator.
Deque<Iterator> stack = new LinkedList();
// The next object to deliver.
Object next;
private FlatteningIterator(Object o) {
this.o = o;
}
@Override
public boolean hasNext() {
// Keep looking until found one or exhausted
while (next == null && (!stack.isEmpty() || o != null)) {
if (o != null) {
// Check o first.
if (o instanceof Iterator) {
// Any kind of iterator?
stack.push((Iterator) o);
} else if (o instanceof Iterable) {
// Any Iterable.
stack.push(((Iterable) o).iterator());
} else if (o.getClass().isArray()) {
// Primitive array! Use apache IteratorUtils
stack.push(IteratorUtils.arrayIterator(o));
} else {
// Just return the object.
next = o;
}
o = null;
}
// Still not found one?
if (next == null) {
// Get it from the current iterator?
Iterator it = stack.peek();
if (it != null) {
if (it.hasNext()) {
// Walk it.
o = it.next();
} else {
// Exhausted the iterator.
stack.remove();
}
}
}
}
return next != null;
}
@Override
public Object next() {
Object n = hasNext() ? next : null;
next = null;
return n;
}
}
public static Iterator<Object> flatten(Object o) {
return new FlatteningIterator(o);
}
public void test() {
List<Object> test = new ArrayList<>();
test.add("Hello");
test.add(Arrays.asList(1, 2, new int[]{3, 6, 9, 12}, 4, 5));
test.add("Bye");
Iterator f = flatten(test);
for (Object o : Iterables.in(f)) {
System.out.print(o);
if (f.hasNext()) {
System.out.print(",");
}
}
System.out.println();
}
source to share
Unlike ruby, java is a statically typed language. This means that you cannot have arrays in it that contain both ints and arrays as elements (well, you can ... but you shouldn't).
So, antialiasing in java would look something like this (I do it with lists because it's a little simpler for example, but it's the same idea):
public static List<String> flatten(List<List<String>> list) {
List<String> result = new LinkedList<~>();
for(List<String> l: list) result.addAll(l);
return result;
}
source to share