0

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)
user2621826
  • 19
  • 2
  • 11
  • 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 Oct 11 '21 at 09:29
  • @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 Oct 11 '21 at 09:44
  • You did exactly what I said. You added a sequentializing subkey. – user207421 Oct 11 '21 at 09:47
  • @user207421 What are the overflow problems you mentioned above? is it the integer limits? although we will not have a big dataset but want to understand what u meant. – user2621826 Oct 11 '21 at 13:30
  • Make the PQ's priority a tuple of actual priority and time of addition to the PQ. The comparator should then use the priorities if they're different, but break ties by time if the priorities are the same. Since "time" is relative order of entry, you could just use an incrementing counter as a surrogate. – pjs Oct 14 '21 at 15:35

1 Answers1

0

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();
        }
    }
}

}

user2621826
  • 19
  • 2
  • 11