]>
Commit | Line | Data |
---|---|---|
bb849dbd RC |
1 | /* |
2 | * Copyright (c) 2001, Robert Collins. | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or modify | |
5 | * it under the terms of the GNU General Public License as published by | |
6 | * the Free Software Foundation; either version 2 of the License, or | |
7 | * (at your option) any later version. | |
8 | * | |
9 | * A copy of the GNU General Public License can be found at | |
10 | * http://www.gnu.org/ | |
11 | * | |
12 | * Written by Robert Collins <rbtcollins@hotmail.com> | |
13 | * | |
14 | */ | |
15 | ||
16 | #ifndef _LIST_H_ | |
17 | #define _LIST_H_ | |
18 | ||
cbfc4215 | 19 | #include "stdlib.h" |
bb849dbd RC |
20 | #include "sys/types.h" |
21 | ||
22 | /* Creates a list/array of type T (must have a field key of type U), | |
23 | * with index type U and U comparison Ucmp. | |
24 | */ | |
25 | template < class T, class U, int | |
26 | Ucmp (U, U) > | |
27 | class list | |
28 | { | |
29 | T **pointerblock; | |
30 | size_t _number; | |
31 | size_t _space; | |
32 | ||
33 | public: | |
34 | list ():pointerblock (0), _number (0), _space (0) | |
35 | { | |
36 | }; | |
37 | // ~list () ... | |
38 | /* get an element if it exists */ | |
7e8fc33c | 39 | T *getbykey (const U); |
bb849dbd RC |
40 | /* add an element if it does not exist and return a reference */ |
41 | T & registerbykey (U); | |
42 | /* add an element if one with the same key does not exist */ | |
43 | T & registerbyobject (T &); | |
de6a1a64 | 44 | /* remove by index */ |
cc7493c3 | 45 | T *removebyindex (size_t); |
cbfc4215 | 46 | size_t number () const |
bb849dbd RC |
47 | { |
48 | return _number; | |
49 | }; | |
50 | /* get by offset - not thread safe - starts at 1 */ | |
cbfc4215 | 51 | T *operator [] (size_t n) const |
bb849dbd RC |
52 | { |
53 | return n && n <= _number ? pointerblock[n - 1] : 0; | |
54 | }; | |
55 | /* TODO: delete */ | |
cc7493c3 RC |
56 | private: |
57 | // ensure there is enough array space. | |
58 | void checksize (void); | |
59 | // perform an insertion. | |
60 | void insert (size_t, T *); | |
bb849dbd RC |
61 | }; |
62 | ||
63 | template < class T, class U, int | |
64 | Ucmp (U, U) > | |
7e8fc33c | 65 | T * list < T, U, Ucmp >::getbykey (const U key) |
bb849dbd RC |
66 | { |
67 | for (size_t n = 0; n < _number; n++) | |
68 | if (Ucmp (pointerblock[n]->key, key) == 0) | |
69 | return pointerblock[n]; | |
70 | return 0; | |
71 | } | |
72 | ||
73 | ||
74 | template < class T, class U, int | |
75 | Ucmp (U, U) > | |
76 | T & list < T, U, Ucmp >::registerbykey (U key) | |
77 | { | |
78 | T *tempT = getbykey (key); | |
79 | if (!tempT) | |
80 | { | |
bb849dbd RC |
81 | tempT = new T (key); |
82 | size_t n; | |
83 | for (n = 0; | |
84 | n < _number && Ucmp (pointerblock[n]->key, tempT->key) < 0; n++); | |
cc7493c3 | 85 | insert (n, tempT); |
bb849dbd RC |
86 | } |
87 | return *tempT; | |
88 | } | |
89 | ||
90 | /* TODO: factor both insertion routines into one */ | |
91 | template < class T, class U, int | |
92 | Ucmp (U, U) > | |
93 | T & list < T, U, Ucmp >::registerbyobject (T & newobj) | |
94 | { | |
95 | T *tempT = getbykey (newobj.key); | |
96 | if (!tempT) | |
97 | { | |
bb849dbd RC |
98 | tempT = &newobj; |
99 | size_t n; | |
100 | for (n = 0; | |
101 | n < _number && Ucmp (pointerblock[n]->key, tempT->key) < 0; n++); | |
cc7493c3 | 102 | insert (n, tempT); |
bb849dbd RC |
103 | } |
104 | return *tempT; | |
105 | } | |
106 | ||
cc7493c3 RC |
107 | template < class T, class U, int |
108 | Ucmp (U, U) > | |
de6a1a64 RC |
109 | T * list < T, U, Ucmp >::removebyindex (size_t index) |
110 | { | |
111 | if (index && index <= _number) | |
112 | { | |
cc7493c3 | 113 | T *rv = pointerblock[index - 1]; |
de6a1a64 | 114 | /* remove from index - 1 */ |
cc7493c3 RC |
115 | for (size_t i = index; i < _number; ++i) |
116 | pointerblock[i - 1] = pointerblock[i]; | |
117 | --_number; | |
de6a1a64 RC |
118 | return rv; |
119 | } | |
120 | return 0; | |
121 | } | |
122 | ||
cc7493c3 RC |
123 | template < class T, class U, int |
124 | Ucmp (U, U) > void | |
125 | list < T, U, Ucmp >::checksize () | |
126 | { | |
127 | if (_number == _space) | |
128 | { | |
129 | T **newptr = new (T *)[_space + 20]; | |
130 | if (!newptr) | |
131 | { | |
132 | //die - todo enable exceptions | |
133 | exit (100); | |
134 | } | |
135 | for (size_t i = 0; i < _number; ++i) | |
136 | newptr[i] = pointerblock[i]; | |
137 | delete[]pointerblock; | |
138 | pointerblock = newptr; | |
139 | /* TODO: Parameterise this too */ | |
140 | _space += 20; | |
141 | } | |
142 | } | |
143 | template < class T, class U, int | |
144 | Ucmp (U, U) > void | |
145 | list < T, U, Ucmp >::insert (size_t where, T * someT) | |
146 | { | |
147 | // doesn't change where | |
148 | checksize (); | |
149 | /* insert at where */ | |
150 | for (size_t i = _number; where < i; --i) | |
151 | pointerblock[i] = pointerblock[i - 1]; | |
152 | pointerblock[where] = someT; | |
153 | ++_number; | |
154 | } | |
155 | ||
156 | ||
bb849dbd | 157 | #endif /* _LIST_H_ */ |