d07c171f |
1 | /* |
2 | Copyright (C) 2003 Rice1964 |
3 | |
4 | This program is free software; you can redistribute it and/or |
5 | modify it under the terms of the GNU General Public License |
6 | as published by the Free Software Foundation; either version 2 |
7 | of the License, or (at your option) any later version. |
8 | |
9 | This program is distributed in the hope that it will be useful, |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 | GNU General Public License for more details. |
13 | |
14 | You should have received a copy of the GNU General Public License |
15 | along with this program; if not, write to the Free Software |
16 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
17 | */ |
18 | |
19 | #ifndef _SORTED_LIST_H_ |
20 | #define _SORTED_LIST_H_ |
21 | |
22 | #include <cstring> |
23 | |
24 | template<class Key, class Element> |
25 | class CSortedList |
26 | { |
27 | private: |
28 | Key *keys; |
29 | Element *elements; |
30 | int curSize; |
31 | int maxSize; |
32 | |
33 | public: |
34 | CSortedList(int size=1000) |
35 | { |
36 | maxSize = size; |
37 | curSize = 0; |
38 | keys = new Key[size]; |
39 | elements = new Element[size]; |
40 | } |
41 | |
42 | ~CSortedList() |
43 | { |
44 | delete [] keys; |
45 | delete [] elements; |
46 | } |
47 | |
48 | int size() |
49 | { |
50 | return curSize; |
51 | } |
52 | |
53 | void clear() |
54 | { |
55 | curSize = 0; |
56 | } |
57 | |
58 | void add(Key key, Element ele) |
59 | { |
60 | int i = find(key); |
61 | if( i >= 0 ) |
62 | { |
63 | elements[i] = ele; |
64 | return; |
65 | } |
66 | |
67 | if( curSize == maxSize ) |
68 | { |
69 | // Need to increase maxSize |
70 | Key *oldkeys = keys; |
71 | Element *oldelements = elements; |
72 | int oldmaxsize = maxSize; |
73 | maxSize *= 2; |
74 | |
75 | keys = new Key[maxSize]; |
76 | elements = new Element[maxSize]; |
77 | std::memcpy(keys,oldkeys,oldmaxsize*sizeof(Key)); |
78 | std::memcpy(elements,oldelements,oldmaxsize*sizeof(Element)); |
79 | } |
80 | |
81 | for( i=0; i<curSize; i++ ) |
82 | { |
83 | if( keys[i] > key ) |
84 | { |
85 | // Found the spot |
86 | break; |
87 | } |
88 | } |
89 | |
90 | for( int j=curSize; j>i; j-- ) |
91 | { |
92 | keys[j] = keys[j-1]; |
93 | elements[j] = elements[j-1]; |
94 | } |
95 | |
96 | keys[i] = key; |
97 | elements[i] = ele; |
98 | curSize++; |
99 | } |
100 | |
101 | Element operator[](int index) |
102 | { |
103 | if( index >= curSize ) |
104 | index = curSize-1; |
105 | else if( index < 0 ) |
106 | index = 0; |
107 | |
108 | return elements[index]; |
109 | } |
110 | |
111 | Element get(Key key) |
112 | { |
113 | int index = Find(key); |
114 | return this->operator[](index); |
115 | } |
116 | |
117 | // Binary search |
118 | int find(Key key) |
119 | { |
120 | if( curSize <= 0 ) |
121 | return -1; |
122 | |
123 | int dwMin = 0; |
124 | int dwMax = curSize - 1; |
125 | int index = -1; |
126 | |
127 | int dwRange; |
128 | int dwIndex; |
129 | |
130 | while (true) |
131 | { |
132 | dwRange = dwMax - dwMin; |
133 | dwIndex = dwMin + (dwRange/2); |
134 | |
135 | if( keys[dwIndex] == key ) |
136 | { |
137 | index = dwIndex; |
138 | break; |
139 | } |
140 | |
141 | // If the range is 0, and we didn't match above, then it must be unmatched |
142 | if (dwRange == 0) |
143 | break; |
144 | |
145 | // If lower, check from min..index |
146 | // If higher, check from index..max |
147 | if (key < keys[dwIndex]) |
148 | { |
149 | // Lower |
150 | dwMax = dwIndex; |
151 | } |
152 | else |
153 | { |
154 | // Higher |
155 | dwMin = dwIndex + 1; |
156 | } |
157 | } |
158 | |
159 | return index; |
160 | } |
161 | }; |
162 | |
163 | #endif |
164 | |