LazyMultiListQueue

    package org.drools.util;
    
    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    import org.drools.common.AgendaItem;
    import org.drools.conflict.DepthConflictResolver;
    import org.drools.reteoo.ReteTuple;
    import org.drools.util.LazyMultiListQueue.PropagationCounterEntry.ActivationComparator;
    import org.drools.util.LinkedList.LinkedListIterator;
    
    public class LazyMultiListQueue
        implements
        Queue {
    
        //Map map = new HashMap();
        //private SalienceBucket salienceBucket;
    
        private SalienceBucket minus10 = new SalienceBucket( -10 );
        private SalienceBucket plus10  = new SalienceBucket( 10 );
        private SalienceBucket zero   = new SalienceBucket( 5 );
        private SalienceBucket plus5   = new SalienceBucket( 0 );
    
    
        public Queueable dequeue() {        
            SalienceBucket salienceBucket = null;
            if ( !plus10.isEmptry() ) {
                salienceBucket = plus10;
            } else if ( !plus5.isEmptry() ) {
                salienceBucket = plus5;
            } else if ( !zero.isEmptry() ) {
                salienceBucket = zero;
            } else if ( !minus10.isEmptry() ) {
                salienceBucket = minus10;
            }    
            
            return ( salienceBucket != null ) ? salienceBucket.dequeue() : null;
        }
    
        public Queueable dequeue(int index) {
            // not used
            return null;
        }
    
        public void enqueue(Queueable queueable) {
            AgendaItem item = (AgendaItem) queueable;
            int salience =  item.getRule().getSalience();
            
            SalienceBucket salienceBucket = null;
            switch ( salience ) {
                case -10:
                    salienceBucket = minus10;
                    break;
                case 0:
                    salienceBucket = zero;
                break;
                case 5:
                    salienceBucket = plus5;
                    break;
                case 10:
                    salienceBucket = plus10;
                    break;
            }
            
            //SalienceBucket salienceBucket = ( SalienceBucket ) map.get(  salience );
    //        if ( salienceBucket == null ) {
    //            salienceBucket = new SalienceBucket( item.getRule().getSalience() );
    //            map.put( salience,
    //                     salienceBucket );
    //        }
            salienceBucket.add( item );
        }
    
        public boolean isEmpty() {
            return false; //this.map.isEmptry();
        }
    
        public void clear() {
            //this.map.clear();
        }
    
        public int size() {
            //return this.map.size;
            return -1;
        }
    
        public Object[] toArray(Object[] array) {
            //return getQueueable();
            return null;
        }
    
        public Queueable[] getQueueable() {
            //return new Queueable[] { this.current };
            return null;
        }
    
        public static class SalienceBucket
            implements
            Comparable<SalienceBucket> {
            private int        salience;
            private LinkedList list;
            private int        size;
    
            public SalienceBucket(int salience) {
                this.salience = salience;
                this.list = new LinkedList();
            }
    
            public long getNumber() {
                return this.salience;
            }
    
            public void add(AgendaItem item) {
                size++;
    
                //ReteTuple tuple = (ReteTuple) item.getTuple();
                //long newRecency = tuple.getRecency();
                long counter = item.getPropagationContext().getPropagationNumber();
    
                PropagationCounterEntry last = (PropagationCounterEntry) list.getLast();
                if ( last == null || counter > last.getCounter() ) {
                    last = new PropagationCounterEntry( this,
                                                        counter );
                    this.list.add( last );
                }
                last.add( item );
            }
    
            public void remove(PropagationCounterEntry entry) {
                this.list.remove( entry );
            }
    
            public Queueable dequeue() {
                PropagationCounterEntry tier = (PropagationCounterEntry) list.getLast();
                return (tier != null) ? tier.dequeue() : null;
            }
    
            public int size() {
                return this.size;
            }
    
            public boolean isEmptry() {
                return this.size == 0;
            }
    
            public void clear() {
                this.list.clear();
            }
    
            public void decreaseSize() {
                this.size--;
            }
    
            public int compareTo(SalienceBucket object) {
                return (int) (this.salience - object.getNumber());
            }
        }
    
        public static class PropagationCounterEntry extends AbstractBaseLinkedListNode
            implements
            Serializable {
            private long                 counter;
            private SalienceBucket       parent;
    
            private LinkedList           list;
    
            private LinkedListNode       next;
    
            private boolean              sorted;
    
            private ActivationComparator comparator = ActivationComparator.getInstance();
    
            public PropagationCounterEntry(SalienceBucket parent,
                                           long counter) {
                this.counter = counter;
                this.parent = parent;
                this.list = new LinkedList();
                this.sorted = false;
            }
    
            public void setNext(LinkedListNode next) {
                this.next = next;
            }
    
            public LinkedListNode getNext() {
                return this.next;
            }
    
            public long getCounter() {
                return this.counter;
            }
    
            public void add(AgendaItem item) {
                this.list.add( item );
                item.addToRecencyTierEntry( this );
            }
    
            public void remove(AgendaItem item) {
                this.list.remove( item );
                this.parent.decreaseSize();
                if ( this.list.isEmpty() ) {
                    this.parent.remove( this );
                }
    
            }
    
            public Queueable dequeue() {
                // lazy sort on first access
                if ( !this.sorted ) {
                    //jdkMergeSortList( this.list );
                    LinkedListNode node = mergesort( this.list.getFirst(),
                                                     this.list.size() );
                    this.list.setPayload( node );
                    this.sorted = true;
                }
    
                Queueable item = (Queueable) this.list.removeLast();
                this.parent.decreaseSize();
                if ( this.list.isEmpty() ) {
                    this.parent.remove( this );
                }
                return item;
            }
    
            private void jdkMergeSortList(LinkedList list) {
                //int point = list.size() / 2;
                LinkedListNode[] array = new LinkedListNode[list.size()];
                LinkedListNode node = list.removeFirst();
                for ( int i = 0, length = array.length; i < length; i++ ) {
                    array+ = node;
                    node = list.removeFirst();
                }
                list.clear();
    
                // Sort the array and rebuild the linked list
                Arrays.sort( array,
                             new ActivationComparator() );
                for ( int i = 0, length = array.length; i < length; i++ ) {
                    list.add( array+ );
                }
            }
    
            private LinkedListNode mergesort(LinkedListNode head,
                                             int size) {
                // empty or one-node lists are already sorted
                if ( head == null || head.getNext() == null ) {
                    return head;
                }
    
                int firstHalfSize = size / 2;
                int secondHalfSize = size - firstHalfSize;
                // split list in two, get reference to second half
                LinkedListNode secondhalf = split( head,
                                                   firstHalfSize );
    
                // recursively sort sublists
                head = mergesort( head,
                                  firstHalfSize );
                secondhalf = mergesort( secondhalf,
                                        secondHalfSize );
    
                // merge sorted sublists into one sorted list
                return merge( head,
                              secondhalf );
            }
    
            private LinkedListNode split(LinkedListNode head,
                                         int point) {
                LinkedListNode ptr = head;
                for ( int i = 0; i < point - 1; i++ ) {
                    ptr = ptr.getNext();
                }
                LinkedListNode secondHalf = ptr.getNext();
                ptr.setNext( null );
    
                return secondHalf;
            }
    
            private LinkedListNode merge(LinkedListNode head1,
                                         LinkedListNode head2) {
                // merging with an empty list requires no work
                if ( head1 == null ) {
                    return head2;
                }
                if ( head2 == null ) {
                    return head1;
                }
    
                // pick smaller value to be first
                if ( comparator.compare( head1,
                                         head2 ) < 0 ) {
                    LinkedListNode node = merge( head1.getNext(),
                                                 head2 );
                    head1.setNext( node );
                    node.setPrevious( head1 );
                    return head1;
                } else {
                    LinkedListNode node = merge( head1,
                                                 head2.getNext() );
                    head2.setNext( node );
                    node.setPrevious( head2 );
                    return head2;
                }
            }
    
            private void split(LinkedListNode node,
                               int point,
                               SentinalNode left,
                               SentinalNode right) {
                left.node = node;
                for ( int i = 0; i < point; i++ ) {
                    node = node.getNext();
                }
    
                // break the links
                node.getPrevious().setNext( null );
                node.setPrevious( null );
                right.node = node;
            }
    
            public class SentinalNode extends AbstractBaseLinkedListNode {
                public LinkedListNode node;
                public int            size;
            }
    
            private void sortList(LinkedList list) {
                if ( list.size() == 1 ) {
                    return; // only one entry, no need to sort;
                }
    
                // Get the second to last
                AgendaItem current = (AgendaItem) list.getLast().getPrevious();
    
                while ( current != null ) {
                    // find the next item to swap with                     
                    AgendaItem nextItem = (AgendaItem) current.getNext();
                    AgendaItem tempItem = nextItem;
                    while ( tempItem != null ) {
                        if ( insertAfter( current,
                                          tempItem ) ) {
                            nextItem = tempItem;
                        } else {
                            break;
                        }
                        tempItem = (AgendaItem) tempItem.getNext();
                    }
    
                    if ( tempItem != nextItem ) {
                        AgendaItem newCurrent = (AgendaItem) current.getPrevious();
                        this.list.remove( current );
                        this.list.insertAfter( nextItem,
                                               current );
                        current = newCurrent;
                    } else {
                        current = (AgendaItem) current.getPrevious();
                    }
    
                }
            }
    
            public static class ActivationComparator
                implements
                Comparator<AgendaItem> {
                public static final ActivationComparator instance = new ActivationComparator();
    
                public static final ActivationComparator getInstance() {
                    return instance;
                }
    
                private ActivationComparator() {
    
                }
    
                public int compare(AgendaItem object0,
                                   AgendaItem object1) {
                    return (int) (object0.getTuple().getRecency() - object1.getTuple().getRecency());
                }
    
            }
    
            private boolean insertAfter(AgendaItem item1,
                                        AgendaItem item2) {
                ReteTuple tuple1 = (ReteTuple) item1.getTuple();
                ReteTuple tuple2 = (ReteTuple) item2.getTuple();
    
                return tuple1.getRecency() > tuple2.getRecency();
    
                //            if ( tuple1.getParent() != null ) {
                //                if ( tuple2.getParent() != null ) {
                //                    // check with parents
                //                    return insertAfter( tuple1.getParent(),
                //                                        tuple1.getParent() );
                //                } else {
                //                    // tuple2 has no parents, tuple1 does, so tuple1 has priority                    
                //                    return true;
                //                }
                //            } else if ( tuple2.getParent() != null ) {
                //                // tuple1 has no parents, tuple2 does, so tuple2 has priority 
                //                return false;
                //            } else {
                //                // both have null parents, both still the same, so don't bother doing the swap
                //                return false;
                //            }
            }
    
            //        private boolean insertAfter(ReteTuple tuple1,
            //                                    ReteTuple tuple2) {
            //            long recency1 = tuple1.getFactHandle().getRecency();
            //            long recency2 = tuple2.getFactHandle().getRecency();
            //
            //            if ( recency1 == recency2 ) {
            //                if ( tuple1.getParent() != null ) {
            //                    if ( tuple2.getParent() != null ) {
            //                        // check with parents
            //                        return insertAfter( tuple1.getParent(),
            //                                            tuple2.getParent() );
            //                    } else {
            //                        // tuple2 has no parents, tuple1 does, so tuple1 has priority
            //                        return true;
            //                    }
            //                } else if ( tuple2.getParent() != null ) {
            //                    // tuple1 has no parents, tuple2 does, so tuple2 has priority 
            //                    return false;
            //                } else {
            //                    // both have null parents, both still the same, so don't bother doing the swap
            //                    return false;
            //                }
            //            } else if ( recency1 > recency2 ) {
            //                // recency1 is higher tham recency2, so tuple1 has priority
            //                return true;
            //            } else {
            //                // recency1 is lower tham recency2, so tuple2 has priority
            //                return false;
            //            }
            //        }
        }
    }