table.cpp

orange源码 数据挖掘技术

/*
    This file is part of Orange.

    Orange is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Orange is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Orange; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    Authors: Janez Demsar, Blaz Zupan, 1996--2002
    Contact: [e-mail]
*/


#include "random.hpp"
#include "vars.hpp"
#include "domain.hpp"
#include "domaindepot.hpp"
#include "filter.hpp"
#include "distvars.hpp"
#include "stladdon.hpp"

#include "crc.h"

#include "table.ppp"


TExampleTable::TExampleTable(PDomain dom, bool owns)
: TExampleGenerator(dom),
  examples(NULL),
  _Last(NULL),
  _EndSpace(NULL),
  ownsExamples(owns)
{ version = ++generatorVersion; }


/* Careful: the meaning of 'owns' is the opposite of what we have
   in Python: if owns==true, then the table doesn't hold only the
   references to examples (in another table) but has its own examples! */
TExampleTable::TExampleTable(PExampleGenerator gen, bool owns)
: TExampleGenerator(gen->domain),
  examples(NULL),
  _Last(NULL),
  _EndSpace(NULL),
  ownsExamples(owns)
{ 
  if (!ownsExamples) {
    lock = fixedExamples(gen);
    addExamples(lock);
  }
  else
    addExamples(gen);
}


TExampleTable::TExampleTable(PDomain dom, PExampleGenerator gen, bool filterMetas)
: TExampleGenerator(dom),
  examples(NULL),
  _Last(NULL),
  _EndSpace(NULL),
  ownsExamples(true)
{ 
  addExamples(gen, filterMetas);
}


TExampleTable::TExampleTable(PExampleGenerator alock, int)
: TExampleGenerator(alock ? alock->domain : PDomain()),
  examples(NULL),
  _Last(NULL),
  _EndSpace(NULL),
  ownsExamples(false),
  lock(alock)
{ 
  version = ++generatorVersion;
}


TExampleTable::TExampleTable(PExampleGeneratorList tables)
: TExampleGenerator(PDomain()),
  examples(NULL),
  _Last(NULL),
  _EndSpace(NULL),
  ownsExamples(true),
  lock()
{
  if (!tables->size())
    raiseError("merging constructor was given no datasets to merge");

  TDomainList domains;
  int size = tables->front()->numberOfExamples();
  vector<TExampleIterator> iterators;
  PITERATE(TExampleGeneratorList, sdi, tables) {
    if ((*sdi)->numberOfExamples() != size)
      raiseError("cannot merge dataset of unequal sizes");
    domains.push_back((*sdi)->domain);
    iterators.push_back((*sdi)->begin());
  }

  TDomainMultiMapping mapping;
  domain = combineDomains(PDomainList(domains), mapping);

  int exno = 0;
  for(; iterators.front(); exno++) {
    TExample *example = mlnew TExample(domain);
    addExample(example);
    TDomainMultiMapping::const_iterator dmmi(mapping.begin());
    TExample::iterator ei(example->begin()), ee(example->end());
    TVarList::const_iterator vi(domain->variables->begin());
    for(; ei!=ee; ei++, dmmi++, vi++) {
      bool notfirst = 0;
      for(vector<pair<int, int> >::const_iterator sdmmi((*dmmi).begin()), sdmme((*dmmi).end()); sdmmi!=sdmme; sdmmi++) {
        if (!mergeTwoValues(*ei, (*iterators[(*sdmmi).first])[(*sdmmi).second], notfirst++ != 0))
          raiseError("mismatching value of attribute '%s' in example #%i", (*vi)->name.c_str(), exno);
      }
    }

    // copy meta attributes and increase the iterators
    for(vector<TExampleIterator>::iterator ii(iterators.begin()), ie(iterators.end()); ii!=ie; ++*(ii++)) {
      ITERATE(TMetaValues, mvi, (**ii).meta) {
        if (example->hasMeta((*mvi).first)) {
          if (!mergeTwoValues(example->getMeta((*mvi).first), (*mvi).second, true)) {
            PVariable metavar = domain->getMetaVar((*mvi).first, false);
            if (metavar && metavar->name.length())
              raiseError("Meta attribute '%s' has ambiguous values on example #%i", metavar->name.c_str(), exno);
            else
              raiseError("Meta attribute %i has ambiguous values on example #%i", (*mvi).first, exno);
          }
        }
        else
          example->setMeta((*mvi).first, (*mvi).second);
      }
    }
  }

  version = ++generatorVersion;
}


TExampleTable::~TExampleTable()
{ 
  if (examples) {
    if (ownsExamples)
      for(TExample **t = examples; t != _Last; )
        delete *(t++);
    free(examples);
  }
}


int TExampleTable::traverse(visitproc visit, void *arg) const
{ 
  TRAVERSE(TExampleGenerator::traverse);
  if (ownsExamples)
    for(TExample **ee = examples; ee != _Last; ee++)
      TRAVERSE((*ee)->traverse)

  return 0;
}


int TExampleTable::dropReferences() 
{ 
  DROPREFERENCES(TExampleGenerator::dropReferences);
  clear();
  return 0;
}


void TExampleTable::reserve(const int &i)
{ 
  if (!examples) {
    if (i) {
      examples = (TExample **)malloc(i * sizeof(TExample *));
      _Last = examples;
      _EndSpace = examples + i;
    }
    else {
      _Last = _EndSpace = examples;
    }
  }

  else {
    if (!i) {
      if (examples) {
        if (_Last == examples) {
          free(examples);
          _Last = _EndSpace = examples = NULL;
        }
        // else do nothing: reserve should not remove examples!
      }
      else {
        _Last = _EndSpace = examples;
      }
    }
    else {
      if (i>_Last - examples) {
        int lastofs = _Last - examples;
        TExample **newexamples = (TExample **)realloc(examples, i * sizeof(TExample));
        if (!newexamples)
          raiseErrorWho("resize", "out of memory");
        examples = newexamples;
        _Last = examples + lastofs;
        _EndSpace = examples + i;
      }
      // else do nothing: i is too small and reserve should not remove examples!
    }
  }
}


void TExampleTable::growTable()
{
  reserve(!examples ? 256 : int(1.25 * (_EndSpace - examples)));
}


void TExampleTable::shrinkTable()
{
  if (_Last == examples)
    reserve(0);
  else {
    int sze = int(1.25 * (_Last-examples));
    if (sze < 256)
      sze = 256;
    if (sze < _EndSpace - examples)
      reserve(sze);
  }
}


TExample &TExampleTable::at(const int &i)
{
  if (_Last == examples)
    raiseError("no examples");
  if ((i<0) || (i >= _Last-examples))
    raiseError("index %i out of range 0-%i", i, _Last-examples-1);

  return *examples[i];
}


const TExample &TExampleTable::at(const int &i) const
{
  if (_Last == examples)
    raiseError("no examples");
  if ((i<0) || (i >= _Last-examples))
    raiseError("index %i out of range 0-%i", i, _Last-examples-1);

  return *examples[i];
}


TExample &TExampleTable::back() 
{
  if (_Last == examples)
    raiseError("no examples");

  return *_Last[-1];
}


const TExample &TExampleTable::back() const
{
  if (_Last == examples)
    raiseError("no examples");

  return *_Last[-1];
}


void TExampleTable::clear()
{
  if (examples) {
    if (ownsExamples)
      while (_Last != examples)
        delete *--_Last;
    free(examples);
  }
  _Last = _EndSpace = examples = NULL;
  examplesHaveChanged();
}


bool TExampleTable::empty() const
{ 
  return (_Last == examples);
}


TExample &TExampleTable::front() 
{
  if (_Last == examples)
    raiseError("no examples");

  return **examples;
}


const TExample &TExampleTable::front() const
{
  if (_Last == examples)
    raiseError("no examples");

  return **examples;
}


TExample &TExampleTable::operator[](const int &i)
{
  return *examples[i];
}


const TExample &TExampleTable::operator[](const int &i) const
{
  return *examples[i];
}


void TExampleTable::push_back(TExample *x)
{
  if (_Last == _EndSpace)
    growTable();
  *(_Last++) = x;

  examplesHaveChanged();
}


TExample &TExampleTable::new_example()
{
  TExample *x = mlnew TExample(domain);
  push_back(x);
  return *x;
}


void TExampleTable::delete_last()
{ if (_Last == examples)
    raiseError("no examples");
  erase(_Last-1);
}


int TExampleTable::size() const
{
  return examples ? _Last - examples : 0;
}


void TExampleTable::erase(const int &sti)
{
  if (_Last == examples)
    raiseError("no examples");
  if (sti >= _Last-examples)
    raiseError("index %i out of range 0-%i", sti, _Last-examples-1);
  erase(examples + sti);
}


void TExampleTable::erase(const int &sti, const int &eni)
{
  if (_Last == examples)
    raiseError("no examples");
  if (sti >= _Last-examples)
    raiseError("index %i out of range 0-%i", sti, _Last-examples-1);
  erase(examples + sti, examples + eni);
}


void TExampleTable::erase(TExample **ptr)
{
  if (ownsExamples)
    delete *ptr;
  memmove(ptr, ptr+1, sizeof(TExample **)*(_Last - ptr - 1));
  _Last--;
  examplesHaveChanged();
}


void TExampleTable::erase(TExample **fromPtr, TExample **toPtr)
{
  if (ownsExamples) {
    TExample **ee = fromPtr;
    while (ee != toPtr)
      delete *(ee++);
  }

  memmove(fromPtr, toPtr, sizeof(TExample **)*(_Last - toPtr));

  _Last -= (toPtr - fromPtr);

  shrinkTable();
  examplesHaveChanged();