Quelle FastRemovalDequeue.java Sprache: JAVA

/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements.  See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You 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.jasper.util;

/**
* The FastRemovalDequeue is a Dequeue that supports constant time removal of
* entries. This is achieved by using a doubly linked list and wrapping any object
* added to the collection with an Entry type, that is returned to the consumer.
* When removing an object from the list, the consumer provides this Entry object.
*
* The Entry type is nearly opaque to the consumer of the queue. The only public
* member is the getter for any object displaced when adding a new object to the
* queue. This can be used to destroy that object.
*
* The Entry object contains the links pointing to the neighbours in the doubly
* linked list, so that removal of an Entry does not need to search for it but
* instead can be done in constant time.
*
* The implementation is fully thread-safe.
*
* Invalidation of Entry objects during removal from the list is done
* by setting their "valid" field to false. All public methods which take Entry
* objects as arguments are NOP if the entry is no longer valid.
*
* A typical use of the FastRemovalDequeue is a list of entries in sorted order,
* where the sort position of an object will only switch to first or last.
*
* Whenever the sort position needs to change, the consumer can remove the object
* and reinsert it in front or at the end in constant time.
* So keeping the list sorted is very cheap.
*
* @param <T> The type of elements in the queue
*/
public class FastRemovalDequeue<T> {

    /** Maximum size of the queue */
    private final int maxSize;
    /** First element of the queue. */
    protected Entry first;
    /** Last element of the queue. */
    protected Entry last;
    /** Size of the queue */
    private int size;

    /**
     * Initialize empty queue.
     *
     * @param maxSize The maximum size to which the queue will be allowed to
     *                grow
     */
    public FastRemovalDequeue(int maxSize) {
        if (maxSize <=1 ) {
            maxSize = 2;
        }
        this.maxSize = maxSize;
        first = null;
        last = null;
        size = 0;
    }

    /**
     * Retrieve the size of the list.
     * This method also needs to be externally synchronized to
     * ensure correct publication of changes.
     *
     * @return the size of the list.
     * */
    public synchronized int getSize() {
        return size;
    }

    /**
     * Adds an object to the start of the list and returns the entry created for
     * said object. The entry can later be reused for moving the entry.
     *
     * @param object the object to prepend to the start of the list.
     * @return an entry for use when the object should be moved.
     * */
    public synchronized Entry push(final T object) {
        Entry entry = new Entry(object);
        if (size >= maxSize) {
            entry.setReplaced(pop());
        }
        if (first == null) {
            first = last = entry;
        } else {
            first.setPrevious(entry);
            entry.setNext(first);
            first = entry;
        }
        size++;

        return entry;
    }

    /**
     * Adds an object to the end of the list and returns the entry created for
     * said object. The entry can later be reused for moving the entry.
     *
     * @param object the object to append to the end of the list.
     * @return an entry for use when the object should be moved.
     * */
    public synchronized Entry unpop(final T object) {
        Entry entry = new Entry(object);
        if (size >= maxSize) {
            entry.setReplaced(unpush());
        }
        if (first == null) {
            first = last = entry;
        } else {
            last.setNext(entry);
            entry.setPrevious(last);
            last = entry;
        }
        size++;

        return entry;
    }

    /**
     * Removes the first element of the list and returns its content.
     *
     * @return the content of the first element of the list.
     **/
    public synchronized T unpush() {
        T content = null;
        if (first != null) {
            Entry element = first;
            first = first.getNext();
            content = element.getContent();
            if (first == null) {
                last =null;
            } else {
                first.setPrevious(null);
            }
            size--;
            element.invalidate();
        }
        return content;
    }

    /**
     * Removes the last element of the list and returns its content.
     *
     * @return the content of the last element of the list.
     **/
    public synchronized T pop() {
        T content = null;
        if (last != null) {
            Entry element = last;
            last = last.getPrevious();
            content = element.getContent();
            if (last == null) {
                first = null;
            } else {
                last.setNext(null);
            }
            size--;
            element.invalidate();
        }
        return content;
    }

    /**
     * Removes any element of the list and returns its content.
     *
     * @param element The element to remove
     */
    public synchronized void remove(final Entry element) {
        if (element == null || !element.getValid()) {
            return;
        }
        Entry next = element.getNext();
        Entry prev = element.getPrevious();
        if (next != null) {
            next.setPrevious(prev);
        } else {
            last = prev;
        }
        if (prev != null) {
            prev.setNext(next);
        } else {
            first = next;
        }
        size--;
        element.invalidate();
    }

    /**
     * Moves the element in front.
     *
     * Could also be implemented as remove() and
     * push(), but explicitly coding might be a bit faster.
     *
     * @param element the entry to move in front.
     * */
    public synchronized void moveFirst(final Entry element) {
        if (element.getValid() &&
            element.getPrevious() != null) {
            Entry prev = element.getPrevious();
            Entry next = element.getNext();
            prev.setNext(next);
            if (next != null) {
                next.setPrevious(prev);
            } else {
                last = prev;
            }
            first.setPrevious(element);
            element.setNext(first);
            element.setPrevious(null);
            first = element;
        }
    }

    /**
     * Moves the element to the back.
     *
     * Could also be implemented as remove() and
     * unpop(), but explicitly coding might be a bit faster.
     *
     * @param element the entry to move to the back.
     * */
    public synchronized void moveLast(final Entry element) {
        if (element.getValid() &&
            element.getNext() != null) {
            Entry next = element.getNext();
            Entry prev = element.getPrevious();
            next.setPrevious(prev);
            if (prev != null) {
                prev.setNext(next);
            } else {
                first = next;
            }
            last.setNext(element);
            element.setPrevious(last);
            element.setNext(null);
            last = element;
        }
    }

    /**
     * Implementation of a doubly linked list entry.
     * All implementation details are private.
     * For the consumer of the above collection, this
     * is simply garbage in, garbage out.
     */
    public class Entry {

        /** Is this entry still valid? */
        private boolean valid = true;
        /** The content this entry is valid for. */
        private final T content;
        /** Optional content that was displaced by this entry */
        private T replaced = null;
        /** Pointer to next element in queue. */
        private Entry next = null;
        /** Pointer to previous element in queue. */
        private Entry previous = null;

        private Entry(T object) {
            content = object;
        }

        private boolean getValid() {
            return valid;
        }

        private void invalidate() {
            this.valid = false;
            this.previous = null;
            this.next = null;
        }

        public final T getContent() {
            return content;
        }

        public final T getReplaced() {
            return replaced;
        }

        private void setReplaced(final T replaced) {
            this.replaced = replaced;
        }

        public final void clearReplaced() {
            this.replaced = null;
        }

        private Entry getNext() {
            return next;
        }

        private void setNext(final Entry next) {
            this.next = next;
        }

        private Entry getPrevious() {
            return previous;
        }

        private void setPrevious(final Entry previous) {
            this.previous = previous;
        }

        @Override
        public String toString() {
            return "Entry-" + content.toString();
        }
    }

}

quality100%

¤ Dauer der Verarbeitung: 0.3 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.