Fixed a bug in the UT_RBTree::insert code.
I've added code that can checks if the invariants of
the rb tree are conserved (#ifdef DEBUG).
I have a new bug (this time related to erasing the
root of the tree)
I will fix it tomorrow (I need some sleep now)
P.S.: I've done a little test (10 random insertions &
10 random erases of these numbers, I will increase
this number as I fix bugs).
Attached is the source code. It needs the STL,
namespaces, etc. Btw, I suppose that I'm not dreaming
or something... msvc doesn't cares about koenig's
rule, doesn't it?
I had:
random_shuffle(numbers.begin(), numbers.end());
but it was saying that I was lacking a std::
go figure... crappy compiler
(in addition, it seems to work for operators!
at least std::cout << "hello"; works right... pretty
weird)
It should compile right with gcc & msvc (well it
should compile right with any c++ compilers (I
think)... the real ones ;-)
Cheers,
--
Joaqu�n Cuenca Abela
[EMAIL PROTECTED]
__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail
http://personal.mail.yahoo.com/
#include <deque>
#include <iostream>
#include <algorithm>
#include "ut_set.h"
#include "ut_assert.h"
template <class ForwardIterator, class T>
inline void iota(ForwardIterator first, ForwardIterator last, T value)
{
while (first != last)
*first++ = value++;
}
int main()
{
typedef std::deque<int> NumCont;
typedef NumCont::const_iterator CItNumCont;
UT_Set s;
NumCont numbers(10);
iota(numbers.begin(), numbers.end(), 0);
// ARRGGGGH!!! Why this _C_R_A_P_P_Y_ MSVC compiler don't catch this
// function using Koenig's rule????!!!
std::random_shuffle(numbers.begin(), numbers.end());
// berk. Lack of templates gives us reinterpret_cast...
// what would be next? end of world?
CItNumCont numbers_end(numbers.end());
for (CItNumCont it(numbers.begin()); it != numbers_end; ++it)
{
s.insert(reinterpret_cast<UT_Set::key_t> (*it));
if (!s.checkInvariants())
{
s.print();
return 1;
}
}
std::random_shuffle(numbers.begin(), numbers.end());
numbers_end = numbers.end();
const UT_Set::Iterator set_end(s.end());
for (CItNumCont it1(numbers.begin()); it1 != numbers_end; ++it1)
{
std::cout << "So far everything seems right:\n";
s.print();
UT_Set::Iterator sit(s.find(reinterpret_cast<UT_Set::key_t> (*it1)));
if (sit == set_end)
{
std::cerr << "Error removing " << *it1 << '\n';
s.print();
return 2;
}
else
s.erase(sit);
if (!s.checkInvariants())
{
std::cerr << "Error removing " << *it1 << '\n';
std::cout << "Screwed.\n" << '\n';
s.print();
return 3;
}
}
return 0;
}
