/*

 * Copyright (C) 2003, 2006 Apple Computer, Inc.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

 */

#include "config.h"

#include "DeprecatedPtrListImpl.h"

#include <cstddef>

#include <algorithm>

#include <wtf/Assertions.h>

#include <wtf/Noncopyable.h>

namespace WebCore {

class DeprecatedListNode : public Noncopyable

{

public:

    DeprecatedListNode(void *d) : data(d), next(0), prev(0) { }

    void *data;

    DeprecatedListNode *next;

    DeprecatedListNode *prev;

};

static DeprecatedListNode *copyList(DeprecatedListNode *l, DeprecatedListNode *&tail)

{

    DeprecatedListNode *node = l;

    DeprecatedListNode *copyHead = 0;

    DeprecatedListNode *last = 0;

    while (node != 0) {

        DeprecatedListNode *copy = new DeprecatedListNode(node->data);

        if (last != 0) {

            last->next = copy;

        } else {

            copyHead = copy;

        }

        copy->prev = last;

        last = copy;

        node = node->next;

    }

    tail = last;

    return copyHead;

}

DeprecatedPtrListImpl::DeprecatedPtrListImpl(void (*deleteFunc)(void *)) :

    head(0),

    tail(0),

    cur(0),

    nodeCount(0),

    deleteItem(deleteFunc),

    iterators(0)

{

}

DeprecatedPtrListImpl::DeprecatedPtrListImpl(const DeprecatedPtrListImpl &impl) :

    cur(0),

    nodeCount(impl.nodeCount),

    deleteItem(impl.deleteItem),

    iterators(0)

{

    head = copyList(impl.head, tail);

}

DeprecatedPtrListImpl::~DeprecatedPtrListImpl()

{

    clear(false);

    DeprecatedPtrListImplIterator *next;

    for (DeprecatedPtrListImplIterator *it = iterators; it; it = next) {

        next = it->next;

        it->list = 0;

        ASSERT(!it->node);

        it->next = 0;

        it->prev = 0;

    }

}

void DeprecatedPtrListImpl::clear(bool deleteItems)

{

    DeprecatedListNode *next;

    for (DeprecatedListNode *node = head; node; node = next) {

        next = node->next;

        if (deleteItems)

            deleteItem(node->data);

        delete node;

    }

    head = 0;

    tail = 0;

    cur = 0;

    nodeCount = 0;

    for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next)

        it->node = 0;

}

void *DeprecatedPtrListImpl::at(unsigned n)

{

    DeprecatedListNode *node;

    if (n >= nodeCount - 1) {

        node = tail;

    } else {

        node = head;

        for (unsigned i = 0; i < n && node; i++) {

            node = node->next;

        }

    }

    cur = node;

    return node ? node->data : 0;

}

bool DeprecatedPtrListImpl::insert(unsigned n, const void *item)

{

    if (n > nodeCount) {

        return false;

    }

    DeprecatedListNode *node = new DeprecatedListNode(const_cast<void*>(item));

    if (n == 0) {

        // inserting at head

        node->next = head;

        if (head) {

            head->prev = node;

        }

        head = node;

        if (tail == 0) {

            tail = node;

        }

    } else if (n == nodeCount) {

        // inserting at tail

        node->prev = tail;

        if (tail) {

            tail->next = node;

        }

        tail = node;

    } else {

        // general insertion

        // iterate to one node before the insertion point, can't be null

        // since we know n > 0 and n < nodeCount

        DeprecatedListNode *prevNode = head;

        for (unsigned i = 0; i < n - 1; i++) {

            prevNode = prevNode->next;

        }

        node->prev = prevNode;

        node->next = prevNode->next;

        if (node->next) {

            node->next->prev = node;

        }

        prevNode->next = node;

    }

    nodeCount++;

    cur = node;

    return true;

}

bool DeprecatedPtrListImpl::remove(bool shouldDeleteItem)

{

    DeprecatedListNode *node = cur;

    if (node == 0) {

        return false;

    }

    if (node->prev == 0) {

        head = node->next;

    } else {

        node->prev->next = node->next;

    }

    if (node->next == 0) {

        tail = node->prev;

    } else {

        node->next->prev = node->prev;

    }

    if (node->next) {

        cur = node->next;

    } else {

        cur = node->prev;

    }

    for (DeprecatedPtrListImplIterator *it = iterators; it; it = it->next) {

        if (it->node == node) {

            it->node = cur;

        }

    }

    if (shouldDeleteItem) {

        deleteItem(node->data);

    }

    delete node;

    nodeCount--;

    return true;

}

bool DeprecatedPtrListImpl::remove(unsigned n, bool deleteItem)

{

    if (n >= nodeCount) {

        return false;

    }

    at(n);

    return remove(deleteItem);

}

bool DeprecatedPtrListImpl::removeFirst(bool deleteItem)

{

    return remove(0, deleteItem);

}

bool DeprecatedPtrListImpl::removeLast(bool deleteItem)

{

    return remove(nodeCount - 1, deleteItem);

}

bool DeprecatedPtrListImpl::removeRef(const void *item, bool deleteItem)

{

    DeprecatedListNode *node;

    node = head;

    while (node && item != node->data) {

        node = node->next;

    }

    if (node == 0) {

        return false;

    }

    cur = node;

    return remove(deleteItem);

}

void *DeprecatedPtrListImpl::getFirst() const

{

    return head ? head->data : 0;

}

void *DeprecatedPtrListImpl::getLast() const

{

    return tail ? tail->data : 0;

}

void *DeprecatedPtrListImpl::getNext() const

{

    return cur && cur->next ? cur->next->data : 0;

}

void *DeprecatedPtrListImpl::getPrev() const

{

    return cur && cur->prev ? cur->prev->data : 0;

}

void *DeprecatedPtrListImpl::current() const

{

    if (cur) {

        return cur->data;

    } else {

        return 0;

    }

}

void *DeprecatedPtrListImpl::first()

{

    cur = head;

    return current();

}

void *DeprecatedPtrListImpl::last()

{

    cur = tail;

    return current();

}

void *DeprecatedPtrListImpl::next()

{

    if (cur) {

        cur = cur->next;

    }

    return current();

}

void *DeprecatedPtrListImpl::prev()

{

    if (cur) {

        cur = cur->prev;

    }

    return current();

}

void *DeprecatedPtrListImpl::take(unsigned n)

{

    void *retval = at(n);

    remove(false);

    return retval;

}

void *DeprecatedPtrListImpl::take()

{

    void *retval = current();

    remove(false);

    return retval;

}

void DeprecatedPtrListImpl::append(const void *item)

{

    insert(nodeCount, item);

}

void DeprecatedPtrListImpl::prepend(const void *item)

{

    insert(0, item);

}

unsigned DeprecatedPtrListImpl::containsRef(const void *item) const

{

    unsigned count = 0;

    for (DeprecatedListNode *node = head; node; node = node->next) {

        if (item == node->data) {

            ++count;

        }

    }

    return count;

}

int DeprecatedPtrListImpl::findRef(const void *item)

{

    DeprecatedListNode *node = head;

    int index = 0;

    while (node && item != node->data) {

        node = node->next;

        index++;

    }

    cur = node;

    if (node == 0) {

        return -1;

    }

    return index;

}

DeprecatedPtrListImpl &DeprecatedPtrListImpl::assign(const DeprecatedPtrListImpl &impl, bool deleteItems)

{

    clear(deleteItems);

    DeprecatedPtrListImpl(impl).swap(*this);

    return *this;

}

void DeprecatedPtrListImpl::addIterator(DeprecatedPtrListImplIterator *iter) const

{

    iter->next = iterators;

    iter->prev = 0;

    if (iterators) {

        iterators->prev = iter;

    }

    iterators = iter;

}

void DeprecatedPtrListImpl::removeIterator(DeprecatedPtrListImplIterator *iter) const

{

    if (iter->prev == 0) {

        iterators = iter->next;

    } else {

        iter->prev->next = iter->next;

    }

    if (iter->next) {

        iter->next->prev = iter->prev;

    }

}

void DeprecatedPtrListImpl::swap(DeprecatedPtrListImpl &other)

{

    using std::swap;

    ASSERT(iterators == 0);

    ASSERT(other.iterators == 0);

    swap(head, other.head);

    swap(tail, other.tail);

    swap(cur, other.cur);

    swap(nodeCount, other.nodeCount);

    swap(deleteItem, other.deleteItem);

}

DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator() :

    list(0),

    node(0)

{

}

DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImpl &impl)  :

    list(&impl),

    node(impl.head)

{

    impl.addIterator(this);

}

DeprecatedPtrListImplIterator::~DeprecatedPtrListImplIterator()

{

    if (list) {

        list->removeIterator(this);

    }

}

DeprecatedPtrListImplIterator::DeprecatedPtrListImplIterator(const DeprecatedPtrListImplIterator &impl) :

    list(impl.list),

    node(impl.node)

{

    if (list) {

        list->addIterator(this);

    }

}

unsigned DeprecatedPtrListImplIterator::count() const

{

    return list == 0 ? 0 : list->count();

}

void *DeprecatedPtrListImplIterator::toFirst()

{

    if (list) {

        node = list->head;

    }

    return current();

}

void *DeprecatedPtrListImplIterator::toLast()

{

    if (list) {

        node = list->tail;

    }

    return current();

}

void *DeprecatedPtrListImplIterator::current() const

{

    return node == 0 ? 0 : node->data;

}

void *DeprecatedPtrListImplIterator::operator--()

{

    if (node) {

        node = node->prev;

    }

    return current();

}

void *DeprecatedPtrListImplIterator::operator++()

{

    if (node) {

        node = node->next;

    }

    return current();

}

DeprecatedPtrListImplIterator &DeprecatedPtrListImplIterator::operator=(const DeprecatedPtrListImplIterator &impl)

{

    if (list) {

        list->removeIterator(this);

    }

    list = impl.list;

    node = impl.node;

    if (list) {

        list->addIterator(this);

    }

    return *this;

}

}