CODEWITHSUNDEEP
javasortingcomparatorpriority-queuecomparable
Ashwin Shirva
Ashwin Shirva

Reputation: 1441

Sorting priority queue for a range of elements with higher priority and other elements with lower priority

I have an entity class with the following fields: id, orderNo. Each entity must be stored in a java priority queue. Elements with id between 1 - 3000 have higher priority and must be stored in ascending order of orderNo above the elements with id > 3000. Elements with ids > 3000 are stored in the ascending order of orderNo below the higher priority elements (with ids 1 - 3000).

Eg: 

(1st insertion to queue: id=4000 orderNo=1) 
(2nd insertion to queue: id=5000 orderNo=2) 
(3rd insertion to queue: id=100  orderNo=3)
(4th insertion to queue: id=50   orderNo=4)

Expected sort sequence: 

(id=100  orderNo=3) 
(id=50   orderNo=4) 
(id=4000 orderNo=1) 
(id=5000 orderNo=2)

OrderEntity class: 

public class OrderEntity implements Comparable<OrderEntity> {
    private int id;
    private int getOrderNo;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getOrderNo() {
        return getOrderNo;
    }

    public void setOrderNo(int getOrderNo) {
        this.getOrderNo = getOrderNo;
    }

    @Override
    public int compareTo(OrderEntity arg0) {
        if ((this.getId() >= 1 && this.getId() <= 3000) && (arg0.getId() >= 1 && arg0.getId() <= 3000)) {
            if (this.getOrderNo() > arg0.getOrderNo()) {
                return 1;
            } else {
                return 0;
            }
        } else if ((this.getId() <= 3000) && (arg0.getId() > 3000)) {
            return 1;
        } else if ((this.getId() > 3000) && (arg0.getId() <= 3000)) {
            return 1;
        } else if ((this.getId() > 3000) && (arg0.getId() > 3000)) {
            if (this.getOrderNo() > arg0.getOrderNo()) {
                return 1;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    }
}

OrderProcessor class:

public class OrderProcessor {
    private static int count;
    static Queue<OrderEntity> pq = new PriorityQueue<>();

    public String createOrder(int id) {
        OrderEntity orderEntity = new OrderEntity();
        orderEntity.setId(id);
        count = count + 1;
        orderEntity.setOrderNo(count);
        pq.add(orderEntity);

        String res = "";
        for (OrderEntity rd : pq) {
            res = res + rd.getId() + " " + rd.getOrderNo() + "\n";
        }
        return res.trim();
    }
}

Upvotes: 0

Views: 1410

Answers (2)

Mehdi Javan
Mehdi Javan

Reputation: 1091

In such cases that the natural ordering of the objects is different from your special requirement it's better not to use Comparable because it might have other usages in future. So, the remaining solution is using Comparator which suits your problem very well because your OrderEntity class won't have a dependency on this special compare. the following is a sample code showing the solution:

import java.util.Comparator;
import java.util.PriorityQueue;

public class OrderProcessor {
    public static void main(String[] args) {
        PriorityQueue<OrderEntity> q = new PriorityQueue<>(new OrderEntityComparator());
        q.add(new OrderEntity(4000, 1));
        q.add(new OrderEntity(5000, 2));
        q.add(new OrderEntity(100, 3));
        q.add(new OrderEntity(50, 4));

        while(!q.isEmpty())
            System.out.println(q.poll());
    }

    public static class OrderEntityComparator implements Comparator<OrderEntity> {

        @Override
        public int compare(OrderEntity o1, OrderEntity o2) {
            if(o1.getId() <= 3000 && o2.getId() <= 3000)
                return Integer.compare(o1.getOrderNo(), o2.getOrderNo());
            if(o1.getId() > 3000 && o2.getId() > 3000)
                return Integer.compare(o1.getOrderNo(), o2.getOrderNo());
            if(o1.getId() <= 3000 && o2.getId() > 3000)
                return -1;
            return 1;
        }
    }

    public static class OrderEntity {
        private int id;
        private int orderNo;

        public OrderEntity(int id, int orderNo) {
            this.id = id;
            this.orderNo = orderNo;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public int getOrderNo() {
            return orderNo;
        }

        public void setOrderNo(int orderNo) {
            this.orderNo = orderNo;
        }

        @Override
        public String toString() {
            return "OrderEntity{" +
                    "id=" + id +
                    ", orderNo=" + orderNo +
                    '}';
        }
    }
}

edited:

In case you don't want to remove elements by calling poll method, you have to sort your elements in an array or a List, something like this:

    OrderEntity[] a = new OrderEntity[q.size()];
    q.toArray(a);
    Arrays.sort(a, new OrderEntityComparator());

    for(OrderEntity entity : a)
        System.out.println(entity);

In fact, in such case you don't need to use a PriorityQueue and a simple sort on a List or an array will do the job.

Upvotes: 2

Abhijit Sarkar
Abhijit Sarkar

Reputation: 24518

Here is a solution using Java 8 that doesn't need any complicated comparator implementation. I ran it against both the examples you provided. The trick is to realize that there are 2 groups of ids, those <= 3000, and those above. If you can somehow normalize the numbers in these 2 groups, then you can simply use natural ordering of the normalized ids followed by natural ordering by order number.

public class Main {
    private static Comparator<OrderEntity> orderEntityComparator =
        Comparator.<OrderEntity, Integer>comparing(OrderEntity::getId,
                comparingInt(id -> id / 3000)
        )
                .thenComparingInt(OrderEntity::getOrderNo);

    public static void main(String[] args) {
        PriorityQueue<OrderEntity> queue = new PriorityQueue<>(orderEntityComparator);
        queue.add(new OrderEntity(4000, 1));
        queue.add(new OrderEntity(5000, 2));
        queue.add(new OrderEntity(100, 3));
        queue.add(new OrderEntity(50, 4));

        // 100, 50, 4000, 5000

        queue.clear();

        queue.add(new OrderEntity(100, 1));
        queue.add(new OrderEntity(200, 2));
        queue.add(new OrderEntity(4000, 3));
        queue.add(new OrderEntity(300, 4));

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
        // 100, 200, 300, 4000
    }

    static class OrderEntity {
        private int id;
        private int orderNo;

        public OrderEntity(int id, int orderNo) {
            this.id = id;
            this.orderNo = orderNo;
        }

        public int getId() {
            return id;
        }

        public int getOrderNo() {
            return orderNo;
        }

        @Override
        public String toString() {
            return String.format("(id=%d, orderNo=%d)", id, orderNo);
        }
    }
}

Upvotes: 0

Related Questions