Quadcap Embeddable Database

com/quadcap/util/DList.java

Go to the documentation of this file.

package com.quadcap.util;

/* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.io.*;

import java.util.Enumeration;
/**
 * This class manages a doubly linked list, with head and tail.  It's
 * actually implemented as a circular list, with a single head pointer,
 * and the tail is <code>head.prev</code>.<p>
 *
 * It would be good to have list primitives that worked well moving items
 * from one list to another.  moveFront(), in particular, should be able
 * to splice an object out of one list and put it at the front of a
 * different list.<p>
 *
 * @author Stan Bailes
 */
public class DList {
    /** The number of entries in the list.  We are careful to track the
     * size accurately. */
    int                         size;

    /** The head of the list, null if the list is empty.  Also, an indirect
     * pointer to the tail of the list, since the list is linked circularly. */
    DListItem                   head;

    /**
     * Construct an empty DList.
     */
    public DList() {
        head = null;
        size = 0;
    }

    /**
     * Make the DList a specified size, adding null entries or deleting
     * tail entries.
     *
     * @param newsize the new size of the list
     */
    public void resize(int newsize) {
        while (size < newsize) addBack((Object)null);
        try {
            while (size > newsize) popBack();
        } catch (ListException e) {
            // rethrow as exception?
            throw new RuntimeException(e.toString());
        }
    }

    /**
     * Return the number of items in the list.
     *
     * @return the list's size
     */
    public int size() {
        return this.size;
    }

    /**
     * Add an object to the front of the list.
     *
     * @param obj the object to add
     */
    public DListItem addFront(Object obj) {
        DListItem d = new DListItem(obj);
        addFront(d);
        return d;
    }

    /**
     * Add an object after an existing list item.
     *
     * @param d the item after which the object is added
     * @param obj the object to add
     */
    public void addAfter(DListItem d, Object obj) {
        DListItem e = new DListItem(obj);
        e.next = d.next;
        e.next.prev = e;
        e.prev = d;
        d.next = e;
    }

    /**
     * Add an object before an existing list item.
     *
     * @param d the item before which the object is added
     * @param obj the object to add
     */
    public void addBefore(DListItem d, Object obj) {
        DListItem e = new DListItem(obj);
        e.next = d;
        e.prev = d.prev;
        e.prev.next = e;
        d.prev = e;
    }

    /**
     * Add an object to the back of the list.
     * @param obj the object to add
     */
    public DListItem addBack(Object obj) {
        DListItem d = new DListItem(obj);
        addBack(d);
        return d;
    }

    /**
     * Access the object at the front of the list.  Throw an exception
     * if the list is empty.
     *
     * @return the item at the head of the list
     */
    public DListItem head() throws ListException {
        if (head == null) throw new ListException("head() of empty list");
        return head;
    }

    /**
     * Access the object at the back of the list.  Throw an exception
     * if the list is empty.
     *
     * @return the item at the tail of the list
     */
    public DListItem tail() throws ListException {
        if (head == null) throw new ListException("tail() of empty list");
        return head.prev;
    }

    /**
     * Remove and return the item at the front of the list.
     *
     * @return the item at the head of the list
     */
    public DListItem popFront() throws ListException {
        if (head == null) throw new ListException("popFront() of empty list");
        DListItem d = head;
        unlink(d);
        if (d == d.next) head = null;
        else head = d.next;
        return d;
    }
    
    /**
     * Remove and return the item at the back of the list.
     *
     * @return the item at the tail of the list
     */     
    public DListItem popBack() throws ListException {
        if (head == null) throw new ListException("popBack() of empty list");
        DListItem d = head.prev;
        unlink(d);
        if (d == d.next) head = null;
        return d;
    }
    
    /**
     * This method returns a string containing the display representation
     * of this list.
     */
    public String toString() {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        show(new PrintStream(bos));
        return bos.toString();
    }

    /**
     * This method displays a list on the specified output stream.
     */
    public void show(PrintWriter os, String delim) {
        String delimiter = "";
        os.print("(");
        if (head != null) {
            boolean started = false;
            for (DListItem d = head; !started || d != head; d = d.next) {
                if (d.obj == null) continue;
                started = true;
                os.print(delimiter + d.obj);
                delimiter = delim;
            }
        }
        os.println(")");
    }

    /**
     * This method displays a list using commas as delimiters.
     *
     * @param os the PrintStream on which to display this list.
     */
    public void show(PrintStream os) {
        show(new PrintWriter(os), ", ");
    }      

    /**
     * This method displays a list using commas as delimiters.
     *
     * @param os the PrintWriter on which to display this list.
     */
    public void show(PrintWriter os) {
        show(os, ", ");
    }      

    //------------------------------------------------------------------------
    // private implementation
    //------------------------------------------------------------------------

    /**
     * Move the specified item, which is assumed to be already in the
     * list, to the front of this list.
     *
     * @param d the item to be placed at the front of this list.
     */
    public final void moveFront(DListItem d) {
        if (d != head) {
            d.next.prev = d.prev;
            d.prev.next = d.next;
            d.next = head != null ? head : d;
            d.prev = head != null ? head.prev : d;
            d.prev.next = d;
            d.next.prev = d;
            head = d;
        }
    }

    /* addFront */
    final void addFront(DListItem d) {
        addBack(d);
        head = d;
    }

    /* addBack */
    final void addBack(DListItem d) {
        size++;
        d.next = head != null ? head : d;
        d.prev = head != null ? head.prev : d;
        d.prev.next = d;
        d.next.prev = d;
        if (head == null) head = d;
    }

    /* unlink */
    public final void unlink(DListItem d) {
        if (d != null) {
            d.next.prev = d.prev;
            d.prev.next = d.next;
            if (d == d.next) {
                head = null;
            } else if (head == d) {
                head = d.next;
            }
            size--;
        }
    }

    /**
     * Return an enumeration of all of the items in this list.
     */
    public Enumeration elements() {
        final DList thislist = this;
        final DListItem thisd = head;
        
        return new Enumeration() {
            DList               dlist = thislist;
            DListItem           d = thisd;
            boolean             first = true;
            public boolean hasMoreElements() {
                return d != null && first || d != dlist.head;
            }
            public Object nextElement() {
                Object obj = d.obj;
                d = d.next;
                first = false;
                return obj;
            }
        };
    }
}