110 lines
2.9 KiB
C
110 lines
2.9 KiB
C
/*
|
|
an ordered array is just a regular array except all elements must be in order,
|
|
so there a few things to note:
|
|
|
|
1. inserting must respect order
|
|
2. removing must respect order
|
|
3. serching can be made faster with binary search
|
|
*/
|
|
|
|
#include <stdbool.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
typedef struct FixedOrderedArray {
|
|
int capacity;
|
|
int index; // index next to insert at, arr[index] should be empty
|
|
int data[];
|
|
} FixedOrderedArray;
|
|
|
|
|
|
FixedOrderedArray *new_fixed_ordered_array(int capacity) {
|
|
FixedOrderedArray *arr = malloc(sizeof(FixedOrderedArray) + (sizeof(int) * capacity));
|
|
arr->capacity = capacity;
|
|
arr->index = 0;
|
|
|
|
return (arr);
|
|
}
|
|
|
|
void fixed_ordered_array_insert(FixedOrderedArray *arr, int val) {
|
|
if (arr->capacity == arr->index) {
|
|
fprintf(stderr, "ERROR: array is at capacity, cannot append value\n");
|
|
exit(1);
|
|
}
|
|
|
|
if (arr->index == 0) {
|
|
arr->data[0] = val;
|
|
arr->index++;
|
|
} else if (val >= arr->data[arr->index - 1]) {
|
|
arr->data[arr->index] = val;
|
|
arr->index++;
|
|
} else if (val <= arr->data[0]) { // its smallest to add to start
|
|
for (int i = arr->index; i > 0; i--) { // shift everything to the right
|
|
arr->data[i] = arr->data[i - 1];
|
|
}
|
|
arr->data[0] = val;
|
|
arr->index++;
|
|
} else { // look for where it belongs
|
|
for (int i = 0; i < arr->index; i++) {
|
|
if (arr->data[i] > val) { // we must shift everything to the right up to this index
|
|
for (int j = arr->index; j > i; j--) {
|
|
arr->data[j] = arr->data[j - 1];
|
|
}
|
|
arr->data[i] = val;
|
|
arr->index++;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
bool search_fixed_ordered_array(FixedOrderedArray *arr, int val) {
|
|
if (arr->index == 0) {
|
|
return (false);
|
|
}
|
|
|
|
if (val < arr->data[0]) {
|
|
return (false);
|
|
}
|
|
|
|
if (val > arr->data[arr->index - 1]) {
|
|
return (false);
|
|
}
|
|
|
|
for (int i = 0; i < arr->index; i++) {
|
|
if (val == arr->data[i]) {
|
|
return (true);
|
|
} else if (arr->data[i] > val) {
|
|
return (false);
|
|
}
|
|
}
|
|
return (false);
|
|
}
|
|
|
|
void print_array_list(FixedOrderedArray *arr) {
|
|
printf("[");
|
|
for (int i = 0; i < arr->index; i++) {
|
|
printf(" %d ", arr->data[i]);
|
|
}
|
|
|
|
printf("]\t<capacity: %d; index: %d>\n", arr->capacity, arr->index);
|
|
}
|
|
|
|
int main() {
|
|
FixedOrderedArray *arr = new_fixed_ordered_array(5);
|
|
|
|
fixed_ordered_array_insert(arr, 10);
|
|
print_array_list(arr);
|
|
fixed_ordered_array_insert(arr, 9);
|
|
print_array_list(arr);
|
|
fixed_ordered_array_insert(arr, 13);
|
|
print_array_list(arr);
|
|
fixed_ordered_array_insert(arr, 11);
|
|
print_array_list(arr);
|
|
fixed_ordered_array_insert(arr, 9);
|
|
print_array_list(arr);
|
|
|
|
bool result = search_fixed_ordered_array(arr, 11);
|
|
printf("the result is %d\n", result);
|
|
}
|