/*****************************************************************************
 * Project: RooFit                                                           *
 * Package: RooFitCore                                                       *
 *    File: $Id: RooHashTable.cc,v 1.16 2005/06/20 15:44:53 wverkerke Exp $
 * Authors:                                                                  *
 *   WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu       *
 *   DK, David Kirkby,    UC Irvine,         dkirkby@uci.edu                 *
 *                                                                           *
 * Copyright (c) 2000-2005, Regents of the University of California          *
 *                          and Stanford University. All rights reserved.    *
 *                                                                           *
 * Redistribution and use in source and binary forms,                        *
 * with or without modification, are permitted according to the terms        *
 * listed in LICENSE (http://roofit.sourceforge.net/license.txt)             *
 *****************************************************************************/

#include "RooFit.h"

#include "TMath.h"
#include "TMath.h"
#include "TCollection.h"
#include "RooHashTable.h"
#include "RooLinkedList.h"
#include "RooAbsArg.h"
#include "RooSetPair.h"

ClassImp(RooHashTable)
;

 RooHashTable::RooHashTable(Int_t capacity, HashMethod hashMethod) :
  _hashMethod(hashMethod)
{
  if (capacity <= 0) {
    capacity = TCollection::kInitHashTableCapacity;
  }  
  _size = (Int_t)TMath::NextPrime(TMath::Max(capacity,(int)TCollection::kInitHashTableCapacity));
  _arr  = new RooLinkedList* [_size] ;
  memset(_arr, 0, _size*sizeof(RooLinkedList*));

  _usedSlots = 0 ;
  _entries   = 0 ;
}


 RooHashTable::RooHashTable(const RooHashTable& other) :
  TObject(other),
  _hashMethod(other._hashMethod),
  _usedSlots(other._usedSlots), 
  _entries(other._entries), 
  _size(other._size)
{
  _arr  = new RooLinkedList* [_size] ;
  memset(_arr, 0, _size*sizeof(RooLinkedList*));  
  Int_t i ;
  for (i=0 ; i<_size ; i++) {
    if (other._arr[i]) {
      _arr[i] = new RooLinkedList(*other._arr[i]) ;
    }
  }
}


 void RooHashTable::add(TObject* arg, TObject* hashArg) 
{
  Int_t slot = hash(hashArg?hashArg:arg) % _size ;
  if (!_arr[slot]) {
    _arr[slot] = new RooLinkedList(0) ;
    _usedSlots++ ;
   }
   _arr[slot]->Add(arg);
   _entries++;
}



 Bool_t RooHashTable::remove(TObject* arg, TObject* hashArg)
{
  Int_t slot = hash(hashArg?hashArg:arg) % _size ;
  if (_arr[slot]) {
    if (_arr[slot]->Remove(arg)) {
      _entries-- ;
      if (_arr[slot]->GetSize()==0) {
	delete _arr[slot] ;
	_arr[slot] = 0 ;
	_usedSlots-- ;
      }
      return kTRUE ;
    }
  }
  return kFALSE ;
}



 Double_t RooHashTable::avgCollisions() const 
{
  Int_t i,h[20] ;
  for (i=0 ;  i<20 ; i++) h[i]=0 ; 

  for (i=0 ; i<_size ; i++) {
    if (_arr[i]) {
      Int_t count = _arr[i]->GetSize() ;
      if (count<20) {
	h[count]++ ;
      } else {
	h[19]++ ;
      }
    } else {
      h[0]++ ;
    }
  }

  for (i=0 ; i<20 ; i++) {
    cout << "h[" << i << "] = " << h[i] << endl ;
  }
  return 0 ;
}


 Bool_t RooHashTable::replace(const TObject* oldArg, const TObject* newArg, const TObject* oldHashArg) 
{
  Int_t slot = hash(oldHashArg?oldHashArg:oldArg) % _size ;
  if (_arr[slot]) {
    return _arr[slot]->Replace(oldArg,newArg) ;
  }
  return kFALSE ;
}


 TObject* RooHashTable::find(const char* name) const 
{
  if (_hashMethod != Name) assert(0) ;

  Int_t slot = TMath::Hash(name) % _size ;
  if (_arr[slot]) return _arr[slot]->find(name) ;
  return 0;  
}


 TObject* RooHashTable::find(const TObject* hashArg) const 
{
  if (_hashMethod != Pointer) assert(0) ;

  Int_t slot = hash(hashArg) % _size ;
  if (_arr[slot]) return _arr[slot]->FindObject(hashArg) ;
  return 0;  
}


 RooLinkedListElem* RooHashTable::findLinkTo(const TObject* hashArg) const 
{
  if (_hashMethod != Pointer) assert(0) ;

  Int_t slot = hash(hashArg) % _size ;
  if (_arr[slot]) {
    Int_t i ; 
    for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
      RooLinkedListElem* elem = (RooLinkedListElem*)_arr[slot]->At(i) ;
      if (elem->_arg == hashArg) return elem ;
    }
  }
  return 0;  
}



 RooSetPair* RooHashTable::findSetPair(const RooArgSet* set1, const RooArgSet* set2) const 
{  
  if (_hashMethod != Intrinsic) assert(0) ;

  Int_t slot = RooSetPair(set1,set2).Hash() % _size ;
  if (_arr[slot]) {
    Int_t i ; 
    for (i=0 ; i<_arr[slot]->GetSize() ; i++) {
      RooSetPair* pair = (RooSetPair*)_arr[slot]->At(i) ;
      if (pair->_set1==set1 && pair->_set2==set2) {
	return pair ;
      }
    }
  }

  return 0 ;
}




 RooHashTable::~RooHashTable() 
{  
  Int_t i ;
  for (i=0 ; i<_size ; i++) {
    if (_arr[i]) delete _arr[i] ;  
  }
  delete[] _arr ;
}