Java example source code file (vectset.cpp)

This example Java source code file (vectset.cpp) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

anotb, bnota, for, get, pointer, return, set, then, vectorset, vectorset::operator, vseti_, while

The vectset.cpp Java example source code

/*
 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code 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 General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "libadt/vectset.hpp"
#include "memory/allocation.inline.hpp"

// Vector Sets - An Abstract Data Type

// %%%%% includes not needed with AVM framework - Ungar
// #include "port.hpp"
//IMPLEMENTATION
// #include "vectset.hpp"

// BitsInByte is a lookup table which tells the number of bits that
// are in the looked-up number.  It is very useful in VectorSet_Size.

uint8 bitsInByte[256] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

//------------------------------VectorSet--------------------------------------
// Create a new, empty Set.
VectorSet::VectorSet(Arena *arena) : Set(arena) {
  size = 2;                     // Small initial size
  data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32));
  data[0] = 0;                  // No elements
  data[1] = 0;
}

//------------------------------Construct--------------------------------------
Set &VectorSet_Construct(Arena *arena)
{
  return *(new VectorSet(arena));
}

//------------------------------operator=--------------------------------------
Set &VectorSet::operator = (const Set &set)
{
  if( &set == this ) return *this;
  FREE_FAST(data);
  // The cast is a virtual function that checks that "set" is a VectorSet.
  slamin(*(set.asVectorSet()));
  return *this;
}

//------------------------------slamin-----------------------------------------
// Initialize one set with another.  No regard is made to the existing Set.
void VectorSet::slamin(const VectorSet& s)
{
  size = s.size;                // Use new size
  data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size
  memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array
}

//------------------------------grow-------------------------------------------
// Expand the existing set to a bigger size
void VectorSet::grow( uint newsize )
{
  newsize = (newsize+31) >> 5;  // Convert to longwords
  uint x = size;
  while( x < newsize ) x <<= 1;
  data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32));
  memset((char *)(data + size), 0, (x - size)*sizeof(uint32));
  size = x;
}

//------------------------------operator<<=------------------------------------
// Insert a member into an existing Set.
Set &VectorSet::operator <<= (uint elem)
{
  register uint word = elem >> 5;            // Get the longword offset
  register uint32 mask = 1L << (elem & 31);  // Get bit mask

  if( word >= size )            // Need to grow set?
    grow(elem+1);               // Then grow it
  data[word] |= mask;           // Set new bit
  return *this;
}

//------------------------------operator>>=------------------------------------
// Delete a member from an existing Set.
Set &VectorSet::operator >>= (uint elem)
{
  register uint word = elem >> 5; // Get the longword offset
  if( word >= size )              // Beyond the last?
    return *this;                 // Then it's clear & return clear
  register uint32 mask = 1L << (elem & 31);     // Get bit mask
  data[word] &= ~mask;            // Clear bit
  return *this;
}

//------------------------------operator&=-------------------------------------
// Intersect one set into another.
VectorSet &VectorSet::operator &= (const VectorSet &s)
{
  // NOTE: The intersection is never any larger than the smallest set.
  if( s.size < size ) size = s.size; // Get smaller size
  register uint32 *u1 = data;   // Pointer to the destination data
  register uint32 *u2 = s.data; // Pointer to the source data
  for( uint i=0; i<size; i++)   // For data in set
    *u1++ &= *u2++;             // Copy and AND longwords
  return *this;                 // Return set
}

//------------------------------operator&=-------------------------------------
Set &VectorSet::operator &= (const Set &set)
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) &= *(set.asVectorSet());
}

//------------------------------operator|=-------------------------------------
// Union one set into another.
VectorSet &VectorSet::operator |= (const VectorSet &s)
{
  // This many words must be unioned
  register uint cnt = ((size<s.size)?size:s.size);
  register uint32 *u1 = data;   // Pointer to the destination data
  register uint32 *u2 = s.data; // Pointer to the source data
  for( uint i=0; i<cnt; i++)    // Copy and OR the two sets
    *u1++ |= *u2++;
  if( size < s.size ) {         // Is set 2 larger than set 1?
    // Extend result by larger set
    grow(s.size*sizeof(uint32)*8);
    memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32));
  }
  return *this;                 // Return result set
}

//------------------------------operator|=-------------------------------------
Set &VectorSet::operator |= (const Set &set)
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) |= *(set.asVectorSet());
}

//------------------------------operator-=-------------------------------------
// Difference one set from another.
VectorSet &VectorSet::operator -= (const VectorSet &s)
{
  // This many words must be unioned
  register uint cnt = ((size<s.size)?size:s.size);
  register uint32 *u1 = data;   // Pointer to the destination data
  register uint32 *u2 = s.data; // Pointer to the source data
  for( uint i=0; i<cnt; i++ )   // For data in set
    *u1++ &= ~(*u2++);          // A <-- A & ~B  with longwords
  return *this;                 // Return new set
}

//------------------------------operator-=-------------------------------------
Set &VectorSet::operator -= (const Set &set)
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) -= *(set.asVectorSet());
}

//------------------------------compare----------------------------------------
// Compute 2 booleans: bits in A not B, bits in B not A.
// Return X0 --  A is not a subset of B
//        X1 --  A is a subset of B
//        0X --  B is not a subset of A
//        1X --  B is a subset of A
int VectorSet::compare (const VectorSet &s) const
{
  register uint32 *u1 = data;   // Pointer to the destination data
  register uint32 *u2 = s.data; // Pointer to the source data
  register uint32 AnotB = 0, BnotA = 0;
  // This many words must be unioned
  register uint cnt = ((size<s.size)?size:s.size);

  // Get bits for both sets
  uint i;                       // Exit value of loop
  for( i=0; i<cnt; i++ ) {      // For data in BOTH sets
    register uint32 A = *u1++;  // Data from one guy
    register uint32 B = *u2++;  // Data from other guy
    AnotB |= (A & ~B);          // Compute bits in A not B
    BnotA |= (B & ~A);          // Compute bits in B not A
  }

  // Get bits from bigger set
  if( size < s.size ) {
    for( ; i<s.size; i++ )      // For data in larger set
      BnotA |= *u2++;           // These bits are in B not A
  } else {
    for( ; i<size; i++ )        // For data in larger set
      AnotB |= *u1++;           // These bits are in A not B
  }

  // Set & return boolean flags
  return ((!BnotA)<<1) + (!AnotB);
}

//------------------------------operator==-------------------------------------
// Test for set equality
int VectorSet::operator == (const VectorSet &s) const
{
  return compare(s) == 3;       // TRUE if A and B are mutual subsets
}

//------------------------------operator==-------------------------------------
int VectorSet::operator == (const Set &set) const
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) == *(set.asVectorSet());
}

//------------------------------disjoint---------------------------------------
// Check for sets being disjoint.
int VectorSet::disjoint(const Set &set) const
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  const VectorSet &s = *(set.asVectorSet());

  // NOTE: The intersection is never any larger than the smallest set.
  register uint small_size = ((size<s.size)?size:s.size);
  register uint32 *u1 = data;        // Pointer to the destination data
  register uint32 *u2 = s.data;      // Pointer to the source data
  for( uint i=0; i<small_size; i++)  // For data in set
    if( *u1++ & *u2++ )              // If any elements in common
      return 0;                      // Then not disjoint
  return 1;                          // Else disjoint
}

//------------------------------operator<--------------------------------------
// Test for strict subset
int VectorSet::operator < (const VectorSet &s) const
{
  return compare(s) == 1;       // A subset B, B not subset A
}

//------------------------------operator<--------------------------------------
int VectorSet::operator < (const Set &set) const
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) < *(set.asVectorSet());
}

//------------------------------operator<=-------------------------------------
// Test for subset
int VectorSet::operator <= (const VectorSet &s) const
{
  return compare(s) & 1;        // A subset B
}

//------------------------------operator<=-------------------------------------
int VectorSet::operator <= (const Set &set) const
{
  // The cast is a virtual function that checks that "set" is a VectorSet.
  return (*this) <= *(set.asVectorSet());
}

//------------------------------operator[]-------------------------------------
// Test for membership.  A Zero/Non-Zero value is returned!
int VectorSet::operator[](uint elem) const
{
  register uint word = elem >> 5; // Get the longword offset
  if( word >= size )              // Beyond the last?
    return 0;                     // Then it's clear
  register uint32 mask = 1L << (elem & 31);  // Get bit mask
  return ((data[word] & mask))!=0;           // Return the sense of the bit
}

//------------------------------getelem----------------------------------------
// Get any element from the set.
uint VectorSet::getelem(void) const
{
  uint i;                       // Exit value of loop
  for( i=0; i<size; i++ )
    if( data[i] )
      break;
  uint32 word = data[i];
  int j;                        // Exit value of loop
  for( j= -1; word; j++, word>>=1 );
  return (i<<5)+j;
}

//------------------------------Clear------------------------------------------
// Clear a set
void VectorSet::Clear(void)
{
  if( size > 100 ) {            // Reclaim storage only if huge
    FREE_RESOURCE_ARRAY(uint32,data,size);
    size = 2;                   // Small initial size
    data = NEW_RESOURCE_ARRAY(uint32,size);
  }
  memset( data, 0, size*sizeof(uint32) );
}

//------------------------------Size-------------------------------------------
// Return number of elements in a Set
uint VectorSet::Size(void) const
{
  uint sum = 0;                 // Cumulative size so far.
  uint8 *currByte = (uint8*)data;
  for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process
    sum += bitsInByte[*currByte++];      // Add bits in current byte to size.
  return sum;
}

//------------------------------Sort-------------------------------------------
// Sort the elements for the next forall statement
void VectorSet::Sort(void)
{
}

//------------------------------hash-------------------------------------------
int VectorSet::hash() const
{
  uint32 _xor = 0;
  uint lim = ((size<4)?size:4);
  for( uint i = 0; i < lim; i++ )
    _xor ^= data[i];
  return (int)_xor;
}

//------------------------------iterate----------------------------------------
// Used by Set::print().
class VSetI_ : public SetI_ {
  VectorSetI vsi;
public:
  VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; }

  uint next(void) { ++vsi; return vsi.elem; }
  int  test(void) { return vsi.test(); }
};

SetI_ *VectorSet::iterate(uint &elem) const {
  return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem);
}

//=============================================================================
//------------------------------next-------------------------------------------
// Find and return the next element of a vector set, or return garbage and
// make "VectorSetI::test()" fail.
uint VectorSetI::next(void)
{
  j++;                          // Next element in word
  mask = (mask & max_jint) << 1;// Next bit in word
  do {                          // Do While still have words
    while( mask ) {             // While have bits in word
      if( s->data[i] & mask ) { // If found a bit
        return (i<<5)+j;        // Return the bit address
      }
      j++;                      // Skip to next bit
      mask = (mask & max_jint) << 1;
    }
    j = 0;                      // No more bits in word; setup for next word
    mask = 1;
    for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word
  } while( i<s->size );
  return max_juint;             // No element, iterated them all
}