Array.c

Go to the documentation of this file.

/*
 * Objectively: Ultra-lightweight object oriented framework for GNU C.
 * Copyright (C) 2014 Jay Dolan <jay@jaydolan.com>
 *
 * This software is provided 'as-is', without any express or implied
 * warranty. In no event will the authors be held liable for any damages
 * arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 *
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 *
 * 3. This notice may not be removed or altered from any source distribution.
 */
 
#include "Config.h"
 
#include <assert.h>
#include <stdarg.h>
#include <stdlib.h>
 
#include "Array.h"
#include "Hash.h"
#include "String.h"
 
#if defined(__APPLE__)
 
static int _quicksort(void *data, const void *a, const void *b) {
  return ((Comparator) data)(*((const ident *) a), *((const ident *) b));
}
 
void quicksort(ident base, size_t count, size_t size, Comparator comparator, ident data) {
  qsort_r(base, count, size, comparator, _quicksort);
}
 
#elif defined(_WIN32)
 
static int _quicksort(void *data, const void *a, const void *b) {
  return ((Comparator) data)(*((const ident *) a), *((const ident *) b));
}
 
void quicksort(ident base, size_t count, size_t size, Comparator comparator, ident data) {
  qsort_s(base, count, size, _quicksort, comparator);
}
 
#else
 
static int _quicksort(const void *a, const void *b, void *data) {
  return ((Comparator) data)(*((const ident *) a), *((const ident *) b));
}
 
void quicksort(ident base, size_t count, size_t size, Comparator comparator, ident data) {
  qsort_r(base, count, size, _quicksort, comparator);
}
 
#endif
 
#define _Class _Array
 
#define ARRAY_CHUNK_SIZE 64
 
#pragma mark - Object
 
static Object *copy(const Object *self) {
 
  const Array *this = (Array *) self;
 
  Array *copy = $(alloc(Array), initWithCapacity, this->count);
  assert(copy);
 
  $(copy, addObjectsFromArray, this);
 
  return (Object *) copy;
}
 
static void dealloc(Object *self) {
 
  Array *this = (Array *) self;
 
  for (size_t i = 0; i < this->count; i++) {
    release(this->elements[i]);
  }
 
  free(this->elements);
 
  super(Object, self, dealloc);
}
 
static String *description(const Object *self) {
 
  String *components = $((Array *) self, componentsJoinedByCharacters, ", ");
 
  String *desc = $(alloc(String), initWithFormat, "[%s]", components->chars ?: "");
 
  release(components);
 
  return desc;
}
 
static int hash(const Object *self) {
 
  Array *this = (Array *) self;
 
  int hash = HashForInteger(HASH_SEED, this->count);
 
  for (size_t i = 0; i < this->count; i++) {
    hash = HashForObject(hash, this->elements[i]);
  }
 
  return hash;
}
 
static bool isEqual(const Object *self, const Object *other) {
 
  if (super(Object, self, isEqual, other)) {
    return true;
  }
 
  if (other && $(other, isKindOfClass, _Array())) {
 
    const Array *this = (Array *) self;
    const Array *that = (Array *) other;
 
    if (this->count == that->count) {
 
      for (size_t i = 0; i < this->count; i++) {
 
        const Object *thisObject = this->elements[i];
        const Object *thatObject = that->elements[i];
 
        if ($(thisObject, isEqual, thatObject) == false) {
          return false;
        }
      }
 
      return true;
    }
  }
 
  return false;
}
 
#pragma mark - Array
 
static void addObject(Array *self, const ident obj) {
 
  if (self->count == self->capacity) {
 
    self->capacity += ARRAY_CHUNK_SIZE;
 
    if (self->elements) {
      self->elements = realloc(self->elements, self->capacity * sizeof(ident));
    } else {
      self->elements = calloc(self->capacity, sizeof(ident));
    }
 
    assert(self->elements);
  }
 
  self->elements[self->count++] = retain(obj);
}
 
static void addObjects(Array *self, const ident obj, ...) {
 
  va_list args;
  va_start(args, obj);
 
  ident object = obj;
  while (object) {
    $(self, addObject, object);
    object = va_arg(args, ident);
  }
 
  va_end(args);
}
 
static void addObjectsFromArray(Array *self, const Array *array) {
 
  if (array) {
    for (size_t i = 0; i < array->count; i++) {
      $(self, addObject, array->elements[i]);
    }
  }
}
 
static Array *array(void) {
 
  return $(alloc(Array), init);
}
 
static Array *arrayWithArray(const Array *array) {
 
  return $(alloc(Array), initWithArray, array);
}
 
static Array *arrayWithCapacity(size_t capacity) {
 
  return $(alloc(Array), initWithCapacity, capacity);
}
 
static Array *arrayWithObjects(ident obj, ...) {
 
  Array *array = (Array *) super(Object, alloc(Array), init);
  if (array) {
    va_list args;
    va_start(args, obj);
 
    while (obj) {
      array->elements = realloc(array->elements, ++array->count * sizeof(ident));
      assert(array->elements);
 
      array->elements[array->count - 1] = retain(obj);
      obj = va_arg(args, ident);
    }
 
    va_end(args);
  }
 
  return array;
}
 
static Array *arrayWithVaList(va_list args) {
 
  return $(alloc(Array), initWithVaList, args);
}
 
static String *componentsJoinedByCharacters(const Array *self, const char *chars) {
 
  String *string = $(alloc(String), init);
 
  for (size_t i = 0; i < self->count; i++) {
 
    String *desc = $((Object *) self->elements[i], description);
    $(string, appendString, desc);
 
    release(desc);
 
    if (i < self->count - 1) {
      $(string, appendCharacters, chars);
    }
  }
 
  return (String *) string;
}
 
static String *componentsJoinedByString(const Array *self, const String *string) {
  return $(self, componentsJoinedByCharacters, string->chars);
}
 
static bool containsObject(const Array *self, const ident obj) {
  return $(self, indexOfObject, obj) != -1;
}
 
static void enumerate(const Array *self, ArrayEnumerator enumerator, ident data) {
 
  assert(enumerator);
 
  for (size_t i = 0; i < self->count; i++) {
    enumerator(self, self->elements[i], data);
  }
}
 
static void filter(Array *self, Predicate predicate, ident data) {
 
  assert(predicate);
 
  for (size_t i = 0; i < self->count; i++) {
    if (predicate(self->elements[i], data) == false) {
      $(self, removeObjectAtIndex, i--);
    }
  }
}
 
static Array *filteredArray(const Array *self, Predicate predicate, ident data) {
 
  assert(predicate);
 
  Array *copy = (Array *) $((Object *) self, copy);
 
  $(copy, filter, predicate, data);
 
  return copy;
}
 
static ident find(const Array *self, Predicate predicate, ident data) {
 
  assert(predicate);
 
  for (size_t i = 0; i < self->count; i++) {
    if (predicate(self->elements[i], data)) {
      return self->elements[i];
    }
  }
 
  return NULL;
}
 
static ident firstObject(const Array *self) {
 
  return self->count ? $(self, objectAtIndex, 0) : NULL;
}
 
static ssize_t indexOfObject(const Array *self, const ident obj) {
 
  assert(obj);
 
  for (size_t i = 0; i < self->count; i++) {
    if ($((Object * ) self->elements[i], isEqual, obj)) {
      return i;
    }
  }
 
  return -1;
}
 
static Array *init(Array *self) {
 
  return $(self, initWithCapacity, 0);
}
 
static Array *initWithArray(Array *self, const Array *array) {
 
  self = (Array *) super(Object, self, init);
  if (self) {
 
    self->count = array->count;
    if (self->count) {
 
      self->elements = calloc(self->count, sizeof(ident));
      assert(self->elements);
 
      for (size_t i = 0; i < self->count; i++) {
        self->elements[i] = retain(array->elements[i]);
      }
    }
  }
 
  return self;
}
 
static Array *initWithCapacity(Array *self, size_t capacity) {
 
  self = (Array *) super(Object, self, init);
  if (self) {
 
    self->capacity = capacity;
    if (self->capacity) {
 
      self->elements = calloc(self->capacity, sizeof(ident));
      assert(self->elements);
    }
  }
 
  return self;
}
 
static Array *initWithObjects(Array *self, ...) {
 
  va_list args;
  va_start(args, self);
 
  self = $(self, initWithVaList, args);
 
  va_end(args);
  return self;
}
 
static Array *initWithVaList(Array *self, va_list args) {
 
  self = (Array *) super(Object, self, init);
  if (self) {
 
    ident element = va_arg(args, ident);
    while (element) {
      self->elements = realloc(self->elements, ++self->count * sizeof(ident));
      assert(self->elements);
 
      self->elements[self->count - 1] = retain(element);
      element = va_arg(args, ident);
    }
  }
 
  return self;
}
 
static void insertObjectAtIndex(Array *self, ident obj, size_t index) {
 
  assert(index <= self->count);
 
  $(self, addObject, obj);
 
  for (size_t i = self->count - 1; i > index; i--) {
    self->elements[i] = self->elements[i - 1];
  }
 
  self->elements[index] = obj;
}
 
static ident lastObject(const Array *self) {
 
  return self->count ? $(self, objectAtIndex, self->count - 1) : NULL;
}
 
static void map(Array *self, Functor functor, ident data) {
 
  assert(functor);
 
  for (size_t i = 0; i < self->count; i++) {
    ident obj = functor(self->elements[i], data);
 
    retain(obj);
 
    release(self->elements[i]);
 
    self->elements[i] = obj;
  }
}
 
static Array *mappedArray(const Array *self, Functor functor, ident data) {
 
  assert(functor);
 
  Array *array = $(alloc(Array), initWithCapacity, self->count);
  assert(array);
  
  for (size_t i = 0; i < self->count; i++) {
 
    ident obj = functor(self->elements[i], data);
 
    $(array, addObject, obj);
 
    release(obj);
  }
 
  return array;
}
 
static ident objectAtIndex(const Array *self, size_t index) {
 
  assert(index < self->count);
 
  return self->elements[index];
}
 
static ident reduce(const Array *self, Reducer reducer, ident accumulator, ident data) {
 
  assert(reducer);
 
  for (size_t i = 0; i < self->count; i++) {
    accumulator = reducer(self->elements[i], accumulator, data);
  }
 
  return accumulator;
}
 
static void removeAllObjects(Array *self) {
 
  while (self->count) {
    $(self, removeLastObject);
  }
}
 
static void removeAllObjectsWithEnumerator(Array *self, ArrayEnumerator enumerator, ident data) {
 
  assert(enumerator);
 
  while (self->count) {
 
    enumerator(self, $(self, lastObject), data);
 
    $(self, removeLastObject);
  }
}
 
static void removeLastObject(Array *self) {
 
  if (self->count) {
    $(self, removeObjectAtIndex, self->count - 1);
  }
}
 
static void removeObject(Array *self, const ident obj) {
 
  const ssize_t index = $(self, indexOfObject, obj);
  if (index > -1) {
    $(self, removeObjectAtIndex, index);
  }
}
 
static void removeObjectAtIndex(Array *self, size_t index) {
 
  assert(index < self->count);
 
  release(self->elements[index]);
 
  for (size_t i = index; i < self->count - 1; i++) {
    self->elements[i] = self->elements[i + 1];
  }
 
  self->count--;
}
 
static void setObjectAtIndex(Array *self, const ident obj, size_t index) {
 
  assert(index < self->count);
 
  retain(obj);
 
  release(self->elements[index]);
 
  self->elements[index] = obj;
}
 
static void sort(Array *self, Comparator comparator) {
  quicksort(self->elements, self->count, sizeof(ident), comparator, NULL);
}
 
static Array *sortedArray(const Array *self, Comparator comparator) {
 
  assert(comparator);
 
  Array *array = (Array *) $((Object *) self, copy);
 
  $(array, sort, comparator);
 
  return array;
}
 
#pragma mark - Class lifecycle
 
static void initialize(Class *clazz) {
 
  ((ObjectInterface *) clazz->interface)->copy = copy;
  ((ObjectInterface *) clazz->interface)->dealloc = dealloc;
  ((ObjectInterface *) clazz->interface)->description = description;
  ((ObjectInterface *) clazz->interface)->hash = hash;
  ((ObjectInterface *) clazz->interface)->isEqual = isEqual;
 
  ((ArrayInterface *) clazz->interface)->addObject = addObject;
  ((ArrayInterface *) clazz->interface)->addObjects = addObjects;
  ((ArrayInterface *) clazz->interface)->addObjectsFromArray = addObjectsFromArray;
  ((ArrayInterface *) clazz->interface)->array = array;
  ((ArrayInterface *) clazz->interface)->arrayWithArray = arrayWithArray;
  ((ArrayInterface *) clazz->interface)->arrayWithCapacity = arrayWithCapacity;
  ((ArrayInterface *) clazz->interface)->arrayWithObjects = arrayWithObjects;
  ((ArrayInterface *) clazz->interface)->arrayWithVaList = arrayWithVaList;
  ((ArrayInterface *) clazz->interface)->componentsJoinedByCharacters = componentsJoinedByCharacters;
  ((ArrayInterface *) clazz->interface)->componentsJoinedByString = componentsJoinedByString;
  ((ArrayInterface *) clazz->interface)->containsObject = containsObject;
  ((ArrayInterface *) clazz->interface)->enumerate = enumerate;
  ((ArrayInterface *) clazz->interface)->filter = filter;
  ((ArrayInterface *) clazz->interface)->filteredArray = filteredArray;
  ((ArrayInterface *) clazz->interface)->find = find;
  ((ArrayInterface *) clazz->interface)->firstObject = firstObject;
  ((ArrayInterface *) clazz->interface)->indexOfObject = indexOfObject;
  ((ArrayInterface *) clazz->interface)->init = init;
  ((ArrayInterface *) clazz->interface)->initWithArray = initWithArray;
  ((ArrayInterface *) clazz->interface)->initWithCapacity = initWithCapacity;
  ((ArrayInterface *) clazz->interface)->initWithObjects = initWithObjects;
  ((ArrayInterface *) clazz->interface)->initWithVaList = initWithVaList;
  ((ArrayInterface *) clazz->interface)->insertObjectAtIndex = insertObjectAtIndex;
  ((ArrayInterface *) clazz->interface)->lastObject = lastObject;
  ((ArrayInterface *) clazz->interface)->map = map;
  ((ArrayInterface *) clazz->interface)->mappedArray = mappedArray;
  ((ArrayInterface *) clazz->interface)->objectAtIndex = objectAtIndex;
  ((ArrayInterface *) clazz->interface)->reduce = reduce;
  ((ArrayInterface *) clazz->interface)->removeAllObjects = removeAllObjects;
  ((ArrayInterface *) clazz->interface)->removeAllObjectsWithEnumerator = removeAllObjectsWithEnumerator;
  ((ArrayInterface *) clazz->interface)->removeLastObject = removeLastObject;
  ((ArrayInterface *) clazz->interface)->removeObject = removeObject;
  ((ArrayInterface *) clazz->interface)->removeObjectAtIndex = removeObjectAtIndex;
  ((ArrayInterface *) clazz->interface)->setObjectAtIndex = setObjectAtIndex;
  ((ArrayInterface *) clazz->interface)->sort = sort;
  ((ArrayInterface *) clazz->interface)->sortedArray = sortedArray;
}
 
Class *_Array(void) {
  static Class *clazz;
  static Once once;
 
  do_once(&once, {
    clazz = _initialize(&(const ClassDef) {
      .name = "Array",
      .superclass = _Object(),
      .instanceSize = sizeof(Array),
      .interfaceOffset = offsetof(Array, interface),
      .interfaceSize = sizeof(ArrayInterface),
      .initialize = initialize,
    });
  });
 
  return clazz;
}
 
#undef _Class