/*
     Пример реализации ИНТРУЗИВНОЙ контейнерно-итераторной модели

     Дисциплина: Объектно-ориентированное программирование
           Тема: Элементы обобщённого программирования
     Компилятор: Visual C++ 2015
          Автор: А.Л.Хижа., доцент каф. компьтерных технологий, ФПМ, ДНУ.
                 2017-06-10
*/
#include<iostream>

using std::cin;
using std::cout;
using std::endl;
using std::ostream;

class Object
{
  public:
   virtual bool operator==(Object*)=0;
   virtual ostream& print(ostream&)=0;
   virtual Object* clone()=0;
};

class Int: public Object
{
   int i;
  public:
   Int(int ii):i(ii){}
   virtual
   bool operator==(Object*po)
   {
     return i==((Int*)po)->i;
   }
   virtual ostream& print(ostream&o){ return o<<i; }
   virtual Object* clone(){ return new Int( i ); }
};

class Iterator
{
  protected:
   Object **curr;
  public:
   Iterator(Object**p) { curr = p; }
   virtual bool operator==(Iterator&i){return curr==i.curr;};
   virtual void operator++(int){ curr++;};
   virtual Object& operator*(){return **curr;};
};


class List
{
    struct ListElem
    {
      ListElem *next;
      Object  *item;
    };
    ListElem *head;
  public:
    class ListIterator: public Iterator
    {
       typedef List:: ListElem  TElem;
      public:
       ListIterator(TElem*p):Iterator((Object**)p){}
       ListIterator(Iterator &i):Iterator(i){}
       /*
       bool operator==(Iterator &i)
	  { return (TElem*)curr==(TElem*)((ListIterator&)i).curr;}
       */
       void operator++(int) { curr=(Object**)((TElem*)curr)->next; }
       Object& operator*(){ return *( ((TElem*)curr)->item); }
    };

    List(Object**a,int n):head(NULL)
    {
       for(int i=0;i<n;i++)
          Insert(a[i]->clone());
    }
    void Insert(Object*po)
    {  ListElem* ptr=new ListElem;
       ptr->next=head;  ptr->item=po;
       head=ptr;
    }
    ListIterator begin(){ return ListIterator(head); }
    ListIterator end()  { return ListIterator(NULL); }
};

Iterator find(Iterator &beg, Iterator &end, Object *pval)
{
  Iterator &i=beg;
  for(;!(i==end)&&!((*i)==pval);)
     i++;
  return i;
}

ostream& operator<<(ostream&o, Object&obj)
{
  return obj.print(o);
}

int main()
{
  // "Usual"  array
  Object **a;
  int n;
  cin >> n;
  a = new Object*[n];
  for(int i=0;i<n;i++)
  {
     int val;
     cin >> val;
     a[i] = new Int(val);
  }
  Iterator ai = find(Iterator(a), Iterator(a+n), &Int(3));
  if(ai==Iterator(a+n))
     cout << ":(" << endl;
  else
     cout << "* Iterator = " << *ai << endl;
  // Linked list
  List lst(a,n);
  List::ListIterator li=find(lst.begin(),lst.end(),&Int(3));
  if(li==lst.end())
     cout << "NULL" << endl;
  else
     cout << "* ListIterator = " << *li << endl;

  return 0;
}