diff options
Diffstat (limited to 'gnu/lib/libg++/g++-include/OSLSet.ccP')
| -rw-r--r-- | gnu/lib/libg++/g++-include/OSLSet.ccP | 321 |
1 files changed, 321 insertions, 0 deletions
diff --git a/gnu/lib/libg++/g++-include/OSLSet.ccP b/gnu/lib/libg++/g++-include/OSLSet.ccP new file mode 100644 index 000000000000..bfd32ae954ce --- /dev/null +++ b/gnu/lib/libg++/g++-include/OSLSet.ccP @@ -0,0 +1,321 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of the GNU C++ Library. This library is free +software; you can redistribute it and/or modify it under the terms of +the GNU Library General Public License as published by the Free +Software Foundation; either version 2 of the License, or (at your +option) any later version. This library is distributed in the hope +that it will be useful, but WITHOUT ANY WARRANTY; without even the +implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR +PURPOSE. See the GNU Library General Public License for more details. +You should have received a copy of the GNU Library General Public +License along with this library; if not, write to the Free Software +Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include "<T>.OSLSet.h" + + +Pix <T>OSLSet::seek(<T&> item) +{ + for (Pix i = p.first(); i != 0; p.next(i)) + { + int cmp = <T>CMP(item, p(i)); + if (cmp == 0) + return i; + else if (cmp < 0) + return 0; + } + return 0; +} + +Pix <T>OSLSet::add(<T&> item) +{ + Pix i = p.first(); + if (i == 0) + { + ++count; + return p.prepend(item); + } + int cmp = <T>CMP(item, p(i)); + if (cmp == 0) + return i; + else if (cmp < 0) + { + ++count; + return p.prepend(item); + } + else + { + Pix trail = i; + p.next(i); + for (;;) + { + if (i == 0) + { + ++count; + return p.append(item); + } + cmp = <T>CMP(item, p(i)); + if (cmp == 0) + return i; + else if (cmp < 0) + { + ++count; + return p.ins_after(trail, item); + } + else + { + trail = i; + p.next(i); + } + } + } +} + +void <T>OSLSet::del(<T&> item) +{ + Pix i = p.first(); + if (i == 0) + return; + int cmp = <T>CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + --count; + p.del_front(); + } + else + { + Pix trail = i; + p.next(i); + while (i != 0) + { + cmp = <T>CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + --count; + p.del_after(trail); + return; + } + else + { + trail = i; + p.next(i); + } + } + } +} + + +int <T>OSLSet::operator <= (<T>OSLSet& b) +{ + if (count > b.count) return 0; + Pix i = first(); + Pix j = b.first(); + for (;;) + { + if (i == 0) + return 1; + else if (j == 0) + return 0; + int cmp = <T>CMP(p(i), b.p(j)); + if (cmp == 0) + { + next(i); b.next(j); + } + else if (cmp < 0) + return 0; + else + b.next(j); + } +} + +int <T>OSLSet::operator == (<T>OSLSet& b) +{ + if (count != b.count) return 0; + if (count == 0) return 1; + Pix i = p.first(); + Pix j = b.p.first(); + while (i != 0) + { + if (!<T>EQ(p(i),b.p(j))) return 0; + next(i); + b.next(j); + } + return 1; +} + + +void <T>OSLSet::operator |= (<T>OSLSet& b) +{ + if (&b == this || b.count == 0) + return; + else + { + Pix j = b.p.first(); + Pix i = p.first(); + Pix trail = 0; + for (;;) + { + if (j == 0) + return; + else if (i == 0) + { + for (; j != 0; b.next(j)) + { + ++count; + p.append(b.p(j)); + } + return; + } + int cmp = <T>CMP(p(i), b.p(j)); + if (cmp <= 0) + { + if (cmp == 0) b.next(j); + trail = i; + next(i); + } + else + { + ++count; + if (trail == 0) + trail = p.prepend(b.p(j)); + else + trail = p.ins_after(trail, b.p(j)); + b.next(j); + } + } + } +} + + +void <T>OSLSet::operator -= (<T>OSLSet& b) +{ + if (&b == this) + clear(); + else if (count != 0 && b.count != 0) + { + Pix i = p.first(); + Pix j = b.p.first(); + Pix trail = 0; + for (;;) + { + if (j == 0 || i == 0) + return; + int cmp = <T>CMP(p(i), b.p(j)); + if (cmp == 0) + { + --count; + b.next(j); + if (trail == 0) + { + p.del_front(); + i = p.first(); + } + else + { + next(i); + p.del_after(trail); + } + } + else if (cmp < 0) + { + trail = i; + next(i); + } + else + b.next(j); + } + } +} + +void <T>OSLSet::operator &= (<T>OSLSet& b) +{ + if (b.count == 0) + clear(); + else if (&b != this && count != 0) + { + Pix i = p.first(); + Pix j = b.p.first(); + Pix trail = 0; + for (;;) + { + if (i == 0) + return; + else if (j == 0) + { + if (trail == 0) + { + p.clear(); + count = 0; + } + else + { + while (i != 0) + { + --count; + next(i); + p.del_after(trail); + } + } + return; + } + int cmp = <T>CMP(p(i), b.p(j)); + + if (cmp == 0) + { + trail = i; + next(i); + b.next(j); + } + else if (cmp < 0) + { + --count; + if (trail == 0) + { + p.del_front(); + i = p.first(); + } + else + { + next(i); + p.del_after(trail); + } + } + else + b.next(j); + } + } +} + + +int <T>OSLSet::OK() +{ + int v = p.OK(); + v &= count == p.length(); + Pix trail = p.first(); + if (trail == 0) + v &= count == 0; + else + { + Pix i = trail; next(i); + while (i != 0) + { + v &= <T>CMP(p(trail), p(i)) < 0; + trail = i; + next(i); + } + } + if (!v) error("invariant failure"); + return v; +} |