|
bag.c
Click here to get the file
Size
40.2 kB
-
File type
text/plain
File contents
/*ident "@(#)Set:incl/bag.c 3.1" */
/******************************************************************************
*
* C++ Standard Components, Release 3.0.
*
* Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc.
* Copyright (c) 1988, 1989, 1990 AT&T. All Rights Reserved.
*
* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System
* Laboratories, Inc. The copyright notice above does not evidence
* any actual or intended publication of such source code.
*
******************************************************************************/
#ifndef _BAG_C_
#define _BAG_C_
// T is the type parameter;
// H is the name of the hash function
// (Bag_zero should be used if the client does
// not supply its own function).
template <class T>
Bag_bucketiter_ATTLC<T>::~Bag_bucketiter_ATTLC()
{
if ( my_bag == 0 )
return;
if ( this == my_bag->iter_head ) {
// Case 1: iterator at head of chain
my_bag->iter_head = next_it;
}
else {
// Case 2: iterator in middle of chain
Bag_bucketiter_ATTLC<T>* x;
Bag_bucketiter_ATTLC<T>* an_it;
for ( an_it=my_bag->iter_head ;
(x = an_it->next_it) != this ; an_it = x );
an_it->next_it = next_it;
}
}
template <class T>
Bag_bucketiter_ATTLC<T>::Bag_bucketiter_ATTLC(const Bag<T>& b):
my_bag((Bag<T>*)&b),
next_it(b.iter_head)
{
((Bag<T>*)(&b))->iter_head = this;
}
template <class T>
Bag_bucketiter_ATTLC<T>::Bag_bucketiter_ATTLC(const Bag_bucketiter_ATTLC<T>& bi)
: my_bag(bi.my_bag),
next_it(my_bag->iter_head)
{
my_bag->iter_head = this;
}
template <class T>
Bag_bucketiter_ATTLC<T>&
Bag_bucketiter_ATTLC<T>::operator=(const Bag_bucketiter_ATTLC<T>& bi)
{
if (this == my_bag->iter_head) {
my_bag->iter_head = next_it;
} else {
Bag_bucketiter_ATTLC<T>* p = my_bag->iter_head;
while (p->next_it != this) {
p = p->next_it;
}
p->next_it = next_it;
}
my_bag = bi.my_bag;
next_it = my_bag->iter_head;
my_bag->iter_head = this;
return *this;
}
// first() and next() are similar to Shopiro's
// original pset iterator functions first() and
// next(); they walk the leaves of the tree,
// returning Bag_bucket_ATTLC<T>)*.
template <class T>
const Bag_bucket_ATTLC<T>*
Bag_bucketiter_ATTLC<T>::first()
{
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp;
if ( my_bag == 0 )
return 0;
pos.curr_depth = -1;
if ( my_bag->contents.is_null() )
return 0;
if ( my_bag->contents.is_leaf() ) {
// 'contents' is a Bag_bucket_ATTLC<T>*
bp = (Bag_bucket_ATTLC<T>*)my_bag->contents.external_leaf();
}
else {
// 'contents' is a Bag_internal_node_ATTLC*. Search the
// subtree rooted at this node looking for the
// leftmost leaf.
nodep = my_bag->contents.next_node();
for ( ; ; ) {
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
// Scan this Bag_internal_node_ATTLC from left to right
// looking for a non-null Bag_internal_item_ATTLC
for ( itemp = &nodep->item[0];;itemp++ ) {
#ifdef DEBUG_ATTLC
assert(itemp < &nodep->item[BAG_NODE_SIZE_ATTLC]);
#endif
if ( !itemp->is_null() )
break;
}
pos.curr_pos[++pos.curr_depth] = itemp;
// If this Bag_internal_item_ATTLC is a leaf, the search
// is over; otherwise, iteratively 'recurse'
if ( itemp->is_leaf() )
break;
nodep = itemp->next_node();
}
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
}
// bp now points to a Bag_bucket_ATTLC<T>
pos.curr_value = bp->hashval;
return bp;
}
template <class T>
const Bag_bucket_ATTLC<T>*
Bag_bucketiter_ATTLC<T>::next()
{
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp;
if ( my_bag == 0 )
return 0;
// Search the index for pos.curr_value. Since
// pos caches the result of the last iterator
// access, the loop should exit almost immediately,
// unless Bag mutation has occurred since the last
// access.
if ( pos.curr_depth == -1 )
itemp = &my_bag->contents;
else
itemp = pos.curr_pos[pos.curr_depth];
int unshift = BAG_INITIAL_SHIFT_ATTLC + BAG_SHIFT_INCR_ATTLC +
pos.curr_depth * BAG_SHIFT_INCR_ATTLC;
long mask = BAG_MASK_BITS_ATTLC << unshift;
nodep = 0;
for ( ; ; mask <<= BAG_SHIFT_INCR_ATTLC, unshift += BAG_SHIFT_INCR_ATTLC ) {
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
if ( itemp->is_null() )
break;
else if ( itemp->is_leaf() ) {
// While searching for current_value, we have found
// a leaf. This may or may not be the leaf containing
// the current value, depending on whether the
// Bag_bucket containing the current value has been
// deleted or not.
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
Set_or_Bag_hashval hval = bp->hashval;
if ( hval == pos.curr_value || BAG_LT_ATTLC(hval,pos.curr_value) ) {
// Case 1: we either (a) found the current value or
// (b) passed it (it must have been deleted).
break;
}
else {
// The leaf points to a Bag_bucket containing a hash
// value GREATER THAN the current value, so the
// current value must have been deleted. The
// Bag_bucket pointed to is, by definition, the "next"
// Bag_bucket, the one we arelooking for.
pos.curr_value = hval;
return bp;
}
}
else {
// Node: search subindex
nodep = itemp->next_node();
#ifdef DEBUG_ATTLC
assert(nodep);
#endif
pos.curr_pos[++pos.curr_depth] = itemp =
&nodep->item[(((unsigned long)pos.curr_value) & mask) >> unshift];
}
}
// pos.curr_pos is now up-to-date and we are ready
// to locate the NEXT Bag_bucket_ATTLC<T> starting from
// here.
if ( pos.curr_depth == -1 ) {
// There was only one hash Bag_bucket; the iteration
// is therefore terminated.
return 0;
}
// Find the next Bag_bucket_ATTLC<T>
if ( nodep == 0 ) {
if ( pos.curr_depth == 0 )
nodep = my_bag->contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
}
for ( ; ; ) {
#ifdef DEBUG_ATTLC
assert(&nodep->item[0] <= itemp && itemp < &nodep->item[BAG_NODE_SIZE_ATTLC]);
#endif
// Scan rightward within this node, looking for a
// non-null item
while ( itemp < &nodep->item[BAG_NODE_SIZE_ATTLC-1] )
if ( !(++itemp)->is_null() )
goto found;
// Scan reached end of node without finding anything;
// pop up one level in order to continue the walk
if ( pos.curr_depth-- == 0 ) {
// The Bag is exhausted, so the iteration is terminated
return 0;
}
itemp = pos.curr_pos[pos.curr_depth];
if ( pos.curr_depth == 0 )
nodep = my_bag->contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
}
found:
// itemp now points either to the leaf we're looking
// for or the root of a subtree containing the leaf.
pos.curr_pos[pos.curr_depth] = itemp;
while ( !itemp->is_leaf() ) {
#ifdef DEBUG_ATTLC
assert(itemp->is_node());
#endif
nodep = itemp->next_node();
// Scan to right within this node
for ( itemp = &nodep->item[0];;itemp++ ) {
#ifdef DEBUG_ATTLC
assert(itemp < &nodep->item[BAG_NODE_SIZE_ATTLC]);
#endif
if ( !itemp->is_null() )
break;
}
pos.curr_pos[++pos.curr_depth] = itemp;
}
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
pos.curr_value = bp->hashval;
return bp;
}
template <class T>
const Bag_pair<T>*
Bagiter<T>::first()
{
// This version has been simplified by using
// Bag_bucketiter::first()
const Bag_bucket_ATTLC<T>* bp = ((Bag_bucketiter_ATTLC<T>*)this)->first();
if ( bp == 0 )
return 0;
delete itp;
itp=new Listiter< Bag_pair<T> >(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* result;
itp->next(result);
// Cast the pointer to const so the client can't
// modify the element
return (const Bag_pair<T>*)result;
}
template <class T>
const Bag_pair<T>*
Bagiter<T>::next()
{
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp;
Bag_pair<T>* result;
// TBD_see if this code can be simplified by using
// Bag_bucketiter_ATTLC<T>::next()
#ifdef DEBUG_ATTLC
assert(my_bag);
#endif
// New List-style iterator has next() as only public
// member function; first() is private and called
// internally only if this is the first call to next(),
// i.e., only if inited=0.
if ( inited==0 ) {
const Bag_pair<T>* tp = first();
if ( tp ) inited=1;
return tp;
}
// Search the index for the pos.curr_value. Since
// pos normally caches the results of the
// most recent iterator access, the loop should
// exit almost immediately.
if ( pos.curr_depth == -1)
itemp = &my_bag->contents;
else
itemp = pos.curr_pos[pos.curr_depth];
int unshift = BAG_INITIAL_SHIFT_ATTLC + BAG_SHIFT_INCR_ATTLC +
pos.curr_depth * BAG_SHIFT_INCR_ATTLC;
long mask = BAG_MASK_BITS_ATTLC << unshift;
nodep = 0;
for ( ; ; mask <<= BAG_SHIFT_INCR_ATTLC, unshift += BAG_SHIFT_INCR_ATTLC ) {
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
if ( itemp->is_null() )
break;
else if ( itemp->is_leaf() ) {
// While searching for current_value, we have found
// a leaf. This may or may not be the leaf containing
// the current value, depending on whether the
// Bag_bucket containing the current value has been
// deleted or not.
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
Set_or_Bag_hashval hval = bp->hashval;
if ( hval == pos.curr_value || BAG_LT_ATTLC(hval,pos.curr_value) ) {
// Case 1: we either (a) found the current value or
// (b) passed it (it must have been deleted)
break;
}
else {
// The leaf we have found points to a Bag_bucket
// containing a next GREATER THAN the current value
// (the current value must have been deleted).
pos.curr_value = hval;
delete itp;
itp = new Listiter< Bag_pair<T> >(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
itp->next(result);
return (const Bag_pair<T>*)result;
}
}
else {
// Node: search subindex
nodep = itemp->next_node();
#ifdef DEBUG_ATTLC
assert(nodep);
#endif
pos.curr_pos[++pos.curr_depth] = itemp =
&nodep->item[(((unsigned long)pos.curr_value) & mask) >> unshift];
}
}
// curr_pos is now up-to-date and we are ready
// to locate the next value starting from here.
if ( pos.curr_depth == -1 ) {
// There is only one Bag_bucket; if we have not not
// yet returned all Bag_pairs on the collision list,
// return the next one; otherwise, the iteration
// is terminated
//
// TBD_note: It is possible that Bag mutation occurred
// that (1) deleted all the elements in a List and then
// (2) re-created a List with the same hash value. In
// this case, *itp refers to a non-existeng List. We
// must guard against this case by using Listiter::the_list.
if ( !itp->the_list() )
return 0;
else {
if ( itp->at_end() )
return 0;
else {
itp->next(result);
return (const Bag_pair<T>*)result;
}
}
}
// There are multiple Bag_buckets.
if ( itemp->is_leaf() &&
((Bag_bucket_ATTLC<T>*)itemp->external_leaf())->hashval== pos.curr_value )
{
// See if there are more elements in this bucket
if ( itp->the_list() ) {
if ( !itp->at_end() ) {
// Move on to the next element
itp->next(result);
return (const Bag_pair<T>*)result;
}
}
}
// Find the next leaf.
// TBD_can we use Bag_bucketiter_ATTLC<T>::next() here?
if ( nodep == 0 ) {
if ( pos.curr_depth == 0 )
nodep = my_bag->contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
}
for ( ; ; ) {
#ifdef DEBUG_ATTLC
assert(&nodep->item[0] <= itemp && itemp < &nodep->item[BAG_NODE_SIZE_ATTLC]);
#endif
// Scan rightward within this node, looking for a
// non-null item
while ( itemp < &nodep->item[BAG_NODE_SIZE_ATTLC-1] ) {
if ( !(++itemp)->is_null() )
goto found;
}
// Scan reached end of node without finding anything;
// pop up one level in order to continue the walk
if ( pos.curr_depth-- == 0 ) {
// The Bag is exhausted, so the iteration is terminated
return 0;
}
itemp = pos.curr_pos[pos.curr_depth];
if ( pos.curr_depth == 0 )
nodep = my_bag->contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
}
found:
// itemp now points either to the leaf we're looking
// for or the root of a subindex containing the leaf.
pos.curr_pos[pos.curr_depth] = itemp;
while ( !itemp->is_leaf() ) {
#ifdef DEBUG_ATTLC
assert(itemp->is_node());
#endif
nodep = itemp->next_node();
// Scan to right within this node
for (itemp = &nodep->item[0];;itemp++ ) {
#ifdef DEBUG_ATTLC
assert(itemp < &nodep->item[BAG_NODE_SIZE_ATTLC]);
#endif
if ( !itemp->is_null() )
break;
}
pos.curr_pos[++pos.curr_depth] = itemp;
}
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
pos.curr_value = bp->hashval;
delete itp;
itp = new Listiter< Bag_pair<T> >(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
itp->next(result);
return (const Bag_pair<T>*)result;
}
template <class T>
Bag<T>::Bag() : sze(0),sze_unique(0),iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
}
template <class T>
Bag<T>::Bag(const T& t0) : sze(0),sze_unique(0),iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
insert(t0);
}
template <class T>
Bag<T>::Bag(const T& t0, const T& t1):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
insert(t0);
insert(t1);
}
template <class T>
Bag<T>::Bag(const T& t0, const T& t1, const T& t2):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
insert(t0);
insert(t1);
insert(t2);
}
template <class T>
Bag<T>::Bag(const T& t0, const T& t1, const T& t2, const T& t3):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
insert(t0);
insert(t1);
insert(t2);
insert(t3);
}
template <class T>
Bag<T>::Bag(const Bag<T>& a, const Bag<T>& b, Bag_union_ATTLC*):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
make_setlogic(a,b,1);
}
template <class T>
Bag<T>::Bag(const Bag<T>& a, const Bag<T>& b, Bag_inter_ATTLC*):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
make_setlogic(a,b,0);
}
template <class T>
Bag<T>::Bag(const Bag<T>& a, const Bag<T>& b, Bag_diff_ATTLC*):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
make_setlogic(a,b,2);
}
template <class T>
Bag<T>::Bag(const Bag<T>& a, const Bag<T>& b, Bag_xor_ATTLC*):
sze(0),
sze_unique(0),
iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
make_setlogic(a,b,3);
}
template <class T>
Bag<T>&
Bag<T>::operator=(const Bag<T>& b)
{
if ( this != &b ) {
remove_all();
Bag_bucketiter_ATTLC<T> bi(b);
const Bag_bucket_ATTLC<T>* bp = bi.first();
while ( bp ) {
Listiter< Bag_pair<T> > li(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !li.at_end() ) {
Bag_pair<T>* tp;
li.next(tp);
insert(tp->value,tp->count);
}
bp = bi.next();
}
}
return *this;
}
template <class T>
int
Bag<T>::containment(const Bag<T>& b, int comp_type) const
{
switch(comp_type) {
case 0: // bag equality
if ( size() != b.size() )
return 0;
break;
case 1: // subset
if ( size() > b.size() )
return 0;
break;
case 2: // proper subset
if ( size() >= b.size() )
return 0;
break;
}
Bag_bucketiter_ATTLC<T> a_it(*this);
Bag_bucketiter_ATTLC<T> b_it(b);
const Bag_bucket_ATTLC<T>* ap = a_it.first();
const Bag_bucket_ATTLC<T>* bp = b_it.first();
while ( ap && bp ) {
if ( ap->hashval == bp->hashval ) {
// Make sure ap->collision_list is a subset of
// bp->collision_list
if ( ap->collision_list.length() > bp->collision_list.length() )
return 0;
Listiter< Bag_pair<T> > lia(((Bag_bucket_ATTLC<T>*)ap)->collision_list);
Listiter< Bag_pair<T> > lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !lia.at_end() ) {
Bag_pair<T>* atp;
lia.next(atp);
lib.reset();
int ok=0;
while ( !lib.at_end() ) {
Bag_pair<T>* btp;
lib.next(btp);
if ( atp->value == btp->value && atp->count <= btp->count ) {
ok=1;
break;
}
}
if ( !ok )
return 0;
}
ap = a_it.next();
bp = b_it.next();
}
else if ( BAG_LT_ATTLC(ap->hashval,bp->hashval) ) {
// *ap contains values that can't be in b, since we've
// already passed the point where they would be found;
// return failure
return 0;
}
else {
// *ap contains values that may be in a future
// Bag_bucket of b; increment b_it
bp = b_it.next();
}
}
// The relation is true only if a_it is exhasted
return ap==0;
}
template <class T>
const Bag_pair<T>*
Bag<T>::insert(const T& value, int count)
{
if ( count<=0 )
return 0;
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp;
Bag_pair<T>* result;
// Hash the value
Set_or_Bag_hashval hval = hash(value);
// See how much of hval matches pos.curr_value
// (equivalently, see how much of pos is valid.)
// This will determine where we start looking for the
// insertion point. This is an optimization that takes
// advantage of the phenomenon that many operations
// create a Bag by walking an existing index and
// inserting its elements into the new Bag.
long mask = BAG_MASK_BITS_ATTLC << BAG_INITIAL_SHIFT_ATTLC;
int depth;
for ( depth = -1 ; depth < pos.curr_depth ;
depth++, mask <<= BAG_SHIFT_INCR_ATTLC ) {
if ( (pos.curr_value & mask) != (hval & mask) )
break;
}
// If depth = -1, no bits match;
// if depth = 0, bits 0..3 match, etc.
register int unshift = BAG_INITIAL_SHIFT_ATTLC + BAG_SHIFT_INCR_ATTLC +
depth * BAG_SHIFT_INCR_ATTLC;
if ( depth == -1 )
itemp = &contents;
else
itemp = pos.curr_pos[depth];
// Clobber all the active iterators
warn_iterators();
// Find the insertion point
pos.curr_value = hval;
nodep = 0;
for ( pos.curr_depth = depth ; ;
mask <<= BAG_SHIFT_INCR_ATTLC, unshift += BAG_SHIFT_INCR_ATTLC )
{
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
if ( itemp->is_null() )
break;
else if ( itemp->is_leaf() ) {
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
if ( bp->hashval == hval ) {
// The 'value' goes in this Bag_bucket
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
while ( it.next(tp) ) {
if ( tp->value == value ) {
sze += count;
tp->count += count;
return tp;
}
}
// The value is not already in the Bag_bucket;
// insert it
sze_unique+=1;
sze += count;
Bag_pair<T> pair1;
pair1.value = value;
pair1.count = count;
it.insert_next(pair1);
it.peek_next(result);
return result;
}
else {
// This Bag_bucket is not the one where the value
// belongs; a subindex will have to be created
// containing both this Bag_bucket and a new one
// created to hold 'value.'
break;
}
}
else {
// Node: search subindex
nodep = itemp->next_node();
#ifdef DEBUG_ATTLC
assert(nodep);
#endif
pos.curr_pos[++pos.curr_depth] = itemp = &nodep->item[(hval & mask) >> unshift];
}
}
// ASSERT: itemp is either null or is a leaf that must
// be moved down into a subindex containing BOTH the
// existing leaf and a new leaf pointing to a new
// Bag_bucket containing 'value.' In either case, the
// cardinality of the Bag is increased by 'count'.
sze_unique += 1;
sze += count;
if ( itemp->is_null() ) {
// Make this null slot into a leaf pointing to a new
// Bag_bucket containing 'value'
itemp->make_leaf( new Bag_bucket_ATTLC<T> );
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
bp->hashval = hval;
Bag_pair<T> pair2;
pair2.value = value;
pair2.count = count;
// bp->collision_list.insert_next(pair2);
// bp->collision_list.peek_next(result);
Listiter< Bag_pair<T> > cit(bp->collision_list);
cit.insert_next(pair2);
cit.peek_next(result);
if ( pos.curr_depth > 0 )
pos.curr_pos[pos.curr_depth-1]->next_node()->busy_count++;
else if ( pos.curr_depth == 0 )
contents.next_node()->busy_count++;
return result;
}
else {
#ifdef DEBUG_ATTLC
assert(itemp->is_leaf());
#endif
// Replace this leaf by a subindex containing both the
// original leaf and a new leaf pointing to a new
// Bag_bucket containing 'value'
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
Set_or_Bag_hashval temp = bp->hashval;
int ind1,ind2;
for ( ; ; mask <<= BAG_SHIFT_INCR_ATTLC, unshift += BAG_SHIFT_INCR_ATTLC )
{
itemp->make_node(nodep = new Bag_internal_node_ATTLC);
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
ind1 = int(((unsigned long)temp & mask) >> unshift);
ind2 = int((hval & mask) >> unshift);
if ( ind1 != ind2 )
// Serendipitous case
break;
nodep->busy_count = 1;
itemp = &nodep->item[ind1];
pos.curr_pos[++pos.curr_depth] = itemp;
}
// Move the existing leaf down into the subindex
nodep->item[ind1].make_leaf(bp);
// Make a new leaf and Bag_bucket for 'value'
itemp = &nodep->item[ind2];
itemp->make_leaf( new Bag_bucket_ATTLC<T> );
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
bp->hashval = hval;
Bag_pair<T> pair;
pair.value = value;
pair.count = count;
// bp->collision_list.insert_next(pair);
// bp->collision_list.peek_next(result);
Listiter< Bag_pair<T> > bit(bp->collision_list);
bit.insert_next(pair);
bit.peek_next(result);
pos.curr_pos[++pos.curr_depth] = itemp;
nodep->busy_count = 2;
return result;
}
}
template <class T>
unsigned int
Bag<T>::remove(const T& value, int count)
{
if ( count<=0 )
return 0;
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp=0;
unsigned int result;
// Hash the value
Set_or_Bag_hashval hval = hash(value);
// See how much of hval matches pos.curr_value
// (equivalently, see how much of pos is valid.)
// This will determine where we start looking for the
// deletion point. This is an optimization that takes
// advantage of the phenomenon that many operations
// create a Bag by walking an existing index and
// inserting its elements into the new Bag.
long mask = BAG_MASK_BITS_ATTLC << BAG_INITIAL_SHIFT_ATTLC;
int depth;
for ( depth = -1 ; depth < pos.curr_depth ;
depth++, mask <<= BAG_SHIFT_INCR_ATTLC ) {
if ( (pos.curr_value & mask) != (hval & mask) )
break;
}
// If depth = -1, no bits match;
// If depth = 0, bits 0...3 match, etc.
register int unshift = BAG_INITIAL_SHIFT_ATTLC + BAG_SHIFT_INCR_ATTLC +
depth * BAG_SHIFT_INCR_ATTLC;
if ( depth == -1 )
itemp = &contents;
else
itemp = pos.curr_pos[depth];
nodep = 0;
pos.curr_value = hval;
warn_iterators();
// Find the leaf pointing to the Bag_bucket containing
// the value to be deleted.
for ( pos.curr_depth = depth ; ; mask <<= BAG_SHIFT_INCR_ATTLC,
unshift += BAG_SHIFT_INCR_ATTLC ) {
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
if ( itemp->is_null() ) {
// The value must have been deleted already.
// Return failure.
return 0;
}
if ( itemp->is_leaf() ) {
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
if ( bp->hashval == hval )
// The value may be in the Bag_bucket pointed to by
// this leaf.
break;
else
// The leaf must have been deleted and subsequently
// replaced by a different Bag_bucket (one with a
// different hash value). Return failure.
return 0;
}
else {
// Node: search subindex
nodep = itemp->next_node();
#ifdef DEBUG_ATTLC
assert(nodep);
#endif
pos.curr_pos[++pos.curr_depth] = itemp =
&nodep->item[(pos.curr_value & mask)>>unshift];
}
}
#ifdef DEBUG_ATTLC
assert(bp && bp->hashval==hval);
#endif
// We found the Bag_bucket; locate the value in the
// collision list and remove it
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
int found=0;
while ( it.next(tp) ) {
if ( tp->value == value ) {
found=1;
if ( tp->count > count ) {
result = count;
tp->count -= result;
}
else {
sze_unique -= 1;
result = tp->count;
it.remove_prev();
}
sze -= result;
break;
}
}
if ( !found )
// The value was not found; return failure
return 0;
// The value was found and deleted. We must now
// worry about the Bag_bucket becoming empty.
if ( bp->collision_list.length() > 0 )
// The collision list still has one or more elements.
return result;
// The collision list has become empty as a result of
// this deletion; we must delete the Bag_bucket and
// fix up the index accordingly.
if ( pos.curr_depth == -1 ) {
// Contents was a leaf and its Bucket now contains
// an empty list; the Bag is now empty
#ifdef DEBUG_ATTLC
assert(sze == 0);
#endif
delete bp;
itemp->make_null();
return result;
}
// Nodep is the pointer to the node containing
// this leaf (it will be zero if the cache was
// up-to-date when we entered this function
if ( nodep == 0 ) {
if ( pos.curr_depth == 0 )
nodep = contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
}
if ( --(nodep->busy_count) > 1 )
{
// Easy case: node still has at least one leaf left
delete bp;
itemp->make_null();
return result;
}
// Hard case: node has only one leaf in it; must
// collapse node into a leaf
#ifdef DEBUG_ATTLC
assert(nodep->busy_count == 1);
#endif
// Scan for a non-null item
Bag_internal_item_ATTLC* itp;
for ( itp = &nodep->item[0] ;
itp < &nodep->item[BAG_NODE_SIZE_ATTLC] ; itp++ ) {
if ( itp != itemp && !itp->is_null() )
break;
}
if ( !itp->is_leaf() ) {
// Complicated case: punt (we won't try to absorb
// a node)
delete bp;
itemp->make_null();
return result;
}
Bag_bucket_ATTLC<T>* temp = (Bag_bucket_ATTLC<T>*)itp->external_leaf();
delete bp;
for ( ;; ) {
delete nodep;
if ( pos.curr_depth-- == 0 ) {
contents.make_leaf(temp);
break;
}
if ( pos.curr_depth == 0 )
nodep = contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth-1]->next_node();
if ( nodep->busy_count > 1 ) {
pos.curr_pos[pos.curr_depth]->make_leaf(temp);
break;
}
#ifdef DEBUG_ATTLC
assert(nodep->busy_count == 1);
#endif
}
return result;
}
template <class T>
unsigned int
Bag<T>::remove_all(const T& value)
{
return remove(value,count(value));
}
template <class T>
unsigned int
Bag<T>::remove_all()
{
unsigned int result = sze;
warn_iterators();
Bag_internal_item_ATTLC* itemp = &contents;
if ( itemp->is_null() ) {
#ifdef DEBUG_ATTLC
assert(sze == 0);
assert(sze_unique == 0);
#endif
return result;
}
if ( itemp->is_leaf() ) {
#ifdef DEBUG_ATTLC
assert(sze >= 1);
assert(sze_unique >= 1);
#endif
// We must destroy the bucket
Bag_bucket_ATTLC<T>* bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
delete bp;
itemp->make_null();
pos.curr_depth = -1;
sze = 0;
sze_unique = 0;
return result;
}
Bag_internal_node_ATTLC* nodep = itemp->next_node();
itemp = &nodep->item[0];
pos.curr_depth = -1;
for ( ; ; ) {
Bag_internal_item_ATTLC* stopper = (&nodep->item[BAG_NODE_SIZE_ATTLC]);
for ( ; itemp < stopper ; /* itemp++ */ )
{
if ( itemp->is_node() ) {
pos.curr_pos[++pos.curr_depth] = itemp;
nodep = itemp->next_node();
itemp = &nodep->item[0];
stopper = &nodep->item[BAG_NODE_SIZE_ATTLC];
}
else itemp++;
}
// Unlike Set_of_p, we must destroy the buckets
// pointed to by this node
for ( itemp = &nodep->item[0] ; itemp < &nodep->item[BAG_NODE_SIZE_ATTLC] ; itemp++ )
{
if ( itemp->is_leaf() ) {
Bag_bucket_ATTLC<T>* bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
delete bp;
itemp->make_null();
}
}
delete nodep;
if ( pos.curr_depth < 0 )
break;
itemp = pos.curr_pos[pos.curr_depth--] + 1;
if ( pos.curr_depth < 0 )
nodep = contents.next_node();
else
nodep = pos.curr_pos[pos.curr_depth]->next_node();
}
pos.curr_depth = -1;
contents.make_null();
sze = 0;
sze_unique = 0;
return result;
}
template <class T>
const Bag_pair<T>*
Bag<T>::select() const
{
Bag_bucketiter_ATTLC<T> bi(*this);
const Bag_bucket_ATTLC<T>* bp = bi.first();
if ( !bp )
{
return 0;
}
Listiter< Bag_pair<T> > li(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* result;
li.next(result);
return result;
}
template <class T>
const Bag_pair<T>*
Bag<T>::contains(const T& value) const
{
Bag_internal_item_ATTLC* itemp;
Bag_internal_node_ATTLC* nodep;
Bag_bucket_ATTLC<T>* bp;
// Hash the value
Set_or_Bag_hashval hval = hash(value);
// See how much of pos is still good
long mask = BAG_MASK_BITS_ATTLC << BAG_INITIAL_SHIFT_ATTLC;
int depth;
for ( depth = -1 ; depth < pos.curr_depth ; depth++, mask <<= BAG_SHIFT_INCR_ATTLC )
{
if ( (pos.curr_value & mask) != (hval & mask) )
break;
}
register int unshift = BAG_INITIAL_SHIFT_ATTLC + BAG_SHIFT_INCR_ATTLC +
depth * BAG_SHIFT_INCR_ATTLC;
if ( depth == -1 )
itemp = &(((Bag<T> *)this)->contents);
else
itemp = pos.curr_pos[depth];
nodep = 0;
((Bag_position_ATTLC *) &((Bag<T>*)this)->pos)->curr_value = hval;
for ( ((Bag_position_ATTLC *) &((Bag<T>*)this)->pos)->curr_depth = depth ; ;
mask <<= BAG_SHIFT_INCR_ATTLC, unshift += BAG_SHIFT_INCR_ATTLC )
{
#ifdef DEBUG_ATTLC
assert(pos.curr_depth < BAG_POSITIONS_ATTLC);
#endif
if ( itemp->is_null() )
return 0;
if ( itemp->is_leaf() ) {
// Search the the collision list
bp = (Bag_bucket_ATTLC<T>*)itemp->external_leaf();
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
while ( it.next(tp) )
if ( tp->value == value )
return tp;
return 0;
}
else {
nodep = itemp->next_node();
#ifdef DEBUG_ATTLC
assert(nodep);
#endif
((Bag_position_ATTLC *) &((Bag<T>*)this)->pos)->curr_pos[++((Bag_position_ATTLC *) &((Bag<T>*)this)->pos)->curr_depth] = itemp =
&nodep->item[(pos.curr_value & mask) >> unshift];
}
}
}
template <class T>
unsigned int
Bag<T>::count(const T& value) const
{
// New version uses latest version of contains
const Bag_pair<T>* tp = contains(value);
if ( tp )
return tp->count;
else
return 0;
}
template <class T>
Bag<T>&
Bag<T>::operator|=(const Bag<T>& b)
{
if ( this != &b ) {
Bag_bucketiter_ATTLC<T> bi(b);
const Bag_bucket_ATTLC<T>* bp = bi.first();
while ( bp ) {
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
while ( it.next(tp) )
insert(tp->value,tp->count);
bp = bi.next();
}
}
else {
// Union with self: double all counts
Bag_bucketiter_ATTLC<T> bi(*this);
const Bag_bucket_ATTLC<T>* bp = bi.first();
while ( bp ) {
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
while ( it.next(tp) )
tp->count *= 2;
bp = bi.next();
}
}
return *this;
}
template <class T>
Bag<T>&
Bag<T>::operator-=(const Bag<T>& b)
{
if ( this != &b ) {
Bag_bucketiter_ATTLC<T> bi(b);
const Bag_bucket_ATTLC<T>* bp = bi.first();
while ( bp ) {
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
Bag_pair<T>* tp;
while ( it.next(tp) ) {
remove(tp->value,tp->count);
}
bp = bi.next();
}
}
else
remove_all();
return *this;
}
template <class T>
Bag<T>&
Bag<T>::operator&=(const Bag<T>& b)
{
if ( this != &b ) {
Bag_bucketiter_ATTLC<T> ai(*this);
const Bag_bucket_ATTLC<T>* ap = ai.first();
while ( ap ) {
Listiter< Bag_pair<T> > it(((Bag_bucket_ATTLC<T>*)ap)->collision_list);
Bag_pair<T>* tp;
while ( it.the_list() && it.next(tp) ) {
// remove may delete the bucket; beware of dangling
// list iterator.
int my_count = tp->count;
#ifdef DEBUG_ATTLC
assert(my_count>0);
#endif
int b_count = b.count(tp->value);
int retain;
if ( my_count < b_count )
retain = my_count;
else
retain = b_count;
int subtract = my_count - retain;
if ( subtract > 0 )
(void)remove(tp->value,subtract);
}
ap = ai.next();
}
}
return *this;
}
template <class T>
Bag<T>&
Bag<T>::operator^=(const Bag<T>& b)
{
if ( this != &b ) {
Bag_bucketiter_ATTLC<T> a_it(*this);
Bag_bucketiter_ATTLC<T> b_it(b);
const Bag_bucket_ATTLC<T>* ap = a_it.first();
const Bag_bucket_ATTLC<T>* bp = b_it.first();
while ( ap && bp ) {
if ( ap->hashval == bp->hashval ) {
// The two hash values are equal; this means the two
// collision lists may contain equal values (which must
// be weeded out)
Listiter< Bag_pair<T> >
lia(((Bag_bucket_ATTLC<T>*)ap)->collision_list);
Listiter< Bag_pair<T> >
lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
lib.reset();
while ( !lib.at_end() ) {
Bag_pair<T>* btp;
Bag_pair<T>* atp;
lib.next(btp);
int found=0;
// Guard against the case where removing from this list
// causes the list to disappear
if ( lia.the_list() ) {
lia.reset();
while ( !lia.at_end() ) {
lia.next(atp);
if ( atp->value == btp->value ) {
found=1;
break;
}
}
}
if ( found ) {
int a_count = atp->count;
int b_count = btp->count;
int new_a_count = a_count - b_count;
if ( new_a_count<0 )
new_a_count = - new_a_count;
if ( new_a_count < a_count )
remove(atp->value, a_count - new_a_count);
else {
// new_a_count >= a_count
insert(atp->value, new_a_count - a_count);
}
}
else
insert(btp->value,btp->count);
}
ap = a_it.next();
bp = b_it.next();
}
else if ( BAG_LT_ATTLC(ap->hashval, bp->hashval) ) {
ap = a_it.next();
}
else {
Listiter< Bag_pair<T> >
lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !lib.at_end() ) {
Bag_pair<T>* btp;
lib.next(btp);
insert(btp->value,btp->count);
}
bp = b_it.next();
}
}
while ( bp ) {
Listiter< Bag_pair<T> >
lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !lib.at_end() ) {
Bag_pair<T>* btp;
lib.next(btp);
insert(btp->value,btp->count);
}
bp = b_it.next();
}
}
else {
remove_all();
}
return *this;
}
template <class T>
void
Bag<T>::warn_iterators() const
{
Bag_bucketiter_ATTLC<T>* it;
for ( it = iter_head;it;it = it->next_it )
it->clobber();
}
template <class T>
void
Bag<T>::histogram(Map<Set_or_Bag_hashval,unsigned>& m) const
{
// Iterate over Bag_buckets, creating a Map from
// bp->hashval to bp->collision_list.length().
Bag_bucketiter_ATTLC<T> bi(*this);
const Bag_bucket_ATTLC<T>* bp = bi.first();
m = Map<Set_or_Bag_hashval,unsigned>();
while ( bp ) {
m[bp->hashval] = bp->collision_list.length();
bp = bi.next();
}
}
template <class T>
void
Bag<T>::check() const
{
Bag_bucketiter_ATTLC<T> bi(*this);
const Bag_bucket_ATTLC<T>* bp = bi.first();
#ifdef DEBUG_ATTLC
Set_or_Bag_hashval oldhashval=0;
#endif
int first=1;
while ( bp ) {
// Bag_buckets must be stored in increasing order of
// hash value
if ( first )
first=0;
else {
#ifdef DEBUG_ATTLC
assert(BAG_LT_ATTLC(oldhashval,bp->hashval));
#endif
}
#ifdef DEBUG_ATTLC
oldhashval = bp->hashval;
#endif
// Collision lists may not be empty
#ifdef DEBUG_ATTLC
assert(bp->collision_list.length()>0);
#endif
// Collision lists may not contain duplicates and
// counts must be greater than or equal to 1
Listiter< Bag_pair<T> > it1(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !it1.at_end() ) {
Bag_pair<T>* p1;
it1.next(p1);
#ifdef DEBUG_ATTLC
assert(p1->count>=1);
#endif
Listiter< Bag_pair<T> > it2(it1);
while ( !it2.at_end() ) {
Bag_pair<T>* p2;
it2.next(p2);
#ifdef DEBUG_ATTLC
assert(!(p1->value == p2->value));
#endif
}
}
bp = bi.next();
}
}
template <class T>
Bag<T>::~Bag()
{
// TBD_study this
/*
for ( Bag_bucketiter_ATTLC<T>* it = iter_head;it;it = it->next_it ) {
// Break const
Bag<T>// cheat = (Bag<T>//)&it->my_bag;
*cheat = 0;
}
*/
remove_all();
}
template <class T>
Bag<T>::Bag(const Bag<T>& b): sze(0),sze_unique(0),iter_head(0)
{
pos.curr_depth = -1;
contents.make_null();
Bag_bucketiter_ATTLC<T> bi(b);
const Bag_bucket_ATTLC<T>* bp = bi.first();
while ( bp ) {
Listiter< Bag_pair<T> > li(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !li.at_end() ) {
Bag_pair<T>* tp;
li.next(tp);
insert(tp->value,tp->count);
}
bp = bi.next();
}
}
template <class T>
void
Bag<T>::make_setlogic(const Bag<T>& a,const Bag<T>& b, int l_type)
{
// l_type = 0 (intersection), 1 (union), 2 (set difference), 3 (xor)
#ifdef DEBUG_ATTLC
assert(sze == 0);
#endif
Bag_bucketiter_ATTLC<T> a_it(a), b_it(b);
const Bag_bucket_ATTLC<T>* ap = a_it.first(), *bp = b_it.first();
Bag_pair<T> *atp, *btp;
while ( ap && bp ) {
Listiter< Bag_pair<T> > lia(((Bag_bucket_ATTLC<T>*)ap)->collision_list);
Listiter< Bag_pair<T> > lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
if ( ap->hashval == bp->hashval ) {
// insert all of the necessary items from B
if ( l_type == 1 ) {
while ( !lib.at_end() ) {
lib.next(btp);
insert(btp->value,btp->count);
}
}
else if ( l_type == 3 ) {
while ( !lib.at_end() ) {
lib.next(btp);
lia.reset();
int fcount=btp->count;
while ( !lia.at_end() ) {
lia.next(atp);
if ( atp->value == btp->value ) {
fcount=atp->count - btp->count;
if ( fcount < 0 )
fcount = -fcount;
break;
}
}
if ( fcount )
insert(btp->value,fcount);
}
}
// insert all of the necessary items from A
lia.reset();
while ( !lia.at_end() ) {
lia.next(atp);
if (l_type == 1 )
insert(atp->value,atp->count);
else {
lib.reset();
int fcount;
if ( l_type == 0 )
fcount = 0;
else
fcount = atp->count;
while ( !lib.at_end() ) {
lib.next(btp);
if ( atp->value == btp->value ) {
switch(l_type) {
case 0:
fcount=atp->count;
if ( fcount>btp->count )
fcount=btp->count;
break;
case 2:
fcount=atp->count-btp->count;
break;
case 3:
fcount=0;
}
break;
}
}
if (fcount>0 )
insert(atp->value,fcount);
}
}
ap = a_it.next();
bp = b_it.next();
}
else if ( SET_LT_ATTLC(ap->hashval,bp->hashval) ) {
// an entire bucket of values in A but not in B
if (l_type != 0 )
while ( !lia.at_end() ) {
lia.next(atp);
insert(atp->value,atp->count);
}
ap = a_it.next();
}
else {
// an entire bucket of values in B but not in A
if ( l_type == 1 || l_type == 3 )
while ( !lib.at_end() ) {
lib.next(btp);
insert(btp->value,btp->count);
}
bp = b_it.next();
}
}
// Insert the leftovers
if ( l_type != 0 ) {
for ( ; ap ; ap = a_it.next() ) {
Listiter< Bag_pair<T> > lia(((Bag_bucket_ATTLC<T>*)ap)->collision_list);
while ( !lia.at_end() ) {
lia.next(atp);
insert(atp->value,atp->count);
}
}
}
if ( l_type == 1 || l_type == 3 ) {
for ( ; bp ; bp = b_it.next() ) {
Listiter< Bag_pair<T> > lib(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !lib.at_end() ) {
lib.next(btp);
insert(btp->value,btp->count);
}
}
}
}
#include <iostream.h>
template <class T>
ostream&
Bag<T>::print(ostream& os) const
{
Bag_bucketiter_ATTLC<T> bi(*this);
const Bag_bucket_ATTLC<T>* bp = bi.first();
os << "{";
while ( bp ) {
Listiter< Bag_pair<T> > li(((Bag_bucket_ATTLC<T>*)bp)->collision_list);
while ( !li.at_end() ) {
Bag_pair<T>* tp;
li.next(tp);
os << "("
<< tp->count
<< ","
<< tp->value
<< ")"
;
}
bp = bi.next();
}
os << "}";
return os;
}
#endif
|
«
|
March
2025
|
»
|
Su |
Mo |
Tu |
We |
Th |
Fr |
Sa |
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
|
|
|
|
|
|