Buchempfehlung
Mikrocomputertechnik mit Controllern der Atmel AVR-RISC-Familie
Mikrocomputertechnik mit Controllern der Atmel AVR-RISC-Familie
Umfassend, aber leicht verständlich führt dieses Buch in die Programmierung von ATMEL AVR Mikrocontrollern ein. [Mehr Infos...]
FreeBASIC-Chat
Es sind Benutzer im FreeBASIC-Chat online.
(Stand:  )
FreeBASIC bei Twitter
Twitter FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!

fb:porticula NoPaste

Info
Info / Hilfe
Liste
Übersicht / Liste
Neu
Datei hochladen
Suche
Quellcode suchen
Download
Dateidownload

Liste (Bugfix2)

Uploader:MitgliedStueber
Datum/Zeit:13.06.2010 19:55:55

'Verkette Listen - Thomas Stüber
'überarbeitete Version mit höherer Performence
'Die Funktionsnamen sind von QList übernommen
'Dieser Header steht unter der LGPL
'
'
'Dokumentation:
'
'Constructor()         Erzeugt entweder eine leere Liste oder eine Kopie einer anderen Liste.
'append()              Hängt ein Element an
'prepend()             Stellt ein Element vor die Liste
'insert()              Fügt ein Element an eine beliebige Stelle ein.
'replace()             Ersetzt den Wert eines Elements mit einem neuen Wert.
'at()                  Gibt den Wert am angegebenen Index zurück.
'first()               Gibt den ersten Wert in der Liste zurück.
'last()                Gibt den letzten Wert in der Liste zurück.
'mid()                 Gibt eine Teilliste von Position p mit der länge l zurück. Wenn l = -1 wird die Liste bis zum Ende zurückgegeben.
'value()               Gibt den Wert am übergebenen Index zurück. Wenn der Index ungültig ist wird der der Parameter default zurückgegeben.
'takeAt()              Gibt den Wert am übergebenen Index zurück und löscht das Element.
'takeFirst()           Gibt den Wert am Anfang der Liste zurück und löscht das Element.
'takeLast()            Gibt den Wert am Ende der Liste zurück und löscht das Element.
'move()                Bewegt ein Element vom einen Index zum anderen.
'swapItems()           Tauscht die Werte von zwei Elementen.
'removeAt()            Löscht das Element am angegebenen Index.
'removeAll()           Löscht alle Elemente mit dem angegebenen Wert.
'removeOne()           Löscht das erste Element mit dem angegebenen Wert.
'removeFirst()         Löscht das erste Element der Liste.
'removeLast()          Löscht das letzte Element der Liste.
'clear()               Löscht alle Elemente in der Liste.
'count()               Gibt die Anzahl der Elemente in der Liste zurück oder die Anzahl der Elemente mit dem angegebenen Wert.
'contains()            Gibt true zurück wenn die Liste den Wert enthält, andernfalls false
'endsWith()            Gibt true zurück wenn die Liste mit dem Wert anfängt, andernfalls false
'startsWith()          Gibt true zurück wenn die Liste mit dem Wert endet, andernfalls false
'isEmpty()             Gibt true zurück wenn count() = 0, andernfalls false
'indexOf()             Sucht den ersten Index mit dem angegebenen Wert von p aus und gibt ihn zurück.
'Operatoren: = (Vergleich), = (Zuweisung), += (Liste oder Element anhängen), <> (Vergleich)


'Hinzufügen (100000 Elemente):
' neue Liste: 0.218 s
' alte Listen: ca. 10800 s
' Verbesserung: 49541%

'Teilliste zurückgeben (50000 Elemente):
' neue Liste: 6.707 * 10^(-2) s
' alte Liste: nicht bestimmbar

'bool ist ein UDT für Wahrheitswerte und ist auch mit externen C und C++ Funktionen kompatibel










#define true 1
#define false 0


type bool
    b as byte

    declare constructor ()
    declare constructor (byval i as integer)
    declare operator let (byval i as integer)
    declare operator cast () as integer
    declare operator cast () as string
end type


constructor bool ()
    b = false
end constructor


constructor bool (byval i as integer)
    b = i
end constructor


operator bool.let(byval i as integer)
    b = i
end operator


operator bool.cast() as integer
    return b
end operator


operator bool.cast() as string
    if b = 0 then return "false"
    return "true"
end operator


operator = (byref b1 as bool, byref b2 as bool) as byte
    if b1.b = false and b2.b = false then return true
    if b1.b <> false and b2.b = false then return false
    if b1.b = false and b2.b <> false then return false
    if b1.b <> false and b2.b <> false then return true
end operator











type ListData
    nextItem as ListData ptr
    prevItem as ListData ptr
    value as string
end type





type List
    declare constructor ()
    declare constructor (byref other as list)
    declare destructor ()

    firstItem as ListData ptr
    lastItem as ListData ptr
    tempItem as ListData ptr
    tempIndex as integer
    c as integer

    declare sub append (byval d as string)
    declare sub prepend (byval d as string)
    declare sub insert (byval index as integer, byval d as string)
    declare sub replace (byval index as integer, byval s as string)

    declare function at (byval index as integer) as string
    declare function itemAt (byval index as integer) as ListData ptr
    declare function first () as string
    declare function last () as string
    declare function mid (byval p as integer, byval l as integer = -1) as list
    declare function value (byval index as integer, byref default as string) as string

    declare function takeAt (byval index as integer) as string
    declare function takeFirst () as string
    declare function takeLast () as string

    declare sub move (byval index1 as integer, byval index2 as integer)
    declare sub swapItems (byval index1 as integer, byval index2 as integer)

    declare sub clear ()
    declare sub removeAt(byval index as integer)
    declare function removeAll (byval d as string) as integer
    declare sub removeFirst()
    declare sub removeLast()
    declare function removeOne(byval d as string) as bool

    declare function contains (byval d as string) as bool
    declare function count () as integer
    declare function count(byval d as string) as integer
    declare function endsWith(byval d as string) as bool
    declare function indexOf(byval d as string, byval p as integer = 0) as integer
    declare function isEmpty() as bool
    declare function startsWith(byval d as string) as bool

    declare operator let (byref l as list)
    declare operator += (byref l as list)
    declare operator += (byval d as string)
end type



constructor List ()
    firstItem = 0
    lastItem = 0
    tempItem = 0
    tempIndex = 0
    c = 0
end constructor



constructor List (byref other as list)
    clear()
    if other.count() = 0 then exit constructor
    for i as integer = 0 to other.count()-1
        append(other.at(i))
    next
end constructor




destructor List ()
    clear()
end destructor







sub List.insert(byval index as integer, byval d as string)
    if index > c then
        print "Der Index " + str(index) + " ist zu hoch"
        print "Insert wird abgebrochen"
        exit sub
    end if

    if index < 0 then
        print "Der Index " + str(index) + " ist negativ"
        print "Insert wird abgebrochen"
        exit sub
    end if

    dim as ListData ptr new_data = new ListData
    new_data->value = d

    if index = 0 then

        dim t as ListData ptr = firstItem
        firstItem = new_data
        firstItem->nextItem = t
        if t <> 0 then t->prevItem = firstItem
        if c = 0 then lastItem = firstItem
    elseif index = c then

        dim t as ListData ptr = lastItem
        lastItem = new_data
        lastItem->prevItem = t
        if t <> 0 then t->nextItem = lastItem

    else
        dim as ListData ptr fromThis
        dim as integer richtung = 0
        dim as integer dif
        dim as integer dif1 = index, dif2 = c-index, dif3 = abs(index-tempIndex)
        if dif1 <= dif2 and dif1 <= dif3 then
            fromThis = firstItem
            richtung = 0
            dif = dif1
        elseif dif2 <= dif1 and dif2 <= dif3 then
            fromThis = lastItem
            richtung = 1
            dif = dif2
        elseif dif3 <= dif1 and dif3 <= dif2 then
            fromThis = tempItem
            if tempIndex < index then
                richtung = 0
            elseif tempIndex > index then
                richtung = 1
            elseif tempindex = index then
                richtung = -1
            end if
            dif = dif3
        end if


        if richtung = -1 then

            dim pi as ListData ptr = fromThis->prevItem
            dim ni as ListData ptr = fromThis

            if pi <> 0 then pi->nextItem = new_data
            if ni <> 0 then ni->prevItem = new_data
            new_data->prevItem = pi
            new_data->nextItem = ni

        elseif richtung = 0 then
            dim t as ListData ptr = fromThis
            if dif = 1 then
                t = t->nextItem
            else
                for i as integer = 0 to dif-1
                    t = t->nextItem
                next
            end if
            dim pi as ListData ptr = t->prevItem
            dim ni as ListData ptr = t
            if pi <> 0 then pi->nextItem = new_data
            if ni <> 0 then ni->prevItem = new_data
            new_data->prevItem = pi
            new_data->nextItem = ni

        elseif richtung = 1 then
            dim t as ListData ptr = fromThis
            if dif = 1 then
                t = t->prevItem
            else
                for i as integer = 0 to dif
                    t = t->prevItem
                next
            end if
            dim pi as ListData ptr = t
            dim ni as ListData ptr = t->nextItem
            if pi <> 0 then pi->nextItem = new_data
            if ni <> 0 then ni->prevItem = new_data
            new_data->prevItem = pi
            new_data->nextItem = ni
        end if

    end if


    c += 1
    tempIndex = index
    tempItem = new_data

end sub




sub List.replace (byval index as integer, byval s as string)
    if index > c-1 then
        print "Der Index " + str(index) + " ist zu hoch"
        print "Insert wird abgebrochen"
        exit sub
    end if

    if index < 0 then
        print "Der Index " + str(index) + " ist negativ"
        print "Insert wird abgebrochen"
        exit sub
    end if

    itemAt(index)->value = s
end sub




function List.itemAt (byval index as integer) as ListData ptr
    if index > c-1 then
        print "Der Index " + str(index) + " ist zu hoch"
        print "Insert wird abgebrochen"
        return 0
    end if

    if index < 0 then
        print "Der Index " + str(index) + " ist negativ"
        print "Insert wird abgebrochen"
        return 0
    end if

    if index = 0 then

        return firstItem

    elseif index = c-1 then

        return lastItem

    else
        dim as ListData ptr fromThis
        dim as integer richtung = 0
        dim as integer dif
        dim as integer useTemp
        dim as integer dif1 = index, dif2 = c-index, dif3 = abs(index-tempIndex)
        if dif1 <= dif2 and dif1 <= dif3 then
            fromThis = firstItem
            richtung = 0
            dif = dif1
        elseif dif2 <= dif1 and dif2 <= dif3 then
            fromThis = lastItem
            richtung = 1
            dif = dif2
        elseif dif3 <= dif1 and dif3 <= dif2 then
            fromThis = tempItem
            if tempIndex < index then
                richtung = 0
            elseif tempIndex > index then
                richtung = 1
            elseif tempindex = index then
                richtung = -1
            end if
            dif = dif3
        end if


        if richtung = -1 then
            tempIndex = index
            tempItem = fromThis
            return fromThis


        elseif richtung = 0 then
            dim t as ListData ptr = fromThis
            if dif = 1 then
                t = t->nextItem
            else
                for i as integer = 0 to dif-1
                    t = t->nextItem
                next
            end if

            tempIndex = index
            tempItem = t
            return t

        elseif richtung = 1 then
            dim t as ListData ptr = fromThis
            if dif = 1 then
                t = t->prevItem
            else
                for i as integer = 0 to dif-2
                    t = t->prevItem
                next
            end if


            tempIndex = index
            tempItem = t
            return t
        end if

    end if

end function




function List.at(byval index as integer) as string
    dim as ListData ptr t = itemAt(index)
    if t = 0 then exit function
    return t->value
end function




function List.value(byval index as integer, byref default as string) as string
    if index > c-1 then
        return default
    end if

    if index < 0 then
        return default
    end if
    dim as ListData ptr t = itemAt(index)
    if t = 0 then exit function
    return t->value
end function




function List.first() as string
    if c = 0 then exit function
    return firstItem->value
end function




function List.last() as string
    if c = 0 then exit function
    return lastItem->value
end function




function List.mid(byval p as integer, byval l as integer) as list
    if p > c-1 then
        print "Der Index " + str(p) + " ist zu hoch"
        print "Insert wird abgebrochen"
        return list
    end if

    if p < 0 then
        print "Der Index " + str(p) + " ist negativ"
        print "Insert wird abgebrochen"
        return list
    end if

    dim as list t
    if l = -1 then l = c-p

    if l+p-1 > c-1 then
        print "Der Index " + str(l+p-1) + " ist zu hoch"
        print "Insert wird abgebrochen"
        return list
    end if

    if l+p-1 < 0 then
        print "Der Index " + str(l+p-1) + " ist negativ"
        print "Insert wird abgebrochen"
        return list
    end if


    for i as integer = p to l+p-1
        t.append(at(i))
    next
    return t
end function




sub List.append(byval d as string)
    insert(c,d)
end sub




sub List.prepend(byval d as string)
    insert(0,d)
end sub




sub List.move (byval index1 as integer, byval index2 as integer)
    dim as string s = at(index1)
    removeAt(index1)
    insert(index2,s)
end sub




sub List.swapItems (byval index1 as integer, byval index2 as integer)
    dim as string s1 = at(index1)
    dim as string s2 = at(index2)
    replace(index2,s1)
    replace(index1,s2)
end sub




sub List.clear()
    dim t as ListData ptr = firstItem
    dim t2 as ListData ptr = firstItem
    for i as integer = 0 to c-1
        t2 = t->nextItem
        delete t
        t = t2
        c -= 1
    next
end sub




sub List.removeAt(byval index as integer)
    if index > c-1 then
        print "Der Index " + str(index) + " ist zu hoch"
        print "Insert wird abgebrochen"
        exit sub
    end if

    if index < 0 then
        print "Der Index " + str(index) + " ist negativ"
        print "Insert wird abgebrochen"
        exit sub
    end if

    dim as ListData ptr t = itemAt(index)
    dim as ListData ptr ni = t->nextItem
    dim as ListData ptr pi = t->prevItem
    if ni <> 0 then ni->prevItem = pi
    if pi <> 0 then pi->nextItem = ni

    c -= 1
    if ni <> 0 then
        tempItem = ni
        tempIndex = index
    elseif pi <> 0 then
        tempItem = pi
        tempIndex = index-1
    else
        tempItem = 0
        tempIndex = 0
    end if

    if index = 0 then firstItem = ni
    if index = c then lastItem = pi
    if c = 0 then
        firstItem = 0
        lastItem = 0
        tempItem = 0
        tempIndex = 0
        c = 0
    end if
    delete t
end sub




function List.removeAll(byval d as string) as integer
    dim as integer i = 0
    dim as integer r = 0
    do
        i = indexOf(d)
        if i <> -1 then
            removeAt(i)
            r += 1
        else
            exit do
        end if
    loop
    return r
end function




function List.removeOne(byval d as string) as bool
    dim as integer index = indexOf(d)
    if index = -1 then return false
    removeAt(index)
    return true
end function




function List.contains(byval d as string) as bool
    dim t as ListData ptr = firstItem
    for i as integer = 0 to c-1
        if d = t->value then return true
        t = t->nextitem
    next
    return false
end function




function List.count() as integer
    return c
end function




function List.count(byval d as string) as integer
    dim t as ListData ptr = firstItem
    dim n as integer = 0
    for i as integer = 0 to c-1
        if d = t->value then n += 1
        t = t->nextitem
    next
    return n
end function




function List.endsWith(byval d as string) as bool
    if c = 0 then return false
    if lastItem->value = d then return true
    return false
end function




function List.isEmpty() as bool
    if c = 0 then return true
    return false
end function




function List.indexOf(byval d as string, byval index as integer) as integer
    dim as ListData ptr t = firstItem
    for i as integer = index to c-1-index
        if d = t->value then return i
        t = t->nextitem
    next
    return -1
end function




function List.startsWith(byval d as string) as bool
    if c = 0 then return false
    if firstItem->value = d then return true
    return false
end function




function List.takeAt (byval index as integer) as string
    dim as string s = at(index)
    removeAt(index)
    return s
end function




function List.takeFirst () as string
    dim as string s = at(0)
    removeAt(0)
    return s
end function




function List.takeLast () as string
    dim as string s = at(c-1)
    removeAt(c-1)
    return s
end function




operator List.let(byref l as list)
    clear()
    if l.count() = 0 then exit operator
    for i as integer = 0 to l.count()-1
        append(l.at(i))
    next
end operator




operator List.+=(byref l as list)
    if l.count() = 0 then exit operator
    for i as integer = 0 to l.count()-1
        append(l.at(i))
    next
end operator




operator List.+=(byval d as string)
    append(d)
end operator




operator + (byref l1 as list, byref l2 as list) as list
    dim as list l
    for i as integer = 0 to l1.count()-1
        l.append(l1.at(i))
    next
    for i as integer = 0 to l2.count()-1
        l.append(l2.at(i))
    next
    return l
end operator




operator = (byref l1 as list, byref l2 as list) as bool
    if l1.c <> l2.c then return false
    for i as integer = 0 to l1.c-1
        if l1.at(i) <> l2.at(i) then return false
    next
    return true
end operator




operator <> (byref l1 as list, byref l2 as list) as bool
    if l1.c <> l2.c then return true
    for i as integer = 0 to l1.c-1
        if l1.at(i) <> l2.at(i) then return true
    next
    return false
end operator