2 * Amiga Generic Set - set of libraries and includes to ease sw development for all Amiga platforms
3 * Copyright (C) 2001-2011 Tomasz Wiszkowski Tomasz.Wiszkowski at gmail.com.
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include <LibC/LibC.h>
28 template <typename T
, long minSize
=16>
37 void qsort(T
* arr
, int size
, int(func
)(const T
&, const T
&))
41 int s1
= 0; // best result will be given
42 int s2
= size
; // ....
43 T
* ar2
= new T
[size
]; // when we use pointers here :]
44 T el
= arr
[size
/2]; // middle element
46 for (int i
=0; i
<size
; i
++) // so, for almost every element
48 if (i
== size
/2) // almost - except for the middle one
51 if (func(arr
[i
], el
) < 0) // fill table from both ways
52 ar2
[s1
++] = arr
[i
]; // if smaller - from one end
54 ar2
[--s2
] = arr
[i
]; // if greater - from another
57 ar2
[s1
] = el
; // put last element :)
59 for (int i
=0; i
<size
; i
++) // clone table
62 delete [] ar2
; // kill the temp
65 qsort(&arr
[s2
], size
-s2
, func
);
71 ASSERT(lCurrentSize
<= lTotalSize
);
72 if (lCurrentSize
== lTotalSize
)
74 lTotalSize
<<= 1; // twice that much
75 T
* pNewElem
= new T
[lTotalSize
];
76 for (int32 i
=0; i
<lCurrentSize
; i
++)
77 pNewElem
[i
] = pElements
[i
];
83 static int compare(const T
&a
, const T
&b
)
99 pElements
= new T
[lTotalSize
];
103 VectorT(const VectorT
<T
, minSize
> &src
)
113 T
& operator [] (int32 lElement
) const
115 ASSERT((lElement
>= -lCurrentSize
) && (lElement
< lCurrentSize
));
118 return pElements
[lElement
];
120 return pElements
[lCurrentSize
+ lElement
];
123 T
& Get(int lElement
) const
125 return (*this)[lElement
];
128 VectorT
<T
, minSize
>& operator << (T pNewElement
)
132 pElements
[lCurrentSize
] = pNewElement
;
154 lTotalSize
= minSize
;
156 pElements
= new T
[minSize
];
164 VectorT
<T
, minSize
>& operator >> (T pOldElement
)
167 for (i
=0; i
<lCurrentSize
; i
++)
169 if (pElements
[i
] == pOldElement
)
175 if (i
== lCurrentSize
) // not found.
180 for (; i
<lCurrentSize
; i
++)
182 pElements
[i
] = pElements
[i
+1];
185 // removing item does not change order;
195 VectorT
<T
, minSize
>& Sort(int(func
)(const T
&, const T
&))
200 qsort(pElements
, lCurrentSize
, func
);
205 VectorT
<T
, minSize
>& ForEach(bool(func
)(const T
&))
207 for (int32 i
=0; i
<lCurrentSize
; i
++)
209 if (!func(pElements
[i
]))
216 VectorT
<T
, minSize
>& InsertElem(T elem
, int32 pos
)
218 ASSERT((pos
>= 0) && (pos
<= lCurrentSize
));
220 if (pos
>= (int32
)lCurrentSize
)
231 for (int i
=lCurrentSize
; i
>pos
; --i
)
232 pElements
[i
] = pElements
[i
-1];
233 pElements
[pos
] = elem
;
238 VectorT
<T
, minSize
>& RemoveElem(int32 pos
)
240 ASSERT((pos
>= 0) && (pos
< lCurrentSize
));
241 *this >> pElements
[pos
];
245 VectorT
<T
, minSize
>& InsertSorted(T elem
, int(func
)(const T
&, const T
&))
247 register int pos
= (lCurrentSize
+ 1) / 2;
248 register int step
= pos
;
258 if (0 > func(elem
, pElements
[pos
-1]))
268 if (pos
< (int32
)lCurrentSize
)
270 if (0 < func(elem
, pElements
[pos
]))
274 if (pos
> (int32
)lCurrentSize
)
283 return InsertElem(elem
, pos
);
286 int IndexOf(T elem
, int(func
)(const T
&, const T
&))
288 register int pos
= (lCurrentSize
) / 2;
289 register int step
= (lCurrentSize
+1) / 2;
293 if (lCurrentSize
== 0)
301 if (0 == func(elem
, pElements
[pos
]))
305 * check if we have a match
307 res
= func(elem
, pElements
[pos
]);
310 if ((pos
== (lCurrentSize
-1)) && (res
> 0))
312 if ((pos
== 0) && (res
== 0))
330 if (pos
>= lCurrentSize
)
331 pos
= lCurrentSize
-1;
337 VectorT
<T
, minSize
>& operator =(const VectorT
<T
, minSize
> &src
)
339 lCurrentSize
= src
.lCurrentSize
;
340 lTotalSize
= src
.lTotalSize
;
341 pElements
= new T
[lTotalSize
];
342 bSorted
= src
.bSorted
;
344 for (int32 i
=0; i
<lCurrentSize
; i
++)
346 pElements
[i
] = src
.pElements
[i
];