CharSet.java

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * This file is part of SableCC.                             *
 * See the file "LICENSE" for copyright information and the  *
 * terms and conditions for copying, distribution and        *
 * modification of SableCC.                                  *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

package org.sablecc.sablecc;

import java.util.*;
import java.util.Enumeration;
import java.util.Vector;

public class CharSet implements Cloneable
{
  private final Vector intervals = new Vector(0);

  public CharSet(char c)
  {
    intervals.addElement(new Interval(c, c));
  }

  public CharSet(char start, char end)
  {
    intervals.addElement(new Interval(start, end));
  }

  private CharSet(Vector intervals)
  {
    for(Enumeration e = intervals.elements(); e.hasMoreElements();)
    {
      this.intervals.addElement(((Interval) e.nextElement()).clone());
    }
  }

  public Object clone()
  {
    return new CharSet(intervals);
  }

  public Interval findOverlap(Interval interval1)
  {
    int low = 0;
    int high = intervals.size() - 1;
    Interval interval2;
    Interval result = null;

    while(high >= low)
    {
      int middle = (high + low) / 2;

      interval2 = (Interval) intervals.elementAt(middle);

      if(interval1.start <= interval2.end)
      {
        if(interval1.end >= interval2.start)
        {
          result = interval2;
          // we continue, to find the lowest matching interval!
        }

        high = middle - 1;
      }
      else
      {
        low = middle + 1;
      }
    }

    return result;
  }

  private void remove
    (Interval interval)
  {
    intervals.removeElement(interval);
  }

  private void add
    (Interval interval)
  {
    for(int i = 0; i < intervals.size(); i++)
    {
      Interval iv = (Interval) intervals.elementAt(i);

      if(iv.start > interval.start)
      {
        intervals.insertElementAt(interval, i);
        return;
      }
    }

    intervals.addElement(interval);
  }

  public CharSet union(CharSet chars)
  {
    CharSet result = (CharSet) clone();

    Interval interval;
    Interval largeInterval;
    Interval overlap;

    for(Enumeration e = chars.intervals.elements(); e.hasMoreElements();)
    {
      interval = (Interval) ((Interval) e.nextElement()).clone();

      do
      {
        largeInterval = new Interval(
                          (interval.start == 0) ? (char) 0 : (char) (interval.start - 1),
                          (interval.end == 0xffff) ? (char) 0xffff : (char) (interval.end + 1));

        overlap = result.findOverlap(largeInterval);
        if(overlap != null)
        {
          result.remove(overlap);
          interval.start = (char) Math.min(interval.start, overlap.start);
          interval.end = (char) Math.max(interval.end, overlap.end);
        }
      }
      while(overlap != null);

      result.add(interval);
    }

    return result;
  }

  public CharSet diff(CharSet chars)
  {
    CharSet result = (CharSet) clone();

    Interval interval;
    Interval overlap;

    for(Enumeration e = chars.intervals.elements(); e.hasMoreElements();)
    {
      interval = (Interval) ((Interval) e.nextElement()).clone();

      do
      {
        overlap = result.findOverlap(interval);
        if(overlap != null)
        {
          result.remove(overlap);
          if(overlap.start < interval.start)
          {
            result.add(new Interval(overlap.start, (char) (interval.start - 1)));
          }
          if(overlap.end > interval.end)
          {
            result.add(new Interval((char) (interval.end + 1), overlap.end));
          }
        }
      }
      while(overlap != null);
    }

    return result;
  }

  public String toString()
  {
    StringBuffer result = new StringBuffer();

    for(Enumeration e = intervals.elements(); e.hasMoreElements();)
    {
      result.append("[" + e.nextElement() + "] ");
    }

    return "" + result;
  }

  public static class Interval implements Cloneable
  {
    public Interval(char start, char end)
    {
      this.start = start;
      this.end = end;
    }

    public Object clone()
    {
      return new Interval(start, end);
    }

    private String c(char c)
    {
      if((c >= 32) && (c < 127))
      {
        return "" + c;
      }

      return "" + ((int) c);
    }

    public String toString()
    {
      if(start < end)
      {
        return c(start) + " .. " + c(end);
      }
      else
      {
        return c(start);
      }
    }

    public char start;
    public char end;
  }

  public static class IntervalCast implements Cast
  {
    public final static IntervalCast instance = new IntervalCast();

    private IntervalCast()
    {}

    public Object cast(Object o)
    {
      return (Interval) o;
    }
  }
}