inline void BinarySearchTree<T>::deepCopy(const BinarySearchTreeNode<T>* node)
	{
		if (node != NULL)
			insert(node->value);

		if (node->left != NULL)
			deepCopy(node->left);

		if (node->right != NULL)
			deepCopy(node->right);
	}

    PQueue<ElemType> &PQueue<ElemType>::operator=(const PQueue &src) {
		if (this != &src) {
			delete[] arr;
			deepCopy(src);			
		}
		return *this;
	}

int main () {
    DataStruct dsOne;
    DataStruct dsTwo;
    DataStruct dsThree;

    int data_two = 2;
    // assign the datas to mainsOne
    dsOne.data_one = 1;
    dsOne.data_two = &data_two;

    // shallow copy dsOne to dsTwo
    memcpy(&dsTwo, &dsOne, sizeof(DataStruct));
    // deep copy dsOne to dsThree
    deepCopy(&dsThree, &dsOne);
    // show the value of original data
    printf("original data_one is %d,\noriginal data_two is %d\n\n", dsOne.data_one, *dsOne.data_two);

    // change the data of dsOne
    dsOne.data_one = 3;
    *dsOne.data_two = 4;

    // show the data of dsTwo after dsOne changed
    // actually dsOne.data_two and dsTwo.data_two
    // point to the same address, so the value of
    // *dsTwo->data_two is changed
    printf("data_one in dsTwo is %d,\ndata_two in dsTwo is %d\n\n", dsTwo.data_one, *dsTwo.data_two);
    // show the data of dsThree after dsOne changed
    // the address that dsThree.data_two points to and
    // the address of dsOne.data_two are not the same,
    // so *dsThree.data_two keep the original value.
    printf("data_one in dsThree is %d,\ndata_two in dsThree is %d\n\n", dsThree.data_one, *dsThree.data_two);

    system("PAUSE");
}

std::list<Scientist> ScientistRepository::list(std::string col, std::string mod) {
    std::list<Scientist> outList = std::list<Scientist>();
    outList = deepCopy();
    Comparer comp = Comparer(col,mod);
    outList.sort(comp);
    return outList;
}

ClusterGraph::ClusterGraph(
	const ClusterGraph &C,
	Graph &G,
	ClusterArray<cluster> &originalClusterTable,
	NodeArray<node> &originalNodeTable,
	EdgeArray<edge> &edgeCopy)
:
	GraphObserver(&G),
	m_lcaSearch(0),
	m_vAncestor(0),
	m_wAncestor(0)
{
	m_clusterIdCount = 0;
	m_postOrderStart = 0;
	m_rootCluster    = 0;

	m_allowEmptyClusters = true;
	m_updateDepth   = false;
	m_depthUpToDate = false;

	m_nClusters = 0;
	m_lcaNumber = 0;

	m_clusterArrayTableSize = C.m_clusterArrayTableSize;
	deepCopy(C, G, originalClusterTable, originalNodeTable, edgeCopy);
}

/*
  Insert key = id, payload = value into the hash table.
  Auto doubling the hash table if the size of the hash table reaches 2/3 of the capacity, 
   where 2/3 is the load factor.
*/
int insertItem(HashTable* table, char* id, Value* value){
  if (table){
    if ((table->size) >= ((table->capacity)*2/3)){
      autoDouble(table);
    }
    
    int key = hash(table, id);
    if (key == -1){
      return 0;
    }
    int length = 0;
    while (id[length]!='\0'){
      length++;
    }
    length++;
    char* copiedID = (char*)malloc(sizeof(char)*length);
    strncpy(copiedID,id,length-1);
    copiedID[length-1]='\0';
    Value* keyVal = (Value*)malloc(sizeof(Value));
    keyVal->type = symbolType;
    keyVal->symbolValue = copiedID;
    
    if ((table->entries)[key].cdr){
      freeValue((table->entries)[key].cdr);
    }
    (table->entries)[key].car = keyVal;
    (table->entries)[key].cdr = deepCopy(value);
    (table->size)++;
    return 1;
  }
  else{
    return 0;
  }
}

//  deep copy the things in parse tree
Value* deepCopyFun(Value *function){
  if (function){
    Value *value = (Value *)malloc(sizeof(Value));
    if (function->type == primitiveType){
      value->type = primitiveType;
      value->primitiveValue = function->primitiveValue;
      return value;
    }else if (function->type == closureType){
      value->type=closureType;
      value->closureValue = (Closure *)malloc(sizeof(Closure));
      value->closureValue->body = deepCopy(function->closureValue->body);
      value->closureValue->args = deepCopyLinkedList(function->closureValue->args);
      value->closureValue->parent = function->closureValue->parent;
      if (function->closureValue->identifier){
	value->closureValue->identifier = (char *)malloc(sizeof(char)*(strlen(function->closureValue->identifier)+1));
	strcpy(value->closureValue->identifier,function->closureValue->identifier);
	value->closureValue->identifier[strlen(function->closureValue->identifier)] = '\0';	
      }else{
	value->closureValue->identifier = NULL;
      } 
      return value;
    }else{
      free(value);
    } 
  }
  return NULL;
}

Lexicon& Lexicon::operator=(const Lexicon& src) {
    if (this != &src) {
        clear();
        deepCopy(src);
    }
    return *this;
}

MSTableColumnGroup &MSTableColumnGroup::operator=(const MSTableColumnGroup &tableColumnGroup_)
{
    if (&tableColumnGroup_!=this)
    {
        return deepCopy(tableColumnGroup_);
    }
    return *this;
}

//===========================================
// Sprite::Sprite
//===========================================
Sprite::Sprite(const Sprite& copy, long name)
   : Asset(internString("Sprite")),
     Entity(copy, name),
     EntityAnimations(copy, this),
     EntityTransformations(copy, this) {

   deepCopy(copy);
}

Macro& Driver::macro( const HashedString& name ) {
  std::pair< MacroMap::iterator, MacroMap::iterator > range = m_macros.equal_range( name );
  if ( range.first == range.second ) {
      return ( *m_macros.insert( std::make_pair( deepCopy( name.str() ), Macro() ) ) ).second;
  } else {
    return ( *( --range.second ) ).second;
  }
}

/* \brief Sets the value of the Array at the specified index.
 *
 * \param id
 * 	The ID of the type that the element should be.
 *
 * \param pos
 * 	The index to create the item at.
 * 
 * \param value
 * 	The value of the element to create.
 */
void CS225::Array::Set(int id, int pos, int value)
{ 
	deepCopy();
	//setter will delete the old and create new 
	//slightly inefficient if new and old have the same type
	delete data[pos];
	data[pos] = pElementFactory->MakeElement(id,value); 
}

void Driver::addMacro( const Macro & macro ) {
  std::pair< MacroMap::iterator, MacroMap::iterator > range = m_macros.equal_range( macro.name() );

  if ( range.first == range.second ) {
      m_macros.insert( std::make_pair( deepCopy( macro.name() ), macro ) );
  } else {
    ///Insert behind the other macros
      m_macros.insert( range.second, std::make_pair( deepCopy( macro.name() ), macro ) );
    Macro cp = this->macro( macro.name() );
    assert( macro == cp );
  }

#ifdef CACHELEXER
  if( m_currentLexerCache )
    m_currentLexerCache->addDefinedMacro( macro );
#endif
}

ClusterGraph::ClusterGraph(const ClusterGraph &C,Graph &G)
	: GraphObserver(&G), m_clusterIdCount(0),m_postOrderStart(0),
	  m_rootCluster(0), m_nClusters(0),
	m_lcaNumber(0), m_lcaSearch(0), m_vAncestor(0), m_wAncestor(0),
	m_allowEmptyClusters(1), m_updateDepth(false), m_depthUpToDate(false)
{
	deepCopy(C,G);
	m_clusterArrayTableSize = C.m_clusterArrayTableSize;
}

UBItem* UBGraphicsPolygonItem::deepCopy() const
{
    UBGraphicsPolygonItem* copy = deepCopy(this->polygon());
    copy->mOriginalLine = this->mOriginalLine;
    copy->mOriginalWidth = this->mOriginalWidth;
    copy->mIsNominalLine = this->mIsNominalLine;

    return copy;
}

//===========================================
// Polygon::Polygon
//
// Contruct deep copy
//===========================================
Polygon::Polygon(const Polygon& poly)
   : Asset(internString("Polygon")),
     Shape(poly),
     m_outlineModel(Renderer::LINES),
     m_interiorModel(Renderer::TRIANGLES),
     m_renderer(Renderer::getInstance()) {

   deepCopy(poly);
}

    std::shared_ptr< GroupTree > GroupTree::deepCopy() const {
        std::shared_ptr< GroupTree > newTree(new GroupTree());
        std::shared_ptr< GroupTreeNode > currentOriginNode = m_root;
        std::shared_ptr< GroupTreeNode > currentNewNode = newTree->getNode("FIELD");

        deepCopy(currentOriginNode, currentNewNode);
        return newTree;

    }

ArrayData* deepCopyArray(ArrayData* arr) {
  ArrayInit ai(arr->size(), ArrayInit::Mixed{});
  for (ArrayIter iter(arr); iter; ++iter) {
    Variant v = iter.secondRef();
    deepCopy(v.asTypedValue());
    ai.setValidKey(iter.first(), std::move(v));
  }
  return ai.toArray().detach();
}

 void GroupTree::deepCopy(std::shared_ptr< GroupTreeNode > origin, std::shared_ptr< GroupTreeNode > copy) const {
     std::map<std::string, std::shared_ptr< GroupTreeNode > >::const_iterator iter = origin->begin();
     while (iter != origin->end()) {
         std::shared_ptr< GroupTreeNode > originChild = (*iter).second;
         std::shared_ptr< GroupTreeNode > copyChild = copy->addChildGroup(originChild->name());
         deepCopy(originChild, copyChild);
         ++iter;
     }
 }

DawgLexicon& DawgLexicon::operator =(const DawgLexicon& src) {
    if (this != &src) {
        if (edges != NULL) {
            delete[] edges;
        }
        deepCopy(src);
    }
    return *this;
}