Repository navigation
Expand file tree
/
Copy pathsortedarray.h
More file actions
178 lines (154 loc) · 5.59 KB
/
Copy pathsortedarray.h
File metadata and controls
178 lines (154 loc) · 5.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/*
Copyright (c) 2016, Stefan Cloudt
Permission to use, copy, modify, and/or distribute this software
for any purpose with or without fee is hereby granted, provided
that the above copyright notice and this permission notice appear
in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/**
* @file sortedarray.h
*
* @brief Automatically sorted and resizing array
*
* An SortedArray is an automatically resizing sorted array. Most operations
* run O(n) worst case running time. Some operations run in O(log n).
*
* To retrieve a value use the sortedarray structure by accessing the data
* field.
*
* To create a SortedArray, use @ref sortedarray_new
* To destroy a SortedArray, use @ref sortedarray_free
*
* To add a value to a SortedArray, use @ref sortedarray_insert.
*
* To remove a value from a SortedArray, use @ref sortedarray_remove
* or @ref sortedarray_remove_range.
*/
#ifndef ALGORITHM_SORTEDARRAY_H
#define ALGORITHM_SORTEDARRAY_H
#ifdef __cplusplus
extern "C" {
#endif
#ifdef TEST_ALTERNATE_VALUE_TYPES
#include "alt-value-type.h"
#else
/**
* A value to store in @ref SortedArray.
*/
typedef void *SortedArrayValue;
/**
* A null @ref SortedArrayValue.
*/
#define SORTED_ARRAY_NULL ((void *) 0)
#endif /* #ifndef TEST_ALTERNATE_VALUE_TYPES */
/**
* A SortedArray structure. Use @ref sortedarray_new to create one.
*
* The SortedArray is an automatically resizing array which stores its elements
* in sorted order. User-defined functions determine the sorting order. All
* operations on a SortedArray maintain the sorted property. Most operations
* are done in O(n) time, but searching can be done in O(log n) worst case.
*
* @see sortedarray_new
*/
typedef struct _SortedArray SortedArray;
/**
* Compare two values in a SortedArray to determine their order.
*
* @param value1 The first value to compare.
* @param value2 The second value to compare.
* @return Less than zero if value1 is compared smaller than
* value2, zero if they compare equal, or greater than
* zero if value1 compares greate than value2.
*/
typedef int (*SortedArrayCompareFunc)(SortedArrayValue value1,
SortedArrayValue value2);
/**
* @brief Function to retrieve element at index i from array
*
* @param array The pointer to the sortedarray to retrieve the element from.
* @param i The index of the element to retrieve.
* @return The i-th element of the array, or NULL if array was NULL.
*/
SortedArrayValue sortedarray_get(SortedArray *array, unsigned int i);
/**
* @brief Function to retrieve the length of the SortedArray array.
*
* @param array The array to retrieve the length from.
* @return The length of the SortedArray.
*/
unsigned int sortedarray_length(SortedArray *array);
/**
* Allocate a new SortedArray for use.
*
* @param length Indication to the amount of memory that should be
* allocated. If 0 is given, then a default is used.
* @param cmp_func The function used to determine the relative order of
* two values in the SortedArray. This may not be NULL.
*
* @return A new SortedArray or NULL if it was not possible to
* allocate one.
*/
SortedArray *sortedarray_new(unsigned int length,
SortedArrayCompareFunc cmp_func);
/**
* Frees a SortedArray from memory.
*
* @param sortedarray The SortedArray to free.
*/
void sortedarray_free(SortedArray *sortedarray);
/**
* Remove a value from a SortedArray at a specified index while maintaining the
* sorted property.
*
* @param sortedarray The SortedArray to remove a value from.
* @param index The index to remove from the array.
* @return Zero on failure, non-zero on success.
*/
int sortedarray_remove(SortedArray *sortedarray, unsigned int index);
/**
* Remove a range of entities from a SortedArray while maintaining the sorted
* property.
*
* @param sortedarray The SortedArray to remove the range of values from.
* @param index The starting index of the range to remove.
* @param length The length of the range to remove.
* @return Zero on failure, non-zero on success.
*/
int sortedarray_remove_range(SortedArray *sortedarray, unsigned int index,
unsigned int length);
/**
* Insert a value into a SortedArray while maintaining the sorted property.
*
* @param sortedarray The SortedArray to insert into.
* @param data The data to insert.
*
* @return Zero on failure, or a non-zero value if successfull.
*/
int sortedarray_insert(SortedArray *sortedarray, SortedArrayValue data);
/**
* Find the index of a value in a SortedArray.
*
* @param sortedarray The SortedArray to find in.
* @param data The value to find.
* @return The index of the value or -1 if the value is not found.
*/
int sortedarray_index_of(SortedArray *sortedarray, SortedArrayValue data);
/**
* Remove all values from a SortedArray.
*
* @param sortedarray The SortedArray to clear.
*/
void sortedarray_clear(SortedArray *sortedarray);
#ifdef __cplusplus
}
#endif
#endif /* #ifndef ALGORITHM_SORTEDARRAY_H */