/*
 * SynchroList.java - Synchronized List
 *
 * Copyright (C) 1998 Charles McManis, All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies.
 *
 * CHUCK MCMANIS MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
 * SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING
 * BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. CHUCK MCMANIS
 * SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT
 * OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 */

import java.util.Enumeration;
import java.util.Vector;

/**
 * The Synchronized List
 *
 * A synchronized list is one in which there can be multiple threads
 * of execution putting things on the list, and enumerating the list.
 *
 */
public class SynchroList {
    private ChuckBitSet players = new ChuckBitSet();

    /* return a new player ID from the list */
    private int newPlayerID() {
        int i = 0;
        while (players.get(i)) i++;
        players.set(i);
        return i;
    }


    /**
     * The inner Link class is used to link the objects together into
     * a doubly linked list. This "helper" class wraps both next and
     * previous pointers with a state vector to identify when a particular
     * object is currently participating in a list.
     */
    class Link {
        private Object data;
        private Link nxt, prv;

        /**
         * Create a new Link and insert it between nodes p and n
         */
        Link(Object o, Link p, Link n) {
            nxt = n; prv = p; data = o;
            if (n != null)
                n.prv = this;
            if (p != null)
                p.nxt = this;
        }

        /** return the held object reference */
        Object getData() { return data; }

        /** return the link after this one. */
        Link next() { return nxt; }
        Link next(Link newNext) { Link r = nxt; nxt = newNext; return r;}

        /** return the link before this one. */
        Link prev() { return prv; }
        Link prev(Link newPrev) { Link r = prv; prv = newPrev; return r;}

        public String toString() { return "Link("+data+")"; }

        /*
         * Now to add a notion of which threads have this Link
         * in an enumeration they are holding open ...
         */
        ChuckBitSet inplay = new ChuckBitSet();

        /** return true if this link is on one or more Enumerations */
        boolean inPlay() { return ! inplay.isZero(); }

        /** Return true if this link is on the passed Enumeration */
        boolean inPlay(int who) { return inplay.get(who); }

        /** Mark this link as being in an enumeration */
        void setPlayer(int who) { inplay.set(who); }

        /** Remove this link from being on a particular enumeration */
        synchronized void release(int who) {
             inplay.clear(who);
             notifyAll();
        }

        /** return the identity of the last active enumeration */
        int lastPlayer() { return inplay.lastBit(); }

        /**
         * Applet version ONLY, includes position diagnostics
         * and state, as to whether or not we are blocking a
         * writing thread.
         */
        int nPlayers() {
            int l = inplay.lastBit();
            int res = 1;

            if (inplay.isZero())
               return 0;
               
            for (int k = 0; k < l; k++) {
                if (inPlay(k))
                   res++;
            }
            return res;
        }

        private boolean block;

        void setBlocking() { block = true; }

        void clearBlocking() { block = false; }

        boolean isBlocking() { return block; }

    }

    /**
     * The inner Link Enumerator class provides a selected series
     * of objects from the pile. These can either be all of the objects
     * or a subset based on bounding from/to object pairs.
     */
    class LinkEnumerator implements Enumeration {
        private Link current, last;
        private int id;

        private void markLinks(Link from, Link to) {
            Link tmp;

            if (from == null)
               from = head;
            id = newPlayerID();
            for (tmp = from; tmp != to; tmp = tmp.next()) {
                tmp.setPlayer(id);
            }
        }

        /**
         * Create an enumerator for all objects.
         */
        LinkEnumerator( ) {
            current = head;
            markLinks(current, null);
        }

        /**
         * Create an enumerator from the specified object to the end of
         * the list.
         */
        LinkEnumerator(Object from) {
            last = null;
            for (current = head; current != null; current = current.next()) {
                if (cmp.lessThan(from, current.getData()))
                   break;
            }
            markLinks(current, null);
        }

        /**
         * Create an enumerator that consists of a particular set of
         * objects.
         */
        LinkEnumerator(Object from, Object to) {
            last = null;

            if (cmp.greaterThan(from, to)) {
                Object tmp = from;
                from = to;
                to = tmp;
            }

            for (current = head; current != null; current = current.next()) {
                if (cmp.lessThan(from, current.getData()))
                   break;
            }

            for (last = current; last != null; last = last.next()) {
                if (! cmp.greaterThan(to, last.getData()))
                    break;
            }
            markLinks(current, last);
        }


        /**
         * Implementation of the Enumeration Interface's hasMoreElements.
         * In this case if current in non-null then it will be returned on
         * the next call so we return true.
         */
        public boolean hasMoreElements() { return (current != null); }

        /**
         * Implementation of the Enumeration Interface's nextElement method.
         * We return the object from the current link, and note it for later.
         * when we return the next link we release our hold on the previous
         * one.
         */
        public Object nextElement() {
            Object result = null;

            if (current != null) {
                result = current.getData();
                current.release(id);
                current = current.next();
            }

            if (current == last) {
                players.clear(id);
                current = null;
            }


            return result;
        }

        /**
         * This finalizer will clean up the enumerator if the object
         * is garbage collected without being fully enumerated.
         */
        public void finalize() {
            boolean didRelease = false;
            if (current == null)
               return;

            for (Link l = current; l != null; l = l.next()) {
                if (l.inPlay(id)) {
                    l.release(id);
                    didRelease = true;
                }
            }
            if (didRelease)
                players.clear(id);
        }

    }


    Comparator cmp;
    Link head, tail;

    /**
     * Create an unsorted list.
     */
    public SynchroList() {  }

    /**
     * Create a prioritized list.
     */
    public SynchroList(Comparator c) { cmp = c; }

    /**
     * Insert the object before the pointed to Link.
     */
    private void before(Object o, Link p) {
        synchronized (p) {
            while (p.inPlay()) {
                p.setBlocking();
                try { p.wait(); }
                catch (InterruptedException e) { break; }
            }
            p.clearBlocking();
            new Link(o, p.prev(), p);
        }
    }

    /**
     * Insert the object after the pointed to link.
     */
    private void after(Object o, Link p) {
        synchronized (p) {
            while (p.inPlay()) {
                p.setBlocking();
                try { p.wait(); }
                catch (InterruptedException e) { break; }
            }
            p.clearBlocking();
            new Link(o, p, p.next());
        }
    }

    /**
     * Remove the Link indicated.
     */
    private void remove(Link p) {
        synchronized (p) {
            while (p.inPlay()) {
                p.setBlocking();
                try { p.wait(); }
                catch (InterruptedException e) { break; }
            }
            p.clearBlocking();
            if (p.prev() == null) {
                head = p.next();
                (p.next()).prev(null);
            } else if (p.next() == null) {
                tail = p.prev();
                (p.prev()).next(null);
            } else {
                p.prev().next(p.next());
                p.next().prev(p.prev());
            }
        }
    }


    /**
     * Interface for adding objects to the collection. In the example you
     * cannot delete objects, although adding deletion is pretty straight
     * forward.
     */
    public void add(Object o) {
        // if cmp is null, always add to the tail of the list.
        if (cmp == null) {
            if (head == null) {
                head = new Link(o, null, null);
                tail = head;
            } else {
                tail = new Link(o, tail, null);
            }
            return;
        }

        cmp.typeCheck(o); // Validate its type

        if (head == null) {
            head = new Link(o, null, null);
            tail = head;
        } else if (cmp.lessThan(o, head.getData())) {
           head = new Link(o, null, head);
        } else {
            Link l;
            for (l = head; l.next() != null; l = l.next()) {
                if (cmp.lessThan(o, l.getData())) {
                    before(o, l);
                    return;
                }
            }
            tail = new Link(o, tail, null);
        }
        return;
    }

    public boolean delete(Object o) {
        if (cmp == null)
            return false;
        for (Link l = head; l != null; l = l.next()) {
            if (cmp.equalTo(o, l.getData())) {
               remove(l);
               return true;
            }
            if (cmp.lessThan(o, l.getData()))
               break;
        }
        return false;
    }


    /**
     * The enumerator generators are synchronized because the list must
     * remain stable during their generation, however once generated
     * the object is no longer synchronized. The ListEnumerator object will
     * prevent corruption to the list.
     */
    public synchronized Enumeration elements() {
        return new LinkEnumerator();
    }
    public synchronized Enumeration elements(Object fr) {
        return new LinkEnumerator(fr);
    }
    public synchronized Enumeration elements(Object fr, Object to) {
        return new LinkEnumerator(fr, to);
    }

    /**
     * These methods extract data from 'behind' the scenes for the
     * Synchro applet to display.
     */
    public synchronized Vector stateEnum() {
        return stateEnum(null, null);
    }

    public synchronized Vector stateEnum(Object fr) {
        return stateEnum(fr, null);
    }

    public synchronized Vector stateEnum(Object fr, Object to) {
        Vector res;
        int startpos;
        Link c, l;

        if ((to != null) && cmp.greaterThan(fr, to)) {
            Object tmp = fr;
            fr = to;
            to = tmp;
        }

        startpos = 0;
        for (c = head; (fr != null) && (c != null); c = c.next()) {
            startpos++;
            if (cmp.lessThan(fr, c.getData()))
               break;
        }

        if (to != null) {
             for (l = c; l != null; l = l.next()) {
                 if (! cmp.greaterThan(to, l.getData()))
                     break;
             }
        } else l = null;

        if (c == null)
            return null; // no data to return

        res = new Vector();
        while (c != l) {
            res.addElement(new State(startpos++,
                               c.nPlayers(),
                               c.isBlocking()));
            c = c.next();
        }
        return res;
    }


    public int size() {
        int result = 0;
        for (Link l = head; l != null; l = l.next()) result++;
        return result;
    }
}