Java range query using TreeMap.subMap()


  • 10

    Given the granularity we can set a lower bound and upper bound of timestamp so we could do a range query using TreeMap. To get the lower bound we append a suffix of "2000:01:01:00:00:00" to the prefix of s and to get the upper bound we append a suffix of "2017:12:31:23:59:59" to the prefix of e.

    public class LogSystem {
        private String min, max;
        private HashMap<String, Integer> map;
        private TreeMap<String, LinkedList<Integer>> logs;
        public LogSystem() {
            min = "2000:01:01:00:00:00";
            max = "2017:12:31:23:59:59";
            map = new HashMap<>();
            map.put("Year", 4);
            map.put("Month", 7);
            map.put("Day", 10);
            map.put("Hour", 13);
            map.put("Minute", 16);
            map.put("Second", 19);
            logs = new TreeMap<>();
        }
    
        public void put(int id, String timestamp) {
            if(!logs.containsKey(timestamp)) logs.put(timestamp, new LinkedList<>());
            logs.get(timestamp).add(id);
        }
    
        public List<Integer> retrieve(String s, String e, String gra) {
            int index = map.get(gra);
            String start = s.substring(0, index)+min.substring(index), end = e.substring(0, index)+max.substring(index);
            NavigableMap<String, LinkedList<Integer>> sub = logs.subMap(start, true, end, true);
            LinkedList<Integer> ans = new LinkedList<>();
            for (Map.Entry<String, LinkedList<Integer>> entry : sub.entrySet()) {
                ans.addAll(entry.getValue());
            }
            return ans;
        }
    }

  • 0
    H

    @dreamchase said in Java range query using TreeMap.subMap():

    NavigableMap

    I got this error: error: cannot find symbol: class NavigableMap


  • 0
    F

    @hpnhxxwn change it to Map<String, LinkedList<Integer>>, that will work


  • 0
    Z

    Similar idea with TreeMap.tailMap(Object fromKey)

    class LogSystem {
        TreeMap<String, Set<Integer>> logMap;
        public LogSystem() {
            logMap=new TreeMap<>();
        }
        
        public void put(int id, String timestamp) {
            logMap.putIfAbsent(timestamp, new HashSet<>());
            logMap.get(timestamp).add(id);
        }
        
        public List<Integer> retrieve(String s, String e, String gra) {
            s=format(s, gra, true); e=format(e, gra, false);
            
            List<Integer> res=new ArrayList<>();
            String ceilingKey=logMap.ceilingKey(s);
            if (ceilingKey==null) return res;
            
            for (String timestamp:logMap.tailMap(ceilingKey).keySet())
                 if (timestamp.compareTo(e)<=0) res.addAll(logMap.get(timestamp));           
            return res;
        }
        
        private String format(String timestamp, String gra, boolean start){
            if (gra.equals("Year")){
                timestamp=timestamp.substring(0,  4);
                timestamp+=(start)?":00:00:00:00:00":":12:31:23:59:59";
            }else if (gra.equals("Month")){
                timestamp=timestamp.substring(0,  7);
                timestamp+=(start)?":00:00:00:00":":31:23:59:59";
            }else if (gra.equals("Day")){
                timestamp=timestamp.substring(0, 10);
                timestamp+=(start)?":00:00:00":":23:59:59";
            }else if (gra.equals("Hour")){
                timestamp=timestamp.substring(0, 13);
                timestamp+=(start)?":00:00":":59:59";
            }else if (gra.equals("Minute")){
                timestamp=timestamp.substring(0, 16);
                timestamp+=(start)?":00":":59";
            }
            return timestamp;
        }
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.