#include <assert.h>
#include <stdarg.h>
#include <stdlib.h>
#include "Hash.h"
#include "Set.h"
#include "String.h"

Macros
#define	_Class _Set

#define	SET_DEFAULT_CAPACITY 64

#define	SET_GROW_FACTOR 2.0

#define	SET_MAX_LOAD 0.75f

Functions
Class *	_Set (void)

static void	addObject (Set *self, const ident obj)

static void	addObject_resize (Set *set)
	A helper for resizing Sets as Objects are added to them.

static void	addObjectsFromArray (Set self, const Array array)

static void	addObjectsFromArray_enumerator (const Array *array, ident obj, ident data)
	ArrayEnumerator for addObjectsFromArray.

static void	addObjectsFromSet (Set self, const Set set)

static void	addObjectsFromSet_enumerator (const Set *set, ident obj, ident data)
	SetEnumerator for addObjectsFromSet.

static Array *	allObjects (const Set *self)

static void	allObjects_enumerator (const Set *set, ident obj, ident data)
	SetEnumerator for allObjects.

static bool	containsObject (const Set *self, const ident obj)

static bool	containsObjectMatching (const Set *self, Predicate predicate, ident data)

static Object *	copy (const Object *self)

static void	dealloc (Object *self)

static String *	description (const Object *self)

static void	enumerateObjects (const Set *self, SetEnumerator enumerator, ident data)

static void	filter (Set *self, Predicate predicate, ident data)

static Set *	filteredSet (const Set *self, Predicate predicate, ident data)

static int	hash (const Object *self)

static Set *	init (Set *self)

static void	initialize (Class *clazz)

static Set *	initWithArray (Set self, const Array array)

static void	initWithArray_enumerator (const Array *array, ident obj, ident data)
	ArrayEnumerator for initWithArray.

static Set *	initWithCapacity (Set *self, size_t capacity)

static Set *	initWithObjects (Set *self,...)

static Set *	initWithSet (Set self, const Set set)

static void	initWithSet_enumerator (const Set *set, ident obj, ident data)
	SetEnumerator for initWithSet.

static bool	isEqual (const Object self, const Object other)

static Set *	mappedSet (const Set *self, Functor functor, ident data)

static ident	reduce (const Set *self, Reducer reducer, ident accumulator, ident data)

static void	removeAllObjects (Set *self)

static void	removeObject (Set *self, const ident obj)

static Set *	set (void)

static Set *	setWithArray (const Array *array)

static Set *	setWithCapacity (size_t capacity)

static Set *	setWithObjects (ident obj,...)

static Set *	setWithSet (const Set *set)

Macro Definition Documentation

◆ _Class

#define _Class _Set

Definition at line 32 of file Set.c.

◆ SET_DEFAULT_CAPACITY

#define SET_DEFAULT_CAPACITY 64

Definition at line 34 of file Set.c.

◆ SET_GROW_FACTOR

#define SET_GROW_FACTOR 2.0

Definition at line 35 of file Set.c.

◆ SET_MAX_LOAD

#define SET_MAX_LOAD 0.75f

Definition at line 36 of file Set.c.

Function Documentation

◆ _Set()

Class * _Set ( void )

Definition at line 669 of file Set.c.

                  {
  static Class *clazz;
  static Once once;
 
  do_once(&once, {
    clazz = _initialize(&(const ClassDef) {
      .name = "Set",
      .superclass = _Object(),
      .instanceSize = sizeof(Set),
      .interfaceOffset = offsetof(Set, interface),
      .interfaceSize = sizeof(SetInterface),
      .initialize = initialize,
    });
  });
 
  return clazz;
}

◆ addObject()

static void addObject	(	Set *	self,
		const ident	obj
	)

static

Definition at line 175 of file Set.c.

                                                  {
 
  addObject_resize(self);
 
  const size_t bin = HashForObject(HASH_SEED, obj) % self->capacity;
 
  Array *array = self->elements[bin];
  if (array == NULL) {
    array = self->elements[bin] = $(alloc(Array), init);
  }
 
  if ($((Array *) array, containsObject, obj) == false) {
    $(array, addObject, obj);
    self->count++;
  }
}

◆ addObject_resize()

static void addObject_resize ( Set * set )

static

A helper for resizing Sets as Objects are added to them.

Remarks: Static method invocations are used for all operations.

Definition at line 139 of file Set.c.

                                       {
 
  if (set->capacity) {
 
    const float load = set->count / (float) set->capacity;
    if (load >= SET_MAX_LOAD) {
 
      size_t capacity = set->capacity;
      ident *elements = set->elements;
 
      set->capacity = set->capacity * SET_GROW_FACTOR;
      set->count = 0;
 
      set->elements = calloc(set->capacity, sizeof(ident));
      assert(set->elements);
 
      for (size_t i = 0; i < capacity; i++) {
 
        Array *array = elements[i];
        if (array) {
          $(set, addObjectsFromArray, array);
          release(array);
        }
      }
 
      free(elements);
    }
  } else {
    $(set, initWithCapacity, SET_DEFAULT_CAPACITY);
  }
}

◆ addObjectsFromArray()

static void addObjectsFromArray	(	Set *	self,
		const Array *	array
	)

static

Definition at line 203 of file Set.c.

                                                               {
 
  if (array) {
    $(array, enumerate, addObjectsFromArray_enumerator, self);
  }
}

◆ addObjectsFromArray_enumerator()

static void addObjectsFromArray_enumerator	(	const Array *	array,
		ident	obj,
		ident	data
	)

static

ArrayEnumerator for addObjectsFromArray.

Definition at line 195 of file Set.c.

                                                                                      {
  $((Set *) data, addObject, obj);
}

◆ addObjectsFromSet()

static void addObjectsFromSet	(	Set *	self,
		const Set *	set
	)

static

Definition at line 221 of file Set.c.

                                                         {
 
  if (set) {
    $(set, enumerateObjects, addObjectsFromSet_enumerator, self);
  }
}

◆ addObjectsFromSet_enumerator()

static void addObjectsFromSet_enumerator	(	const Set *	set,
		ident	obj,
		ident	data
	)

static

SetEnumerator for addObjectsFromSet.

Definition at line 213 of file Set.c.

                                                                                {
  $((Set *) data, addObject, obj);
}

◆ allObjects()

static Array * allObjects ( const Set * self )

static

Definition at line 239 of file Set.c.

                                          {
 
  Array *objects = $(alloc(Array), initWithCapacity, self->count);
 
  $(self, enumerateObjects, allObjects_enumerator, objects);
 
  return objects;
}

◆ allObjects_enumerator()

static void allObjects_enumerator	(	const Set *	set,
		ident	obj,
		ident	data
	)

static

SetEnumerator for allObjects.

Definition at line 231 of file Set.c.

                                                                         {
  $((Array *) data, addObject, obj);
}

◆ containsObject()

static bool containsObject	(	const Set *	self,
		const ident	obj
	)

static

Definition at line 252 of file Set.c.

                                                             {
 
  if (self->capacity) {
    const size_t bin = HashForObject(HASH_SEED, obj) % self->capacity;
 
    const Array *array = self->elements[bin];
    if (array) {
      return $(array, containsObject, obj);
    }
  }
 
  return false;
}

◆ containsObjectMatching()

static bool containsObjectMatching	(	const Set *	self,
		Predicate	predicate,
		ident	data
	)

static

Definition at line 270 of file Set.c.

                                                                                     {
 
  assert(predicate);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j++) {
        if (predicate($(array, objectAtIndex, j), data)) {
          return true;
        }
      }
    }
  }
 
  return false;
}

◆ copy()

static Object * copy ( const Object * self )

static

See also: Object::copy(const Object *)

Definition at line 43 of file Set.c.

                                        {
 
  const Set *this = (Set *) self;
 
  Set *that = $(alloc(Set), initWithCapacity, this->capacity);
 
  $(that, addObjectsFromSet, this);
 
  return (Object *) that;
}

◆ dealloc()

static void dealloc ( Object * self )

static

See also: Object::dealloc(Object *)

Definition at line 57 of file Set.c.

                                  {
 
  Set *this = (Set *) self;
 
  for (size_t i = 0; i < this->capacity; i++) {
    release(this->elements[i]);
  }
 
  free(this->elements);
 
  super(Object, self, dealloc);
}

◆ description()

static String * description ( const Object * self )

static

See also: Object::description(const Object *)

Definition at line 73 of file Set.c.

                                               {
 
  const Array *array = $((Set *) self, allObjects);
 
  return $((Object *) array, description);
}

◆ enumerateObjects()

static void enumerateObjects	(	const Set *	self,
		SetEnumerator	enumerator,
		ident	data
	)

static

Definition at line 294 of file Set.c.

                                                                                    {
 
  assert(enumerator);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j++) {
        enumerator(self, $(array, objectAtIndex, j), data);
      }
    }
  }
}

◆ filter()

static void filter	(	Set *	self,
		Predicate	predicate,
		ident	data
	)

static

Definition at line 314 of file Set.c.

                                                               {
 
  assert(predicate);
 
  self->count = 0;
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      $(array, filter, predicate, data);
 
      if (array->count == 0) {
        release(array);
        self->elements[i] = NULL;
      } else {
        self->count += array->count;
      }
    }
  }
}

◆ filteredSet()

static Set * filteredSet	(	const Set *	self,
		Predicate	predicate,
		ident	data
	)

static

Definition at line 341 of file Set.c.

                                                                          {
 
  assert(predicate);
 
  Set *set = $(alloc(Set), init);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j++) {
        ident obj = $(array, objectAtIndex, j);
 
        if (predicate(obj, data)) {
          $(set, addObject, obj);
        }
      }
    }
  }
 
  return set;
}

◆ hash()

static int hash ( const Object * self )

static

See also: Object::hash(const Object *)

Definition at line 83 of file Set.c.

                                    {
 
  const Set *this = (Set *) self;
 
  int hash = HashForInteger(HASH_SEED, this->count);
 
  for (size_t i = 0; i < this->capacity; i++) {
    if (this->elements[i]) {
      hash = HashForObject(hash, this->elements[i]);
    }
  }
 
  return hash;
}

◆ init()

static Set * init ( Set * self )

static

Definition at line 369 of file Set.c.

                            {
 
  return $(self, initWithCapacity, SET_DEFAULT_CAPACITY);
}

◆ initialize()

static void initialize ( Class * clazz )

static

See also: Class::initialize(Class *)

Definition at line 632 of file Set.c.

                                     {
 
  ((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;
 
  ((SetInterface *) clazz->interface)->addObject = addObject;
  ((SetInterface *) clazz->interface)->addObjectsFromArray = addObjectsFromArray;
  ((SetInterface *) clazz->interface)->addObjectsFromSet = addObjectsFromSet;
  ((SetInterface *) clazz->interface)->allObjects = allObjects;
  ((SetInterface *) clazz->interface)->containsObject = containsObject;
  ((SetInterface *) clazz->interface)->containsObjectMatching = containsObjectMatching;
  ((SetInterface *) clazz->interface)->enumerateObjects = enumerateObjects;
  ((SetInterface *) clazz->interface)->filter = filter;
  ((SetInterface *) clazz->interface)->filteredSet = filteredSet;
  ((SetInterface *) clazz->interface)->init = init;
  ((SetInterface *) clazz->interface)->initWithArray = initWithArray;
  ((SetInterface *) clazz->interface)->initWithCapacity = initWithCapacity;
  ((SetInterface *) clazz->interface)->initWithObjects = initWithObjects;
  ((SetInterface *) clazz->interface)->initWithSet = initWithSet;
  ((SetInterface *) clazz->interface)->mappedSet = mappedSet;
  ((SetInterface *) clazz->interface)->reduce = reduce;
  ((SetInterface *) clazz->interface)->removeAllObjects = removeAllObjects;
  ((SetInterface *) clazz->interface)->removeObject = removeObject;
  ((SetInterface *) clazz->interface)->set = set;
  ((SetInterface *) clazz->interface)->setWithArray = setWithArray;
  ((SetInterface *) clazz->interface)->setWithCapacity = setWithCapacity;
  ((SetInterface *) clazz->interface)->setWithObjects = setWithObjects;
  ((SetInterface *) clazz->interface)->setWithSet = setWithSet;
}

◆ initWithArray()

static Set * initWithArray	(	Set *	self,
		const Array *	array
	)

static

Definition at line 385 of file Set.c.

                                                         {
 
  self = (Set *) super(Object, self, init);
  if (self) {
    if (array) {
      $(array, enumerate, initWithArray_enumerator, self);
    }
  }
 
  return self;
}

◆ initWithArray_enumerator()

static void initWithArray_enumerator	(	const Array *	array,
		ident	obj,
		ident	data
	)

static

ArrayEnumerator for initWithArray.

Definition at line 377 of file Set.c.

                                                                                {
  $((Set *) data, addObject, obj);
}

◆ initWithCapacity()

static Set * initWithCapacity	(	Set *	self,
		size_t	capacity
	)

static

Definition at line 401 of file Set.c.

                                                         {
 
  self = (Set *) super(Object, self, init);
  if (self) {
 
    self->capacity = capacity;
    if (self->capacity) {
 
      self->elements = calloc(self->capacity, sizeof(ident));
      assert(self->elements);
    }
  }
 
  return self;
}

◆ initWithObjects()

static Set * initWithObjects	(	Set *	self,
			...
	)

static

Definition at line 421 of file Set.c.

                                            {
 
  self = (Set *) super(Object, self, init);
  if (self) {
 
    va_list args;
    va_start(args, self);
 
    while (true) {
 
      ident obj = va_arg(args, ident);
      if (obj) {
        $(self, addObject, obj);
      } else {
        break;
      }
    }
 
    va_end(args);
  }
 
  return self;
}

◆ initWithSet()

static Set * initWithSet	(	Set *	self,
		const Set *	set
	)

static

Definition at line 456 of file Set.c.

                                                   {
 
  self = (Set *) super(Object, self, init);
  if (self) {
    if (set) {
      $(set, enumerateObjects, initWithSet_enumerator, self);
    }
  }
 
  return self;
}

◆ initWithSet_enumerator()

static void initWithSet_enumerator	(	const Set *	set,
		ident	obj,
		ident	data
	)

static

SetEnumerator for initWithSet.

Definition at line 448 of file Set.c.

                                                                          {
  $((Set *) data, addObject, obj);
}

◆ isEqual()

static bool isEqual	(	const Object *	self,
		const Object *	other
	)

static

See also: Object::isEqual(const Object *, const Object *)

Definition at line 101 of file Set.c.

                                                             {
 
  if (super(Object, self, isEqual, other)) {
    return true;
  }
 
  if (other && (self->clazz == other->clazz)) {
 
    const Set *this = (Set *) self;
    const Set *that = (Set *) other;
 
    if (this->count == that->count) {
 
      Array *objects = $(this, allObjects);
 
      for (size_t i = 0; i < objects->count; i++) {
        const ident obj = $(objects, objectAtIndex, i);
 
        if ($(that, containsObject, obj) == false) {
          release(objects);
          return false;
        }
      }
 
      release(objects);
      return true;
    }
  }
 
  return false;
}

◆ mappedSet()

static Set * mappedSet	(	const Set *	self,
		Functor	functor,
		ident	data
	)

static

Definition at line 472 of file Set.c.

                                                                    {
 
  assert(functor);
 
  Set *set = $(alloc(Set), initWithCapacity, self->count);
  assert(set);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    const Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j++) {
 
        ident obj = functor(array->elements[j], data);
 
        $(set, addObject, obj);
 
        release(obj);
      }
    }
  }
 
  return set;
}

◆ reduce()

static ident reduce	(	const Set *	self,
		Reducer	reducer,
		ident	accumulator,
		ident	data
	)

static

Definition at line 502 of file Set.c.

                                                                                     {
 
  assert(reducer);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    const Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j++) {
        accumulator = reducer(array->elements[j], accumulator, data);
      }
    }
  }
 
  return accumulator;
}

◆ removeAllObjects()

static void removeAllObjects ( Set * self )

static

Definition at line 524 of file Set.c.

                                        {
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
      release(array);
      self->elements[i] = NULL;
    }
  }
 
  self->count = 0;
}

◆ removeObject()

static void removeObject	(	Set *	self,
		const ident	obj
	)

static

Definition at line 542 of file Set.c.

                                                     {
 
  if (self->capacity == 0) {
    return;
  }
 
  const size_t bin = HashForObject(HASH_SEED, obj) % self->capacity;
 
  Array *array = self->elements[bin];
  if (array) {
 
    const ssize_t index = $(array, indexOfObject, obj);
    if (index > -1) {
 
      $(array, removeObjectAtIndex, index);
 
      if (((Array *) array)->count == 0) {
        release(array);
        self->elements[bin] = NULL;
      }
 
      self->count--;
    }
  }
}

◆ set()

static Set * set ( void )

static

Definition at line 572 of file Set.c.

                      {
 
  return $(alloc(Set), init);
}

◆ setWithArray()

static Set * setWithArray ( const Array * array )

static

Definition at line 581 of file Set.c.

                                             {
 
  return $(alloc(Set), initWithArray, array);
}

◆ setWithCapacity()

static Set * setWithCapacity ( size_t capacity )

static

Definition at line 590 of file Set.c.

                                             {
 
  return $(alloc(Set), initWithCapacity, capacity);
}

◆ setWithObjects()

static Set * setWithObjects	(	ident	obj,
			...
	)

static

Definition at line 599 of file Set.c.

                                           {
 
  Set *set = (Set *) $((Object *) alloc(Set), init);
  if (set) {
 
    va_list args;
    va_start(args, obj);
 
    while (obj) {
      $(set, addObject, obj);
      obj = va_arg(args, ident);
    }
 
    va_end(args);
  }
 
  return set;
}

◆ setWithSet()

static Set * setWithSet ( const Set * set )

static

Definition at line 622 of file Set.c.

                                       {
 
  return $(alloc(Set), initWithSet, set);
}

Macros

Functions

Macro Definition Documentation

◆ _Class

◆ SET_DEFAULT_CAPACITY

◆ SET_GROW_FACTOR

◆ SET_MAX_LOAD

Function Documentation

◆ _Set()

◆ addObject()

◆ addObject_resize()

◆ addObjectsFromArray()

◆ addObjectsFromArray_enumerator()

◆ addObjectsFromSet()

◆ addObjectsFromSet_enumerator()

◆ allObjects()

◆ allObjects_enumerator()

◆ containsObject()

◆ containsObjectMatching()

◆ copy()

◆ dealloc()

◆ description()

◆ enumerateObjects()

◆ filter()

◆ filteredSet()

◆ hash()

◆ init()

◆ initialize()

◆ initWithArray()

◆ initWithArray_enumerator()

◆ initWithCapacity()

◆ initWithObjects()

◆ initWithSet()

◆ initWithSet_enumerator()

◆ isEqual()

◆ mappedSet()

◆ reduce()

◆ removeAllObjects()

◆ removeObject()

◆ set()

◆ setWithArray()

◆ setWithCapacity()

◆ setWithObjects()

◆ setWithSet()