Inner join of two ArrayLists purely in Java

Question

Is there a way to do the inner join of two ArrayLists of two different objects based on one field?

Let's say I've got:

ArrayList<Car>
ArrayList<Owner>

Car would have these attributes: Weight, Top speed, OwnerId

Owner would have these attributes: Name, Age, Id

The result would be an ArrayList<Result> with attributes: Weight, Top speed, Id, Name, Age

And I want to make an inner join of these 2 based on a single field called Id. Is there any optimal way to do that without using a database or nested loops?

Answer 1

Assuming that the type of Id implements Comparable:

Firstly, sort the lists, so that the Ids are in ascending order:

Collections.sort(cars, new Comparator<Car>() {
  @Override public int compare(Car a, Car b) {
    return a.OwnerId.compareTo(b.OwnerId);
  }
});
Collections.sort(owners, new Comparator<Owner>() {
  @Override public int compare(Owner a, Owner b) {
    return a.Id.compareTo(b.Id);
  }
});

Then, loop through the elements:

int ci = 0, oi = 0;
while (ci < cars.size() && oi < owners.size()) {

Walk through the cars list looking for a contiguous block where the Id field is the same:

  Id idStart = cars.get(ci).OwnerId;
  int carStart = ci;
  while (ci < cars.size() && cars.get(ci).OwnerId.equals(idStart)) {
    ++ci;
  }
  List<Car> carsWithId = cars.subList(carStart, ci);

Then skip past all of the Owner instances with smaller Ids:

  while (oi < owners.size() && owners.get(oi).Id.compareTo(idStart) < 0) {
    ++oi;
  }

Then find the block of Owner instances with the same Id as the cars:

  int ownerStart = oi;
  while (oi < owners.size() && owners.get(oi).Id.equals(idStart)) {
    ++oi;
  }
  List<Owner> ownersWithId = owners.subList(ownerStart, oi);

Finally, do something with the car/owner pairs with equal ids:

  for (Car car : carsWithId) {
    for (Owner owner : ownersWithId) {
      System.out.println(car + ", " + owner);
    }
  }
}

Answer 2

Assuming you:

• use Java 8
• you have List<Car> cars and List<Owner> owners
• Result has a constructor that takes a Car and an Owner

This is how you can get List<Result>:

final Map<Integer, Owner> ownersById = owners.stream()
   .collect(Collectors.toMap(k -> k.id, k -> k));
final List<Result> results = cars.stream()
   .map(car -> new Result(car, ownersById.get(car.OwnerId)))
   .collect(Collectors.toList());

Which:

• creates a java.util.Map instance where the key is owner id and the value is the owner instance
• then iterates through the cars and creates Result instances, which contain a reference to the car and the owner, which is looked up using the previously created map

Answer 3

You can use Collection.retainAll() method.

You have to implement in a special way (see code below) equals method inside your Car and Owner classes.

For example, supposing that both Car and Owner classes have a String id property the code would be:

public static void main(String[] args) {        
    ArrayList<Car> list1 = new ArrayList<Car>();
    list1.add(new Car("ID1"));
    list1.add(new Car("ID2"));
    list1.add(new Car("ID3"));


    ArrayList<Owner> list2 = new ArrayList<Owner>();
    list2.add(new Owner("ID1"));
    list2.add(new Owner("ID3"));
    list2.add(new Owner("ID4"));

    list1.retainAll(list2);
    System.out.println(list1);
}

static class Car
{
    public Car(String id)
    {
        super();
        this.id = id;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;

        if (obj instanceof Owner)
        {
            Owner other = (Owner) obj;
            if (id == null)
            {
                if (other.id != null)
                    return false;
            }
            else if (!id.equals(other.id))
                return false;
        }
        else if (obj instanceof Car)
        {
            Car other = (Car) obj;
            if (id == null)
            {
                if (other.id != null)
                    return false;
            }
            else if (!id.equals(other.id))
                return false;
        }
        return true;
    }

    @Override
    public String toString()
    {
        return "Car [id=" + id + "]";
    }

    public String id;
}

static class Owner
{
    public Owner(String id)
    {
        super();
        this.id = id;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (obj instanceof Owner)
        {
            Owner other = (Owner) obj;
            if (id == null)
            {
                if (other.id != null)
                    return false;
            }
            else if (!id.equals(other.id))
                return false;
        }
        else if (obj instanceof Car)
        {
            Car other = (Car) obj;
            if (id == null)
            {
                if (other.id != null)
                    return false;
            }
            else if (!id.equals(other.id))
                return false;
        }


        return true;
    }

    @Override
    public String toString()
    {
        return "Owner [id=" + id + "]";
    }

    public String id;
}

The output will be:

[Car [id=ID1], Car [id=ID3]]

Obviously in this case you'll have a Car list, if you want another type you can make sure that both classes inherit from the same super class or you can make sure that both classes implements the same interface and than manage that interface type.

Answer 4

It is not possible the way you think of it, especially ArrayList can contain only one sort of type (or the subtypes / implementing classes). But it could be a solution for you to use another datastructure that maps the objects by their ids.

HashMap<Integer, HashMap<Car, Owner>> map;

Edit: The Integer-type in the HashMap could be used to store the id which is the connection between the car and the owner. If you do something like:

map.get(10)

it will return as HashMap instance, containing one car as a key and one owner as the coresponding value which both should have the id 10. But this is not implicit, you have to take sure of that by creating the Map.

Also, you could write a class that "maps" the inner join:

public class CarToOwner() {
     private Car car;
     private Owner owner;
}

Edit: If you have a class which contains the car and the owner, it maps directly the relationship between them. You have to take sure either that the id of both types is the same as the connection between them when creating an instance of the CarToOwner-class.

In fact, this is not a really clean solution belonging to some purposes. I would only use this as a "quick and dirty" approach for showing a table in a GUI.

Edit: For cars with multiple owners or owners with multiple cars, it is necessary to store the attributes in lists in CarToOwner or create multiple CarToOwner-instances.

Answer 5

First iterate over the List<Car> (you should work with the Interface and not the implementation) and add each element in a Map<Integer, Car>. (I suppose the ID is unique).

Then iterate over the List<Owner> and store the result in List<Result>. Of course you will need a constructor for Result that takes a Car and an Owner.

No nested loops here :)

Answer 6

If you just want the intersection of the two arrays, you just have to loop on one list and whenever you find an element in the other list that have a matched ID to the current loop element, put it on a third list (the one that you want to hold the intersection elements)