region.java

use Java code to draw on pad canvas

   * Collapse the region into its extent box. Useful if the region becomes
   * very complex (number of rectangles is getting high) and the client
   * accepts the (in general) coarser result region.
   */
  public void collapse()
  {
    rectangles_[0] = extent_.y1;
    rectangles_[1] = extent_.y2;    
    rectangles_[2] = extent_.x1;
    rectangles_[3] = extent_.x2;
    nRectangles_ = 1;
  }
  
  

  /**
   * Perform a logical set operation between this and the specified
   * region. Corresponds to miRegionOp in Region.c of X11.
   * 
   * @param region         Region to combine with.
   * @param operationType  Combination operator.
   */
  private void combine (Region region, int operationType)
  {
    // This is the only method (with sub methods) that utilize the
    // common working area gRectangles_. The lock ensures that only
    // one thread access this variable at any time.
    while (isLocked_);
    isLocked_ = true;

    int r1 = 0;
    int r2 = 0;
    int r1End = nRectangles_        << 2;
    int r2End = region.nRectangles_ << 2;

    // Initialize the working region
    gNRectangles_ = 0;

    int yTop    = 0;
    int yBottom = extent_.y1 < region.extent_.y1 ?
                  extent_.y1 : region.extent_.y1;

    int previousBand = 0;
    int currentBand;

    int r1BandEnd, r2BandEnd;
    int top, bottom;
    
    // Main loop
    do {
      currentBand = gNRectangles_;

      // Find end of the current r1 band
      r1BandEnd = r1 + 4;
      while (r1BandEnd != r1End &&
             rectangles_[r1BandEnd] == rectangles_[r1])
        r1BandEnd += 4;

      // Find end of the current r2 band
      r2BandEnd = r2 + 4;
      while (r2BandEnd != r2End &&
             region.rectangles_[r2BandEnd] == region.rectangles_[r2])
        r2BandEnd += 4;

      // First handle non-intersection band if any
      if (rectangles_[r1] < region.rectangles_[r2]) {
        top    = Math.max (rectangles_[r1],    yBottom);
        bottom = Math.min (rectangles_[r1+1],  region.rectangles_[r2]);

        if (top != bottom)
          nonOverlap1 (rectangles_, r1, r1BandEnd, top, bottom, operationType);

        yTop = region.rectangles_[r2];
      }
      else if (region.rectangles_[r2] < rectangles_[r1]) {
        top    = Math.max (region.rectangles_[r2],   yBottom);
        bottom = Math.min (region.rectangles_[r2+1], rectangles_[r1]);

        if (top != bottom)
          nonOverlap2 (region.rectangles_,
                       r2, r2BandEnd, top, bottom, operationType);

        yTop = rectangles_[r1];
      }
      else
        yTop = rectangles_[r1];
      
      // Then coalesce if possible
      if (gNRectangles_ != currentBand)
        previousBand = coalesceBands (previousBand, currentBand);
      currentBand = gNRectangles_;

      // Check if this is an intersecting band
      yBottom = Math.min (rectangles_[r1+1], region.rectangles_[r2+1]);
      if (yBottom > yTop)
        overlap (rectangles_,        r1, r1BandEnd,
                 region.rectangles_, r2, r2BandEnd,
                 yTop, yBottom, operationType);

      // Coalesce again
      if (gNRectangles_ != currentBand)
        previousBand = coalesceBands (previousBand, currentBand);

      // If we're done with a band, skip forward in the region to the next band
      if (rectangles_[r1+1]        == yBottom) r1 = r1BandEnd;
      if (region.rectangles_[r2+1] == yBottom) r2 = r2BandEnd;

    } while (r1 != r1End && r2 != r2End);

    currentBand = gNRectangles_;
    
    //
    // Deal with whichever region still has rectangles left
    //
    if (r1 != r1End) {
      do {

        r1BandEnd = r1;
        while (r1BandEnd < r1End &&
               rectangles_[r1BandEnd] == rectangles_[r1])
          r1BandEnd += 4;

        top    = Math.max (rectangles_[r1], yBottom);
        bottom = rectangles_[r1+1];
        
        nonOverlap1 (rectangles_, r1, r1BandEnd, top, bottom, operationType);
        r1 = r1BandEnd;
        
      } while (r1 != r1End);
    }
    else if (r2 != r2End) {
      do {

        r2BandEnd = r2;
        while (r2BandEnd < r2End &&
               region.rectangles_[r2BandEnd] == region.rectangles_[r2])
          r2BandEnd += 4;

        top    = Math.max (region.rectangles_[r2], yBottom);
        bottom = region.rectangles_[r2+1];
        
        nonOverlap2 (region.rectangles_, r2, r2BandEnd, top, bottom,
                     operationType);
        r2 = r2BandEnd;
        
      } while (r2 != r2End);
    }

    // Coalesce again
    if (currentBand != gNRectangles_)
      coalesceBands (previousBand, currentBand);

    // Copy the work region into this
    checkMemory (this, gNRectangles_);
    System.arraycopy (gRectangles_, 0, rectangles_, 0, gNRectangles_ << 2);
    nRectangles_ = gNRectangles_;

    isLocked_ = false;
  }


  
  private void nonOverlap1 (int rectangles[], int r, int rEnd,
                            int yTop, int yBottom, int operationType)
  {
    int i = gNRectangles_ << 2;
    
    if (operationType == OPERATION_UNION ||
        operationType == OPERATION_SUBTRACTION) {
      while (r != rEnd) {
        checkMemory (null, gNRectangles_ + 1);

        gRectangles_[i] = yTop;            i++;
        gRectangles_[i] = yBottom;         i++;
        gRectangles_[i] = rectangles[r+2]; i++;
        gRectangles_[i] = rectangles[r+3]; i++;
        gNRectangles_++;
        r += 4;
      }
    }
  }
  

  
  private void nonOverlap2 (int rectangles[], int r, int rEnd,
                            int yTop, int yBottom, int operationType)
  {
    int i = gNRectangles_ << 2;
    
    if (operationType == OPERATION_UNION) {
      while (r != rEnd) {
        checkMemory (null, gNRectangles_ + 1);
        gRectangles_[i] = yTop;            i++;
        gRectangles_[i] = yBottom;         i++;
        gRectangles_[i] = rectangles[r+2]; i++;
        gRectangles_[i] = rectangles[r+3]; i++;

        gNRectangles_++;
        r += 4;
      }
    }
  }
  

  private void overlap (int rectangles1[], int r1, int r1End,
                        int rectangles2[], int r2, int r2End,
                        int yTop, int yBottom, int operationType)
  {
    int i = gNRectangles_ << 2;

    //
    // UNION
    //
    if (operationType == OPERATION_UNION) {
      while (r1 != r1End && r2 != r2End) {
        if (rectangles1[r1+2] < rectangles2[r2+2]) {
          if (gNRectangles_ > 0            &&
              gRectangles_[i-4] == yTop    &&
              gRectangles_[i-3] == yBottom &&
              gRectangles_[i-1] >= rectangles1[r1+2]) {
            if (gRectangles_[i-1] < rectangles1[r1+3])
              gRectangles_[i-1] = rectangles1[r1+3];
          }
          else {
            checkMemory (null, gNRectangles_ + 1);
            
            gRectangles_[i]   = yTop;
            gRectangles_[i+1] = yBottom;
            gRectangles_[i+2] = rectangles1[r1+2];
            gRectangles_[i+3] = rectangles1[r1+3];
            
            i += 4;
            gNRectangles_++;
          }

          r1 += 4;
        }
        else {
          if (gNRectangles_ > 0            &&
              gRectangles_[i-4] == yTop    &&
              gRectangles_[i-3] == yBottom &&
              gRectangles_[i-1] >= rectangles2[r2+2]) {
            if (gRectangles_[i-1] < rectangles2[r2+3])
              gRectangles_[i-1] = rectangles2[r2+3];
          }
          else {
            checkMemory (null, gNRectangles_ + 1);

            gRectangles_[i]   = yTop;
            gRectangles_[i+1] = yBottom;
            gRectangles_[i+2] = rectangles2[r2+2];
            gRectangles_[i+3] = rectangles2[r2+3];

            i += 4;
            gNRectangles_++;
          }

          r2 += 4;
        }
      }

      if (r1 != r1End) {
        do {
          if (gNRectangles_ > 0            &&
              gRectangles_[i-4] == yTop    &&
              gRectangles_[i-3] == yBottom &&
              gRectangles_[i-1] >= rectangles1[r1+2]) {
            if (gRectangles_[i-1] < rectangles1[r1+3])
              gRectangles_[i-1] = rectangles1[r1+3];
          }
          else {
            checkMemory (null, gNRectangles_ + 1);

            gRectangles_[i]   = yTop;
            gRectangles_[i+1] = yBottom;
            gRectangles_[i+2] = rectangles1[r1+2];
            gRectangles_[i+3] = rectangles1[r1+3];

            i += 4;
            gNRectangles_++;
          }

          r1 += 4;
          
        } while (r1 != r1End);
      }
      else {
        while (r2 != r2End) {
          if (gNRectangles_ > 0            &&
              gRectangles_[i-4] == yTop    &&
              gRectangles_[i-3] == yBottom &&
              gRectangles_[i-1] >= rectangles2[r2+2]) {
            if (gRectangles_[i-1] < rectangles2[r2+3])
              gRectangles_[i-1] = rectangles2[r2+3];
          }
          else {
            checkMemory (null, gNRectangles_ + 1);

            gRectangles_[i]   = yTop;
            gRectangles_[i+1] = yBottom;
            gRectangles_[i+2] = rectangles2[r2+2];
            gRectangles_[i+3] = rectangles2[r2+3];

            i += 4;
            gNRectangles_++;
          }

          r2 += 4;
        }
      }
    }

    //
    // SUBTRACT
    //
    else if (operationType == OPERATION_SUBTRACTION) {
      int x1 = rectangles1[r1+2];
      
      while (r1 != r1End && r2 != r2End) {
        if (rectangles2[r2+3] <= x1)
          r2 += 4;
        else if (rectangles2[r2+2] <= x1) {
          x1 = rectangles2[r2+3];
          if (x1 >= rectangles1[r1+3]) {
            r1 += 4;
            if (r1 != r1End) x1 = rectangles1[r1+2];
          }
          else
            r2 += 4;
        }
        else if (rectangles2[r2+2] < rectangles1[r1+3]) {
          checkMemory (null, gNRectangles_ + 1);
          
          gRectangles_[i+0] = yTop;
          gRectangles_[i+1] = yBottom;
          gRectangles_[i+2] = x1;
          gRectangles_[i+3] = rectangles2[r2+2];

          i += 4;
          gNRectangles_++;

          x1 = rectangles2[r2+3];
          if (x1 >= rectangles1[r1+3]) {
            r1 += 4;
            if (r1 != r1End) x1 = rectangles1[r1+2];
            else             r2 += 4;
          }
        }
        else {
          if (rectangles1[r1+3] > x1) {
            checkMemory (null, gNRectangles_ + 1);
            
            gRectangles_[i+0] = yTop;
            gRectangles_[i+1] = yBottom;
            gRectangles_[i+2] = x1;
            gRectangles_[i+3] = rectangles1[r1+3];

            i += 4;
            gNRectangles_++;
          }
          
          r1 += 4;
          if (r1 != r1End) x1 = rectangles1[r1+2];
        }
      }
      while (r1 != r1End) {
        checkMemory (null, gNRectangles_ + 1);
          
        gRectangles_[i+0] = yTop;
        gRectangles_[i+1] = yBottom;
        gRectangles_[i+2] = x1;
        gRectangles_[i+3] = rectangles1[r1+3];

        i += 4;
        gNRectangles_++;

        r1 += 4;
        if (r1 != r1End) x1 = rectangles1[r1+2];
      }
    }

    //
    // INTERSECT
    //
    else if (operationType == OPERATION_INTERSECTION) {
      while (r1 != r1End && r2 != r2End) {
        int x1 = Math.max (rectangles1[r1+2], rectangles2[r2+2]);
        int x2 = Math.min (rectangles1[r1+3], rectangles2[r2+3]);

        if (x1 < x2) {
          checkMemory (null, gNRectangles_ + 1);

          gRectangles_[i]   = yTop;
          gRectangles_[i+1] = yBottom;
          gRectangles_[i+2] = x1;
          gRectangles_[i+3] = x2;
          
          i += 4;
          gNRectangles_++;
        }

        if      (rectangles1[r1+3] < rectangles2[r2+3]) r1 += 4;
        else if (rectangles2[r2+3] < rectangles1[r1+3]) r2 += 4;
        else {
          r1 += 4;
          r2 += 4;
        }
      }
    }
  }
  
  

  /**
   * Corresponds to miCoalesce in Region.c of X11.
   */
  private int coalesceBands (int previousBand, int currentBand)
  {
    int r1   = previousBand  << 2;
    int r2   = currentBand   << 2;
    int rEnd = gNRectangles_ << 2;

    // Number of rectangles in prevoius band
    int nRectanglesInPreviousBand = currentBand - previousBand;

    // Number of rectangles in current band
    int nRectanglesInCurrentBand  = 0;
    int r = r2;
    int y = gRectangles_[r2];
    while (r != rEnd && gRectangles_[r] == y) {
      nRectanglesInCurrentBand++;
      r += 4;
    }

    // If more than one band was added, we have to find the start
    // of the last band added so the next coalescing job can start
    // at the right place.
    if (r != rEnd) {
      rEnd -= 4;
      while (gRectangles_[rEnd-4] == gRectangles_[rEnd])
        rEnd -= 4;

      currentBand = rEnd >> 2 - gNRectangles_;
      rEnd = gNRectangles_ << 2;
    }

    if (nRectanglesInCurrentBand == nRectanglesInPreviousBand &&
        nRectanglesInCurrentBand != 0) {
      
      // The bands may only be coalesced if the bottom of the previous
      // band matches the top of the current.
      if (gRectangles_[r1+1] == gRectangles_[r2]) {
        
        // Chek that the bands have boxes in the same places
        do {
          if ((gRectangles_[r1+2] != gRectangles_[r2+2]) ||
              (gRectangles_[r1+3] != gRectangles_[r2+3]))
            return currentBand; // No coalescing
          
          r1 += 4;
          r2 += 4;
          
          nRectanglesInPreviousBand--;
        } while (nRectanglesInPreviousBand != 0);

        //
        // OK, the band can be coalesced
        //
        
        // Adjust number of rectangles and set pointers back to start
        gNRectangles_ -= nRectanglesInCurrentBand;
        r1 -= nRectanglesInCurrentBand << 2;
        r2 -= nRectanglesInCurrentBand << 2;        

        // Do the merge
        do {
          gRectangles_[r1+1] = gRectangles_[r2+1];
          r1 += 4;
          r2 += 4;
          nRectanglesInCurrentBand--;
        } while (nRectanglesInCurrentBand != 0);

        // If only one band was added we back up the current pointer
        if (r2 == rEnd)
          currentBand = previousBand;
        else {
          do {
            gRectangles_[r1] = gRectangles_[r2];
            r1++;
            r2++;
          } while (r2 != rEnd);
        }
      }
    }

    return currentBand;
  }
  


  /**
   * Update region extent based on rectangle values.