public unsafe class Element
    {
        public string subString;
        public Element Back;
        public Element[] Next = new Element[10];
        public int status;  // 1 - prefix
        public Element()
        {
           // Console.WriteLine("Wstawiono nowa tabele");
        }
    }

    class Program
    {


        public static object[] dane = new object[3];
        public static object[] relacje = new object[2];
        public static Element root;

        public static string FindPrefix(string pesel, string tmp)
        {
            string substring=null;

                 int len = 0;
                    for (int i = 0; i < tmp.Length; i++)  // przeszukiwanie substringa
                    {
                        if (tmp[i] == pesel[i])
                            len++;
                        else break;
                    }


                    for (int i = 0; i < len; i++)
                    {
                        substring = substring+ pesel[i];
                    }
            return substring;
        }

        public static string CutPrefix(string tmp, int len)
        {
            string wynik = null;
            for (int i = len; i < tmp.Length; i++)
            {
                wynik += tmp[i];
            }
            return wynik;
        }

        public static Element Find()
        {
            Element element = root;
            while (element != null)
            {
                Element element2 = element;
                for (int i = 0; i < 10; i++)
                {
                    if (element2.Next[i] != null)
                        Console.WriteLine(element2.Next[i].subString);

                }
                element = element.Next[9];

            }
            return element;

        }

        public static void View()
        {
            Element element = root;

            while (element != null)
            {

                Element element2 = element;
                for (int i = 0; i < 10; i++)
                {
                    if (element2.Next[i] != null)
                        Console.WriteLine(element2.Next[i].subString);

                }

                element = element.Next[9];

            }
        }




        public unsafe static void Collision(Element src, Element desc)
        {
              Console.WriteLine("Wykryto kolizje ");

              if (src.status == 1) // jesli to juz jest prefix
              {
                  string prefix = FindPrefix(desc.subString, src.subString);
//-----------------------
                    // jesli prefix jest krotszy od aktualnego = jest kolizja wyzej
                  if (prefix.Length < src.subString.Length)
                  {
                      Element upper = new Element();  //1
                      upper.subString = prefix;

                      //int ntx = int.Parse(tmp[0].ToString());
                      src.Back = upper; //2  src.subString[0]

                      string tmp = CutPrefix(src.subString, prefix.Length); // 3
                      src.subString = tmp;

                      int ntx = int.Parse(tmp[0].ToString()); //4
                      upper.Next[ntx] = src;

                      AddToNode(upper, desc);

                  }
                  //---------------------------
                  else
                  {
                      desc.subString = CutPrefix(desc.subString, prefix.Length);
                      AddToNode(src, desc);
                  }
              }
              else // jak to normalny wezel
              {

                  string prefix = FindPrefix(desc.subString, src.subString);
                  // pierwszy element
                  Element first = new Element();
                  first.subString = CutPrefix(src.subString, prefix.Length);

                  AddToNode(src, first);

                  // drugi element
                  Element second = new Element();
                  second.subString = CutPrefix(desc.subString, prefix.Length);

                  AddToNode(src, second);

                  // podmiana wezla ojca
                  src.subString = prefix;
                  src.status = 1;
              }

        }


        public unsafe static void AddToNode(Element src,Element desc)
        {
            int ntx = int.Parse(desc.subString[0].ToString()); // pobieram first character

            if (src.Next[ntx] == null)
            {
                src.Next[ntx] = new Element();
                src.Next[ntx] = desc;
                desc.Back = &src;
                Console.WriteLine("Dodano: ojciec"+src.subString+" syn:"+desc.subString);
            }
            else //
            {
                Collision(src.Next[ntx], desc);
               // Console.WriteLine("Juz cos jest na pozycji");
            }

        }



        public static void Add(string pesel)
        {
            int a = int.Parse(pesel[0].ToString()); // wyciagamy pierwsza liczbe i lecimy do tej komorki w tabeli
            Element element = root;



            Element toSend = new Element();
            toSend.subString = pesel;


            while (element != null)
            {
                if (element.Next[a] == null)  // jesli w danej komorce nic jeszcze nie ma
                {
                    element.Next[a] = new Element();
                    element.Next[a].subString = pesel;    // jesli jest wolny to wpisz pesel
                    Console.WriteLine("Dodano pesel " + pesel);

                    Element element2 = element.Next[a];
                    element2.Back = element;
                    break;
                }
                else   // jesli nie jest nullem to wchodzimy
                {
                    while (element != null)
                    {
                        Element Back = element.Next[a];
                        element = element.Next[a];

                        string SUB = FindPrefix(pesel, Back.subString); // sprawdzamy poprzedni z aktualnym
                        string temp = CutPrefix(pesel, SUB.Length);

                       int ntx = int.Parse(temp[0].ToString());

                       if (element.Next[ntx] == null)   // jesli syn ma w tym miejscu nulla
                        {
                            element.Next[ntx] = new Element();
                            element.Next[ntx].subString = CutPrefix(pesel, SUB.Length);//pesel;

                            if (Back.subString.Length > SUB.Length) // zamiana roota
                            {
                                Back.subString = SUB; // podmiana na krotszy
                                AddToNode(Back, toSend);
                            }

                            if (Back.subString.Length != SUB.Length)
                            {
                                temp = CutPrefix(Back.subString, SUB.Length);// Back.subString;
                                ntx = int.Parse(temp[0].ToString()); // wyciagamy pierwsza liczbe i lecimy do tej komorki w tabeli
                                element.Next[ntx] = new Element();
                                element.Next[ntx].subString = temp;

                                Back.subString = SUB;
                            }
                            break;
                        }


                       if (element.Next[ntx] != null) // jesli ktos juz jest w tym miejscu
                       {
                           string old = element.Next[ntx].subString;
                           string prefix = FindPrefix(pesel, old);

                           //update old(delete prefix)
                           old = CutPrefix(old, prefix.Length);

                           element.Next[ntx].subString = prefix;

                           Element old_e = element.Next[ntx];
                           element = element.Next[ntx];

                           element.Next[ntx] = new Element();



                       }


                    }
                    break;
                }
            }

        }


        static void Main(string[] args)
        {
            //drzewo PATRICIA
            dane[0] = new string('a', 1);  // PESEL
            dane[1] = new string('a', 1);   // IMIE
            dane[2] = new string('a', 1);   //NAZWISKO

            relacje[0] = new string('a', 1);  // PESEL
            relacje[1] = new string('a', 1);  // PESEL


            //tworzymy liste (root) (1 poziom) (1 liczba z peselu) 0-9 = 10 miejsc w tablicy
            //    PatriciaTree = new Osoba[10];
            //PatriciaTree Tree = new PatriciaTree();

            //Tree.LoadDatabase();

            root = new Element(); // root
            Console.WriteLine("Dodano root ");


            Element element = new Element();
            element.subString = "90111111111";
            AddToNode(root, element);

            Element element2 = new Element();
            element2.subString = "90122222222";
            AddToNode(root, element2);

            Element element3 = new Element();
            element3.subString = "91000022220";
            AddToNode(root, element3);

            View();
            Console.ReadKey();
        }





    }

}