Make Priority Queues follow FIFO order when priority is same in Java

0
votes

I am working on a algorithm where in I want to maintain FIFO order in a priority queues for elements having same priority when removing elements from this prioroty queue.

Although, I have seen to solution to automatically-incremented sequence number as a secondary key, and use it to break ties, link here and I need something similar but the issue I am facing is that the element I want to compare - TestItemChange (class in below example) doesnt implement comparable and I cant (and dont want to) modify this to make it implement . So right now, without the FIFO ordering in priority queues I was using a comparator method being sent while creating it.

The only thing I need now is it make it FIFO when same priority. How can I implement the automatically-incremented sequence number in below solution without making TestItemChange implement comparable? I havent worked much on these interfaces and any guidance here will be really helpful.

Any leads will be really helpful.

CODE --

import java.util.*;
import java.util.stream.Collectors;

public class PriorityQueues {

  public static void main(String []args){
    TestPriorityQueue obj = new TestPriorityQueue();
    obj.build();
  }

  static class TestPriorityQueue {
    private static final Map<String, Integer> PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP = new HashMap<>();

    public void build(){

        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("fashionProduct", 0);
        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("bonusContent", 1);

        final List<TestTimedItemChange> changesCollection = new ArrayList<>();

        final List<TestEvent> eventList = getEvents();
        final Map<String, String> eventIdToTypeMap = eventList.stream().collect(
                Collectors.toMap(TestEvent::getItemId, TestEvent::getEventType));

        final Queue<TestTimedItemChange> pinnedItemsInQuickView =
                new PriorityQueue<>(getTimedItemChangeComparator(eventIdToTypeMap));

        for (final TestEvent event : eventList) {
            final TestTimedItemChange newItemToAdd = buildTimedItemChange(event.getItemId(), event.getStartTime(),
                    "add");

            if (changesCollection.size() >= 4) {
                final TestTimedItemChange oldItemToRemove = pinnedItemsInQuickView.peek();
                changesCollection.add(buildTimedItemChange(oldItemToRemove.getItemId(),
                        Math.max(newItemToAdd.getTimePosition(), oldItemToRemove.getTimePosition()),
                        "remove"));
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.remove(oldItemToRemove);
                pinnedItemsInQuickView.add(newItemToAdd);

            } else {
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.add(newItemToAdd);
            }


        }

        changesCollection.stream().forEach(cc -> System.out.println(cc));

    }

    private TestTimedItemChange buildTimedItemChange(final String itemId, final long timePosition,
                                                     final String itemChangeType) {
        TestTimedItemChange testTimedItemChange = new TestTimedItemChange();
        testTimedItemChange.setItemId(itemId);
        testTimedItemChange.setChangeType(itemChangeType);
        testTimedItemChange.setTimePosition(timePosition);

        return testTimedItemChange;
    }

    private static Comparator<TestTimedItemChange> getTimedItemChangeComparator(final Map<String, String> eventIdToTypeMap) {
        Comparator<TestTimedItemChange> comparator = new Comparator<TestTimedItemChange>() {
            @Override
            public int compare(final TestTimedItemChange timedItemChange1, final TestTimedItemChange timedItemChange2) {
                final String eventType1 = eventIdToTypeMap.get(timedItemChange1.getItemId());
                final String eventType2 = eventIdToTypeMap.get(timedItemChange2.getItemId());
                if (eventType1.equals(eventType2)) {
                    //greater timeposition should be removed last.
                    return (int) (timedItemChange1.getTimePosition() - timedItemChange2.getTimePosition());
                }
                //greater priority should be removed last.
                return PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(timedItemChange1.getItemId())) -
                        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(timedItemChange2.getItemId()));
            }
        };
        return comparator;
    }

    private List<TestEvent> getEvents() {
        List<TestEvent> eventList = new ArrayList<>();
        TestEvent event4 = new TestEvent();
        event4.setItemId("bts-0");
        event4.setEventType("bonusContent");
        event4.setStartTime(0L);
        eventList.add(event4);

        TestEvent event1 = new TestEvent();
        event1.setItemId("xst-prd-210");
        event1.setEventType("fashionProduct");
        event1.setStartTime(0L);
        eventList.add(event1);

        TestEvent event2 = new TestEvent();
        event2.setItemId("xst-prd-211");
        event2.setEventType("fashionProduct");
        event2.setStartTime(200L);
        eventList.add(event2);

        TestEvent event3 = new TestEvent();
        event3.setItemId("xst-prd-212");
        event3.setEventType("fashionProduct");
        event3.setStartTime(200L);
        eventList.add(event3);

        TestEvent event8 = new TestEvent();
        event8.setItemId("xst-prd-216");
        event8.setEventType("fashionProduct");
        event8.setStartTime(200L);
        eventList.add(event8);

        TestEvent event9 = new TestEvent();
        event9.setItemId("xst-prd-217");
        event9.setEventType("fashionProduct");
        event9.setStartTime(200L);
        eventList.add(event9);

        TestEvent event10 = new TestEvent();
        event10.setItemId("xst-prd-218");
        event10.setEventType("fashionProduct");
        event10.setStartTime(200L);
        eventList.add(event10);


        return eventList;
    }

    private class TestEvent {
        private String itemId;
        private String eventType;
        private Long startTime;

        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getStartTime() {
            return startTime;
        }

        public void setStartTime(Long startTime) {
            this.startTime = startTime;
        }

        
    }

    private class TestTimedItemChange {
        private String itemId;
        private String eventType;
        private Long timePosition;
        private String changeType;

        public String getChangeType() {
            return changeType;
        }

        public void setChangeType(String changeType) {
            this.changeType = changeType;
        }


        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getTimePosition() {
            return timePosition;
        }

        public void setTimePosition(Long timePosition) {
            this.timePosition = timePosition;
        }

        
    }
}

}

OUTPUT -

TimedItemChange(changeType=add, timePosition=0, itemId=bts-0)
TimedItemChange(changeType=add, timePosition=0, itemId=xst-prd-210)
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-211)
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-212)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-210) //correct removal based on starttime/timeposition
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-216)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-212)//wrong removal - should have been 211 as it was inserted before 212  
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-217)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-216) //wrong removal
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-218)
1
javacomparatorpriority-queuefifo
You can only accomplish this by using a stable sort, and PriorityQueue does not provide it. See the Javadoc. One workaround is to add a sequence subkey at the end of the key, but you run into overflow problems if the dataset is large enough. - user207421
@user207421 Check my answer - tried something and its working. Do check and let me know if something can be improved - Also, s there any other way by not adding a wrapper class? - user2621826
You did exactly what I said. You added a sequentializing subkey. - user207421

1 Answers

0
votes

I worked and this seems to be working - Basically wrapped the TestTimeItemChange class - Entry class - and getting the comparator seperately.

Is there any other way by not adding a wrapper class?

working code -

package com.amazon.atv.xray.vending.service.assemblerV2.builder.change;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class PriorityQueues {

  public static void main(String []args){
    TestPriorityQueue obj = new TestPriorityQueue();
    obj.build();
  }

 static class TestPriorityQueue {

    private static class Entry {

        private final static AtomicInteger seq = new AtomicInteger(0);
        final int order;
        final TestTimedItemChange timedItemChange;

        public int getOrder() {
            return order;
        }

        public TestTimedItemChange getTimedItemChange() {
            return timedItemChange;
        }

        public Entry(final TestTimedItemChange timedItemChange) {
            this.timedItemChange = timedItemChange;
            order = seq.incrementAndGet();
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("Entry(");

            ret.append("timedItemChange=");
            ret.append(timedItemChange.toString());
            ret.append(", ");

            ret.append("seq=");
            ret.append(String.valueOf(order));

            ret.append(")");

            return ret.toString();
        }

    }

   private static Comparator<Entry> getTimedItemChangeComparatorFIFO(final Map<String, String> eventIdToTypeMap) {
        Comparator<Entry> comparator = new Comparator<Entry>() {
            @Override
            public int compare(final Entry entry1, final Entry entry2) {
                int result = PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(entry1.getTimedItemChange().getItemId())) -
                        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(entry2.getTimedItemChange().getItemId()));
                if (result == 0)
                    return Integer.compare(entry1.getOrder(), entry2.getOrder());
                return result;
            }
        };
        return comparator;
    }

    private static final Map<String, Integer> PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP = new HashMap<>();

    public void build(){

        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("fashionProduct", 0);
        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("bonusContent", 1);

        final List<TestTimedItemChange> changesCollection = new ArrayList<>();

        final List<TestEvent> eventList = getEvents();
        final Map<String, String> eventIdToTypeMap = eventList.stream().collect(
                Collectors.toMap(TestEvent::getItemId, TestEvent::getEventType));

        final Queue<Entry> pinnedItemsInQuickView =
                new PriorityQueue<>(getTimedItemChangeComparatorFIFO(eventIdToTypeMap));

        for (final TestEvent event : eventList) {
            final TestTimedItemChange newItemToAdd = buildTimedItemChange(event.getItemId(), event.getStartTime(),
                    "add");

            if (changesCollection.size() >= 4) {
                //System.out.println(pinnedItemsInQuickView.remove());
                final TestTimedItemChange oldItemToRemove = pinnedItemsInQuickView.remove().getTimedItemChange();
                changesCollection.add(buildTimedItemChange(oldItemToRemove.getItemId(),
                        Math.max(newItemToAdd.getTimePosition(), oldItemToRemove.getTimePosition()),
                        "remove"));
                changesCollection.add(newItemToAdd);
                //pinnedItemsInQuickView.remove();
                pinnedItemsInQuickView.add(new Entry(newItemToAdd));

            } else {
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.add(new Entry(newItemToAdd));
            }


        }

        changesCollection.stream().forEach(cc -> System.out.println(cc));

    }

    private TestTimedItemChange buildTimedItemChange(final String itemId, final long timePosition,
                                                     final String itemChangeType) {
        TestTimedItemChange testTimedItemChange = new TestTimedItemChange();
        testTimedItemChange.setItemId(itemId);
        testTimedItemChange.setChangeType(itemChangeType);
        testTimedItemChange.setTimePosition(timePosition);

        return testTimedItemChange;
    }

    private List<TestEvent> getEvents() {
        List<TestEvent> eventList = new ArrayList<>();
        TestEvent event4 = new TestEvent();
        event4.setItemId("bts-0");
        event4.setEventType("bonusContent");
        event4.setStartTime(0L);
        eventList.add(event4);

        TestEvent event1 = new TestEvent();
        event1.setItemId("xst-prd-210");
        event1.setEventType("fashionProduct");
        event1.setStartTime(0L);
        eventList.add(event1);

        TestEvent event2 = new TestEvent();
        event2.setItemId("xst-prd-211");
        event2.setEventType("fashionProduct");
        event2.setStartTime(200L);
        eventList.add(event2);

        TestEvent event3 = new TestEvent();
        event3.setItemId("xst-prd-212");
        event3.setEventType("fashionProduct");
        event3.setStartTime(200L);
        eventList.add(event3);

        TestEvent event8 = new TestEvent();
        event8.setItemId("xst-prd-216");
        event8.setEventType("fashionProduct");
        event8.setStartTime(200L);
        eventList.add(event8);

        TestEvent event9 = new TestEvent();
        event9.setItemId("xst-prd-217");
        event9.setEventType("fashionProduct");
        event9.setStartTime(200L);
        eventList.add(event9);

        TestEvent event10 = new TestEvent();
        event10.setItemId("xst-prd-218");
        event10.setEventType("fashionProduct");
        event10.setStartTime(200L);
        eventList.add(event10);


        return eventList;
    }

    private class TestEvent {
        private String itemId;
        private String eventType;
        private Long startTime;

        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getStartTime() {
            return startTime;
        }

        public void setStartTime(Long startTime) {
            this.startTime = startTime;
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("XrayEvent(");

            ret.append("startTime=");
            ret.append(String.valueOf(startTime));
            ret.append(", ");

            ret.append("eventType=");
            ret.append(String.valueOf(eventType));
            ret.append(", ");

            ret.append("itemId=");
            ret.append(String.valueOf(itemId));
            ret.append(")");
            return ret.toString();
        }
    }

    private class TestTimedItemChange {
        private String itemId;
        private String eventType;
        private Long timePosition;
        private String changeType;

        public String getChangeType() {
            return changeType;
        }

        public void setChangeType(String changeType) {
            this.changeType = changeType;
        }


        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getTimePosition() {
            return timePosition;
        }

        public void setTimePosition(Long timePosition) {
            this.timePosition = timePosition;
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("TimedItemChange(");

            ret.append("changeType=");
            ret.append(String.valueOf(changeType));
            ret.append(", ");

            ret.append("timePosition=");
            ret.append(String.valueOf(timePosition));
            ret.append(", ");

            ret.append("itemId=");
            ret.append(String.valueOf(itemId));
            ret.append(")");

            return ret.toString();
        }
    }
}

}