table.cpp

orange源码 数据挖掘技术

}


void TExampleTable::insert(const int &sti, const TExample &ex)
{
  if (ex.domain != domain)
    raiseError("examples has invalid domain (ExampleTable.insert doesn't convert)");
  if (sti > _Last-examples)
    raiseError("index %i out of range 0-%i", sti, _Last-examples);
  
  if (_Last == _EndSpace)
    growTable();

  TExample **sp = examples + sti;
  memmove(sp+1, sp, sizeof(TExample **)*(_Last - sp));
  *sp = ownsExamples ? CLONE(TExample, &ex) : const_cast<TExample *>(&ex);
  _Last++;

  examplesHaveChanged();
}


TExampleIterator TExampleTable::begin()
{
  return TExampleIterator(this, examples ? *examples : NULL, (void *)examples);
}


void TExampleTable::copyIterator(const TExampleIterator &src, TExampleIterator &dest)
{ 
  TExampleGenerator::copyIterator(src, dest);
  dest.data = src.data;
}


void TExampleTable::increaseIterator(TExampleIterator &it)
{
  if (++((TExample **&)(it.data)) == _Last)
    deleteIterator(it);
  else
    it.example = *(TExample **)(it.data);
}


bool TExampleTable::sameIterators(const TExampleIterator &i1, const TExampleIterator &i2)
{
  return (i1.data==i2.data);
}


bool TExampleTable::remove(TExampleIterator &it)
{
  erase( (TExample **)it.data );
  examplesHaveChanged();
  return true;
}


bool TExampleTable::randomExample(TExample &ex)
{
  if (!randomGenerator)
    randomGenerator = mlnew TRandomGenerator();

  if (!size())
    return 0;
  ex = operator[](randomGenerator->randint(size()));
  return true;
}


/*  Searches for the example in the table and returns its class, if found. If there are more
    different classes, it raises an exception, if example has no DK's, or returns DK otherwise.
    If there's no corresponding example, it returns DK. 
    IN FUTURE: This method should return distributed values if more answers are possible.
*/
TValue TExampleTable::operator ()(const TExample &exam)
{
  if (empty())
    return domain->classVar->DK();
  TExample cexam(exam);
  cexam.setClass(domain->classVar->DK());

  bool hasValue = false;
  TValue toret;
  for(TExample **ri = examples; ri!=_Last; ri++)
    if (cexam.compatible(**ri)) {
      if (!hasValue) {
        hasValue = true;
        toret = (**ri).getClass(); 
      }
      else if (!toret.compatible((**ri).getClass())) {
        // returns DK if the query contains specials, raises an exception otherwise
        int Na = domain->attributes->size();
        for(TExample::iterator vi(cexam.begin()); !((*vi).isSpecial()) && --Na; ++vi);
        if (Na)
          return domain->classVar->DK();
        else
          raiseError("ambiguous example (cannot determine the class value)");
      }
    }
  return hasValue ? toret : domain->classVar->DK();
}


int TExampleTable::numberOfExamples()
{
  return size();
}


float TExampleTable::weightOfExamples(const int &weightID) const
{
  float weight = 0;
  for(TExample **ri = examples; ri != _Last; ri++)
    weight += WEIGHT(**ri);
  return weight;
}


void TExampleTable::addExample(const TExample &example, bool filterMetas)
{
  if (ownsExamples)
    if (example.domain == domain)
      push_back(CLONE(TExample, &example));
    else
      push_back(mlnew TExample(domain, example, !filterMetas));
  else
    if (example.domain == domain)
      push_back(const_cast<TExample *>(&example));
    else
      raiseError("domain mismatch (cannot convert a reference to example)");

  examplesHaveChanged();
}


void TExampleTable::addExample(TExample *example)
{
  if (example->domain != domain)
    raiseError("cannot add pointers to examples of different domains");
  push_back(example);
  examplesHaveChanged();
}

void TExampleTable::addExamples(PExampleGenerator gen, bool filterMetas)
{
  if (ownsExamples)
    if (gen->domain == domain)
      PEITERATE(ei, gen)
        push_back(CLONE(TExample, &*ei)); 
    else
      PEITERATE(ei, gen)
        push_back(mlnew TExample(domain, *ei, !filterMetas)); 

  else {
    if (gen->domain == domain)
      PEITERATE(ei, gen)
        push_back(&*ei); 
    else
      raiseError("domain mismatch (cannot convert a reference to example)");
  }

  examplesHaveChanged();
}


bool TExampleTable::removeExamples(TFilter &filter)
{ 
  TExample **ri = examples, **ci;
  for( ; (ri!=_Last) && !filter(**ri); ri++);
  if ((ci=ri)==_Last)
    return 0;

  while(++ri!=_Last)
    if (!filter(**ri)) {
      if (ownsExamples)
        delete *ci;
      **(ci++) = **ri;
    }
  erase(ci, _Last);

  examplesHaveChanged();
  return 1;
}


bool TExampleTable::removeExample(TExample &exam)
{ // 'filter' dies before 'exam' and may contain a wrapped reference
  TFilter_sameExample filter = TFilter_sameExample(PExample(exam));
  return removeExamples(filter);
}


bool TExampleTable::removeCompatible(TExample &exam)
{ // 'filter' dies before 'exam' and may contain a wrapped reference
  TFilter_compatibleExample filter = TFilter_compatibleExample(PExample(exam));
  return removeExamples(filter);
}


class TExI {
public:
  TExample *example;
  int i;
  
  TExI(TExample *ex = NULL, const int ii=0)
  : example(ex),
    i(ii)
  {}
};


bool lesstexi(const TExI &a, const TExI &b)
{ return *a.example < *b.example; }


void TExampleTable::removeDuplicates(const int &weightID)
{ 
  if (empty())
    return;

  vector<TExI> exi(_Last - examples);
  int i = 0;
  for(TExample **ep = examples; ep!=_Last; exi[i] = TExI(*(ep++), i), i++);
  stable_sort(exi.begin(), exi.end(), lesstexi);

  bool removed = false;
  vector<TExI>::iterator fromPtr(exi.begin()), toPtr(fromPtr), ePtr(exi.end()); 
  while(++fromPtr != ePtr) {
    if (*(*fromPtr).example == *(*toPtr).example) {
      if (weightID)
        (*(*toPtr).example)[weightID].floatV += WEIGHT(*(*fromPtr).example);
      if (ownsExamples)
        delete examples[(*fromPtr).i];
      examples[(*fromPtr).i] = NULL;
      removed = true;
    }
    else
      toPtr = fromPtr;
  }

  if (!removed)
    return;

  TExample **fromE = examples;
  while (*fromE) // do not need to check !=_Last; there is a null pointer somewhere
    fromE++;

  TExample **toE = fromE++; // toE points to the next free spot
  for(; fromE != _Last; fromE++)
    if (*fromE)
      *toE++ = *fromE;

  _Last = toE;

  shrinkTable();
  examplesHaveChanged();
}


// Changes the domain and converts all the examples.
void TExampleTable::changeDomain(PDomain dom, bool filterMetas)
{
  domain = dom;
  if (ownsExamples)
    for (TExample **ri = examples; ri!=_Last; ri++) {
      TExample *tmp = mlnew TExample(dom, **ri, !filterMetas);
      delete *ri;
      *ri = tmp;
    }

  else {
    for (TExample **ri = examples; ri!=_Last; ri++)
      *ri = mlnew TExample(dom, **ri, !filterMetas);
    ownsExamples = false;
    lock = PExampleGenerator();
  }

  examplesHaveChanged();
}


void TExampleTable::addMetaAttribute(const int &id, const TValue &value)
{ 
  PEITERATE(ei, this)
    (*ei).setMeta(id, value);

  examplesHaveChanged();
}


void TExampleTable::copyMetaAttribute(const int &id, const int &source, TValue &defaultVal)
{
  if (source) {
    PEITERATE(ei, this)
      (*ei).setMeta(id, (*ei)[source]);
    examplesHaveChanged();
  }
  else
    addMetaAttribute(id, defaultVal);
}


void TExampleTable::removeMetaAttribute(const int &id)
{
  PEITERATE(ei, this)
    (*ei).removeMetaIfExists(id);

  examplesHaveChanged();
}


class TCompVar {
public:
  int varNum;

  TCompVar(int vn) : varNum(vn) {}
  bool operator()(const TExample *e1, const TExample *e2) const { return (*e1)[varNum].compare((*e2)[varNum])<0; }
};


void TExampleTable::sort()
{
  vector<int> empty;
  sort(empty);
}


// Sort order is reversed (least important first!)
void TExampleTable::sort(vector<int> &sortOrder)
{ 
  if (!sortOrder.size()) 
    for(int i = domain->variables->size(); i; )
      sortOrder.push_back(--i);

  int ssize = _EndSpace-examples;
  int lastOfs = _Last - examples;
  TExample **temp = (TExample **)malloc(ssize * sizeof(TExample *));

  try {
    const_ITERATE(vector<int>, bi, sortOrder) {
      int noVal = domain->getVar(*bi)->noOfValues();
      if (noVal>0) {
        vector<int> valf(noVal+1, 0);
        TExample **t;
        int id = 0;

        for(t = examples; t!= _Last; t++) {
          const TValue &val = (**t)[*bi];
          const int intV = val.isSpecial() ? noVal : val.intV;
          if (intV > noVal) {
            free(temp);
            raiseError("value out attribute '%s' of range", domain->variables->operator[](*bi)->name.c_str());
          }
          valf[intV]++;
        }

        for(vector<int>::iterator ni = valf.begin(); ni!=valf.end(); *(ni++)=(id+=*ni)-*ni);

        for(t = examples; t!= _Last; t++) {
          const TValue &val = (**t)[*bi];
          const int intV = val.isSpecial() ? noVal : val.intV;
          temp[valf[intV]++] = *t;
        }

        t = examples;
        examples = temp;
        temp = t;
        _Last = examples + lastOfs;
        _EndSpace = examples + ssize;
      }

      else
        stable_sort(examples, _Last, TCompVar(*bi));
    }
  }
  catch (...) {
    examplesHaveChanged();
    free(temp);
    throw;
  }

  free(temp);

  examplesHaveChanged();
}


int TExampleTable::checkSum() const
{ unsigned long crc;
  INIT_CRC(crc);

  for(TExample **ei = examples, **ee = _Last; ei!=ee; (*ei++)->addToCRC(crc));

  FINISH_CRC(crc);
  return int(crc & 0x7fffffff);
}

void TExampleTable::sortByPointers()
{
  std::sort((int *)examples, (int *)_Last);
}