source: nanovis/trunk/Chain.cpp @ 4890

/* -*- mode: c++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* The module implements a generic linked list package.
 *
 * Copyright 1991-2004 George A Howlett.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include <stdlib.h>
#include <stdio.h>

#include "Chain.h"

using namespace nv;

typedef int (QSortCompareProc) (const void *, const void *);

/**
 * Removes all the links from the chain, freeing the memory for each
 * link.  Memory pointed to by the link (clientData) is not freed.  It's
 * the caller's responsibility to deallocate it.
 */
void
Chain::reset()
{
    ChainLink *oldPtr;
    ChainLink *linkPtr = _head;

    while (linkPtr != NULL) {
        oldPtr = linkPtr;
        linkPtr = linkPtr->next();
        delete oldPtr;
    }
    init();
}

/**
 * Inserts a link after another link.  If afterPtr is NULL, then the new
 * link is prepended to the beginning of the chain.
 */
void
Chain::linkAfter(ChainLink *linkPtr, ChainLink *afterPtr)
{
    if (_head == NULL) {
        _tail = _head = linkPtr;
    } else {
        if (afterPtr == NULL) {
            /* Prepend to the front of the chain */
            linkPtr->_next = _head;
            linkPtr->_prev = NULL;
            _head->_prev = linkPtr;
            _head = linkPtr;
        } else {
            linkPtr->_next = afterPtr->next();
            linkPtr->_prev = afterPtr;
            if (afterPtr == _tail) {
                _tail = linkPtr;
            } else {
                afterPtr->next()->_prev = linkPtr;
            }
            afterPtr->_next = linkPtr;
        }
    }
    _nLinks++;
}

/**
 * Inserts a new link preceding a given link in a chain.  If beforePtr is
 * NULL, then the new link is placed at the beginning of the list.
 *
 * \param linkPtr New entry to be inserted
 * \param beforePtr Entry to link before
 */
void
Chain::linkBefore(ChainLink *linkPtr,
                  ChainLink *beforePtr)
{
    if (_head == NULL) {
        _tail = _head = linkPtr;
    } else {
        if (beforePtr == NULL) {
            // Append to the end of the chain.
            linkPtr->_next = NULL;
            linkPtr->_prev = _tail;
            _tail->_next = linkPtr;
            _tail = linkPtr;
        } else {
            linkPtr->_prev = beforePtr->prev();
            linkPtr->_next = beforePtr;
            if (beforePtr == _head) {
                _head = linkPtr;
            } else {
                beforePtr->prev()->_next = linkPtr;
            }
            beforePtr->_prev = linkPtr;
        }
    }
    _nLinks++;
}

/**
 * Unlinks a link from the chain. The link is not deallocated, 
 * but only removed from the chain.
 */
void
Chain::unlink(ChainLink *linkPtr)
{
    bool unlinked;              /* Indicates if the link is actually removed
                                 * from the chain. */

    unlinked = false;
    if (_head == linkPtr) {
        _head = linkPtr->next();
        unlinked = true;
    }
    if (_tail == linkPtr) {
        _tail = linkPtr->prev();
        unlinked = true;
    }
    if (linkPtr->next() != NULL) {
        linkPtr->next()->_prev = linkPtr->prev();
        unlinked = true;
    }
    if (linkPtr->prev() != NULL) {
        linkPtr->prev()->_next = linkPtr->next();
        unlinked = true;
    }
    if (unlinked) {
        _nLinks--;
    }
    linkPtr->_prev = linkPtr->_next = NULL;
}

/**
 * Unlinks and frees the given link from the chain.  It's assumed that
 * the link belong to the chain. No error checking is performed to verify
 * this.
 */
void
Chain::deleteLink(ChainLink *linkPtr)
{
    unlink(linkPtr);
    delete linkPtr;
}

/**
 * Creates and new link with the given data and appends it to the end of
 * the chain.
 *
 * \return a pointer to the link created.
 */
ChainLink *
Chain::append(void *clientData)
{
    ChainLink *linkPtr;

    linkPtr = new ChainLink(clientData);
    linkBefore(linkPtr, (ChainLink *)NULL);
    return linkPtr;
}

/**
 * Creates and new link with the given data and prepends it to beginning
 * of the chain.
 *
 * \return a pointer to the link created.
 */
ChainLink  *
Chain::prepend(void *clientData)
{
    ChainLink *linkPtr;

    linkPtr = new ChainLink(clientData);
    linkAfter(linkPtr, (ChainLink *)NULL);
    return linkPtr;
}

/**
 * Find the link at the given position in the chain.
 *
 * \param position Index of link to select from front or back of the chain.
 *
 * \return  the pointer to the link, if that numbered link
 * exists. Otherwise NULL.
 */
ChainLink *
Chain::getNthLink(long position)
{
    ChainLink *linkPtr;

    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) {
        if (position == 0) {
            return linkPtr;
        }
        position--;
    }
    return NULL;
}

/**
 * Sorts the chain according to the given comparison routine.  
 *
 * Side Effects:
 *   The chain is reordered.
 */
void
Chain::sort(ChainCompareProc *proc)
{
    ChainLink *linkPtr;
    long i;

    if (_nLinks < 2) {
        return;
    }
    ChainLink **linkArr = new ChainLink *[_nLinks + 1];
    if (linkArr == NULL) {
        return;                 /* Out of memory. */
    }
    i = 0;
    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->next()) { 
        linkArr[i++] = linkPtr;
    }
    qsort((char *)linkArr, _nLinks, sizeof(ChainLink *), 
          (QSortCompareProc *)proc);

    /* Rethread the chain. */
    linkPtr = linkArr[0];
    _head = linkPtr;
    linkPtr->_prev = NULL;
    for (i = 1; i < _nLinks; i++) {
        linkPtr->_next = linkArr[i];
        linkPtr->next()->_prev = linkPtr;
        linkPtr = linkPtr->next();
    }
    _tail = linkPtr;
    linkPtr->_next = NULL;
    delete [] linkArr;
}