/*
* Copyright (C) 2003 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.
*/
#import "KWQListImpl.h"
#import <cstddef>
#import <algorithm>
#import <CoreFoundation/CFArray.h>
#import "KWQAssertions.h"
class KWQListNode
{
public:
KWQListNode(void *d) : data(d), next(NULL), prev(NULL) { }
void *data;
KWQListNode *next;
KWQListNode *prev;
};
static KWQListNode *copyList(KWQListNode *l, KWQListNode *&tail)
{
KWQListNode *node = l;
KWQListNode *copyHead = NULL;
KWQListNode *last = NULL;
while (node != NULL) {
KWQListNode *copy = new KWQListNode(node->data);
if (last != NULL) {
last->next = copy;
} else {
copyHead = copy;
}
copy->prev = last;
last = copy;
node = node->next;
}
tail = last;
return copyHead;
}
KWQListImpl::KWQListImpl(void (*deleteFunc)(void *)) :
head(NULL),
tail(NULL),
cur(NULL),
nodeCount(0),
deleteItem(deleteFunc),
iterators(NULL)
{
}
KWQListImpl::KWQListImpl(const KWQListImpl &impl) :
cur(NULL),
nodeCount(impl.nodeCount),
deleteItem(impl.deleteItem),
iterators(NULL)
{
head = copyList(impl.head, tail);
}
KWQListImpl::~KWQListImpl()
{
clear(false);
KWQListIteratorImpl *next;
for (KWQListIteratorImpl *it = iterators; it != NULL; it = next) {
next = it->next;
it->list = NULL;
ASSERT(it->node == NULL);
it->next = NULL;
it->prev = NULL;
}
}
void KWQListImpl::clear(bool deleteItems)
{
KWQListNode *next;
for (KWQListNode *node = head; node != NULL; node = next) {
next = node->next;
if (deleteItems) {
deleteItem(node->data);
}
delete node;
}
head = NULL;
tail = NULL;
cur = NULL;
nodeCount = 0;
for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
it->node = NULL;
}
}
void KWQListImpl::sort(int (*compareFunc)(void *a, void *b, void *data), void *data)
{
// no sorting for 0 or 1-element lists
if (nodeCount <= 1) {
return;
}
// special case for 2-element lists
if (nodeCount == 2) {
void *a = head->data;
void *b = head->next->data;
if (compareFunc(a, b, data) <= 0) {
return;
}
head->next->data = a;
head->data = b;
return;
}
// insertion sort for most common sizes
const uint cutoff = 32;
if (nodeCount <= cutoff) {
// Straight out of Sedgewick's Algorithms in C++.
// put all the elements into an array
void *a[cutoff];
uint i = 0;
for (KWQListNode *node = head; node != NULL; node = node->next) {
a[i++] = node->data;
}
// move the smallest element to the start to serve as a sentinel
for (i = nodeCount - 1; i > 0; i--) {
if (compareFunc(a[i-1], a[i], data) > 0) {
void *t = a[i-1];
a[i-1] = a[i];
a[i] = t;
}
}
// move other items to the right and put a[i] into position
for (i = 2; i < nodeCount; i++) {
void *v = a[i];
uint j = i;
while (compareFunc(v, a[j-1], data) < 0) {
a[j] = a[j-1];
j--;
}
a[j] = v;
}
// finally, put everything back into the list
i = 0;
for (KWQListNode *node = head; node != NULL; node = node->next) {
node->data = a[i++];
}
return;
}
// CFArray sort for larger lists
CFMutableArrayRef array = CFArrayCreateMutable(NULL, nodeCount, NULL);
for (KWQListNode *node = head; node != NULL; node = node->next) {
CFArrayAppendValue(array, node->data);
}
CFArraySortValues(array, CFRangeMake(0, nodeCount), (CFComparatorFunction) compareFunc, data);
int i = 0;
for (KWQListNode *node = head; node != NULL; node = node->next) {
node->data = const_cast<void *>(CFArrayGetValueAtIndex(array, i++));
}
CFRelease(array);
}
void *KWQListImpl::at(uint n)
{
KWQListNode *node;
if (n >= nodeCount - 1) {
node = tail;
} else {
node = head;
for (uint i = 0; i < n && node != NULL; i++) {
node = node->next;
}
}
cur = node;
return node ? node->data : 0;
}
bool KWQListImpl::insert(uint n, const void *item)
{
if (n > nodeCount) {
return false;
}
KWQListNode *node = new KWQListNode((void *)item);
if (n == 0) {
// inserting at head
node->next = head;
if (head != NULL) {
head->prev = node;
}
head = node;
if (tail == NULL) {
tail = node;
}
} else if (n == nodeCount) {
// inserting at tail
node->prev = tail;
if (tail != NULL) {
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
KWQListNode *prevNode = head;
for (uint i = 0; i < n - 1; i++) {
prevNode = prevNode->next;
}
node->prev = prevNode;
node->next = prevNode->next;
if (node->next != NULL) {
node->next->prev = node;
}
prevNode->next = node;
}
nodeCount++;
cur = node;
return true;
}
bool KWQListImpl::remove(bool shouldDeleteItem)
{
KWQListNode *node = cur;
if (node == NULL) {
return false;
}
if (node->prev == NULL) {
head = node->next;
} else {
node->prev->next = node->next;
}
if (node->next == NULL) {
tail = node->prev;
} else {
node->next->prev = node->prev;
}
if (node->next != NULL) {
cur = node->next;
} else {
cur = node->prev;
}
for (KWQListIteratorImpl *it = iterators; it != NULL; it = it->next) {
if (it->node == node) {
it->node = cur;
}
}
if (shouldDeleteItem) {
deleteItem(node->data);
}
delete node;
nodeCount--;
return true;
}
bool KWQListImpl::remove(uint n, bool deleteItem)
{
if (n >= nodeCount) {
return false;
}
at(n);
return remove(deleteItem);
}
bool KWQListImpl::removeFirst(bool deleteItem)
{
return remove(0, deleteItem);
}
bool KWQListImpl::removeLast(bool deleteItem)
{
return remove(nodeCount - 1, deleteItem);
}
bool KWQListImpl::remove(const void *item, bool deleteItem, int (*compareFunc)(void *a, void *b, void *data), void *data)
{
KWQListNode *node;
node = head;
while (node != NULL && compareFunc((void *)item, node->data, data) != 0) {
node = node->next;
}
if (node == NULL) {
return false;
}
cur = node;
return remove(deleteItem);
}
bool KWQListImpl::removeRef(const void *item, bool deleteItem)
{
KWQListNode *node;
node = head;
while (node != NULL && item != node->data) {
node = node->next;
}
if (node == NULL) {
return false;
}
cur = node;
return remove(deleteItem);
}
void *KWQListImpl::getFirst() const
{
return head ? head->data : 0;
}
void *KWQListImpl::getLast() const
{
return tail ? tail->data : 0;
}
void *KWQListImpl::current() const
{
if (cur != NULL) {
return cur->data;
} else {
return NULL;
}
}
void *KWQListImpl::first()
{
cur = head;
return current();
}
void *KWQListImpl::last()
{
cur = tail;
return current();
}
void *KWQListImpl::next()
{
if (cur != NULL) {
cur = cur->next;
}
return current();
}
void *KWQListImpl::prev()
{
if (cur != NULL) {
cur = cur->prev;
}
return current();
}
void *KWQListImpl::take(uint n)
{
void *retval = at(n);
remove(false);
return retval;
}
void *KWQListImpl::take()
{
void *retval = current();
remove(false);
return retval;
}
void KWQListImpl::append(const void *item)
{
insert(nodeCount, item);
}
void KWQListImpl::prepend(const void *item)
{
insert(0, item);
}
uint KWQListImpl::containsRef(const void *item) const
{
uint count = 0;
for (KWQListNode *node = head; node != NULL; node = node->next) {
if (item == node->data) {
++count;
}
}
return count;
}
KWQListImpl &KWQListImpl::assign(const KWQListImpl &impl, bool deleteItems)
{
clear(deleteItems);
KWQListImpl(impl).swap(*this);
return *this;
}
void KWQListImpl::addIterator(KWQListIteratorImpl *iter) const
{
iter->next = iterators;
iter->prev = NULL;
if (iterators != NULL) {
iterators->prev = iter;
}
iterators = iter;
}
void KWQListImpl::removeIterator(KWQListIteratorImpl *iter) const
{
if (iter->prev == NULL) {
iterators = iter->next;
} else {
iter->prev->next = iter->next;
}
if (iter->next != NULL) {
iter->next->prev = iter->prev;
}
}
void KWQListImpl::swap(KWQListImpl &other)
{
using std::swap;
ASSERT(iterators == NULL);
ASSERT(other.iterators == NULL);
swap(head, other.head);
swap(tail, other.tail);
swap(cur, other.cur);
swap(nodeCount, other.nodeCount);
swap(deleteItem, other.deleteItem);
}
KWQListIteratorImpl::KWQListIteratorImpl() :
list(NULL),
node(NULL)
{
}
KWQListIteratorImpl::KWQListIteratorImpl(const KWQListImpl &impl) :
list(&impl),
node(impl.head)
{
impl.addIterator(this);
}
KWQListIteratorImpl::~KWQListIteratorImpl()
{
if (list != NULL) {
list->removeIterator(this);
}
}
KWQListIteratorImpl::KWQListIteratorImpl(const KWQListIteratorImpl &impl) :
list(impl.list),
node(impl.node)
{
if (list != NULL) {
list->addIterator(this);
}
}
uint KWQListIteratorImpl::count() const
{
return list == NULL ? 0 : list->count();
}
void *KWQListIteratorImpl::toFirst()
{
if (list != NULL) {
node = list->head;
}
return current();
}
void *KWQListIteratorImpl::toLast()
{
if (list != NULL) {
node = list->tail;
}
return current();
}
void *KWQListIteratorImpl::current() const
{
return node == NULL ? NULL : node->data;
}
void *KWQListIteratorImpl::operator--()
{
if (node != NULL) {
node = node->prev;
}
return current();
}
void *KWQListIteratorImpl::operator++()
{
if (node != NULL) {
node = node->next;
}
return current();
}
KWQListIteratorImpl &KWQListIteratorImpl::operator=(const KWQListIteratorImpl &impl)
{
if (list != NULL) {
list->removeIterator(this);
}
list = impl.list;
node = impl.node;
if (list != NULL) {
list->addIterator(this);
}
return *this;
}