1/*---------------------------------------------------------------------------*
2 *  ArrayListImpl.c  *
3 *                                                                           *
4 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
5 *                                                                           *
6 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
7 *  you may not use this file except in compliance with the License.         *
8 *                                                                           *
9 *  You may obtain a copy of the License at                                  *
10 *      http://www.apache.org/licenses/LICENSE-2.0                           *
11 *                                                                           *
12 *  Unless required by applicable law or agreed to in writing, software      *
13 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
14 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
15 *  See the License for the specific language governing permissions and      *
16 *  limitations under the License.                                           *
17 *                                                                           *
18 *---------------------------------------------------------------------------*/
19
20
21
22#include "ArrayList.h"
23#include "ArrayListImpl.h"
24#include "pmemory.h"
25
26#define MTAG NULL
27#define INITIAL_CAPACITY 16
28
29ESR_ReturnCode ArrayListCreateWithCapacity(ArrayList **self, size_t minCapacity)
30{
31  ArrayListImpl* impl;
32
33  if (self == NULL)
34    return ESR_INVALID_ARGUMENT;
35
36  impl = NEW(ArrayListImpl, MTAG);
37
38  if (impl == NULL)
39    return ESR_OUT_OF_MEMORY;
40
41  impl->Interface.add = &ArrayList_Add;
42  impl->Interface.insertAt = &ArrayList_InsertAt;
43  impl->Interface.contains = &ArrayList_Contains;
44  impl->Interface.destroy = &ArrayList_Destroy;
45  impl->Interface.get = &ArrayList_Get;
46  impl->Interface.getSize = &ArrayList_GetSize;
47  impl->Interface.remove = &ArrayList_Remove;
48  impl->Interface.removeAtIndex = &ArrayList_RemoveAtIndex;
49  impl->Interface.removeAll = &ArrayList_RemoveAll;
50  impl->Interface.set = &ArrayList_Set;
51  impl->Interface.toStaticArray = NULL; /* Not implemented */
52  impl->Interface.clone = &ArrayList_Clone;
53
54  impl->contents = MALLOC(minCapacity * sizeof(void*), MTAG);
55  if (impl->contents == NULL)
56  {
57    FREE(impl);
58    return ESR_OUT_OF_MEMORY;
59  }
60  impl->capacity = minCapacity;
61  impl->minCapacity = minCapacity;
62  impl->size = 0;
63
64  *self = (ArrayList*) impl;
65  return ESR_SUCCESS;
66}
67
68
69ESR_ReturnCode ArrayListCreate(ArrayList** self)
70{
71  return ArrayListCreateWithCapacity(self, INITIAL_CAPACITY);
72}
73
74static ESR_ReturnCode ArrayList_Insert_Internal(ArrayListImpl *impl, size_t index, void *element)
75{
76  size_t i;
77
78  if (impl->size >= impl->capacity)
79  {
80    /* enlarge buffer */
81    size_t newCapacity = impl->capacity * 2;
82    void** temp = REALLOC(impl->contents, newCapacity * sizeof(void*));
83    if (temp == NULL)
84      return ESR_OUT_OF_MEMORY;
85    impl->contents = temp;
86    impl->capacity = newCapacity;
87  }
88
89  for (i = impl->size; i > index; --i)
90    impl->contents[i] = impl->contents[i - 1];
91  ++impl->size;
92  impl->contents[index] = element;
93  return ESR_SUCCESS;
94}
95
96ESR_ReturnCode ArrayList_Add(ArrayList* self, void* element)
97{
98  ArrayListImpl *impl = (ArrayListImpl *) self;
99
100  return ArrayList_Insert_Internal(impl, impl->size, element);
101}
102
103ESR_ReturnCode ArrayList_InsertAt(ArrayList *self, size_t index, void *element)
104{
105  ArrayListImpl *impl = (ArrayListImpl *) self;
106
107  if (index > impl->size)
108    return ESR_ARGUMENT_OUT_OF_BOUNDS;
109
110  return ArrayList_Insert_Internal(impl, index, element);
111}
112
113static ESR_ReturnCode ArrayList_Remove_Internal(ArrayListImpl *impl, size_t i)
114{
115  --impl->size;
116  while (i < impl->size)
117  {
118    impl->contents[i] = impl->contents[i+1];
119    ++i;
120  }
121
122  if (impl->capacity > impl->minCapacity &&
123      impl->size <= impl->capacity / 4)
124  {
125    void** temp;
126    size_t newCapacity = impl->capacity / 2;
127
128    /* shrink buffer */
129    if ((temp = REALLOC(impl->contents, newCapacity * sizeof(void*))) == NULL)
130      return ESR_OUT_OF_MEMORY;
131    impl->contents = temp;
132    impl->capacity = newCapacity;
133  }
134  return ESR_SUCCESS;
135}
136
137ESR_ReturnCode ArrayList_Remove(ArrayList* self, const void* element)
138{
139  ArrayListImpl* impl = (ArrayListImpl*) self;
140  size_t i;
141
142  /* Remove element */
143  for (i = 0; i < impl->size; ++i)
144  {
145    if (impl->contents[i] == element)
146      return ArrayList_Remove_Internal(impl, i);
147  }
148
149  return ESR_NO_MATCH_ERROR;
150}
151
152ESR_ReturnCode ArrayList_RemoveAtIndex(ArrayList* self, size_t index)
153{
154  ArrayListImpl* impl = (ArrayListImpl*) self;
155
156  if (index >= impl->size)
157    return ESR_ARGUMENT_OUT_OF_BOUNDS;
158
159  return ArrayList_Remove_Internal(impl, index);
160}
161
162ESR_ReturnCode ArrayList_RemoveAll(ArrayList* self)
163{
164  ArrayListImpl* impl = (ArrayListImpl*) self;
165
166  impl->size = 0;
167  return ESR_SUCCESS;
168}
169
170ESR_ReturnCode ArrayList_Contains(ArrayList* self, const void* element,
171                                  ESR_BOOL* exists)
172{
173  ArrayListImpl* impl = (ArrayListImpl*) self;
174  size_t i;
175
176  for (i = 0; i < impl->size; ++i)
177  {
178    if (impl->contents[i] == element)
179    {
180      *exists = ESR_TRUE;
181      return ESR_SUCCESS;
182    }
183  }
184  *exists = ESR_FALSE;
185  return ESR_SUCCESS;
186}
187
188ESR_ReturnCode ArrayList_Get(ArrayList* self, size_t index, void** element)
189{
190  ArrayListImpl* impl = (ArrayListImpl*) self;
191
192  if (index >= impl->size)
193    return ESR_ARGUMENT_OUT_OF_BOUNDS;
194  *element = impl->contents[index];
195  return ESR_SUCCESS;
196}
197
198ESR_ReturnCode ArrayList_Set(ArrayList* self, size_t index, void* element)
199{
200  ArrayListImpl* impl = (ArrayListImpl*) self;
201
202  if (index >= impl->size)
203    return ESR_ARGUMENT_OUT_OF_BOUNDS;
204  impl->contents[index] = element;
205  return ESR_SUCCESS;
206}
207
208ESR_ReturnCode ArrayList_GetSize(ArrayList* self, size_t* size)
209{
210  ArrayListImpl* impl = (ArrayListImpl*) self;
211
212  *size = impl->size;
213  return ESR_SUCCESS;
214}
215
216ESR_ReturnCode ArrayList_Clone(ArrayList* self, ArrayList* clone)
217{
218  size_t size, i;
219  void* element;
220  ESR_ReturnCode rc;
221
222  CHK(rc, clone->removeAll(clone));
223  CHK(rc, self->getSize(self, &size));
224  for (i = 0; i < size; ++i)
225  {
226    CHK(rc, self->get(self, i, &element));
227    CHK(rc, clone->add(clone, element));
228  }
229  return ESR_SUCCESS;
230CLEANUP:
231  return rc;
232}
233
234ESR_ReturnCode ArrayList_Destroy(ArrayList* self)
235{
236  ArrayListImpl* impl = (ArrayListImpl*) self;
237
238  FREE(impl->contents);
239  FREE(self);
240  return ESR_SUCCESS;
241}
242