dataadd.c

TV-tree的c实现源码

/* 
 
                  COPYRIGHT NOTICE
 
This material was developed by Christos Faloutsos and King-Ip Lin
at the University of Maryland, College Park, Department of Computer Science.
Permission is granted to copy this software, to redistribute it
on a nonprofit basis, and to use it for any purpose, subject to
the following restrictions and understandings.
 
1. Any copy made of this software must include this copyright notice
in full.
 
2. All materials developed as a consequence of the use of this
software shall duly acknowledge such use, in accordance with the usual
standards of acknowledging credit in academic research.
 
3. The authors have made no warranty or representation that the
operation of this software will be error-free or suitable for any
application, and they are under under no obligation to provide any
services, by way of maintenance, update, or otherwise.  The software
is an experimental prototype offered on an as-is basis.
 
4. Redistribution for profit requires the express, written permission
of the authors.
 
*/

// Author : $Author$
// Date : $Date$
// Id : $Id$
// $Id: data.C,v 1.4 1996/04/18 21:50:24 kilin Exp kilin $ 
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <String.h>
#include "TVdefine.h"
#include "TVvector.h"
#include "dataadd.h"
#include "TVutil.h"

int DataPoints::dim = DEFAULT_DATADIM;

int calv(char f)
{
   if ((f >= 'a') && (f <= 'z'))
      return (f - 'a');  

   if ((f >= 'A') && (f <= 'Z'))
      return (f - 'A');  

   if ((f >= '0') && (f <= '9'))
      return (f - '0' + 26);  

   return 36;
}


int calcoeff(char f, char s)
{
   return calv(f) * 37 + calv(s);
}


void fillarray(String s, String s2, int *position, int *value)
{

   int len = s.length();
   int i, j;
 
   for (j = 0; j < len - 1; j++)
       {
         int coeff = calcoeff(s[j], s[j+1]);
	 int k;
         for (k = 0; (k < len) && (position[k] != -1) && (position[k] != coeff); k++)
	     ;
	 position[k] = coeff;
	 value[k]++;
       }

   len = s2.length();

   for (j = 0; j < len - 1; j++)
       {
         int coeff = calcoeff(s2[j], s2[j+1]);
	 int k;
         for (k = 0; (k < len) && (position[k] != -1) && (position[k] != coeff); k++)
	     ;
	 position[k] = coeff;
	 value[k]++;
       }
}

DataPoints::DataPoints() 
{
   position = value = NULL;
}

void DataPoints::Initpos()
{
   position = new int[address.length() + name.length() - 2];
   value = new int[address.length() + name.length() - 2];

   for (int i = 0; i < address.length() + name.length() - 2; i++)
      {
        position[i] = -1;
        value[i] = 0;
      }

   fillarray(name, address, position, value);
}

DataPoints::DataPoints(char * ia)
{
// cout << "Enter creating datapoints : " << ia << endl;
   char *add = strchr(ia, '|');
   char *add1 = add + sizeof(char);
   char add0[add1 - ia];
   strncpy(add0, ia, add1 - ia - 1);
   add0[add1 - ia - 1] = '\0';
   name = String(add0);
   address = String(add1);
// cout << "name : " << name << "    address : " << address << endl;
   position = value = NULL;
}

DataPoints::DataPoints(char *n, char *add) : name(n), address(add)
{
   // vec = Initvec(0, dim - 1);
   position = value = NULL;
}

DataPoints::DataPoints(const DataPoints& dp)
{
// cout << "DataPoints const construct called\n";
   name = dp.name;
   address = dp.address;
//   vec = dp.vec;
   position = value = NULL;
}


DataPoints::~DataPoints()
{
   if (position)
     delete [] position;
   if (value)
      delete [] value;
}

/*
Vector DataPoints::Initvec(int start, int end)
{
//cout << "Initvec : " << name << " (" << start << ", " << end << ")\n";
   Vector v1(end - start + 1);

   int position[address.length()];
   int value[address.length()];
 
   fillarray(address, position, value);
   int len = address.length();

   int res = 0;

   for (int j = start; j <= end; j++)
     {
	v1[j - start] = 0;
        for (int k = 0; (k < len) && (position[k] != -1); k++)
          v1[j - start] += hadamard_minsize(1369, j, position[k]) * value[k]; 
     }
   return v1;
}
*/

/*
int DataPoints::operator[](int p)
{
   if (p >= vec.GetDim())
     {
        vec <<= Initvec(vec.GetDim(), p);
     }
 
   return (int)(vec[p]);
}
*/

int DataPoints::operator[](int p)
{
   if (!position)
     Initpos();
	 
/*
   int position[address.length()];
   int value[address.length()];
 
   fillarray(address, position, value);
*/
   int len = name.length() + address.length() - 2;

   int res = 0;

   for (int k = 0; (k < len) && (position[k] != -1); k++)
       res += hadamard_minsize(1369, p, position[k]) * value[k]; 

   return res;
}

char* DataPoints::operator()()
{
   char *arr = new char[name.length() + address.length() + 2];
   strcpy(arr, (const char *)name);
   strcat(arr, "|");
   strcat(arr, (const char *)address);
// cout << "operator () : " << arr << "  " << name.length() + address.length() + 2 << endl;
   return arr;
}

int DataPoints::Size() const
{
  return (name.length() + address.length() + 2) * sizeof(char); 
}

DataPoints& DataPoints::operator=(const DataPoints& dp)
{
   name = dp.name;
   address = dp.address;
   return *this;
}

int DataPoints::operator==(const DataPoints& dp) const
{
   int i = 0;
   return (!fcompare(address, dp.address)); 
}

int min3(int a,int b,int c)
{
  if ((a <= b) && (a <= c))
     return(a);
  else
    if (b <= c)
       return(b);
    else
       return(c);
}


int Worddiff(String s1, String s2)
{
  int lens, lenl;
  int i, j, k, temp;
  int diff1[min(s1.length(),s2.length())+1][max(s1.length(),s2.length())+1];
  String w1, w2;

  lens = s1.length();
  lenl = s2.length();
  w1 = s1;
  w2 = s2;
  if (lens > lenl)
     {
       temp = lens;
       lens = lenl;
       lenl = temp;
       w1 = s2;
       w2 = s1;
     }
  for (i=0; i <= lens;  i++)
      diff1[i][0] = i;
  for (i=1; i <= lenl;  i++)
      diff1[0][i] = i;
  for (i = 1; i <= lens; i++)
    {
      for (j = 1; j <= i; j++)
         diff1[i-j+1][ j]  = min3(diff1[i-j][ j-1] + (w1[i-j] != w2[j-1]),
                                diff1[i-j][ j] + 1,
                                diff1[i-j+1][ j-1] + 1);
    }
  for (i = 1; i <= lenl - lens - 1; i++)
    {
      for (j = 1; j <= lens; j++)
         diff1[lens-j+1][ i + j]  = min3(diff1[lens-j][ i+j-1] + (w1[lens-j] != w2[i + j-1]),
                                diff1[lens-j][ i+j] + 1,
                                diff1[lens-j+1][ i+j-1] + 1);
    }
  for (i = 1; i <= lens; i++)
    {
      for (j = 0; j <= lens - i; j++)
         diff1[lens-j][ lenl- lens + j + i]  = min3(diff1[lens-j - 1][ lenl - lens + i+j-1] + (w1[lens-j - 1
] != w2[lenl - lens + i + j-1]),
                                diff1[lens-j - 1][ lenl - lens + i+j] + 1,
                                diff1[lens-j][ lenl - lens + i+j-1] + 1);
    }
 return(diff1[lens][lenl]);
}



float DataPoints::Distance(const DataPoints& dp) 
{
   float res = 0.0;
   return Worddiff(address, dp.address); 
}

istream& operator>>(istream& is, DataPoints& dp)
{
   is >> dp.name >>  dp.address;
   return is;
}

/*
// do not read in the keys
istream& operator>>=(istream& is, DataPoints& dp)
{
   for (int i = 0; i < DataPoints::dim; i++)
     is >> dp.points[i]; 
   return is;
}
*/

istream& operator>>=(istream& is, DataPoints& dp)
{
   is >> dp.name >>  dp.address;
   return is;
}

ostream& operator<<(ostream& os, DataPoints& dp)
{
   os << dp.name << "   " << dp.address;
   return os;
}

ofstream& operator<(ofstream& os, DataPoints& dp)
{
   os << dp.name << "  " << dp.address;
   return os;
}


char *ReadData(ifstream& is, int& size)
{
   DataPoints *dp = new DataPoints;
   is >> *dp;
   size = dp->Size();
   return (char *)dp; 
}

void WriteData(ofstream& of, char *iarray, int size)
{
   DataPoints *dp = (DataPoints *)iarray;
   of < *dp;
}


void PrintData(ostream& of, char *iarray)
{
   DataPoints *dp = (DataPoints *)iarray;
   of << *dp;
}

VCOM_TYPE GetFeature(int fno, char *iarray)
{
  DataPoints *dp = (DataPoints *)iarray;
  return (*dp)[fno - 1];
}

int Equal(char* arr1, char* arr2)
{
  DataPoints *dp1 = (DataPoints *)arr1;
  DataPoints *dp2 = (DataPoints *)arr2;

  return *dp1 == *dp2;
}

char *GetKey(char *arr1, int osize, int& size)
{
  DataPoints *dp1 = (DataPoints *)arr1;

  
  char *k = new char[dp1->name.length() + 1];
  strcpy(k, (const char*)dp1->name);
  return k;
}

void PrintKey(ostream& of, char *iarray)
{
   of << iarray; 
}

float Distance(char* arr1, char* arr2)
{
  DataPoints *dp1 = (DataPoints *)arr1;
  DataPoints *dp2 = (DataPoints *)arr2;

  return dp1->Distance(*dp2);
}