/* Implementation of Objective C NeXT-compatible List object
   
   Copyright (C) 1993 R. Andrew McCallum <mccallum@cs.rochester.edu>
   Dept. of Computer Science, U. of Rochester, Rochester, NY  14627
   
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
   
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   */ 

#include <coll/List.h>
#include <stdlib.h>
#include <coll/collstd.h>

#define LIST_GROW_FACTOR 2

/* Do this before adding an element */
static inline void 
incrementCount(List *self)
{
  (self->numElements)++;
  if (self->numElements == self->maxElements)
    {
      [self setAvailableCapacity:(self->numElements) * LIST_GROW_FACTOR];
    }
}

/* Do this after removing an element */
static inline void
decrementCount(List *self)
{
  (self->numElements)--;
  if (self->numElements < (self->maxElements) / LIST_GROW_FACTOR)
    {
      [self setAvailableCapacity:(self->maxElements) / LIST_GROW_FACTOR];
    }
}

@implementation List
  
+ initialize
{
  if (self == [List class])
    [self setVersion:-1];	/* alpha release */
  return self;
}

// INITIALIZING, FREEING;

- initCount:(unsigned)numSlots;
{
  [super init];
  numElements = 0;
  maxElements = numSlots;
  OBJC_MALLOC(dataPtr, id, maxElements);
  return self;
}

- init
{
  return [self initCount:2];
}


- free
{
  if (dataPtr)
    free(dataPtr);
  return [super free];
}

- freeObjects
{
  [self makeObjectsPerform:@selector(free)];
  [self empty];
  return self;
}

// COPYING;

- shallowCopy
{
  List *c = [super shallowCopy];
  OBJC_MALLOC(c->dataPtr, id, maxElements);
  bcopy(dataPtr, c->dataPtr, numElements * sizeof(id *));
  return c;
}

- deepen
{
  int i;
  
  for (i = 0; i < numElements; i++) 
    {
      dataPtr[i] = [dataPtr[i] deepCopy];
    }
  return self;
}

// COMPARING TWO LISTS;

- (BOOL)isEqual: anObject
{
  int i;
  
  if ( ! [anObject isKindOf:[List class]] )
    return NO;
  for (i = 0; i < numElements; i++)
    /* NeXT documentation says to compare id's. */
    if ( dataPtr[i] != [anObject objectAt:i] )
      return NO;
  return YES;
}

// MANAGING THE STORAGE CAPACITY;

- (unsigned)capacity
{
  return maxElements;
}

- setAvailableCapacity:(unsigned)numSlots
{
  if (numSlots > numElements) 
    {
      maxElements = numSlots;
      dataPtr = (id *) realloc(dataPtr, maxElements * sizeof(id));
      return self;
    }
  return nil;
}

static inline void _makeRoomForAnotherIfNecessary(List *self)
{
  if (self->numElements == self->maxElements) 
    {
      self->maxElements *= 2;
      self->dataPtr = (id *) realloc(self->dataPtr, 
				     self->maxElements * sizeof(id));
    }
}

static inline void _shrinkIfDesired(List *self)
{
  if (self->numElements < (self->maxElements / 2)) 
    {
      self->maxElements /= 2;
      self->dataPtr = (id *) realloc(self->dataPtr, 
				     self->maxElements * sizeof(id));
    }
}

/* Manipulating objects by index */

#define CHECK_INDEX(IND)  if (IND >= numElements) return nil 
#define CHECK_OBJECT(OBJ)  if (!OBJ) return nil
  
- (unsigned)count
{
  return numElements;
}

- objectAt:(unsigned)index
{
  CHECK_INDEX(index);
  return dataPtr[index];
}

- lastObject
{
  if (numElements)
    return dataPtr[numElements-1];
  else
    return nil;
}

- addObject:anObject
{
  CHECK_OBJECT(anObject);
  incrementCount(self);
  dataPtr[numElements-1] = anObject;
  return self;
}

- insertObject:anObject at:(unsigned)index
{
  int i;
  
  CHECK_INDEX(index);
  CHECK_OBJECT(anObject);
  incrementCount(self);
  for (i = numElements-1; i > index; i--)
    dataPtr[i] = dataPtr[i-1];
  dataPtr[i] = anObject;
  return self;
}

- removeObjectAt:(unsigned)index
{
  int i;
  
  CHECK_INDEX(index);
  for (i = index; i < numElements-1; i++)
    dataPtr[i] = dataPtr[i+1];
  decrementCount(self);
  return self;
}

- removeLastObject
{
  if (numElements) 
    {
      id ret = dataPtr[numElements-1];
      decrementCount(self);
      return ret;
    }
  return nil;
}

- replaceObjectAt:(unsigned)index with:newObject
{
  CHECK_INDEX(index);
  CHECK_OBJECT(newObject);
  dataPtr[index] = newObject;
  return self;
}

/* Inefficient, but it handles subclasses of List nicely */
- appendList: (List *)otherList
{
  int i, c;
  
  c = [otherList count];
  for (i = 0; i < c; i++)
    [self addObject:[otherList objectAt:i]];
  return self;
}

/* Manipulating objects by id */

- (unsigned) indexOf:anObject
{
  int i;
  
  for (i = 0; i < numElements; i++)
    if ([dataPtr[i] isEqual:anObject])
      return i;
  return GNU_NOT_IN_LIST;
}

- addObjectIfAbsent:anObject
{
  CHECK_OBJECT(anObject);
  if ([self indexOf:anObject] == GNU_NOT_IN_LIST)
    [self addObject:anObject];
  return self;
}

- removeObject:anObject
{
  CHECK_OBJECT(anObject);
  return [self removeObjectAt:[self indexOf:anObject]];
}

- replaceObject:anObject with:newObject
{
  return [self replaceObjectAt:[self indexOf:anObject]
	       with:newObject];
}

/* Emptying the list */

- empty
{
  numElements = 0;
  maxElements = 2;
  OBJC_REALLOC(dataPtr, id, maxElements);
  return self;
}

/* Archiving */

 - write: (TypedStream*)aStream
 {
   [super write: aStream];
   objc_write_types (aStream, "II", &numElements, &maxElements);
   objc_write_array (aStream, "@", numElements, dataPtr);
   return self;
 }

 - read: (TypedStream*)aStream
 {
   [super read: aStream];
   objc_read_types (aStream, "II", &numElements, &maxElements);
   dataPtr = (id *) malloc (maxElements * sizeof (id));
   objc_read_array (aStream, "@", numElements, dataPtr);
   return self;
 }

/* Sending messages to elements of the list */

- makeObjectsPerform:(SEL)aSel
{
  int i;
  
  for (i = 0; i < numElements; i++)
    [dataPtr[i] perform:aSel];
  return self;
}

- makeObjectsPerform:(SEL)aSel with:anObject
{
  int i;
  
  for (i = 0; i < numElements; i++)
    [dataPtr[i] perform:aSel with:anObject];
  return self;
}

/* Sorting */

- sortUsingMethod:(SEL)aSel inObject:anObject
{
  int (*sorting_imp)(id,SEL,id,id) = 
    (int(*)(id,SEL,id,id))objc_msg_lookup(anObject, aSel);
  int sorting_comparator(const void *o1, const void *o2)
    {
      return sorting_imp(anObject, aSel,
			 *((id *)o1), *((id *)o2));
    }
  
  qsort(dataPtr, numElements, sizeof(id), sorting_comparator);
  return self;
}

/* Old-style creation */

+ newCount:(unsigned)numSlots
{
  return [[self alloc] initCount:numSlots];
}

@end
