Subject: commit -- fix for UT_RBTree
From: Joaquin Cuenca Abela (e98cuenc@yahoo.com)
Date: Tue Jul 17 2001 - 22:27:49 CDT
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 e98cuenc@yahoo.com__________________________________________________ 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; }
This archive was generated by hypermail 2b25 : Tue Jul 17 2001 - 22:27:52 CDT