Find an object in a list without iterating it

Question

I have a class with 3 properties:

private static class OrderListItem {
    public int price;
    public int size;
    public Type type;
}

Items of this class are added in a list. List<OrderListItem> orders_book = new ArrayList<>();

I want to find an object in a list with a specified price. But size and type do not matter. Can I do something like this:

int index = orders_book.indexOf(new OrderListItem(price, **any size**, **any type**)); ?

Or I just must do a "loop" search?

Answer 1

If you need to retrieve an instance with a desired price, then you could use a collection stream with the filter and findAny operations.

int myPrice = /* any value you want */

//This will retrieve an instance with the disired price or null if none is found
OrderListItem item = orders_book.stream()
        .filter(i -> i.getPrice() == myPrice)
        .findFirst()
        .orElse(null);

Alternatively, if you want to retrieve the index of the object with the desired price, then you have two options:

1. Redefine the equals method of your OrderListItem class, to equal two OrderListItems by their price, since the documentation of the indexOf method retrieves an element by its equals method. However, I wouldn't lean towards this solution, as in my opinion the sole price is not enough to equal two order items, but you definitely know better than me the kind of problem you're modelling. So, I'll leave the choice to you. Furthermore, if you redefine the equals method you should also redefine the hashCode method as the general hashcode contract states.

https://docs.oracle.com/javase/8/docs/api/java/util/List.html#indexOf-java.lang.Object-

Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

class OrderListItem {
    public int price;
    public int size;
    public Type type;

    /* ... your implementation ...*/

    @Override
    public int hashCode() {
        return Objects.hash(price);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (this == obj) return true;
        if (getClass() != obj.getClass()) return false;
        OrderListItem other = (OrderListItem) obj;
        return Objects.equals(price, other.price);
    }
}

2. Not redefining the equals method, but retrieving the exact instance with a stream (like in the first snippet) and then using that same instance as a parameter for the indexOf invocation.

int myPrice = /* any value you want */

//This will retrieve an instance with the disired price or null if none is found
OrderListItem item = orders_book.stream()
        .filter(i -> i.getPrice() == myPrice)
        .findFirst()
        .orElse(null);

//Retrieving the index
int index = orders_book.indexOf(item);

Answer 2

I'm offering this answer as a possibility although it may exceed your actual requirements. Using some pre-defined predicates it allows any number of matching, consecutive items to be returned in a List. An empty list will be returned if no match is found.

But first, if you want the index (and maybe the value of the object) you can do it like this with no modification of your class.

• this uses an IntStream to stream all possible indices.
• it maps the index and the object at that index into a Map.entry
• then it filters using the value of the entry against the desired attribute.
• and returns the first one encountered or an Entry with -1 and null. (AbstractMap.SimpleEntry was used here to allow the null value)

int desiredPrice = 3;
Entry<Integer, OrderListItem> result = IntStream
        .range(0, orderList.size())
        .mapToObj(i -> Map.entry(i, orderList.get(i)))
        .filter(e -> e.getValue().getPrice() == desiredPrice)
        .findFirst().orElse(new AbstractMap.SimpleEntry<>(-1,null));

To facilitate the demonstration the following record is used in lieu of a class definition. A class can be directly substituted for this. A Type enum is also provided.

enum Type {
    FICTION, TECHNICAL, BIOGRAPHY
}

private record OrderListItem(int getPrice, int getSize,
        Type getType) {
    
    @Override
    public String toString() {
        return String.format("[%s, %s, %s]", getPrice, getSize,
                getType);
    }
}

Now define some predicates. Each takes an orderListItem object and a Type. The comparison method (equals or == ) is dependent on the attribute type. This predicate and the desired attribute value will be supplied to a method as shown later. Even though you are only interested in price, the others were easy enough to add.

static BiPredicate<OrderListItem, Integer> CHECK_PRICE =
        (order, val) -> order.getPrice() == val;

static BiPredicate<OrderListItem, Type> CHECK_TYPE =
        (order, val) -> order.getType().equals(val);

static BiPredicate<OrderListItem, Integer> CHECK_SIZE =
            (order, val) -> order.getSize() == val;

Some data

List<OrderListItem> orderList =
        ArrayList<>(List.of(new OrderListItem(3, 20, Type.FICTION),
                new OrderListItem(4, 20, Type.TECHNICAL),
                new OrderListItem(5, 20, Type.TECHNICAL),
                new OrderListItem(3, 30, Type.FICTION),
                new OrderListItem(4, 30, Type.FICTION),
                new OrderListItem(5, 30, Type.TECHNICAL),
                new OrderListItem(3, 40, Type.FICTION),
                new OrderListItem(4, 40, Type.BIOGRAPHY),
                new OrderListItem(5, 40, Type.FICTION),
                new OrderListItem(3, 50, Type.FICTION),
                new OrderListItem(4, 50, Type.BIOGRAPHY),
                new OrderListItem(5, 50, Type.BIOGRAPHY)));

Demo

List<OrderListItem> matches =
        retrieve(orderList, CHECK_SIZE, 20, 2);
    
matches.forEach(System.out::println);

prints

[3, 20, FICTION]
[4, 20, TECHNICAL]

The method takes the following arguments.

• the order list
• the predicate for comparison
• the attribute value to compare to
• the desired return count of successful matches (a negative value will result in all matches being returned).

The method works by simple iteration over the orders, applying the predicate to the order and attribute. If a match is found, it is added to the return list and the count is decremented. When the count reaches 0 or the entire list is checked, the list will be returned.

public static <T> List<OrderListItem> retrieve(
        List<OrderListItem> orders,
        BiPredicate<OrderListItem, T> pred, T attribute,
        int count) {
    List<OrderListItem> matches = new ArrayList<>();
    for (OrderListItem order : orders) {
        if (pred.test(order, attribute)) {
            matches.add(order);
            if (--count == 0) {
                break;
            }
        }
    }
    return matches;
}

Performance

Not the best test as compared to JMH but a rough idea.

• First I added the data list to itself 20 times to create a large list.
• The I repeated the above lookup for all records sans the printout.

for (int i = 0; i < 20; i++) {
    orderList.addAll(orderList);
}
System.out.printf("%,d total objects%n",orderList.size());
    
long time = System.nanoTime();
List<OrderListItem> matches =
        retrieve(orderList, CHECK_SIZE, 20, -1);
System.out.println("Execution time ~ "+(System.nanoTime()-time)/1e9 + " sec");

prints

12,582,912 total objects
Execution time ~ 0.632698253 sec

With no matches found for the entire list, the result was Execution time ~ 0.033943752 sec.

For matching the entire list the result was Execution time ~ 0.939900075 sec.

The difference in time is mostly due (imo) to the backing array having to be updated as the capacity is increased. This requires several recopyings of the array. By setting the initial capacity of the returned list to orders.size(), the result for matching and returning all elements is improved.

For matching the entire list with adjusted capacity the result was Execution time ~ 0.19100866 sec

I'm running Windows on an Intel 4 core, I7 processor.

I have no idea how any of the above relates to your requirements but its there for your edification.