Quelltext /~heha/hs/gputils64-210929.zip/libgputils/gpRanges.cpp

/* Was: Bit array support, Now: C++ Ranges list
   Copyright 2016	Molnár Károly
*/

#include "gpRanges.h"

// returns true when e is more than 1 less than a (of next range)
static bool gap(int e, int a) {
  int e1 = e+1;			// Calc possible successor
  if (e1 < e) return true;	// if <e> == MAXINT, don't join!
  return e1 < a;
}

// returns true when the ranges list changes, false otherwise
// a and e must have the right order
bool gp_Ranges::setrange(int a, int e) {
  assert(a<=e);
  std::vector<Range>::iterator it;
  for (it=list.begin(); it!=list.end(); it++) {
    if (gap(e,it->min)) break;		// <it> dahinter: Davor neu erstellen
    if (gap(it->max,a)) continue;	// <it> davor: weiter suchen
    char expandresult = it->expand(a,e);
    if (expandresult&2) {		// Ende wurde erweitert?
// Vereinigung mit Folgeregionen ist möglich!
      int &max = it->max;		// Das neue Ende in gefundenem <it>
      ++it;
      while (it!=list.end()) {		// Solange Folgeindizes existieren
        if (gap(max,it->min)) break;	// <it> dahinter: nichts mehr zu tun
        if (max < it->max) max=it->max;	// einbeziehen falls Folgebereich größer
        it = list.erase(it);		// Folgebereich löschen, <it> = Folgeelement
      }
    }
    return !!expandresult;
  }
  Range n(a,e);
  list.insert(it,n);	// fügt Element /vor/ <it> ein
  return true;
}

// returns true when the ranges list changes, false otherwise
// a and e must have the right order
bool gp_Ranges::clearrange(int a, int e) {
  assert(a<=e);
  std::vector<Range>::iterator it;
  bool ret = false;
  for (it=list.begin(); it!=list.end();) {
// Case 1: Equalness or complete overlap: Clear this range
    if (a<=it->min && it->max<=e) {
      it=list.erase(it); ret=true; continue;
    }
// Case 2: Truly inside: Split range
    if (it->min<a && e<it->max) {
      Range n(it->min,a-1);	// New low part
      it->min = e+1;		// Changed high part
      list.insert(it,n);	// insert low part before current high part
      return true;		// no need for continuation
    }
// Case 3: Hide front of range
    if (it->min<=e) {
      it->min = e+1;		// change range start
      return true;		// no need for continuation
    }
// Case 4: Hide back of range
    if (a<=it->max) {
      it->max=a-1;		// change range end
      ret=true;			// need continuation
    }
// Case 5: No overlap: Continue with next range
    ++it;
  }
  return ret;
}

const gp_Ranges::Range*gp_Ranges::operator[](int i)const {
  std::vector<Range>::const_iterator it;
  for(it=list.begin();it!=list.end();it++) if (it->contains(i)) return &*it;
  return 0;
}