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;
        //            }
        //        }
    }
}