getNext() kind of implementation while doing join over multiple arraylists

Hi,

I want to do the following thing:

Suppose I have k arraylist of any data type. Each list ai has ti elements.


I want to perform join operations using those k lists. However, I want to do the join by implementing a getNext() interface. Where getNext() would be called from the main() with those k lists as input arguments, and it will return me the next join results.

As an example, suppose I have 2 lists a1 and a2. a1 has elements {1,2}, a2 has elements {11,12}. Their join or cartesian product is {1,11} , {1,12}, {2,11}, {2,12}. But I do not want to precompute all the results in the first place. However, each time I need a new result, I will call getNext(a1,a2) from main, and it will return me the next result.

What is the best way to implement this. A sample code would be highly appreciated.

thanks,
SBR

I thought a "join" was an intersection. But anyway...

The iterator needs an index into the cartesian product, and the obvious one to use would be an int[k]. Increment the index much as you would increment a number given its base-10 representation (except that the entry at place k-j would "carry" when it hits tj - for example)

Thanks! Will you please give an example. That will be extremely useful. Or may be if you explain you algorithm using my example would be great

I have 3 lists

A1 has 4 elements
A2 has 10 elements
A3 has 17 elements

If you please explain your point, would be great.

Thanks much!

No, sorry, I'm not going to write the code for you. Others might.

I was just making the observation that a reasonable index for a product is the product of the indices.

A cute refinement might be to only define the Iterator<List<E>> product iterator of two things that can be either Iterable<E> or Iterable<List<E>>. Since you could have the product iterator itself implement Iterable<List<E>> big products would then be made out of little ones.

Thanks much for your help. I didnt expect you to write the code, but I had some doubts on the logic. However it is clear now, after I have worked out a small example myself. Thanks a million.

Quote:

---

I have 3 lists

A1 has 4 elements
A2 has 10 elements
A3 has 17 elements

If you please explain your point, would be great.

---

Consider

A1: a1,a2,a3,a4
A2: b1,b2,b3,...,b10
A3: c1,c2,c3,...,c17

The iterator's state would consist of references to the three underlying lists and an int[] array of size three. I'm calling it the index array and it would be initialised to [0,0,0].

When the caller says getNext() the iterator would take its index array [a,b,c] and return a new list which it populates from the three underlying arrays. The returned list would consist of A1.get(a) A2.get(b) and A3.get(c). Then the iterator would (try to) increment the index array so that it is ready for the next getNext().

This array increments as follows:

[0,0,0] <-- initial value
[0,0,1]
[0,0,2]
[0,0,3]
[0,1,0]<-- because 4 is A1.size() and that's too big
...
[0,9,3]
[1,0,0] <-- because 4 is A1.size() again, and 10 would be A2.size and that is also too big
...
[16,9,3]
null <-- hasNext() should return false at this point

[Edit] Our posts crossed. I'm glad you got it sorted out.

thanks! I got it running... your clues helped a lot :)

If those arrays aren't too large, i.e. the product of their lengths fit in an int, you can keep a single counter i in the range [0, p) where p is the product of the array lengths; finding the individual indexes given the counter i is easy:

Code:

---

int[] indexes= ...;
int[] lengths= ...;
for (int j= 0; i < lengths.length; j++) {
  indexes[j]= i%lengths[j];
  i/= lengths[j];
}

---

kind regards,

Jos