Logo Search packages:      
Sourcecode: fauhdlc version File versions

RangeSet.cpp

/* $Id: RangeSet.cpp 4323 2009-01-27 13:48:12Z potyra $
 *
 * RangeSet defines operation for a Range and sets of ranges, like checking if
 * one range is a subset of another.
 *
 * Copyright (C) 2008-2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

#include <cassert>
#include "frontend/misc/RangeSet.hpp"

namespace ast {

/* **************** nested class Range **************** */
00018 RangeSet::Range::Range(
      universal_integer l, 
      universal_integer r
) : left(l), right(r) 
{
      assert(l <= r);
}

universal_integer
00027 RangeSet::Range::distance(const Range &other) const
{
      if (this->right < other.left) {
            return this->right - other.left;
      }

      if (other.right < this->left) {
            return this->left - other.right;
      }

      return 0;
}

bool
00041 RangeSet::Range::isSubset(const Range &other) const
{
      if ((other.left <= this->left) && (other.right >= this->right)) {
            return true;
      }
      return false;
}

bool
00050 RangeSet::Range::contains(universal_integer value) const
{
      return (value <= this->right) && (this->left <= value);
}


bool
00057 RangeSet::Range::operator ==(const Range &other) const
{
      return (this->left == other.left) && (this->right == other.right);
}

bool
00063 RangeSet::Range::operator <(const Range &other) const
{
      return this->left < other.right;
}

bool
00069 RangeSet::Range::operator >(const Range &other) const
{
      return other.left < this->right;
}


std::list<RangeSet::Range>
00076 RangeSet::Range::operator -(const Range &other) const
{
      std::list<Range> ret;

      if (! other.isSubset(*this)) {
            return ret;
      }

      if (other == *this) {
            return ret;
      }

      // true subset
      if (this->left < other.left) {
            Range r = Range(this->left, other.left - 1);
            ret.push_back(r);
      }

      if (other.right < this->right) {
            Range r = Range(other.right + 1, this->right);
            ret.push_back(r);
      }

      return ret;
}

void
00103 RangeSet::Range::put(std::ostream &stream) const
{
      if (this->left < this->right) {
            stream << '[' << this->left << ", " << this->right << ']';
      } else {
            // range with only one element.
            stream << this->left;
      }

}

/* ******************** RangeSet ******************** */
00115 RangeSet::RangeSet(
      universal_integer l, 
      universal_integer r
)
{
      Range initial = Range(l, r);
      this->ranges.push_back(initial);
}

00124 RangeSet::RangeSet(const DiscreteRange &r)
{
      if (r.getLowerBound() <= r.getUpperBound()) {
            Range initial = Range(r.getLowerBound(), r.getUpperBound());
            this->ranges.push_back(initial);
      }
}

bool
00133 RangeSet::minus(const DiscreteRange &r)
{
      return this->minus(r.getLowerBound(), r.getUpperBound());
}

bool
00139 RangeSet::minus(universal_integer l, universal_integer r)
{
      Range sub = Range(l, r);
      bool found = false;
      std::list<Range>::iterator i;

      for (i = this->ranges.begin(); i != this->ranges.end(); i++) {
            if (sub.isSubset(*i)) {
                  found = true;
                  break;
            }
      }

      if (! found) {    
            return false;
      }

      std::list<Range> ret = (*i) - sub;
      i = this->ranges.erase(i);

      if (! ret.empty()) {
            this->ranges.insert(i, ret.begin(), ret.end());
      }
      
      return true;
}

void
00167 RangeSet::plus(const DiscreteRange &dr)
{
      this->plus(dr.getLowerBound(), dr.getUpperBound());
}

void
00173 RangeSet::plus(universal_integer l, universal_integer r)
{
      assert(l <= r);

      Range nr = Range(l, r);
      universal_integer lb = l;
      universal_integer ub = r;

      std::list<Range>::iterator i1 = this->ranges.begin();
      std::list<Range>::iterator i2;

      // i1 : first range that is at least directly adjacent left to nr, 
      //      or is anywhere right of that place (e.g. overlapping or
      //      right of nr).
      while ((i1 != this->ranges.end()) && (i1->distance(nr) < -1)) {
            i1++;
      }

      i2 = i1;
      // i2 : first range that is at least not adjacent right of nr,
      //      i.e. it doesn't overlap and isn't left of nr.
      while ((i2 != this->ranges.end()) && (i2->distance(nr) < 2)) {
            if (i2->right > ub) {
                  ub = i2->right;
            } 
            
            i2++;
      }

      if (i1 == this->ranges.end()) {
            // no ranges that overlap or are right of r or are
            // adjacent.
            // -> just insert at end.
            this->ranges.push_back(nr);
            return;
      }

      if (i1->left < lb) {
            lb = i1->left;
      }

      // i1 == i2 -> there are no overlapping/adjacent ranges, 
      // as i1 is right of r
      if (i1 == i2) {
            assert((*i1) > nr);
            this->ranges.insert(i1, nr);
            return;
      }

      // [i1, i2) are all overlapping (or form with the new range an
      // a complete range).
      // lb, ub are the lowest and highest bound of r and [i1, i2).
      i1 = this->ranges.erase(i1, i2);
      this->ranges.insert(i1, Range(lb, ub));
}

bool
00230 RangeSet::empty(void) const
{
      return this->ranges.empty();
}

void
00236 RangeSet::clear(void)
{
      this->ranges.clear();
}

universal_integer
00242 RangeSet::getUpperBound(void) const
{
      assert(! this->ranges.empty());
      return this->ranges.back().right;
}

universal_integer
00249 RangeSet::getLowerBound(void) const
{
      assert(! this->ranges.empty());
      return this->ranges.front().left;
}

void
00256 RangeSet::put(std::ostream &stream) const
{
      stream << "{ ";
      for (std::list<Range>::const_iterator i = this->ranges.begin();
            i != this->ranges.end(); i++) {

            if (i != this->ranges.begin()) {
                  stream << ", ";
            }

            i->put(stream);
      }

      stream << " }";
}

bool
00273 RangeSet::contains(universal_integer value) const
{
      for (std::list<Range>::const_iterator i = this->ranges.begin(); 
            i != this->ranges.end(); i++) {

            if (i->contains(value)) {
                  return true;
            }
      }

      return false;
}

std::ostream &
operator <<(std::ostream &stream, const RangeSet &rs)
{
      rs.put(stream);
      return stream;
}

}; /* namespace ast */

Generated by  Doxygen 1.6.0   Back to index