Results 1 to 8 of 8
  1. #1
    SBR
    SBR is offline Member
    Join Date
    Dec 2011
    Posts
    4
    Rep Power
    0

    Default 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

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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 base-10 representation (except that the entry at place k-j would "carry" when it hits tj - for example)
    Last edited by pbrockway2; 12-13-2011 at 06:09 AM.

  3. #3
    SBR
    SBR is offline Member
    Join Date
    Dec 2011
    Posts
    4
    Rep Power
    0

    Default 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!

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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.

  5. #5
    SBR
    SBR is offline Member
    Join Date
    Dec 2011
    Posts
    4
    Rep Power
    0

    Default 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.

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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.
    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.

  7. #7
    SBR
    SBR is offline Member
    Join Date
    Dec 2011
    Posts
    4
    Rep Power
    0

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

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

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default 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];
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. what kind of application is this?
    By mymark in forum SWT / JFace
    Replies: 0
    Last Post: 08-03-2011, 12:11 AM
  2. Hash join algorithm implementation
    By raziya in forum JDBC
    Replies: 0
    Last Post: 07-15-2011, 10:29 AM
  3. Kind of stuck
    By Nicky Swans in forum New To Java
    Replies: 8
    Last Post: 10-22-2010, 02:46 PM
  4. Question on Multiple Listeners implementation
    By StormyWaters in forum AWT / Swing
    Replies: 14
    Last Post: 06-11-2010, 08:28 PM
  5. Total Newbie, Be Kind :)
    By dazza-s in forum New To Java
    Replies: 11
    Last Post: 04-26-2008, 10:54 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •