在包含日期的對象列表中搜索

Question

假設我有一個包含Date字段的消息列表List<Message> conversation。

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

而且我想找到一個時間跨度內的所有消息，由兩個Date對象，fromDate和toDate分隔：

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

郵件列表是按時間排序（舊郵件被前新加那些）。現在，我可以從頭開始遍歷整個列表，並填充messagesInRange，添加指定範圍內的所有消息。一旦我到達比toDate更近的日期，我可以結束迭代，因爲我知道列表已排序。

但是也許在指定的範圍內沒有消息，並且從頭開始迭代是浪費時間。我想知道一個有效的方式來獲取列表中第一條消息的引用，並且從那裏開始迭代。也許這可以用二進制搜索來完成？

Answer 1

• 實現消息比較器;
• 使用SortedSet存儲消息的排序結構。

Java代碼：

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()); 
} 

實現示例：

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); 
    } 
}