SparseVector.cpp

   1 // Implementation of CSparseVector methods
   2 // Copyright © 2009 The University of Chicago
   3 #include "SparseVector.h"
   4
   5 struct BiData
   6 {
   7         int             Integer;
   8         float   m_Values;
   9
  10 };
  11 int CompareBiData (const void*  , const void*  );
  12
  13 CSparseVector::CSparseVector()
  14 {
  15         m_Length                = 0;
  16         m_NumberOfSlots = 10;
  17         m_Values                = new float [m_NumberOfSlots];
  18         m_Dimension             = new int   [m_NumberOfSlots];
  19
  20         for (int i = 0; i < m_NumberOfSlots; i++)
  21         {
  22                 m_Values[i]             = 0;
  23                 m_Dimension[i]  = 0;
  24         }
  25         m_NormalizedFlag        = 0;
  26
  27
  28 };
  29 CSparseVector::CSparseVector ( int n)
  30 {
  31         int MinimumNumberOfSlots = 10;
  32         if (n > MinimumNumberOfSlots)
  33         {
  34                 m_NumberOfSlots = n ;
  35         } else
  36         {
  37                 m_NumberOfSlots = MinimumNumberOfSlots;
  38         }
  39
  40         m_Length                = n;
  41         m_Values                = new float [m_NumberOfSlots];
  42         m_Dimension             = new int   [m_NumberOfSlots];
  43
  44         for (int i = 0; i < m_NumberOfSlots; i++)
  45         {
  46                 m_Values[i]             = 0;
  47                 m_Dimension[i]  = 0;
  48         }
  49         m_NormalizedFlag        = 0;
  50
  51 };
  52 CSparseVector:: CSparseVector (CSparseVector& rhs)
  53 {
  54
  55         m_NumberOfSlots = rhs.GetNumberOfSlots();
  56         m_Length                = rhs.GetLength();
  57
  58         int pos = 0;
  59         while ( GetNextDimension ( m_Dimension[pos], m_Values[pos], pos ) )
  60         {
  61                 // blank intentionally
  62         }
  63
  64         m_NormalizedFlag = rhs.GetNormalizedFlag();
  65 }
  66
  67 CSparseVector:: ~CSparseVector()
  68 {
  69         if (m_Values)    {delete [] m_Values;   }
  70         if (m_Dimension) {delete [] m_Dimension;}
  71 }
  72 /* -colin-
  73 void CSparseVector::Clear()
  74 {
  75         if (m_Length > 0)
  76         {
  77                 for (int i = 0; i < m_NumberOfSlots; i++)
  78                 {
  79                         m_Values[i] = 0;
  80                         m_Dimension[i] = 0;
  81                 }
  82         }
  83         m_NormalizedFlag = 0;
  84 }
  85 */ /*
  86 void CSparseVector::SetLength (int n)
  87 {
  88         m_Length                        = n;
  89         m_NumberOfSlots         = n;
  90         if (m_Values)
  91         {
  92                 delete m_Values;
  93         }
  94         m_Values = new float [n];
  95
  96 }
  97 */
  98 int CSparseVector:: GetLength() {return m_Length;}
  99
 100 /* -colin-
 101 float CSparseVector::operator[] (int n)  // uses internal index, not external --
 102 {
 103         if (n < 0 || n >= m_Length ) {return -1;}
 104         else { return m_Values[n]; };
 105 }
 106
 107  -colin- */
 108 int CSparseVector::GetNumberOfSlots() {return m_NumberOfSlots;}
 109
 110 int     CSparseVector::GetNextDimension (int& DimOut, float& Value, int& Position)
 111 {
 112         if ( Position < 0         )     { return 0; }
 113         if ( Position >= m_Length )     { return 0; }
 114         DimOut = m_Dimension[ Position ];
 115         Value  = m_Values   [ Position ];
 116         Position++;
 117         return 1;
 118
 119 }
 120 /* -colin-
 121 float CSparseVector::GetAt (int dim)  // dim is the value to the outside world
 122 {
 123         int n = ContainsDim(dim);
 124
 125         //if (n == -1 ) {       return -1;      }
 126
 127         if ( n== -1)    { return 0; }
 128         else                    { return  m_Values[n]; };
 129 }
 130
 131 void CSparseVector::operator= (CSparseVector& rhs)
 132 {
 133
 134                 m_Length                = rhs.GetLength();
 135
 136                 if ( rhs.GetLength() > m_NumberOfSlots )
 137                 {
 138                         if (m_Dimension)        delete m_Dimension;
 139                         if (m_Values)           delete m_Values;
 140                         m_NumberOfSlots = rhs.GetLength();
 141                         m_Dimension             = new int   [ m_NumberOfSlots ];
 142                         m_Values                = new float [ m_NumberOfSlots ];
 143                 }
 144                 for (int i = 0; i<m_Length; i++)
 145                 {
 146                         m_Dimension[i] = rhs.m_Dimension[i];
 147                         m_Values[i] = rhs.m_Values[i];
 148                 }
 149
 150 };
 151
 152 int             CSparseVector::operator== (CSparseVector& L2)
 153 {
 154         if (m_Length != L2.GetLength() ) {return 0;}
 155         for (int i = 0; i < m_Length; i++)
 156         {
 157                 if (m_Dimension[i] != L2.m_Dimension[i]) { return 0; }
 158                 if (m_Values[i]    != L2[i] )                    { return 0; }
 159         }
 160         return 1;
 161 };
 162
 163 int CSparseVector::Delete (int Dim)
 164 {
 165         int InternalDim = -1;
 166         if (m_Length == 0)
 167         {
 168                 return -1;
 169         }
 170         for (int i = 0; i < m_Length; i++)
 171         {
 172                 if  ( m_Dimension[i] == Dim)
 173                 {
 174                         InternalDim = i;
 175                         break;
 176                 }
 177         }
 178         if (InternalDim < 0)
 179         {
 180                 return -1;
 181         }
 182         for ( i = InternalDim; i< m_Length -1; i++)
 183         {
 184                 m_Dimension[i] = m_Dimension[i+1];
 185                 m_Values[i] = m_Values[i+1];
 186         }
 187         m_Length--;
 188         return 0;
 189 }
 190
 191 int     CSparseVector::GetTopDimension()
 192 {
 193         return m_Dimension[m_Length -1];
 194 }
 195
 196 void    CSparseVector::SetAt (int dimen, float value) // insert New at the
 197                                                                                                           // right spot.
 198 {       int             index,
 199                         RightSpot;
 200
 201         if ( dimen < 0 )
 202         {
 203                 return;
 204         }
 205         // Find out if the dimension is already represented in this vector...
 206
 207         //--------------------------------------------------
 208         index = ContainsDim (dimen);
 209         if (index >= 0 )                // if it is already represented, fine...
 210         {
 211                 m_Values[index] = value;
 212                 return;
 213         }
 214
 215         //--------------------------------------------------
 216         // Otherwise, we must add a slot to represent it.
 217
 218         m_Length++;
 219
 220         if (m_Length <= m_NumberOfSlots)
 221         {
 222                 for (int i = 0; i < m_Length-1 && dimen > m_Dimension[i]; i++ )
 223                 {
 224                         // nothing here on purpose
 225                 }
 226                 RightSpot = i;
 227                 for (i = m_Length - 1; i > RightSpot; i--)
 228                 {
 229                         m_Dimension[i] = m_Dimension[i-1];
 230                         m_Values[i]    = m_Values [i-1];
 231                 }
 232                 m_Values    [RightSpot] = value;
 233                 m_Dimension [RightSpot] = dimen;
 234         }
 235
 236         else
 237         {
 238
 239                 m_NumberOfSlots *= 2;
 240                 float * Newm_Values    = new float[ m_NumberOfSlots ];
 241                 int   * Newm_Dimension = new int  [ m_NumberOfSlots ];
 242
 243                 for (int i = 0; i< m_Length - 1 && dimen > m_Dimension[i] ; i++)
 244                 {
 245                         Newm_Dimension[i] = m_Dimension[i];
 246                         Newm_Values[i]    = m_Values[i];
 247                 };
 248
 249                 Newm_Values[i]    = value;
 250                 Newm_Dimension[i] = dimen;
 251
 252                 for (i++; i< m_Length; i++)
 253                 {
 254                         Newm_Dimension[i] = m_Dimension[i-1];
 255                         Newm_Values[i]    = m_Values   [i-1];
 256                 };
 257
 258                 if (m_Values)
 259                 {
 260                         delete[] m_Dimension;
 261                         delete [] m_Values;
 262                 }
 263                 m_Values = Newm_Values;
 264                 m_Dimension = Newm_Dimension;
 265         }
 266
 267         m_NormalizedFlag = 0;
 268 }
 269
 270 void CSparseVector::operator() (int n, float val)
 271 {
 272         SetAt (n,val);
 273         m_NormalizedFlag =0;
 274 }
 275
 276 void CSparseVector::IncrementAt(int n, float val )
 277 {
 278         int dim = ContainsDim (n);
 279         if ( dim >= 0   )
 280         {
 281                 m_Values[dim]  += val;
 282                 return;
 283         } else                  // we assume that a value that was not present is taken to be zero.
 284         {
 285                 SetAt (n, val);
 286         }
 287         m_NormalizedFlag =0;
 288 }
 289
 290
 291 int Overlap (CSparseVector& List1, CSparseVector& List2)
 292 {
 293         int             overlap = 0;
 294         int             i = 0,
 295                         j = 0;
 296         float   Val1=0,
 297                         Val2=0;
 298
 299         while ( i < List1.GetLength() && j < List2.GetLength() )
 300         {
 301                 Val1 = List1[i];
 302                 Val2 = List2[j];
 303                 if (Val1 == Val2)
 304                 {
 305                         overlap++;      i++; j++;
 306                 }
 307                 else
 308                 {
 309                         if (Val1 < Val2 )
 310                         {
 311                                 i++;
 312                         }
 313                         else
 314                         {
 315                                 j++;
 316                         }
 317                 }
 318         }
 319         return overlap;
 320 }
 321 void CSparseVector::ClearOut()
 322 {
 323         for (int i = 0; i < m_NumberOfSlots; i++)
 324         {
 325                 m_Values[i] = 0;
 326                 m_Dimension[i] = 0;
 327         }
 328
 329         m_NormalizedFlag = 0;
 330         m_Length = 0;
 331 }
 332
 333 int CSparseVector::ContainsDim (int n)
 334 {       // take advantage of log Size: do this smarter. Do
 335         // this in log n time, not n/2!
 336
 337         if (m_Length == 0) {return -1;}
 338
 339         for (int i = 0; i < m_Length; i++)
 340         {
 341                 if  ( m_Dimension[i] == n)
 342                 {
 343                         return i;
 344                 }
 345         }
 346         return -1;
 347 }
 348
 349
 350
 351
 352 ostream& CSparseVector::OutputToStream (CWordCollection& rWords, ostream& stream,int threshold)
 353 {
 354
 355         BiData*         SortArray  = new BiData[ m_Length ];
 356
 357         for (int i = 0; i<m_Length; i++) {
 358
 359                 SortArray[i].Integer   = m_Dimension[i];
 360                 SortArray[i].m_Values  = m_Values[i];
 361         }
 362
 363         qsort ( (void*) SortArray, m_Length, sizeof (BiData ), CompareBiData );
 364
 365         for ( i = 0; i<m_Length ; i++)
 366         {
 367                 if ( SortArray[i].m_Values < threshold ) {continue;}
 368                 if (SortArray[i].Integer > (int) rWords.GetCount() ||
 369                         SortArray[i].Integer < 0 )
 370                 {continue;}
 371                 stream
 372                         << setw(6)   << SortArray[i].Integer
 373                         << setw(16)  << rWords[ SortArray[i].Integer ]-> GetKey()
 374                         << setw (7)  << SortArray[i].m_Values
 375                         << endl;
 376
 377         }
 378
 379         delete SortArray;
 380         return stream;
 381
 382
 383 }
 384
 385 int CompareBiData (const void* BiData1, const void* BiData2)
 386 {
 387
 388         float S1 = (float) int(  ((BiData*) BiData1)->m_Values                  );
 389         float S2 = (float) int(  ((BiData*) BiData2)->m_Values                  );
 390         if (S2 > S1) {return 1;}
 391         if (S2 < S1) {return -1;}
 392         return 0;
 393
 394 };
 395
 396 void CSparseVector::MakeLogFreq (CWordCollection* Words)
 397 {       int             WordNumber;
 398
 399         for (int i = 0; i < m_Length; i++ )
 400         {
 401                 WordNumber = m_Dimension[i];
 402                 Q_ASSERT ( Words->GetAt (WordNumber) ->GetCorpusCount() > 0 );
 403                 m_Values[i] = float
 404                                         ( log ( m_Values[i] ) -
 405                                           log ( Words->GetAt (WordNumber)->GetCorpusCount() ) );
 406         }
 407         m_NormalizedFlag = 0;
 408 }
 409
 410 void CSparseVector::Normalize()
 411 {       float Total = 0;
 412         for (int i = 0; i < m_Length; i++)
 413         {
 414                 Total += m_Values[i];
 415         }
 416         for (i=0; i < m_Length; i++)
 417         {
 418                 m_Values[i] /=   Total;
 419         }
 420         m_NormalizedFlag = 1;
 421 }
 422  -colin- */
 423 int CSparseVector::GetNormalizedFlag() {return m_NormalizedFlag;}
 424 /* -colin-
 425 float CSparseVector::InnerProduct ( CSparseVector* Vector2)
 426 {
 427         float   Total = 0,
 428                         ThatValue= 0;
 429         int             ThisDim=0;
 430
 431         for (int i = 0; i < m_Length; i++)
 432         {
 433                 ThisDim = m_Dimension[i];
 434                 ThatValue = Vector2->GetAt(ThisDim);
 435                 if (ThatValue >= 0)
 436                 {
 437                         Total += m_Values[i] * ThatValue;
 438                 }
 439         }
 440         return Total;
 441 }
 442  -colin- */
 443
 444