#include <iostream>
#include <cstring>
using namespace std;


class CityList;

class City{
   	friend class CityList;
    char * name;
    int data;

    public:
    City(int data,  const char * name){
    	this->data=data;
    	this->name = new char[strlen(name)+1];
        strcpy(this->name, name);
    	}
    void print(){
		cout<<data<<" "<<name<<endl;
	}
	~City(){
		delete []this->name;
		}
};


class CityList{
    City *city;
    CityList *next;

    public:
    CityList(){
        this->city=NULL;
        this->next=NULL;
    }
    ~CityList(){
        CityList *temp=this;
        while(temp!=NULL){
            if(temp->city!=NULL){
                delete temp->city;
            }
            temp=temp->next;
        }
    }
    void print() {
        if(this->city==NULL){
            return;
        }
		this->city->print();
			if (this->next != NULL) {
			this->next->print();
			}
		}

void clear() {
        if(this->city==NULL){
            return;
        }
        if (this->city != NULL && this->city->data == 0) {
                if (this->next != NULL) {
                        CityList* tmp = this->next;
                        this->city = this->next->city;
                        this->next = this->next->next;
                        delete tmp;
                        this->clear();
                } else {
                        this->city = NULL;
                }
        } else if (this->next != NULL) {
                this->next->clear();
        }
    }

    int &ref(const char *name){
            CityList * temp=this;
            if(temp->city==NULL){
                temp->city=new City(0,name);
                return temp->city->data;
            }
            if(strcmp(temp->city->name, name) > 0){
                CityList *t;
                t=new CityList;
                t->city=new City(0,name);
                t->next=this->next;
                this->next = t;
                City *k = this->city;
                this->city = temp->city;
                t->city = k;
                return this->city->data;
            }
            else{
                CityList *p=this;
                while (temp!=NULL){
                    if(strcmp(temp->city->name, name)==0){
                        return temp->city->data;
                    }
                    if (strcmp(temp->city->name, name)>0){
                        while(p->next!=temp){
                            p=p->next;
                        }
                    p->next=new CityList;
                    p->next->city=new City(0,name);
                    p->next->next=temp;
                    return p->next->city->data;
                    }
                    if(temp->next==NULL){
                        temp->next=new CityList;
                        temp->next->city=new City(0,name);
                        return temp->next->city->data;
                    }
                    temp=temp->next;
                }
            }
    }

};

int main(){
    City d(34,"ewge");
    d.print();
    CityList a;
    a.print();
    a.clear();
    a.ref("ad")=99;
    a.print();
    a.clear();
    a.ref("aha");
    cout<<"``````````````````````````````"<<endl;
    a.ref("we");
    a.ref("fdwfe");
    a.print();
    a.clear();
    cout<<"uuuuuuuuuuuu"<<endl;
    a.print();
    cout<<"------------------"<<endl;



    cout<<"ssssssssssssssssss"<<endl;

    CityList *s=new CityList();
  	s->ref("dsf")=7;
  	s->print();
    return 0;
}