
/*
 * Computer Algebra Kit (c) 1994,98 by Comp.Alg.Objects.  All Rights Reserved.
 * $Id: ccltn.m,v 1.9 1998/11/13 09:45:19 stes Exp $
 */

#include "cakit.h"

static int 
mmbs_check(mmbs_t a, int n)
{
  assert(a && 0 <= n);
  while (n--)
    assert(*a++);
  return 1;
}

static mmbs_t 
mmbs_alloc(int n)
{
  assert(0 <= n);
  return (mmbs_t) OC_Malloc(sizeof(id) * n);
}

static void 
mmbs_copy(mmbs_t c, mmbs_t a, int n)
{
  assert(0 <= n);
  while (n--)
    *c++ = [*a++ cheapCopy];
}

static void 
mmbs_deepcopy(mmbs_t c, mmbs_t a, int n)
{
  assert(0 <= n);
  while (n--)
    *c++ = [*a++ deepCopy];
}

static void 
mmbs_free(mmbs_t a, int n)
{
  assert(0 <= n);
  a += n;
  while (n--) {
    --a;
    *a = [*a free];
  }
  OC_Free(a);			/* points to start of array now ! */
}

static BOOL 
mmbs_eq(mmbs_t a, mmbs_t b, int n)
{
  assert(a != b && 0 <= n);
  while (n--) {
    if (*a != *b && [*a notEqual:*b])
      return NO;
    else {
      a++;
      b++;
    }
  }
  return YES;
}

static unsigned 
mmbs_hash(mmbs_t a, int n)
{
  assert(a && 0 <= n);
  return (n) ? (([a[n - 1] hash] < 8) + (n & 255)) : 0;
}

static mmbs_t 
mmbs_realloc(mmbs_t a, int n)
{
  return (mmbs_t) OC_Realloc(a, n * sizeof(id));
}

static int 
mmbs_insertlast(mmbs_t a, id obj, int n)
{
  a[n++] = obj;
  return n;
}

static int 
mmbs_insertfirst(mmbs_t a, id obj, int n)
{
  int j = n;

  a += n;
  while (j--) {
    mmbs_t t = a - 1;

    *a = *t;
    a = t;
  }
  *a = obj;
  return n + 1;
}

static int 
mmbs_insertat(mmbs_t a, id obj, int i, int n)
{
  if (i == n) {
    return mmbs_insertlast(a, obj, n);
  } else {
    return i + mmbs_insertfirst(a + i, obj, n - i);
  }
}

static id 
mmbs_removelast(mmbs_t a, int n)
{
  id obj;

  assert(n);
  obj = a[n - 1];
  a[n - 1] = nil;
  return obj;
}

static id 
mmbs_removefirst(mmbs_t a, int n)
{
  id obj;

  assert(n);
  obj = *a;
  --n;
  while (n--) {
    mmbs_t t = a + 1;

    *a = *t;
    a = t;
  }
  *a = nil;
  return obj;
}

static id 
mmbs_removeat(mmbs_t a, int i, int n)
{
  return mmbs_removefirst(a + i, n - i);
}

static id 
mmbs_replace(mmbs_t a, int i, id obj, int n)
{
  if (obj && 0 <= i && i < n) {
    id old = a[i];

    a[i] = obj;
    return old;
  } else {
    return nil;
  }
}

static void 
mmbs_swap(mmbs_t a, int i, int j, int n)
{
  assert(a && 0 <= i && i < n && 0 <= j && j < n);
  if (i != j) {
    id t = a[i];

    a[i] = a[j];
    a[j] = t;
  }
}

static id 
mmbs_at(mmbs_t a, int i, int n)
{
  assert(0 <= i && i < n);
  return a[i];
}

static id 
mmbs_last(mmbs_t a, int n)
{
  return (n) ? a[n - 1] : nil;
}

static int 
mmbs_find(mmbs_t a, id obj, int n)
{
  a += n;
  while (n--) {
    a--;
    if (*a == obj || [*a isEqual:obj])
      return n;
  }
  return -1;
}

#define STRIDE_FACTOR 3

static void 
mmbs_sort(mmbs_t self, int count)
{
  id a, b;
  BOOL found;
  int c, d, stride;

  stride = 1;
  while (stride <= count)
    stride = stride * STRIDE_FACTOR + 1;

  while (stride > (STRIDE_FACTOR - 1)) {
    stride = stride / STRIDE_FACTOR;
    for (c = stride; c < count; c++) {
      found = NO;
      d = c - stride;
      assert(0 <= d + stride < count);
      a = self[d + stride];
      while ((d >= 0) && !found) {
	if ([b = self[d] isLess:a]) {
	  self[d + stride] = b;
	  d -= stride;
	} else {
	  found = YES;
	}
      }
      self[d + stride] = a;
    }
  }
}

static BOOL 
mmbs_sorted(mmbs_t self, int count)
{
  id next = nil;

  while (count--) {
    id current = self[count];

    if (next && [current isLess:next])
      return NO;
    next = current;
  }
  return YES;
}

static void 
mmbs_reverse(mmbs_t self, int count)
{
  int i;

  for (i = 0; i < count / 2; i++) {
    id t = self[i];

    self[i] = self[count - i - 1];
    self[count - i - 1] = t;
  }
}

static void 
mmbs_fileout(id aFiler, mmbs_t a, int n)
{
  while (n--) {
    assert([*a check]);
    [aFiler fileOut:a type:'@'];
    a++;
  }
}

static void 
mmbs_filein(id aFiler, mmbs_t a, int n)
{
  while (n--) {
    [aFiler fileIn:a type:'@'];
    a++;
  }
}

static int 
cltn_check(cltn_t a)
{
  assert(a && 0 <= a->count && a->count <= a->capacity);
  assert(mmbs_check(a->members, a->count));
  return 1;
}

static void 
cltn_initcapacity(cltn_t c, int n)
{
  assert(n >= 0);
  c->count = 0;
  c->capacity = n;
  c->members = mmbs_alloc(n);
}

static void 
cltn_initcount(cltn_t c, int n)
{
  assert(n >= 0);
  c->count = n;
  c->capacity = n;
  c->members = mmbs_alloc(n);
}

static void 
cltn_copy(cltn_t c, cltn_t a)
{
  cltn_check(a);
  cltn_initcount(c, a->count);
  mmbs_copy(c->members, a->members, a->count);
}

static void 
cltn_deepcopy(cltn_t c, cltn_t a)
{
  cltn_check(a);
  cltn_initcount(c, a->count);
  mmbs_deepcopy(c->members, a->members, a->count);
}

static void 
cltn_clear(cltn_t c)
{
  cltn_check(c);
  mmbs_free(c->members, c->count);
}

static BOOL 
cltn_eq(cltn_t a, cltn_t b)
{
  assert(a != b);
  cltn_check(a);
  cltn_check(b);
  if (a->count != b->count) {
    return NO;
  } else {
    return mmbs_eq(a->members, b->members, a->count);
  }
}

static unsigned 
cltn_hash(cltn_t a)
{
  cltn_check(a);
  return mmbs_hash(a->members, a->count);
}

static int 
cltn_nummembers(cltn_t a)
{
  return a->count;
}

static void 
cltn_expand(cltn_t c)
{
  assert(c->count == c->capacity);
  c->capacity += 1 + c->count;
  c->members = mmbs_realloc(c->members, c->capacity);
  assert(c->count < c->capacity);
}

static void 
cltn_insert(cltn_t c, id obj)
{
  assert(obj);
  cltn_check(c);
  if (c->count == c->capacity)
    cltn_expand(c);
  c->count = mmbs_insertlast(c->members, obj, c->count);
}

static void 
cltn_insertat(cltn_t c, id obj, int i)
{
  assert(obj && 0 <= i && i < c->count);
  cltn_check(c);
  if (c->count == c->capacity)
    cltn_expand(c);
  c->count = mmbs_insertat(c->members, obj, i, c->count);
}

static id 
cltn_remove(cltn_t c)
{
  if (c->count) {
    id obj = mmbs_removelast(c->members, c->count);

    c->count--;
    return obj;
  } else {
    return nil;
  }
}

static id 
cltn_removeat(cltn_t c, int i)
{
  id obj;

  assert(0 <= i && i < c->count);
  obj = mmbs_removeat(c->members, i, c->count);
  c->count--;
  return obj;
}

static id 
cltn_replace(cltn_t c, int i, id obj)
{
  return mmbs_replace(c->members, i, obj, c->count);
}

static void 
cltn_swap(cltn_t c, int i, int j)
{
  mmbs_swap(c->members, i, j, c->count);
}

static id 
cltn_at(cltn_t c, int i)
{
  cltn_check(c);
  return mmbs_at(c->members, i, c->count);
}

static id 
cltn_last(cltn_t c)
{
  cltn_check(c);
  return mmbs_last(c->members, c->count);
}

static int 
cltn_find(cltn_t c, id obj)
{
  cltn_check(c);
  return mmbs_find(c->members, obj, c->count);
}

static void 
cltn_sort(cltn_t self)
{
  mmbs_sort(self->members, self->count);
}

static void 
cltn_reverse(cltn_t self)
{
  mmbs_reverse(self->members, self->count);
}

static BOOL 
cltn_sorted(cltn_t self)
{
  return mmbs_sorted(self->members, self->count);
}

static void 
cltn_fileout(id aFiler, cltn_t c)
{
  int n = c->count;

  [aFiler fileOut:&n type:'i'];
  mmbs_fileout(aFiler, c->members, n);
}

static void 
cltn_filein(id aFiler, cltn_t c)
{
  int n;

  [aFiler fileIn:&n type:'i'];
  cltn_initcount(c, n);
  mmbs_filein(aFiler, c->members, n);
}

@implementation CACollection
- check
{
  int n = [self size];

  while (n--)
    [[self at:n] check];
  return [super check];
}


- _setUpCapacity:(int)aCapacity
{
  cltn_initcapacity(&value, aCapacity);
  return self;
}

+ new
{
  return [[super new] _setUpCapacity:16];
}

- new:(unsigned)aCapacity
{
  return [self notImplemented:_cmd];
}

+ new:(unsigned)aCapacity
{
  return [[super new] _setUpCapacity:aCapacity];
}

- capacity:(int)aCapacity
{
  return [isa new:aCapacity];
}

- empty
{
  return [isa new];
}
- copy
{
  id copy = [super copy];

  cltn_copy([copy cltn_value], &value);
  return copy;
}

- deepCopy
{
  id copy = [super copy];

  cltn_deepcopy([copy cltn_value], &value);
  return copy;
}

- clear
{
  cltn_clear(&value);
  return [super clear];
}


- (cltn_t) cltn_value
{
  return &value;
}

- (BOOL) isEqual:aCollection
{
  return (self == aCollection) ? YES : cltn_eq(&value, [aCollection cltn_value]);
}

- (unsigned) hash
{
  return cltn_hash(&value);
}

- (BOOL) isEmpty
{
  return [self size] == 0;
}

- (BOOL) notEmpty
{
  return [self size] != 0;
}

- (unsigned) size
{
  return cltn_nummembers(&value);
}

- add:anObject
{
  if (anObject) {
    [self checkRefCountOne];
    cltn_insert(&value, anObject);
    return [self invalidate];
  } else {
    return nil;
  }
}
- addIfAbsent:anObject
{
  if (anObject) {
    int i = [self offsetOf:anObject];

    if (i == -1) {
      return [self add:anObject];
    } else {
      [anObject free];
      return self;
    }
  } else {
    return nil;
  }
}
- at:(unsigned)i insert:anObject
{
  if (anObject) {
    int n = [self size];

    [self checkRefCountOne];
    if (i > n)
      [self error:"-at:insert: index out of bounds"];
    if (i == n) {
      cltn_insert(&value, anObject);
    } else {
      cltn_insertat(&value, anObject, i);
    }
    return [self invalidate];
  } else {
    return nil;
  }
}

- removeLast
{
  [self checkRefCountOne];
  return cltn_remove(&value);
}
- removeAt:(int)i
{
  [self checkRefCountOne];
  return cltn_removeat(&value, i);
}
- remove:anObject
{
  int i = [self offsetOf:anObject];

  return (i == -1) ? nil : [self removeAt:i];
}


- at:(unsigned)i put:anObject
{
  id member;

  [self checkRefCountOne];

  /* CAMatrix makes abuse of this method...
   * the return value can be a pointer to a void object !
   * these reduction methods should be rewritten and not to do that...
   * so don't check self before replacing, and don't check return value
   */

  assert(anObject == nil || [anObject check]);
  member = cltn_replace(&value, i, anObject);
  assert([self check]);
  return member;
}

- swapElementsAt:(int)i:(int)j
{
  [self checkRefCountOne];
  assert([self check]);
  cltn_swap(&value, i, j);
  assert([self check]);
  return self;
}

- eachElement
{
  return [CASequence over:[CACollectionSequence content:[self cheapCopy]]];
}

- eachElementReversed
{
  return [CASequence over:[CACollectionSequenceReversed content:[self cheapCopy]]];
}

- at:(unsigned)i
{
  return cltn_at(&value, i);
}
- (float) floatValueAt:(int)i
{
  return [[self at:i] floatValue];
}
- (int) intValueAt:(int)i
{
  return [[self at:i] intValue];
}
- lastElement
{
  return cltn_last(&value);
}
- (int) offsetOf:anObject
{
  if (anObject) {
    return cltn_find(&value, anObject);
  } else {
    return -1;
  }
}

- (BOOL) isSorted
{
  return cltn_sorted(&value);
}

- (BOOL) notSorted
{
  return [self isSorted] == NO;
}

- sort
{
  [self checkRefCountOne];
  cltn_sort(&value);
  return self;
}

- reverse
{
  [self checkRefCountOne];
  cltn_reverse(&value);
  return self;
}


- merge:aCltn
{
  id new;
  int i, m;
  int j, n;

  if ([self notSorted] || [aCltn notSorted])
    [self error:"Not Sorted"];

  i = 0;
  j = 0;
  m = [self size];
  n = [aCltn size];
  new = [self capacity:m + n];

  while (i < m && j < n) {
    id a = [self at:i];
    id b = [aCltn at:j];

    if ([a isLess:b]) {
      [new add:[b cheapCopy]];
      j++;
    } else {
      [new add:[a cheapCopy]];
      i++;
    }
  }

  while (i < m) {
    [new add:[[self at:i] cheapCopy]];
    i++;
  }
  while (j < n) {
    [new add:[[aCltn at:j] cheapCopy]];
    j++;
  }

  return new;
}

- union:aCltn
{
  int i, n;
  id new = [self empty];

  for (i = 0, n = [self size]; i < n; i++) {
    [new addIfAbsent:[[self at:i] cheapCopy]];
  }
  for (i = 0, n = [aCltn size]; i < n; i++) {
    [new addIfAbsent:[[aCltn at:i] cheapCopy]];
  }
  return new;
}


- printOn:(IOD)aFile
{
  int i, n;

  if ((n = [self size])) {
    fprintf(aFile, "{");
    [[self at:0] printOn:aFile];
    for (i = 1; i < n; i++) {
      fprintf(aFile, ",");
      [[self at:i] printOn:aFile];
    }
    fprintf(aFile, "}");
  } else {
    fprintf(aFile, "{}");
  }

  return self;
}


- fileOutOn:aFiler
{
  [super fileOutOn:aFiler];
  cltn_fileout(aFiler, &value);
  return self;
}

- fileInFrom:aFiler
{
  [super fileInFrom:aFiler];
  cltn_filein(aFiler, &value);
  return self;
}

@end

