ObjFW  Check-in [2cb79baae4]

/*
 * Copyright (c) 2008 - 2010
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE included in
 * the packaging of this file.
 */

#import "OFObject.h"
#import "OFCollection.h"
#import "OFEnumerator.h"

/**
 * \brief A list object.
 *
 * A struct that contains a pointer to the next list object, the previous list
 * object and the object.
 */
typedef struct __of_list_object {
	/// A pointer to the next list object in the list
	struct __of_list_object *next;
	/// A pointer to the previous list object in the list
	struct __of_list_object *prev;
	/// The object for the list object
	id			object;
} of_list_object_t;

/**
 * \brief A class which provides easy to use double-linked lists.
 */
@interface OFList: OFObject <OFCopying, OFCollection, OFFastEnumeration>
{
	of_list_object_t *firstListObject;
	of_list_object_t *lastListObject;
	size_t		 count;
	unsigned long	 mutations;
}

#ifdef OF_HAVE_PROPERTIES
@property (readonly) of_list_object_t *firstListObject;
@property (readonly) of_list_object_t *lastListObject;

#endif

/**
 * \return A new autoreleased OFList
 */
+ list;

/**
 * Removes the object with the specified list object from the list.
 *
 * \param listobj The list object returned by append / prepend
 */
- (void)removeListObject: (of_list_object_t*)listobj;
@end

/// \cond internal
@interface OFListEnumerator: OFEnumerator
{
	of_list_object_t *first;
	of_list_object_t *current;
	unsigned long	 mutations;
	unsigned long	 *mutationsPtr;
}


- initWithFirstListObject: (of_list_object_t*)first
	 mutationsPointer: (unsigned long*)mutations_ptr;
@end
/// \endcond

		lastListObject->next = o;

	lastListObject = o;
	if (firstListObject == NULL)
		firstListObject = o;

	count++;
	mutations++;

	[obj retain];

	return o;
}

- (of_list_object_t*)prependObject: (id)obj

		firstListObject->prev = o;

	firstListObject = o;
	if (lastListObject == NULL)
		lastListObject = o;

	count++;
	mutations++;

	[obj retain];

	return o;
}

- (of_list_object_t*)insertObject: (id)obj

	listobj->prev = o;

	if (listobj == firstListObject)
		firstListObject = o;

	count++;
	mutations++;

	[obj retain];

	return o;
}

- (of_list_object_t*)insertObject: (id)obj

	listobj->next = o;

	if (listobj == lastListObject)
		lastListObject = o;

	count++;
	mutations++;

	[obj retain];

	return o;
}

- (void)removeListObject: (of_list_object_t*)listobj
{
	if (listobj->prev != NULL)
		listobj->prev->next = listobj->next;
	if (listobj->next != NULL)
		listobj->next->prev = listobj->prev;

	if (firstListObject == listobj)
		firstListObject = listobj->next;
	if (lastListObject == listobj)
		lastListObject = listobj->prev;

	count--;
	mutations++;

	[listobj->object release];

	[self freeMemory: listobj];
}

- (size_t)count

		OF_HASH_ADD(hash, h & 0xFF);
	}

	OF_HASH_FINALIZE(hash);

	return hash;
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	of_list_object_t **list_obj = (of_list_object_t**)state->extra;

	state->itemsPtr = objects;
	state->mutationsPtr = &mutations;

	if (state->state == 0) {
		*list_obj = firstListObject;
		state->state = 1;
	}

	if (*list_obj == NULL)
		return 0;

	objects[0] = (*list_obj)->object;
	*list_obj = (*list_obj)->next;
	return 1;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFListEnumerator alloc]
	    initWithFirstListObject: firstListObject
		   mutationsPointer: &mutations] autorelease];
}
@end

/// \cond internal
@implementation OFListEnumerator
- initWithFirstListObject: (of_list_object_t*)first_
	 mutationsPointer: (unsigned long*)mutationsPtr_;
{
	self = [super init];

	first = first_;
	current = first_;
	mutations = *mutationsPtr_;
	mutationsPtr = mutationsPtr_;

	return self;
}

- (id)nextObject
{
	id ret;

	if (*mutationsPtr != mutations)
		@throw [OFEnumerationMutationException newWithClass: isa];

	if (current == NULL)
		return nil;

	ret = current->object;
	current = current->next;

	return ret;
}

- (void)reset
{
	if (*mutationsPtr != mutations)
		@throw [OFEnumerationMutationException newWithClass: isa];

	current = first;
}
@end
/// \endcond

	while ((obj = [enumerator nextObject]) != nil) {
		if (![obj isEqual: c_ary[i]])
			ok = NO;
		[m[0] replaceObjectAtIndex: i
				withObject: @""];
		i++;
	}

	if ([m[0] count] != i)
		ok = NO;

	TEST(@"OFEnumerator's -[nextObject]", ok)

	[enumerator reset];
	[m[0] removeObjectAtIndex: 0];

	EXPECT_EXCEPTION(@"Detection of mutation during enumeration",

	for (OFString *s in m[0]) {
		if (![s isEqual: c_ary[i]])
			ok = NO;
		[m[0] replaceObjectAtIndex: i
				withObject: @""];
		i++;
	}

	if ([m[0] count] != i)
		ok = NO;

	TEST(@"Fast Enumeration", ok)

	[m[0] replaceObjectAtIndex: 0
			withObject: c_ary[0]];
	[m[0] replaceObjectAtIndex: 1
			withObject: c_ary[1]];

};

@implementation TestsAppDelegate (OFListTests)
- (void)listTests
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFList *list;
	OFEnumerator *enumerator;
	of_list_object_t *loe;
	OFString *obj;
	size_t i;
	BOOL ok;

	TEST(@"+[list]", (list = [OFList list]))

	TEST(@"-[appendObject:]", [list appendObject: strings[0]] &&
	    [list appendObject: strings[1]] && [list appendObject: strings[2]])

	TEST(@"-[firstListObject]",

	    [list lastListObject]->object])

	TEST(@"-[insertObject:beforeListObject:]",
	    [list insertObject: strings[0]
	      beforeListObject: [list lastListObject]] &&
	    [[list lastListObject]->prev->object isEqual: strings[0]])


	TEST(@"-[insertObject:afterListObject:]",
	    [list insertObject: strings[2]
	       afterListObject: [list firstListObject]->next] &&
	    [[list lastListObject]->object isEqual: strings[2]])

	TEST(@"-[count]", [list count] == 3)

	TEST(@"-[copy]", (list = [[list copy] autorelease]) &&
	    [[list firstListObject]->object isEqual: strings[0]] &&
	    [[list firstListObject]->next->object isEqual: strings[1]] &&
	    [[list lastListObject]->object isEqual: strings[2]])

	TEST(@"-[isEqual:]", [list isEqual: [[list copy] autorelease]])

	TEST(@"-[objectEnumerator]", (enumerator = [list objectEnumerator]))

	loe = [list firstListObject];
	i = 0;
	ok = YES;
	while ((obj = [enumerator nextObject]) != nil) {
		if (![obj isEqual: loe->object])
			ok = NO;

		loe = loe->next;
		i++;
	}

	if ([list count] != i)
		ok = NO;

	TEST(@"OFEnumerator's -[nextObject]", ok);

	[enumerator reset];
	[list removeListObject: [list firstListObject]];

	EXPECT_EXCEPTION(@"Detection of mutation during enumeration",
	    OFEnumerationMutationException, [enumerator nextObject])

	[list prependObject: strings[0]];

#ifdef OF_HAVE_FAST_ENUMERATION
	loe = [list firstListObject];
	i = 0;
	ok = YES;

	for (OFString *obj in list) {
		if (![obj isEqual: loe->object])
			ok = NO;

		loe = loe->next;
		i++;
	}

	if ([list count] != i)
		ok = NO;

	TEST(@"Fast Enumeration", ok)

	ok = NO;
	@try {
		for (OFString *obj in list)
			[list removeListObject: [list lastListObject]];
	} @catch (OFEnumerationMutationException *e) {
		ok = YES;
		[e dealloc];
	}

	TEST(@"Detection of mutation during Fast Enumeration", ok)
#endif

	[pool drain];
}
@end