The GDS ArraySet Data Structure

We define the ArraySet data structure as:

typedef struct
{
   /*The allocated size for the Element array elements*/
   int capacity;  
   /*How many elements are actually in the array*/
   int size;
   /*The vector containing the elements*/
   Element *elements;
}ArraySet;

The following operations will be implemented:

Operation	Description
Create	Creates a new ArraySet data structure
Resize	Modifies the capacity of the ArraySet in order to save memory
Destroy	Destroys an ArraySet in order to free memory
Belongs	Checking if an object already exists in the set
Add object	Add a new Element to the ArraySet. Before adding it should check that the element doesn't already exists in the set (sets do not allow duplicates).
Remove object	Removes an Element from the ArraySet
Remove all	Removes an object from the ArraySet
Copy	Creates a hard copy of the ArraySet
Equals	Check if two sets contain the same elements
Is subset	Checks if all elements in the first set also belong in the secondary set
Reunion	Creates a new ArraySet containing all unique objects from two sets
Intersection	Creates a new ArraySet containing the objects that belong to two sets
Difference	Creates a new ArraySet containing the objects that belong the the first set, but do not belong to the second set

The functions who are implementing these operations are:

/*
 * Description:
 *  Creates an ArraySet data structure
 * Parameters:
 *  set - a pointer to the set who is going to be created
 * Returns:
 *  A pointer to the initialized set OR
 *  NULL if there is not enough memory
 */
ArraySet* ArraySet_Create(int capacity);
/*
 * Description:
 *  Resizes an ArraySet data structure
 * Parameters:
 *  capacity - the new capacity of the set
 * Returns:
 *  A pointer to the set OR
 *  NULL if there is no memory left or the newCapacity is
 *  smaller than the size of the array.
 */
ArraySet* ArraySet_Resize(ArraySet* set, int newCapacity);
/*
 * Description:
 *  Destroys an ArraySet structure
 * Parameters:
 *  set - a pointer to the set who is going to be created
 * Returns:
 *  NULL
 */
ArraySet* ArraySet_Destroy(ArraySet* set);
/*
 * Description:
 *  Verifies if @object belongs in @set
 * Parameters:
 *  object - a pointer to a object
 *  set - a pointer to a set
 * Returns:
 *  True - if the object exists in the set
 *  False - if the object does not exist in the set
 */
bool ArraySet_Belongs(const Object* object, const ArraySet* set);
/*
 * Description:
 *  Adds an object to a set
 * Parameters:
 *  set - a pointer to the current set
 *  object - a pointer to an object
 * Returns:
 *  A pointer to the current set OR
 *  NULL if the object already exists in the set or
 *    if adding the object would cause a buffer overflow
 */
ArraySet* ArraySet_AddObject(ArraySet* set, const Object* object);
/*
 * Description:
 *  Removes an object from the set
 * Parameters:
 *  set - a pointer to the current set
 *  object - a pointer to an object
 * Returns:
 *  A pointer to the current set OR
 *  NULL if the object does not exist in the set or
 *    if there is no object in the set
 */
ArraySet* ArraySet_RemoveObject(ArraySet* set, const Object *object);
/*
 * Description:
 *  Removes all objects from the set
 * Parameters:
 *  set - a pointer to the current set
 * Returns:
 *  A pointer to the set
 */
ArraySet* ArraySet_RemoveAll(ArraySet* set);
/*
 * Description:
 *  Creates a hard copy of a set
 * Parameters:
 *  set - a pointer to a set
 * Returns:
 *  A pointer to a copy of the set
 */
ArraySet* ArraySet_Copy(const ArraySet* set);
/*
 * Description:
 *  Compares two sets to see if they are equal
 * Parameters:
 *  set1, set2 - pointers to the two sets
 * Returns:
 *  True - if both sets have the same objects
 *  False - if there are differences between the sets
 */
bool ArraySet_Equals(const ArraySet* set1, const ArraySet* set2);
/*
 * Description:
 *  Check is a a set is a subset of another set
 * Parameters:
 *  smallSet - the possible subset
 *  largeSet - the set who is verified
 * Returns:
 *  True - if @smallset is a subset of @largeset
 *  False - otherwise
 */
bool ArraySet_IsSubset(const ArraySet* smallSet, const ArraySet* largeSet);
/*
 * Description:
 *  Creates a new ArraySet containing the result of the reunion
 *  between 2 other sets.
 * Parameters:
 *  set1, set2 - the sets who are going to be reunited
 * Returns:
 *  A pointer to the ArraySet containing the result of the reunion OR
 *  NULL if there is no memory available to allocate for the new set
 */
ArraySet* ArraySet_Reunion(const ArraySet* set1, const ArraySet* set2);
/*
 * Description:
 *  Creates a new ArraySet containing the result of the intersection
 *  between 2 other sets.
 * Parameters:
 *  set1, set2 - the sets who are going to be intersected
 * Returns:
 *  A pointer to the ArraySet containing the result of the intersection OR
 *  NULL if there is no memory available to allocate for the new set
 */
ArraySet* ArraySet_Intersection(const ArraySet* set1, const ArraySet* set2);
/*
 * Description:
 *  Creates a new ArraySet containing the result of the difference
 *  between the first set and the last set.
 * Parameters:
 *  mainSet - the set which will evaluated according to the secondary set
 *  secondarySet - the set containing the objects which will be eliminated
 *        from the main set.
 * Returns:
 *  A pointer to the ArraySet containing the result of set1 \ set2
 *  (the difference between set1 and set2) OR
 *  NULL if there is no memory available to allocate for the new set
 */
ArraySet* ArraySet_Difference(const ArraySet* mainSet, const ArraySet* secondarySet);

If you want to see the implementation details, follow this link:

ArraySet.c

In the examples below we shall consider the sample object defined in the following article:

Defining an Object

Example 1

#include<stdio.h>
#include"Examples.h"
#include"ArraySet.h"
#include"SampleObject.h"

static void PrintArraySet(ArraySet* set)
{
   int i;
   printf("Size: %d Capacity: %d Objects: ", set->size, set->capacity);
   for (i = 0; i < set->size; i++)
   {
      printf("%d ", *(int*)(set->objects[i].data));
   }
   putchar('\n');
}

void ArraySet_Example1(void)
{
   /*We declare 2 ArraySet data structures*/
   ArraySet* s1 = NULL;
   ArraySet* s2 = NULL;
   /*The interface for the objects*/
   Interface* I_Integer = NULL;
   /*Creating the interface*/
   I_Integer = Interface_Create(&Integer_Copy,
                                &Integer_Destroy,
                                &Integer_Compare);
   /*Creating the first set*/
   s1 = ArraySet_Create(10);

   /*We shall add 6 objects who will symbolize the set {-3,5,2,0,-14,3}*/
   ArraySet_AddObject(s1, Object_Create(Integer_Create(-3),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(5),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(2),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(0),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(-14),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(3),I_Integer));

   puts("After adding objects to s1: ");
   PrintArraySet(s1);

   /*Trying to add duplicate values*/
   ArraySet_AddObject(s1, Object_Create(Integer_Create(-3),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(5),I_Integer));
   puts("After adding duplicate values to s1: ");
   PrintArraySet(s1);

   /*Creates a new ArraySet as a copy of the first ArraySet*/
   s2 = ArraySet_Copy(s1);

   /*Removing some objects from the first set*/
   ArraySet_RemoveObject(s1, Object_Create(Integer_Create(-3),I_Integer));
   ArraySet_RemoveObject(s1, Object_Create(Integer_Create(0),I_Integer));
   ArraySet_RemoveObject(s1, Object_Create(Integer_Create(-14),I_Integer));
   puts("After removing some objects from s1: ");
   PrintArraySet(s1);
   puts("s2 remains the same: ");
   PrintArraySet(s2);

   /*Resizing the array*/
   ArraySet_Resize(s1, 6);
   puts("After resizing s1 ");
   PrintArraySet(s1);

   /*After removing all objects from the second set*/
   puts("After removing all objects from s2: ");
   ArraySet_RemoveAll(s2);
   PrintArraySet(s2);
}
/*Output:
 After adding objects to s1:
 Size: 6 Capacity: 10 Objects: -3 5 2 0 -14 3
 After adding duplicate values to s1:
 Size: 6 Capacity: 10 Objects: -3 5 2 0 -14 3
 After removing some objects from s1:
 Size: 3 Capacity: 10 Objects: 5 2 3
 s2 remains the same:
 Size: 6 Capacity: 10 Objects: -3 5 2 0 -14 3
 After resizing s1
 Size: 3 Capacity: 6 Objects: 5 2 3
 After removing all objects from s2:
 Size: 0 Capacity: 10 Objects:
 */

Example 2

#include<stdio.h>
#include"Examples.h"
#include"ArraySet.h"
#include"SampleObject.h"

static void PrintArraySet(ArraySet* set)
{
   int i;
   printf("Size: %d Capacity: %d Objects: ", set->size, set->capacity);
   for (i = 0; i < set->size; i++)
   {
      printf("%d ", *(int*)(set->objects[i].data));
   }
   putchar('\n');
}

void ArraySet_Example2(void)
{
   ArraySet* s1 = NULL;
   ArraySet* s2 = NULL;
   ArraySet* r = NULL;
   Interface *I_Integer = NULL;
   bool result;

   /*Creating the Interface*/
   I_Integer = Interface_Create(&Integer_Copy,
                                &Integer_Destroy,
                                &Integer_Compare);

   /*Creating the first ArraySet and adding objects*/
   s1 = ArraySet_Create(10);
   ArraySet_AddObject(s1, Object_Create(Integer_Create(-3),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(5),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(2),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(0),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(-14),I_Integer));
   ArraySet_AddObject(s1, Object_Create(Integer_Create(3),I_Integer));

   /*Creates the second ArraySet and adding objects*/
   s2 = ArraySet_Create(10);
   ArraySet_AddObject(s2, Object_Create(Integer_Create(0),I_Integer));
   ArraySet_AddObject(s2, Object_Create(Integer_Create(1),I_Integer));
   ArraySet_AddObject(s2, Object_Create(Integer_Create(2),I_Integer));
   ArraySet_AddObject(s2, Object_Create(Integer_Create(0),I_Integer));
   ArraySet_AddObject(s2, Object_Create(Integer_Create(-14),I_Integer));
   ArraySet_AddObject(s2, Object_Create(Integer_Create(3),I_Integer));

   /*Prints the sets*/
   puts("Set S1");
   PrintArraySet(s1);
   puts("Set S2");
   PrintArraySet(s2);

   /*Checks if the set are equal*/
   result = ArraySet_Equals(s1, s2);
   if (result == true)
   {
      puts("S1 and S2 are equal");
   }
   else
   {
      puts("S1 and S2 are  not equal");
   }

   /*Checks if S1 is a subset of S2*/
   result = ArraySet_IsSubset(s1, s2);
   if (result == true)
   {
      puts("S1 is a subset of S2");
   }
   else
   {
      puts("S1 is not a subset of S2");
   }

   /*Computes the reunion of the two sets*/
   r = ArraySet_Reunion(s1, s2);
   puts("Reunion(S1,S2)");
   PrintArraySet(r);
   r = ArraySet_Destroy(r);

   /*Computes the intersection of the two sets*/
   puts("Intersection(S1,S2)");
   r = ArraySet_Intersection(s1, s2);
   PrintArraySet(r);
   r = ArraySet_Destroy(r);

   /*Computes the difference between S1 and S2*/
   r = ArraySet_Difference(s1, s2);
   puts("Difference(S1,S2)");
   PrintArraySet(r);
   r = ArraySet_Destroy(r);

   /*Computes the difference between S2 and S1*/
   r = ArraySet_Difference(s2, s1);
   puts("Difference(S2,S1");
   PrintArraySet(r);
   r = ArraySet_Destroy(r);
}
/*Output:
 Set S1
 Size: 6 Capacity: 10 Elements: -3 5 2 0 -14 3
 Set S2
 Size: 5 Capacity: 10 Elements: 0 1 2 -14 3
 S1 and S2 are  not equal
 S1 is not a subset of S2
 Reunion(S1,S2)
 Size: 7 Capacity: 11 Elements: -3 5 2 0 -14 3 1
 Intersection(S1,S2)
 Size: 4 Capacity: 10 Elements: 2 0 -14 3
 Difference(S1,S2)
 Size: 2 Capacity: 10 Elements: -3 5
 Difference(S2,S1
 Size: 1 Capacity: 10 Elements: 1
*/