Permalink
Reply
Merhaba,
Geçen hafta çok temel olan dizgeler için, çok da gereksiz bir sarmalayıcı yazmıştık ama bugün daha da temel olan ve Türkçe bağlı liste olarak çevrilen konuya girelim dedim. Hem de en en basitinden ve dairesel bir açıyla dalış yapacağız! Buna eski ile yeninin (D ranges) buluşması adını veriyorum:
Koda buyrun, balıklamasına... 😀
struct CircularList(Node) // v1.1 for D Class
{
private Node items, root;
size_t length;
string toString() const {
import std.format: format;
return format("CircularList(%s[%s], %s)",
Type.stringof, length, root);
}
alias Type = typeof(Node.CLL);
void push(Type value) {
if(isEmpty) {
items = new Node(value, null);
root = items;
} else {
items.link = new Node(value, root);
popFront();
}
++length;
}
auto isEmpty() {
return !items;
}
/********************** Input Range Functions */
enum empty = false;
auto front() { return items.link.CLL; }
void popFront() { items = items.link; }
/* (InputRange) */
}
Bugün şu başlığa denk geldim, bu işler bu kadar zor olmamalı dedim kendi kendime. Önce UniversalAdaptor ve sonrası daha da basit olan CircularList ortaya çıktı. Eğer kendi türünüze CLL takma ismi ve link işaretçisi (dikkat, sınıflar referans türü olduğu için * işareti kullanmadım) dahil ederseniz, bunu basitçe kullanabilirsiniz. Örneğin MyString sınıfı için bu kadar basit:
class MyString
{ // Circular Linked List --v
string data; alias CLL = data;
MyString link;
this(string s, MyString n = null) {
data = s;
link = n;
}
// ...
Tabi Node olarak bildirilen tür bir yapı olsaydı açık bir şekilde * işareti kullanmanız gerekiyor. Onun da çözümü kısmen şu (v1.2) olabilir:
struct CircularList(Node) // v1.2 for D
{
static if(is(Node == struct))
{
private Node * items, root;
}
else static if(is(Node == class))
{
private Node items, root;
}
else static assert(0, "\nIt's not a container!");
//..
Tam burada Ali hocama bir soru:
Kodu, static if'ler (sadece class ve struct) ile kısıtladığımızda, derleyici önce alias'ların token'nını çözdüğü için şu test assert'e uğramıyor:
void main() {
enum Test { none }
CircularList!Test itsnotacontainer;
}
Ama bu testi başarıyla, yani hata mesajıyla geçiyor:
void main() {
enum Test { CLL }
CircularList!Test itsnotacontainer;
}
Neyse, kodları parça parça verdim ama merak edenler, class/struct ayırt edilmeksizin şöyle çalıştırabilir:
struct CircularList(Node) // v1.2 for D
{
static if(is(Node == struct))
{
private Node * items, root;
}
else static if(is(Node == class))
{
private Node items, root;
}
else static assert(0, "\nIt's not a container!");
size_t length;
string toString() const
{
import std.format: format;
return format("CircularList(%s[%s], %s)",
Type.stringof, length, root);
}
alias Type = typeof(Node.CLL);
void push(Type value)
{
if(isEmpty)
{
items = new Node(value, null);
root = items;
}
else
{
items.link = new Node(value, root);
popFront();
}
++length;
}
auto isEmpty()
{
return !items;
}
/********************** Input Range Functions */
enum empty = false;
auto front() { return items.link.CLL; }
void popFront() { items = items.link; }
/* (InputRange) */
}
class Bar
{
size_t number; alias CLL = number;
Bar link;
this(size_t number, Bar link = null)
{
this.number = number;
this.link = link;
}
}
struct Foo
{
size_t number; alias CLL = number;
Foo * link = null;
}
void main()
{
CircularList!Bar bar;
CircularList!Foo foo;
foreach(n; 10..16)
{
bar.push(n);
foo.push(n);
}
import std.range : take;
import std.stdio : writeln;
bar.take(8).writeln(": ", bar);
foo.take(8).writeln(": ", foo);
}
Geçen haftaki örnek MyString için ise şöyle:
void main() {
auto merhaba = new MS("Merhaba");
auto sana = new MS("sana");
auto ey = new MS("ey");
auto kelimeler = [ merhaba, sana, ey ];
CircularList!MS test;
foreach(kelime; kelimeler)
{
kelime ~= " ";/*
kelime.writeln;//*/
test.push(kelime.data);
}
test.take(5).writeln;
} /* ÇIKTISI:
["Merhaba ", "sana ", "ey ", "Merhaba ", "sana "]
*/
Burada bir diğer husus, aynı şeyleri referans türü olan class ile değil de struct ile yaparsanız farklı sonuçlar alırsınız. Çünkü taa başta, kelimeler oluşturulurken tek nesne var ve kopyaları alınmıyor. O yüzden bir satırda kelime sonuna boşluk eklenirken, diğer satırda aynı nesneye işaret eden başka bir liste kurabiliyor (push satırı) ve kelimeler dizisi dahil her yerde aynı veri işaret ediliyor. Eee tabi aynı sonucu şöyle de elde edebilirdik:
kelimeler.cycle.take(5).writeln;
// [Merhaba , sana , ey , Merhaba , sana ]
Ancak bağlı listeler ile de çalışmak güzel çünkü aynı yapıya link'leri bölen veya çıkaran başka işlevler yazabilir ya da bölünen/çıkarılan yere başka listelerin düğümlerini ekleyebilir ya da birden fazla roots[] ile listenin istediğiniz yerine çapa (anchor) atabilirsiniz.
Sıralama algoritmaları dahil birçok ikili listelerde kullanılan bu teknikler, yerine göre dizilerden daha hızlı sonuç verebilmektedir.
Başarılar...
