3
\$\begingroup\$

I've implemented a generic data structure to keep track of the median in a streaming list of numbers. I was hoping to gather the community's feedback on code style and taste.

package ad.collections;

import sun.reflect.generics.reflectiveObjects.NotImplementedException;

import java.util.*;

/**
 * Created by adhulipa on 10/28/16.
 */
public class MedianHeap<E extends Number & Comparable> implements Queue<Number> {

    private enum QueueSize { BIGGER, SMALLER };


    private PriorityQueue<E> lowers;
    private PriorityQueue<E> uppers;

    public MedianHeap() {
        super();
        lowers = new PriorityQueue<E>(Collections.reverseOrder());
        uppers = new PriorityQueue<E>();
    }

    @Override
    public boolean offer(Number number) {
        boolean offered;
        if ( !lowers.isEmpty() && isLessThan(number, lowers.peek())) {
            // Cast number to actual type E
            offered = lowers.offer( (E) number);
        } else if ( !uppers.isEmpty() && isGreaterThan(number, uppers.peek())) {
            offered = uppers.offer( (E) number);
        } else {
            // Otherwise, add new number to smaller of the two queues
            Queue smallerQueue = selectQueue(QueueSize.SMALLER);
            offered = smallerQueue.offer(number);
        }

        rebalance();
        return offered;
    }

    @Override
    public Double peek() {
        return this.median(false);
    }

    @Override
    public int size() {
        return lowers.size() + uppers.size();
    }

    @Override
    public boolean isEmpty() {
        return lowers.isEmpty() && uppers.isEmpty();
    }

    @Override
    public Double poll() {
        Double median = this.median(true);
        rebalance();
        return median;
    }

    private void rebalance() {
        while ( Math.abs(lowers.size() - uppers.size()) > 1 ) {
            Queue bigger  = selectQueue(QueueSize.BIGGER);
            Queue smaller = selectQueue(QueueSize.SMALLER);
            smaller.offer(bigger.poll());
        }
    }

    private Double median(boolean isPoll) {
        Double median = null;

        if ( queueSizesEqual() ) {
            median = (lowers.peek().doubleValue() + uppers.peek().doubleValue()) / 2;

            if (isPoll) {
                lowers.poll();
                uppers.poll();
            }

        } else { // peek() bigger queue
            Queue bigger = selectQueue(QueueSize.BIGGER);
            Number medianNumber = (Number) bigger.peek();
            median = medianNumber.doubleValue();

            if (isPoll) {
                bigger.poll();
            }
        }

        return median;

    }

    private boolean queueSizesEqual() {
        return lowers.size() == uppers.size();
    }

    private Queue selectQueue(QueueSize which) {
        Queue smaller = lowers;
        Queue bigger  = uppers;
        Queue answer;

        if (uppers.size() < lowers.size()) {
            smaller = uppers;
            bigger  = lowers;
        } else if (uppers.size() > lowers.size() ){
            bigger  = uppers;
            smaller = lowers;
        }

        switch (which ){

            case BIGGER:
                answer = bigger;
                break;

            case SMALLER:
                answer = smaller;
                break;

            default:
                answer =  smaller;
        }

        return answer;
    }

    private boolean isLessThan(Number newItem, E currentMin) {
        E item = (E) newItem;
        return item.compareTo(currentMin) < 0;
    }

    private boolean isGreaterThan(Number newItem, E currentMax) {
        E item = (E) newItem;
        return item.compareTo(currentMax) > 0;
    }

    /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
        Not Implemented methods below
     * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

    @Override
    public boolean remove(Object o) throws NotImplementedException { throw new NotImplementedException(); }

    @Override
    public boolean contains(Object o) {
        throw new NotImplementedException();
    }

    @Override
    public Iterator<Number> iterator() {
        throw new NotImplementedException();
    }

    @Override
    public Object[] toArray()  {
        throw new NotImplementedException();
    }

    @Override
    public <T> T[] toArray(T[] a)  {
        throw new NotImplementedException();
    }

    @Override
    public boolean add(Number i) throws NotImplementedException {
        throw new NotImplementedException();
    }

    @Override
    public Number remove()  {
        throw new NotImplementedException();
    }

    @Override
    public boolean containsAll(Collection<?> c)  {
        throw new NotImplementedException();
    }

    @Override
    public boolean addAll(Collection<? extends Number> c) {
        throw new NotImplementedException();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new NotImplementedException();
    }

    @Override
    public boolean retainAll(Collection<?> c)  {
        throw new NotImplementedException();
    }

    @Override
    public void clear()  {
        throw new NotImplementedException();
    }

    @Override
    public Number element()  {
        throw new NotImplementedException();
    }

}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

A few of my personal pet hates:

  • You should avoid boxed Doubles as much as possible. If you are looking for a double that you can set to null, you should consider using the OptionalDouble instead.
  • You are violating the contract of the Queue interface. Notably the poll method, which is really only supposed to remove one number from the queue (yours can remove two in some circumstances), and can return an item that was never put in the queue in the first place.
  • The number of NotImplementedExceptions you are throwing around tells me that the Queue interface is not the right one to implement for this purpose. (Frankly, that type of exception should not exist, as it only encourages bad practice.)
\$\endgroup\$
3
  • \$\begingroup\$ 1. Thank you for the note on OptionalDouble -- 2. & 3. That makes sense. This is not a Queue. (i.e. violates the "is-a" rule) What I'm really looking for is a Heap interface. Would you say that it is better to define a Heap interface myself with only the methods (offer, poll, peek, remove, isEmpty & size) ? My MedianHeap can implement this new Heap interface. \$\endgroup\$
    – cafed00d
    Oct 29, 2016 at 22:46
  • \$\begingroup\$ Java does have a heap interface (albeit by a different name - PriorityQueue. That said, I don't think it's appropriate for what you're trying to do, for exactly the same reasons as Queue is not appropriate. I would consider designing an interface that describes only what you need method-wise (why do you need a poll method, for example?). \$\endgroup\$
    – Joe C
    Oct 30, 2016 at 6:44
  • \$\begingroup\$ That sounds good. I'll define my own interface for this problem. I defined the poll method because I was implementing the Queue interface. I thought this data structure as being-a-heap from the get-go. But, now I see that poll is unnecessary. I would instead have a remove(Number element) method which will remove a specific element from the array. Users could also use this method to remove the median if they wished to do so. \$\endgroup\$
    – cafed00d
    Oct 31, 2016 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.