// ********** PrototypeDemo.cpp **********
#include <iostream>
#include <time.h>
using namespace std;

class Prototype {
  public:
    virtual Prototype* clone() = 0;
};
class Node {
  private:
    int key;
    Prototype* obj;
    Node* next;
  public:
     Node(int key, Prototype * obj, Node* next) {
       this->key = key;
       this->obj = obj;
       this->next = next;
     }
     int getKey() { return key; }
     Prototype* getObject() { return obj; }
     Node* getNext() { return next; }
};
class List {
  private:
    Node* head;
  public:
    List() { head = 0; }
    void enqueue(int key, Prototype* obj) {
      head = new Node(key, obj, head); 
    }
    Prototype* find(int key) {
      Node* current = head;
      while (current) {
        if (current->getKey() == key)
          return current->getObject();
        else
          current = current->getNext();
      }
     return 0;
    }
};
const int HASH_SIZE = 1000;
class HashTable {
  private:
    List* array[HASH_SIZE];
  public:
    HashTable() {
      for (int i=0; i<HASH_SIZE; i++) 
        array[i] = new List();
    }
    int hashFunction(int key) {
      return key % HASH_SIZE;
    }
    void insert(int key, Prototype* obj) {
      array[hashFunction(key)]->enqueue(key,obj); 
    }
    Prototype* find(int key) {
      return array[hashFunction(key)]->find(key);
    }
};
class ConcretePrototype1 : public Prototype {
  private:
    int i;
  public:
    ConcretePrototype1(int i){ this->i = i; }
    Prototype* clone() { return new ConcretePrototype1(i); }
    int get() { return i; }
    void set(int i) { this->i = i; }
};
const int MAX_CLONES = 1000;
int main() {
  hrtime_t t1 = gethrtime();
  HashTable* protoManager = new HashTable();
  for (int i=0; i<HASH_SIZE; i++)
    protoManager->insert(i,new ConcretePrototype1(i));
  for (int i=0; i<HASH_SIZE; i++) {
    ConcretePrototype1* p = dynamic_cast<ConcretePrototype1 *>(protoManager->find(i));
    p->set(p->get()+1);
    for (int j=0; j<MAX_CLONES; j++) {
      ConcretePrototype1* proto = dynamic_cast<ConcretePrototype1 *>(p->clone());
    }
  }
  hrtime_t t2 = gethrtime();
  cout << (t2-t1)/1000000 << " ";
  return 1;
}