CODEWITHSUNDEEP
javalistsearch
dazedviper
dazedviper

Reputation: 1022

Searching in a list of objects containing dates

Suppose I have a list of messages List<Message> conversation that have a Date field.

public class Message {
    private Date time;
    ...
}

And I want to find all messages within a timespan, delimited by two Date objects, fromDate and toDate:

public List<Message> getMessagesInRange(final Date fromDate, final Date toDate, final List<Message> conversation) {
    List<Message> messagesInRange = new ArrayList<Message>();
    ...
    return messagesInRange;
}

The list of messages is sorted by time (older messages were added before newer ones). Now, I could iterate through the entirety of the list from the beginning and populate messagesInRange adding all of the messages that are within the range specified. Once I reach a more recent date than toDate, I could end the iteration since I know the list is sorted.

But maybe there are no messages within the specified range, and iterating from the beginning was a waste of time. I'd like to know of an efficient way of getting a reference to the first message in the list that is within the range, and iterate from there. Perhaps this can be done with a binary search?

Upvotes: 0

Views: 1451

Answers (1)

ursa
ursa

Reputation: 4601

  • implement messages comparator;
  • use SortedSet to store sorted structure of your messages.

Java code:

MessageComparator messageComparator = new MessageComparator();
SortedSet<Message> allMessages = new TreeSet<>(messageComparator);

public List<Message> getMessagesInRange(final Date fromDate, final Date toDate, final List<Message> conversation) {
    return new ArrayList<Message>(allMessages.subSet(
        messageComparator.minFrom(fromDate), true,  messageComparator.maxFrom(toDate), true).values());
}

Implementation examples:

public class Message {
    private static final AtomicLong ID_COUNTER = new AtomicLong();
    private final long timestamp;
    private final String text;
    private final long id;

    public Message(Date time, String text) {
        this(time, text, ID_COUNTER.incrementAndGet());
    }

    private Message(Date time, String text, long id) {
        this.timestamp = time.getTime(); // (a) Date is mutable & (b) better memory consumption
        this.text = text == null ? "" : text;
        this.id = id;
    }

    ... // getters & logic (if any)

    // Keep in mind - equals & compareTo should be in sync.
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (null == obj) {
            return false;
        }
        if (!obj.getClass().equals(getClass())) {
            return false;
        }
        Message that = (Message) obj;
        return timestamp == that.timestamp && id == that.id && message.equals(that.message);
    }
}

public class MessageComparator implements Comparator<Message> {
    // Keep in mind - equals & compareTo should be in sync.
    public int compare(Message m1, Message m2) {
        if (m1 == null ? m2 == null : m1.equals(m2)) {
            return 0;
        }
        if (m1 == null) {
            return -1;
        }
        if (m2 == null) {
            return 1;
        }
        int c = Long.compare(m1.timestamp, m2.timestamp);
        if (c != 0) {
            return c;
        }
        c = m1.text.compareTo(m2.text);
        if (c != 0) {
            return c;
        }
        c = Long.compare(m1.id, m2.id);
        return c;
    }

    public Message minFrom(Date date) {
        return new Message(new Date(date.getTime()), null, -1);
    }

    public Message maxFrom(Date date) {
        return new Message(new Date(date.getTime() + 1), null, -1);
    }
}

Upvotes: 1

Related Questions