#include<iostream>

using namespace std;
int main(){
  List<int> x;
  // Insert
  x.InsertItem(4);
  x.InsertItem(3);
  x.InsertItem(7);
  x.InsertItem(9);
  x.InsertItem(13);
  x.InsertItem(2);
  x.InsertItem(6);
  // Delete
  x.DeleteItem(3);
  x.DeleteItem(9);

  cout<<endl<<"After deletion process ..."<<endl
      <<"length is "<<x.Size()<<endl;
  //cout<<"the list contains : "<<endl;
  //x.ResetList();
  for(int i = 0;i<x.Size();i++){
      int temp ;
      x.GetNextItem(temp);
      cout<<temp<<"  "<<endl;
  }

  // RetrieveItem() function
  cout<<endl<<"searching for item 13 "<<endl;
  bool found;
  x.RetrieveItem(13,found);
  if(found)
      cout<<"found "<<endl;
  else
      cout<<"not found "<<endl;
  cout<<endl<<"searching for item 1 "<<endl;
  x.RetrieveItem(1,found);
  if(found)
      cout<<"found "<<endl;
  else
      cout<<"not found "<<endl;

  return 0;
}
const int MAX_ITEMS = 30;
template<class T>
class List{
private:
  int size;
  int currIndex;
  T data[MAX_ITEMS];
public:
    List(){
      size = 0;
      currIndex = -1;
    }
    void InsertItem(T elem){
      if(size > 0){
        for(int i = 0;i<size;i++){
          if(min(data[i], elem) == elem){
            Shift(i);
            data[i] = elem;
            size++;
            break;
          }
        }
    } else {
        data[size] = elem;
        size++;
      }
    }
    void Shift(int index){
      for(int i=size-1; i>=index; --i)
      {
        data[i+1] = data[i];
      }
    }
    void RetrieveItem(T elem, bool& found){
      for(int i=0;i<size;i++){
        if(data[i] == elem){
          found = true;
          break;
        }
      }
    }
    void DeleteItem(T elem){
      for(int i=0;i<size;i++){
        if(elem == data[i]){
          for(int x = i; x < size; x++){
            data[x] = data[x+1];
          }
          size--;
          break;
        }
      }
    }
    void GetNextItem (T& elem){
      currIndex += 1;
      elem = data[currIndex];
    }
    int Size(){
      return size;
    }

};