// project created on 04.04.2006 at 22:51
//#define DEBUG_MSG

using System;
using System.IO;

class MP3Rec
    {
    public MP3Rec  Next;
    public MP3Rec  Prev;    // nur in DLL verwendet
    public string Interpret;
    public string Titel;
    public string Album;
    public string Path;
    public int nkBitRate;
    public int nNum;
    }

class MP3Ref
    {
    public MP3Ref  Next;
    public MP3Rec  Payload;
    }

class MainClass
    {
    // Konstanten
    const string INFILE_PATH = "/home/cbx/FH/SE_2006_SS/web/mp3liste_unsorted_web.txt";

    public enum StorageMode {SingleUnsorted, SingleSorted, DoubleUnsorted, DoubleSorted, BinaryTree};

    // schmutzige Member
    static int nCounter = 0;
    static int nTreeLimit = 0;

//*********************************************************************
// Main()

    public static void Main(string[] args)
        {
        MP3Rec HeadSllUnsorted = new MP3Rec();
        MP3Rec HeadSllSorted   = new MP3Rec();
        MP3Rec HeadTree        = new MP3Rec();

        int nRecords;
        DateTime startTime, stopTime;
        TimeSpan duration;
        
        Console.WriteLine("The MP3-DB");
        
        startTime = DateTime.Now;
        
        nRecords = MP3FileListRead(HeadSllUnsorted, INFILE_PATH, StorageMode.SingleUnsorted);
        stopTime = DateTime.Now;
        duration = stopTime - startTime;
        Console.WriteLine("Read and enqueued {0} Records in {1} Seconds.",nRecords, duration.TotalSeconds);
/*      
        startTime = DateTime.Now;
        nRecords = MP3FileListRead(HeadSllSorted, INFILE_PATH, StorageMode.SingleSorted);
        stopTime = DateTime.Now;
        duration = stopTime - startTime;
        Console.WriteLine("Read and sorted {0} Records in {1} Seconds.",nRecords, duration.TotalSeconds);
*/
        startTime = DateTime.Now;
        nRecords = MP3FileListRead(HeadTree, INFILE_PATH, StorageMode.BinaryTree  );
        stopTime = DateTime.Now;
        duration = stopTime - startTime;
        Console.WriteLine("Read and treesorted {0} Records in {1} Seconds.",nRecords, duration.TotalSeconds);
    
        Console.WriteLine("\n***********************************\n");
                
        // herzeigen...?
/*
        MP3ListTraverseShow(HeadSllSorted, 50);
        MP3ListTraverseCount(HeadSllUnsorted);      
        MP3TreeTraverseShow(HeadTree.Next, 50);
*/
        MP3ListTraverseAdvanced(HeadSllUnsorted);
        MP3ListTraverseFindDups(HeadSllUnsorted);
        }
        
//*********************************************************************
// Das gesamte File einlesen
    public static int MP3FileListRead(MP3Rec Head, string strFile, StorageMode Mode)
        {
        StreamReader inStream;
        int nRecsRead = 0;
        MP3Rec Cur = Head;
        
        if (StorageMode.BinaryTree == Mode)
            Cur = Head.Next;
        
        try 
            {
            inStream = new StreamReader(strFile);
            // Titelzeile ignorieren
            inStream.ReadLine();
            
            MP3Rec listRec;

            nCounter = 0;
            
            while ((listRec = MP3RecordRead(inStream)) != null)
                {
                nRecsRead++;
                switch (Mode)
                    {
                    case StorageMode.SingleUnsorted: 
                        Cur = MP3ListEnqueueTail(Head,Cur,listRec);
                        break;

                    case StorageMode.SingleSorted:  
                        Cur = MP3ListEnqueueSortTitle(Head,Cur,listRec,StorageMode.SingleSorted);
                        break;

                    case StorageMode.BinaryTree: 
                        Cur = MP3TreeInsertSortTitle(Cur,listRec);
                        break;
                        
                    }
                    
#if DEBUG_MSG
                // damit mer net ersaufen...
                if (nRecsRead > 20) break;
#endif
                }
            }
        // einzig handelbarer Fall: Das file gibts nicht => schulfrei!  
        catch (FileNotFoundException ex)
            {
            Console.WriteLine("File not found...");
            return 0;
            }
        
        inStream.Close();

        if (StorageMode.BinaryTree == Mode)
            Head.Next = Cur;
                
        Console.WriteLine("This took {0} Node accesses to enqueue {1} Records", nCounter, nRecsRead);
        return nRecsRead;   
        }

//*********************************************************************
// Einfach am Arsch der Liste anhängen und den neuen Arsch zurückgeben 
    public static MP3Rec MP3ListEnqueueTail(MP3Rec Head, MP3Rec Tail, MP3Rec New)
        {
        Tail.Next = New;
        New.Next  = null;
        nCounter++;
        return New;
        }

//*********************************************************************
// Nach Titel sortiert in die liste hängen 
    public static MP3Rec MP3ListEnqueueSortTitle(MP3Rec Head, MP3Rec Tail, MP3Rec New, StorageMode Mode)
        {
        MP3Rec Cur, Prev;

#if DEBUG_MSG
        Console.WriteLine("Enqueuing {0}", New.Titel);      
#endif

        // Sonderfall ganz Leere Liste: Der erste node darf unconditional dran
        if (Head.Next == null)
            {
            Head.Next = New;
            New.Next  = null;

#if DEBUG_MSG
            Console.WriteLine("Enqueued {0} in empty List", New.Titel);     
#endif
            nCounter++;
            return New;
            }

        // Regulärer Fall: nicht leere Liste
        // Von vorne durch die Liste gehen und dort wo wir nicht mehr kleiner sind, einsortieren 
        for ( Cur = Head.Next, Prev = Head ; Cur != null ; Cur = Cur.Next )
            {
            // einen Zugriff zählen
            nCounter++;

            // vergleichen, ob der aktuelle Node hinter dem neuen kommt
            if (String.Compare (Cur.Titel.ToLower(), New.Titel.ToLower(), true ) > 0)
                {
                // dann davor einsortiern. Gut dass wir den um eins nacheilenden <Prev> haben!
                // zwei mal umbiegen
                Prev.Next = New; // mich selbst beim Vordermann eintragen
                New.Next  = Cur; // Und den aktuellen als meinen Nachfolger
#if DEBUG_MSG
                Console.WriteLine("Enqueued {0} before {1}", New.Titel, Cur.Titel );        
#endif
                break;
                }
            else
                {
                // sonst wars nix
#if DEBUG_MSG
                Console.WriteLine("Compared {0} to {1}", New.Titel, Cur.Titel );        
#endif
                }               

            // schon am Ende? Am Ende anhängen
            if (Cur.Next == null)   
                {
                New.Next = Cur.Next;
                Cur.Next = New;
                        
#if DEBUG_MSG
                Console.WriteLine("Enqueued {0} as Tail", New.Titel);       
#endif
                break; 
                }
                
                
            // Der lauft eins hinterher 
            Prev = Cur; 
            }

#if DEBUG_MSG
        Console.WriteLine("Successfully Enqueued {0}.", New.Titel);     
#endif
        return New;
        }

//*********************************************************************
// in eine Baumstruktur einhängen.  
    public static MP3Rec MP3TreeInsertSortTitle(MP3Rec Root, MP3Rec New)
        {
        
        nCounter++;
        
        if (Root != null)
            {
            // vergleichen, ob der aktuelle Node hinter dem neuen kommt
            if (String.Compare (Root.Titel, New.Titel, true ) > 0)
                {
                // einen linken Subbaum
                Root.Prev = MP3TreeInsertSortTitle(Root.Prev, New);
                }
            else
                {
                // einen rechten Subbaum
                Root.Next = MP3TreeInsertSortTitle(Root.Next, New);
                }
            // Neue Wurzel ist der Subbaum
            return Root;
            }
        else
            {
            // Neue Wurzel ist der neue Block
            return New;
            }     
        }


//*********************************************************************
// Einen Datensatz einlesen...
    public static MP3Rec MP3RecordRead(StreamReader inStream)
        {
        string strLine = inStream.ReadLine();
        
        if (strLine != null)
            {
            string[] strParts = strLine.Split('\t');
            MP3Rec readRec = new MP3Rec();

            readRec.Next      = null;
            readRec.Prev      = null;

            readRec.Interpret = strParts[0].Trim('"').TrimStart(' ','_');
            readRec.Titel     = strParts[1].Trim('"').TrimStart(' ','_');
            readRec.Album     = strParts[2].Trim('"').TrimStart(' ','_');
            readRec.Path      = strParts[4].Trim('"').TrimStart(' ','_');
            
            if (strParts[3].Length > 3)
                readRec.nkBitRate = Convert.ToInt32( strParts[3].Trim('"').Split('k','K')[0] );
            else        
                readRec.nkBitRate = 128;
            return readRec;
            }
        else
            return null;
        } 

//*********************************************************************
    public static void MP3TreeTraverseShow(MP3Rec Root, int nMenge)
        {
        // gaaaanz brutale Abbruchmethode
        if (nTreeLimit > nMenge)
            return;
        
        if (Root != null)
            {
            MP3TreeTraverseShow(Root.Prev, nMenge);
            Console.WriteLine("\"{0}\"\tby >{1}<\tfrom \"{2}\"\tat {3}kBps",
                                Root.Titel, Root.Interpret,
                                Root.Album, Root.nkBitRate );
            nTreeLimit++;
            MP3TreeTraverseShow(Root.Next, nMenge);
            }
        }

//*********************************************************************
    public static void MP3ListTraverseShow(MP3Rec Head, int nMenge)
        {
        int i=0;
        
        for ( MP3Rec Cur = Head.Next ; Cur != null; Cur = Cur.Next )
            {
            Console.WriteLine("\"{0}\"\tby >{1}<\tfrom \"{2}\"\tat {3}kBps",
                                Cur.Titel, Cur.Interpret,
                                Cur.Album, Cur.nkBitRate );
            if ( nMenge > 0 )
                if (++i >= nMenge)
                    break;
            }
        }

//*********************************************************************
    public static void MP3ListTraverseCount(MP3Rec Head)
        {
        int nSongs192k = 0;
        int nSongsWithLove = 0;
        int nSongsWithLiebe = 0;
        int nRate;
        int[] anBitraten = new int[325];
        
        for ( MP3Rec Cur = Head.Next ; Cur != null; Cur = Cur.Next )
            {
            if (Cur.nkBitRate == 192)
                nSongs192k++;
            
            if (Cur.Titel.ToUpper().IndexOf("LOVE") >= 0)
                {
                nSongsWithLove++;
                Console.WriteLine("LOVE #{1} ==> >>{0}<<", Cur.Titel, nSongsWithLove );
                }

            if (Cur.Titel.ToLower().IndexOf("liebe") >= 0)
                nSongsWithLiebe++;
            
            nRate = Cur.nkBitRate;  
            if (nRate < 64)
                nRate = 63;
            else if (nRate > 320)
                nRate = 321;
            
            anBitraten[nRate]++;
            }

        Console.WriteLine("\nUnd hier die Auswertung:\n");
        Console.WriteLine("Es sind {0} Songs mit 192kBps, {1} Songs mit \"love\" und {2} Songs mit \"Liebe\"\n",
                            nSongs192k, nSongsWithLove, nSongsWithLiebe );

        Console.WriteLine("Es sind {0} Songs unter 64kBps",anBitraten[63]);

        for (int nBitrate = 64; nBitrate <= 320 ; nBitrate++)
            {
            if (anBitraten[nBitrate] > 0)
                {
                Console.WriteLine("Es sind {0} Songs mit {1}kBps",anBitraten[nBitrate],nBitrate);
                }
            }
        Console.WriteLine("Es sind {0} Songs über 320kBps",anBitraten[321]);
        }

//*********************************************************************
// Die erweiterten Analysen...

    public static void MP3ListTraverseAdvanced(MP3Rec Head)
        {
        MP3Rec Prev, Comp;
        MP3Rec AlbumList  = new MP3Rec();
        MP3Rec ArtistList = new MP3Rec();
        
        int nAlben   = 0;
        int nArtists = 0;
        
        int nAlbumTraverse, nArtistTraverse;
        
        nAlbumTraverse = nArtistTraverse = 0;
        
        // simple Variante: Die Liste traversieren und jeden Eintrag mit der Albenliste vergleichen.
        // sWenn das Album schon in der Liste steht, abbrechen, sonst, wenn die Suchschleife terminiert 
        // hat anhängen.
        for ( MP3Rec Cur = Head.Next ; Cur != null; Cur = Cur.Next )
            {
            for ( Prev = AlbumList, Comp = AlbumList.Next ; Comp != null; Prev = Comp, Comp = Comp.Next )
                {
                nAlbumTraverse++;
                if (Comp.Album.ToLower() == Cur.Album.ToLower())
                    break;  
                }
                
            if (Comp == null)
                {
                Comp = new MP3Rec();
                Comp.Album = Cur.Album;
                Prev.Next = Comp;
                nAlben++;
                }
            }
            
        // siehe oben
        for ( MP3Rec Cur = Head.Next ; Cur != null; Cur = Cur.Next )
            {
            for ( Prev = ArtistList, Comp = ArtistList.Next ; Comp != null; Prev = Comp, Comp = Comp.Next )
                {
                nArtistTraverse++;
                if (Comp.Interpret.ToLower() == Cur.Interpret.ToLower())
                    break;  
                }
                
            if (Comp == null)
                {
                Comp = new MP3Rec();
                Comp.Interpret = Cur.Interpret;
                Prev.Next = Comp;
                nArtists++;
                }
            }


        Console.WriteLine("\n *********** Alben ***********");
        for ( MP3Rec Cur = AlbumList.Next ; Cur != null; Cur = Cur.Next )
            {
            Console.Write("\"{0}\"\t", Cur.Album );
            }

        Console.WriteLine("\n *********** Interpreten ***********");
        for ( MP3Rec Cur = ArtistList.Next ; Cur != null; Cur = Cur.Next )
            {
            Console.Write("\"{0}\"\t", Cur.Interpret  );
            }
            
        Console.WriteLine();
        Console.WriteLine("Das sind {0} Alben mit     {1} Traversierungen", nAlben, nAlbumTraverse);
        Console.WriteLine("     und {0} Künstler mit  {1} Traversierungen", nArtists, nArtistTraverse);
        
        }
        
//*********************************************************************************
// Duplikate suchen
        
        
    public static void MP3ListTraverseFindDups(MP3Rec Head)
        {
        MP3Rec Comp;
        MP3Ref DupList    = new MP3Ref();
        
        int nDups    = 0;
        int nDupCt   = 0;
        int nDupTraverse = 0;
        
        /*
        hier mehrfach was Neues: Wir bauen eine SLL 
        mit Referenzen auf die Originalknoten auf.
        Die Hauptliste linear traversieren und ab dem 
        gerade aktuellen Knoten vorwärts auf "gleiche"
        Titel scannen. Wenn ein Duplikat gefunden wurde, 
        als gefunden markieren durch nNum != 0. 
        Diese Elemente werden bei den weiteren Suchen 
        übersprungen. Alle gefundenen Duplikate werden in 
        DupList speichersparend nur referenziert.
        */
        MP3Ref DupCur = DupList;
        for ( MP3Rec Cur = Head.Next ; Cur != null; Cur = Cur.Next, nDupCt++)
            
            {
            // wenns noch nicht getaggt wurde
            if (Cur.nNum == 0)
                {
                // ab dem aktuellen Knoten nach hinten.
                for ( Comp = Cur.Next ; Comp != null; Comp = Comp.Next )
                    {
                    nDupTraverse++;
                    // ist ja schon lowercase
                    if (Comp.Titel.ToLower() == Cur.Titel.ToLower())        
                        {
                        // Duplikat zählen
                        nDups++;
                        
                        // dann in die Auswerteliste einhängen
                        // wenn der Ausgangsknoten auch 
                        // noch nicht erfasst wurde
                        if (Cur.nNum == 0)
                            {
                            DupCur.Next = new MP3Ref();
                            DupCur.Next.Payload = Cur;
                            DupCur = DupCur.Next;
                            }

                        DupCur.Next = new MP3Ref();
                        DupCur.Next.Payload = Comp;
                        DupCur = DupCur.Next;
                        
                        // Knoten als bereits erfasst markieren...
                        Comp.nNum = Cur.nNum = nDupCt;
                        
                        }
                    }
                }
            }

        Console.WriteLine("\n *********** Duplikate ***********");
        for ( MP3Ref Cur = DupList.Next ; Cur != null; Cur = Cur.Next )
            {
            Console.WriteLine("\"{0}\" von {1} auf {2}", 
                              Cur.Payload.Titel,
                              Cur.Payload.Interpret, Cur.Payload.Path  );
            }
            
        Console.WriteLine();
        Console.WriteLine("Es gibt {0} Mehrfache mit {1} Traversierungen", 
                          nDups, nDupTraverse);
        
        }       
    } //class

syntax highlighted by Code2HTML, v. 0.9.1