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