/*
 * $Header: /home/cvspublic/jakarta-slide/proposals/tamino/src/util/org/apache/slide/util/cache/LRUQueue.java,v 1.3 2004/07/30 06:52:17 ozeigermann Exp $
 * $Revision: 1.3 $
 * $Date: 2004/07/30 06:52:17 $
 *
 * ====================================================================
 *
 * Copyright 1999-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.slide.util.cache;

import java.util.HashMap;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;

/**
 ** Implements LRU mechanism.
 **  <li>Provides a queuing mechanism for a defined number of elements combined with
 **      an LRU (Last Recently Used) algorithm.</li>
 **  <li>If the number of elements exceeds the capacity of the queue the element
 **      which was enqued first (of the remaining objects) in the queue is displaced</li>
 **  <li>Expects that the queued object are implementing the equals() and hashCode()
 **      methods. </li>
 **
 ** @author    peter.zaretzke@softwareag.com
 ** @version   $Revision: 1.3 $
 **/

public class LRUQueue {
    
    private Entry top = new Entry();
    private HashMap index;
    private int capacity, size;
    private int modificationCount = 0;
    private static final boolean CHAIN_CHECK = false;
    private boolean move = true;
    
    /*******************************************************************************
     * Creates a queue with the passed capacity.
     * @param capacity the capacity
     *******************************************************************************/
    public LRUQueue ( int capacity ) {
        top.next = top.previous = top;
        this.capacity = capacity;
        size = 0;
        index = new HashMap( capacity );
    }
    
    
    
    /*******************************************************************************
     * Enqueues the passed object at top of the list. If the object is already enqued
     * it will just be moved to the top again. Otherwise it will be newly added at the top.
     * If the lists capacity is exhausted the element which was not enqued for the
     * longest time will be removed.
     * @param o object to enqueue
     * @return the removed object or null.
     *******************************************************************************/
    public synchronized Object enqueue ( Object o ) {
        
        Entry e = (Entry) index.get ( o );
        
        if ( e != null ) {
            if ( size >= capacity  ) {
                if ( move = !move ) {
                    if ( e.previous != top ) {
                        moveToTop ( e ); // "touch" element
                        if (CHAIN_CHECK) check();
                        modificationCount++;
                        // System.out.print(".");
                    }
                }
            }
            return null;
        }
        
        // new entry in the queue
        
        if ( size == capacity ) {
            Entry last = top.previous; // get last
            Object result = last.o;    // keep old o to return as result
            last.o = null;             // quicker gc
            if ( index.remove ( result ) == null ) {   // remove object from index
                throw new RuntimeException ("index.remove ( result ) == null " + result + "\n" + index );
            }
            last.o = o;                // re-use the entry object
            index.put ( o, last );
            moveToTop ( last );        // move to top
            if (CHAIN_CHECK) check();
            modificationCount++;
            return result;             // return displaced object
        }
        else {
            // create a new entry and move it to the top
            e = new Entry ( o , top.next, top );
            index.put ( o, e );
            top.next = e;
            e.next.previous = e;
            size++;
            if (CHAIN_CHECK) check();
            modificationCount++;
            return null;
        }
    }
    
    /*******************************************************************************
     * Remove an object from queue.
     * @param o object to remove
     *******************************************************************************/
    public synchronized void remove( Object o ) {
        
        Entry e = (Entry) index.get ( o );
        
        if ( e != null ) {
            index.remove ( e.o );
            // unchain this Entry
            e.previous.next = e.next;
            e.next.previous = e.previous;
            e.next = null;
            e.previous = null;
            e.o = null;
            size--;
            if (CHAIN_CHECK) check();
            modificationCount++;
        }
        
    }
    
    /*******************************************************************************
     *
     *******************************************************************************/
    public synchronized void clear() {
        index.clear();
        Entry r = top.next;
        
        while ( r != top )  {
            r = r.next;
            // do not leave references to make GCs life easier
            r.previous.o = null;
            r.previous.next = null;
            r.previous = null;
        }
        top.next = top.previous = top;
        size = 0;
        modificationCount = 0;
        if (CHAIN_CHECK) check();
    }
    
    /*******************************************************************************
     * Internal method to move an element to the top of the list.
     *******************************************************************************/
    private void moveToTop ( Entry e ) {
        Entry p = e;
        // try {
        if (CHAIN_CHECK) check();
        e.previous.next = e.next;
        e.next.previous = e.previous;
        e.next = top.next;
        e.previous = top;
        top.next.previous = e;
        top.next = e;
        /*
         }
         catch ( Exception ex ) {
         Debug.STACK_TRACE (ex);
         System.out.println ("LRUQueue " + ex
         + "\ne          = " + p
         + "\ne.previous = " + p.previous
         + "\ne.next     = " + p.next
         + "\ncapacity   = " + capacity
         + "\nsize       = " + size
         + "\nindex.size = " + index.size()
         );
         System.out.println ("Queue " + this.toString() );
         }
         */
    }
    
    /*******************************************************************************
     * Resize the queue to the new capacity.
     * @param capacity  capacity
     *******************************************************************************/
    public synchronized void resize ( int capacity ) {
        
        if ( size <= capacity ) {
            this.capacity = capacity;
        }
        
        if ( capacity <= size ) {
            // remove some elements
            Entry e = top, r;
            for ( int i = 0; i < capacity; i++ )
                e = e.next;
            r = e.next;
            top.previous = e;
            e.next = top;
            while ( r != top )  {
                index.remove ( r.o );
                r.o = null;
                r.previous = null;
                e = r;
                r = r.next;
                e.next = null;
            }
            this.capacity = capacity;
            this.size = capacity;
        }
        if (CHAIN_CHECK) check();
        modificationCount++;
    }
    
    /*******************************************************************************
     * Returns an iterator for the queued elements.
     * The iterator does NOT reflect the order in the queue.
     * @return an iterator for the queued elements
     *******************************************************************************/
    public Iterator iterator () {
        return new QueueIterator( this );
    }
    
    /*******************************************************************************
     * Returns the number of elements in the queue.
     * @return the number of elements in the queue
     *******************************************************************************/
    public int size() {
        return size;
    }
    
    /*******************************************************************************
     * Returns the maximum number of elements in the queue.
     * @return the maximum number of elements in the queue
     *******************************************************************************/
    public int capacity() {
        return capacity;
    }
    
    /*******************************************************************************
     * Print the queue as string.
     * @return the queue as string
     *******************************************************************************/
    public String printString() {
        Entry current = top;
        StringBuffer result = new StringBuffer(200);
        if ( size == 0 )
            return "[ ]";
        for ( int i = 0; i < size; i++  ) {
            result.append (i+1).append(" : [").append(current.next.o).append("]\n");
            current = current.next;
        }
        return result.toString();
    }
    
    /*******************************************************************************
     * Returns a string representation of the queue.
     * @return a string representation of the queue
     *******************************************************************************/
    public String toString() {
        Entry current = top;
        StringBuffer result1 = new StringBuffer(200);
        String result2 = "";
        for ( int i = 0; i <= size; i++  ) {
            result1.append ( current.o );
            if ( i != size )
                result1.append(" -> ");
            current = current.next;
        }
        
        current = current.previous; // back to the last
        
        for ( int i = 0; i <= size; i++  ) {
            if ( i == 0  )
                result2 =  String.valueOf (current.o);
            else
                result2 =  current.o + " <- " + result2;
            
            current = current.previous;
        }
        return result1.toString() + "\n" + result2;
    }
    
    /*******************************************************************************
     * Returns a string representation of the queue.
     *******************************************************************************/
    private void check() {
        if ( size != index.size() )
            throw new IllegalStateException ( "size != index.size() " + size + "," + index.size() );
        Entry current = top;
        for ( int i = 0; i <= size; i++  ) {
            if ( current.next.previous != current || current.previous.next != current )
                throw new RuntimeException ("LRUQueue Chain broken, size = " + size);
            current = current.next;
        }
        if ( current != top )
            throw new RuntimeException ("LRUQueue Chain broken +, size = " + size );
    }
    
    /*******************************************************************************
     * Queue Entry.
     *
     * @author    peter.zaretzke@softwareag.com
     * @version   $Revision: 1.3 $
     *******************************************************************************/
    private static class Entry {
        private Object o;
        private Entry next;
        private Entry previous;
        
        /**
         ** Constructor.
         **/
        Entry() {
            this.o = "TOP";
            this.next = this;
            this.previous = this;
        }
        
        /**
         ** Constructor.
         **
         ** @param      o         object
         ** @param      next      next entry
         ** @param      previous  previous entry
         **/
        Entry(Object o, Entry next, Entry previous) {
            this.o = o;
            this.next = next;
            this.previous = previous;
        }
        
        /**
         ** Returns the string representation of this object.
         **
         ** @return  the string representation of this object
         **/
        public String toString () {
            return o.toString();
        }
    }
    
    /*******************************************************************************
     * Iterator for lists with one on none element.
     * @author    peter.zaretzke@softwareag.com
     * @version   $Revision: 1.3 $
     *******************************************************************************/
    final class QueueIterator implements Iterator {
        
        private Entry current;
        private int expectedModificationCount;
        private Object lastReturned = null;
        private LRUQueue owner;
        
        /**
         ** Constructor.
         **
         ** @param      owner   owner
         **/
        QueueIterator ( LRUQueue owner ) {
            this.owner = owner;
            current = top.next;
            expectedModificationCount = modificationCount;
        }
        
        /**
         ** Returns true if current object is not the first one.
         **
         ** @return  true if current object is not the first one, false otherwise
         **/
        public boolean hasNext() {
            return current != top;
        }
        
        /**
         ** Returns the successor.
         **
         ** @return  the successor
         **/
        public Object next() throws NoSuchElementException {
            checkForConcurrentModification ();
            if ( current == top )
                throw new NoSuchElementException();
            Object result = current.o;
            current = current.next;
            lastReturned = result;
            return result;
        }
        
        /**
         ** Remove this object from queue.
         **/
        public void remove() throws IllegalStateException {
            if ( lastReturned != null ) {
                owner. remove ( lastReturned );
                expectedModificationCount++;
            }
            else
                throw new IllegalStateException ("lastReturned = null");
            lastReturned = null;
            // throw new UnsupportedOperationException();
        }
        
        private void checkForConcurrentModification () {
            if ( expectedModificationCount != modificationCount )
                throw new ConcurrentModificationException();
        }
    }
    /*******************************************************************************
     * Main method
     * @param args arguments
     *******************************************************************************/
    public static void main ( String[] args ) {
        
        LRUQueue q = new LRUQueue ( 10 );
        
        String result,h = null;
        
        for ( int i = 0; i <= 10; i ++ ) {
            h = "1.30.0." + i;
            result = (String) q.enqueue ( h );
            if ( result != null )
                System.out.println ("Displaced object " + result );
        }
        
        System.out.println ("Initial Queue: \n" + q.toString() );
        
        h = "1.30.0.11";
        
        result = (String) q.enqueue ( h );
        if ( result != null ) System.out.println ("Displaced object " + result );
        
        System.out.println ("After q.enqueue ( '1.30.0.11' ): \n" + q.toString() );
        
        h = "1.30.0.3";
        
        result = (String) q.enqueue ( h );
        if ( result != null ) System.out.println ("Displaced object " + result );
        
        System.out.println ("After NEW q.enqueue ( '1.30.0.3' ): \n" + q.toString() );
        
        q.resize ( 6 );
        
        System.out.println ("After q.resize ( 6 ): \n" + q.printString() );
        
        System.out.println ("use iterator()" );
        int count = 1;
        for ( Iterator it = q.iterator(); it.hasNext(); count++ )
            System.out.println ("[" + count + "] : " + it.next() );
        
        System.out.println ("remove all elements" );
        
        for ( Iterator it = q.iterator(); it.hasNext(); count++ ) {
            it.next();
            it.remove();
        }
        System.out.println ("after remove: \n" + q.toString() );
        
        System.out.println ("add new elements to empty list (length = 6)" );
        
        for ( int i = 0; i <= 10; i ++ ) {
            h = "1.40.0." + i;
            result = (String) q.enqueue ( h );
            if ( result != null )
                System.out.println ("Displaced object " + result );
        }
        
        System.out.println ("after add new elements: \n" + q.toString() );
        
        q.remove("1.40.0.8");
        System.out.println ("after remove 1.40.0.8: \n" + q.toString() );
        
        result = (String) q.enqueue ( "1.40.0.7" );
        
        System.out.println ("after enqueue 1.40.0.7: \n" + q.toString() );
        
        // raise concurrent modification exception
        System.out.println ("raise a concurrent modification exception " );
        count = 0;
        for ( Iterator it = q.iterator(); it.hasNext(); count++ ) {
            if ( count == 3 )
                q.enqueue ("1.30.0.33");
            System.out.println ("[" + count + "] : " + it.next() );
        }
    }
    
}
