Descriptive and clean Java code


  • 0
    R
    class AllOne {
        class Bucket {
            public int count;
            public Bucket prev; 
            public Bucket next;
            public Set<String> set;
            public Bucket(int count) {
                this.count = count;
            }
        }
        
        
        Bucket head;
        Bucket tail;
        Map<String, Bucket> map;
            
        /** Initialize your data structure here. */
        public AllOne() {
            head = new Bucket(0);
            tail = new Bucket(0);
            head.next = tail;
            tail.prev = head;
            map = new HashMap<>();
        }
        
        public Bucket createBucket(Bucket old, int count) {
            Bucket bucket = new Bucket(count);
            old.prev.next = bucket;
            bucket.prev = old.prev;
            bucket.next = old;
            old.prev = bucket;
            bucket.set = new HashSet<>();
            return bucket;
        }
        
        public void removeBucket(Bucket bucket) {
            bucket.prev.next = bucket.next;
            bucket.next.prev = bucket.prev;
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(!map.containsKey(key)) {
                Bucket bucket;
                if(tail.prev.count != 1) {
                    bucket = createBucket(tail, tail.count + 1);
                    map.put(key, bucket);
                } else {
                    map.put(key, tail.prev);
                    bucket = map.get(key);
                }
                bucket.set.add(key);
            } else {
                Bucket bucket = map.get(key);
                bucket.set.remove(key);
                if(bucket.prev.count == bucket.count + 1) {
                    bucket.prev.set.add(key);
                    map.put(key, bucket.prev);
                } else {
                    Bucket newBucket = createBucket(bucket, bucket.count + 1);
                    newBucket.set.add(key);
                    map.put(key, newBucket);
                }
                if(bucket.set.size() == 0) {
                    removeBucket(bucket);
                }
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if(!map.containsKey(key))
                return;
            Bucket bucket = map.get(key);
            bucket.set.remove(key);
            if(bucket.count == 1) {
                map.remove(key);
            } else {
                if(bucket.next.count == bucket.count - 1) {
                    bucket.next.set.add(key);
                    map.put(key, bucket.next);
                }
                else {
                    Bucket b = createBucket(bucket.next, bucket.count - 1);
                    b.set.add(key);
                    map.put(key, b);
                }
            }
            
            if(bucket.set.size() == 0)
                removeBucket(bucket);
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if(head.next.count == 0 || head.next.set.size() == 0)
                return new String();
            Iterator iterator = head.next.set.iterator();
            return (String)iterator.next();
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if(tail.prev.count == 0 || tail.prev.set.size() == 0)
                return new String();
            Iterator iterator = tail.prev.set.iterator();
            return (String)iterator.next();
        }
    }
    
    /**
     * Your AllOne object will be instantiated and called as such:
     * AllOne obj = new AllOne();
     * obj.inc(key);
     * obj.dec(key);
     * String param_3 = obj.getMaxKey();
     * String param_4 = obj.getMinKey();
     */
    

Log in to reply
 

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