Index: src/OFMutableArray.h
==================================================================
--- src/OFMutableArray.h
+++ src/OFMutableArray.h
@@ -38,11 +38,11 @@
  */
 - (void)addObject: (id)obj
 	  atIndex: (size_t)index;
 
 /**
- * Replaces all objects equivalent to the first specified object with the
+ * Replaces the first object equivalent to the first specified object with the
  * second specified object.
  *
  * \param old The object to replace
  * \param new The replacement object
  */
@@ -52,46 +52,44 @@
 /**
  * Replaces the object at the specified index with the specified object.
  *
  * \param index The index of the object to replace
  * \param obj The replacement object
- * \return The old object, autoreleased
  */
-- (id)replaceObjectAtIndex: (size_t)index
-		withObject: (id)obj;
+- (void)replaceObjectAtIndex: (size_t)index
+		  withObject: (id)obj;
 
 /**
- * Replaces all objects that have the same address as the first specified object
- * with the second specified object.
+ * Replaces the first object that has the same address as the first specified
+ * object with the second specified object.
  *
  * \param old The object to replace
  * \param new The replacement object
  */
 - (void)replaceObjectIdenticalTo: (id)old
 		      withObject: (id)new_;
 
 /**
- * Removes all objects equivalent to the specified object.
+ * Removes the first object equivalent to the specified object.
  *
  * \param obj The object to remove
  */
 - (void)removeObject: (id)obj;
 
 /**
- * Removes all objects that have the same address as the specified object.
+ * Removes the first object that has the same address as the specified object.
  *
  * \param obj The object to remove
  */
 - (void)removeObjectIdenticalTo: (id)obj;
 
 /**
  * Removes the object at the specified index.
  *
  * \param index The index of the object to remove
- * \return The object that was at the index, autoreleased
  */
-- (id)removeObjectAtIndex: (size_t)index;
+- (void)removeObjectAtIndex: (size_t)index;
 
 /**
  * Removes the specified amount of objects from the end of the OFArray.
  *
  * \param nobjects The number of objects to remove

Index: src/OFMutableArray.m
==================================================================
--- src/OFMutableArray.m
+++ src/OFMutableArray.m
@@ -63,27 +63,28 @@
 	for (i = 0; i < count; i++) {
 		if ([objs[i] isEqual: old]) {
 			[new retain];
 			[objs[i] release];
 			objs[i] = new;
+
+			return;
 		}
 	}
 }
 
-- (id)replaceObjectAtIndex: (size_t)index
-		withObject: (id)obj
+- (void)replaceObjectAtIndex: (size_t)index
+		  withObject: (id)obj
 {
 	id *objs = [array cArray];
 	id old;
 
 	if (index >= [array count])
 		@throw [OFOutOfRangeException newWithClass: isa];
 
 	old = objs[index];
 	objs[index] = [obj retain];
-
-	return [old autorelease];
+	[old release];
 }
 
 - (void)replaceObjectIdenticalTo: (id)old
 		      withObject: (id)new
 {
@@ -93,10 +94,12 @@
 	for (i = 0; i < count; i++) {
 		if (objs[i] == old) {
 			[new retain];
 			[objs[i] release];
 			objs[i] = new;
+
+			return;
 		}
 	}
 }
 
 - (void)removeObject: (id)obj
@@ -111,21 +114,11 @@
 			[array removeItemAtIndex: i];
 			mutations++;
 
 			[obj release];
 
-			/*
-			 * We need to get the C array again as it might have
-			 * been relocated. We also need to adjust the count
-			 * as otherwise we would have an out of bounds access.
-			 * As another object will be at the current index now,
-			 * we also need to handle the same index again, thus we
-			 * decrease it.
-			 */
-			objs = [array cArray];
-			count--;
-			i--;
+			return;
 		}
 	}
 }
 
 - (void)removeObjectIdenticalTo: (id)obj
@@ -138,33 +131,22 @@
 			[array removeItemAtIndex: i];
 			mutations++;
 
 			[obj release];
 
-			/*
-			 * We need to get the C array again as it might have
-			 * been relocated. We also need to adjust the count
-			 * as otherwise we would have an out of bounds access.
-			 * As another object will be at the current index now,
-			 * we also need to handle the same index again, thus we
-			 * decrease it.
-			 */
-			objs = [array cArray];
-			count--;
-			i--;
+			return;
 		}
 	}
 }
 
-- (id)removeObjectAtIndex: (size_t)index
+- (void)removeObjectAtIndex: (size_t)index
 {
 	id old = [self objectAtIndex: index];
-
-	[self removeNObjects: 1
-		     atIndex: index];
+	[array removeItemAtIndex: index];
+	[old release];
 
-	return old;
+	mutations++;
 }
 
 - (void)removeNObjects: (size_t)nobjects
 {
 	id *objs = [array cArray], *copy;

Index: tests/OFArrayTests.m
==================================================================
--- tests/OFArrayTests.m
+++ tests/OFArrayTests.m
@@ -85,22 +85,22 @@
 
 	TEST(@"-[replaceObject:identicalTo:]",
 	    R([m[0] replaceObjectIdenticalTo: c_ary[0]
 				  withObject: c_ary[1]]) &&
 	    [[m[0] objectAtIndex: 0] isEqual: c_ary[1]] &&
-	    [[m[0] objectAtIndex: 1] isEqual: c_ary[1]] &&
+	    [[m[0] objectAtIndex: 1] isEqual: c_ary[0]] &&
 	    [[m[0] objectAtIndex: 2] isEqual: c_ary[2]])
 
 	TEST(@"-[replaceObjectAtIndex:withObject:]",
-	    [m[0] replaceObjectAtIndex: 0
-			    withObject: c_ary[0]] &&
+	    R([m[0] replaceObjectAtIndex: 0
+			      withObject: c_ary[0]]) &&
 	    [[m[0] objectAtIndex: 0] isEqual: c_ary[0]] &&
-	    [[m[0] objectAtIndex: 1] isEqual: c_ary[1]] &&
+	    [[m[0] objectAtIndex: 1] isEqual: c_ary[0]] &&
 	    [[m[0] objectAtIndex: 2] isEqual: c_ary[2]])
 
 	TEST(@"-[removeObject:]",
-	    R([m[0] removeObject: c_ary[1]]) && [m[0] count] == 2)
+	    R([m[0] removeObject: c_ary[0]]) && [m[0] count] == 2)
 
 	TEST(@"-[removeObjectIdenticalTo:]",
 	    R([m[0] removeObjectIdenticalTo: c_ary[2]]) && [m[0] count] == 1)
 
 	[m[0] addObject: c_ary[0]];
@@ -107,11 +107,11 @@
 	[m[0] addObject: c_ary[1]];
 	TEST(@"-[removeNObjects:]", R([m[0] removeNObjects: 2]) &&
 	    [m[0] count] == 1 && [[m[0] objectAtIndex: 0] isEqual: c_ary[0]])
 
 	m[1] = [[a[0] mutableCopy] autorelease];
-	TEST(@"-[removeObjectAtIndex:]", [m[1] removeObjectAtIndex: 1] &&
+	TEST(@"-[removeObjectAtIndex:]", R([m[1] removeObjectAtIndex: 1]) &&
 	    [m[1] count] == 2 && [[m[1] objectAtIndex: 1] isEqual: c_ary[2]])
 
 	m[1] = [[a[0] mutableCopy] autorelease];
 	TEST(@"-[removeNObjects:atIndex:]", R([m[1] removeNObjects: 2
 							   atIndex: 0]) &&