Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!fb:porticula NoPaste
Liste (Bugfix2)
| Uploader: |  Stueber |
| 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