Results 1 to 8 of 8
 12132011, 06:53 AM #1Member
 Join Date
 Dec 2011
 Posts
 4
 Rep Power
 0
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
 12132011, 07:05 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,712
 Rep Power
 15
Re: getNext() kind of implementation while doing join over multiple arraylists
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 base10 representation (except that the entry at place kj would "carry" when it hits tj  for example)Last edited by pbrockway2; 12132011 at 07:09 AM.
 12132011, 07:14 AM #3Member
 Join Date
 Dec 2011
 Posts
 4
 Rep Power
 0
Re: getNext() kind of implementation while doing join over multiple arraylists
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!
 12132011, 07:45 AM #4Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,712
 Rep Power
 15
Re: getNext() kind of implementation while doing join over multiple arraylists
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.
 12132011, 07:53 AM #5Member
 Join Date
 Dec 2011
 Posts
 4
 Rep Power
 0
Re: getNext() kind of implementation while doing join over multiple arraylists
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.
 12132011, 07:59 AM #6Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,712
 Rep Power
 15
Re: getNext() kind of implementation while doing join over multiple arraylists
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.
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.
 12132011, 08:24 AM #7Member
 Join Date
 Dec 2011
 Posts
 4
 Rep Power
 0
Re: getNext() kind of implementation while doing join over multiple arraylists
thanks! I got it running... your clues helped a lot :)
 12132011, 08:30 AM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,401
 Blog Entries
 7
 Rep Power
 25
Re: getNext() kind of implementation while doing join over multiple arraylists
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:
Java Code:int[] indexes= ...; int[] lengths= ...; for (int j= 0; i < lengths.length; j++) { indexes[j]= i%lengths[j]; i/= lengths[j]; }
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

what kind of application is this?
By mymark in forum SWT / JFaceReplies: 0Last Post: 08032011, 12:11 AM 
Hash join algorithm implementation
By raziya in forum JDBCReplies: 0Last Post: 07152011, 10:29 AM 
Kind of stuck
By Nicky Swans in forum New To JavaReplies: 8Last Post: 10222010, 02:46 PM 
Question on Multiple Listeners implementation
By StormyWaters in forum AWT / SwingReplies: 14Last Post: 06112010, 08:28 PM 
Total Newbie, Be Kind :)
By dazzas in forum New To JavaReplies: 11Last Post: 04262008, 10:54 PM
Bookmarks