blob: 0852cf9497e2bd79ea734641fc022c3e54deecd5 (
plain)
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
|
// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H
#include <inttypes.h>
#include <stddef.h>
#include <new>
/**
* A simple, resizable array list. Note that this only works with POD types
* (because data is grown via realloc).
*/
template<typename T> class array_list {
static const size_t INITIAL_CAPACITY = 8;
size_t _size;
T * _data;
size_t _capacity;
private:
// private and left undefined to disable copying
array_list(const array_list& rhs);
array_list& operator=(const array_list& rhs);
public:
array_list();
~array_list();
size_t size() const;
int32_t append(T value);
int32_t push(T value);
void pop(T *value);
bool replace(T old_value, T new_value);
int32_t index_of(T value) const;
bool is_empty() const;
T* data();
const T* data() const;
T & operator[](size_t index);
const T & operator[](size_t index) const;
};
template<typename T>
array_list<T>::array_list() {
_size = 0;
_capacity = INITIAL_CAPACITY;
_data = (T *) malloc(sizeof(T) * _capacity);
}
template<typename T>
array_list<T>::~array_list() {
free(_data);
}
template<typename T> size_t
array_list<T>::size() const {
return _size;
}
template<typename T> int32_t
array_list<T>::append(T value) {
return push(value);
}
template<typename T> int32_t
array_list<T>::push(T value) {
if (_size == _capacity) {
size_t new_capacity = _capacity * 2;
void* buffer = realloc(_data, new_capacity * sizeof(T));
if (buffer == NULL) {
fprintf(stderr,
"array_list::push> "
"Out of memory allocating %ld bytes",
(long int) (new_capacity * sizeof(T)));
abort();
}
_data = (T *) buffer;
_capacity = new_capacity;
}
_data[_size ++] = value;
return _size - 1;
}
template<typename T> void
array_list<T>::pop(T *value) {
assert(_size > 0);
if (value != NULL) {
*value = _data[-- _size];
} else {
-- _size;
}
}
/**
* Replaces the old_value in the list with the new_value.
* Returns the true if the replacement succeeded, or false otherwise.
*/
template<typename T> bool
array_list<T>::replace(T old_value, T new_value) {
int index = index_of(old_value);
if (index < 0) {
return false;
}
_data[index] = new_value;
return true;
}
template<typename T> int32_t
array_list<T>::index_of(T value) const {
for (size_t i = 0; i < _size; i++) {
if (_data[i] == value) {
return i;
}
}
return -1;
}
template<typename T> T &
array_list<T>::operator[](size_t index) {
assert(index < size());
return _data[index];
}
template<typename T> const T &
array_list<T>::operator[](size_t index) const {
assert(index < size());
return _data[index];
}
template<typename T> bool
array_list<T>::is_empty() const {
return _size == 0;
}
template<typename T> T*
array_list<T>::data() {
return _data;
}
template<typename T> const T*
array_list<T>::data() const {
return _data;
}
#endif /* ARRAY_LIST_H */
|
