Книга е още в много ранна фаза на написване

Сортиране

Един проблем при писането на родов код е, че сортирането е специфично за ти­па на сортираните неща. Разбира се, един подход е да се напише отделен метод за сортиране за всеки отделен тип, но би трябвало вече да можете да кажете, че то­ва няма да доведе до лесен за повторно използване с други типове код.

Основна задача на проектирането на програми е да се “разделят нещата които се променят от тези които остават същите,” а тука кодът който остава същия е об­щия сортиращ алгоритъм, променят се нещата, които има да се сортират. Та­ка че вместо да се кодира твърдо алгоритъмът в множество сортиращи про­гра­ми ще се използва техниката на callback. С техниката на обратното извикване ко­дът който се променя се запечатва (капсулире) в негов собствен клас, а част­та от кода която остава същата го вика обратно при нужда. По този начин може да се направят различни обекти да изразяват различни начини на кодиране, а да се захравят от един и същ код.

Следващият interface описва как да се сравняват два обекта, капсулирайки с то­ва “нещата които се променят” за този конкретен проблем:

//: c08:Compare.java

// Interface for sorting callback:

package c08;
interface Compare {

boolean lessThan(Object lhs, Object rhs);

boolean lessThanOrEqual(Object lhs, Object rhs);

} ///:~

Един подклас на ArrayList може да създадем който да реализира Quicksort чрез Compare. Алгоритъмът, който е известен заради скоростта си, няма да бъде обяс­няван тук. За подробности виж Practical Algorithms for Programmers, от Binstock & Rex, Addison-Wesley 1995.

//: c08:SortList.java

// A generic sorting list

package c08;

import java.util.*;

private Compare compare; // To hold the callback

public SortList(Compare comp) {

compare = comp;

}

public void sort() {

}

private void quickSort(int left, int right) {

Object o1 = get(right);

int i = left - 1;

int j = right;

while(true) {

while(compare.lessThan(

get(++i), o1))

;

while(j > 0)

get(--j), o1))

break; // out of while

if(i >= j) break;

swap(i, j);

}

swap(i , right);

quickSort(i+1, right);

}

}

private void swap(int loc1, int loc2) {

set(loc1, get(loc2));

set(loc2, tmp);

}

} ///:~

За да се използва SortList трябва да се създаде клас реализиращ Compare за ви­да обекти които ще сортирате. Това е място където вътрешен клас не е ос­нов­но­то нещо, но може да подобри организацията на кода. Ето пример за String обек­ти:

//: c08:StringSortTest.java

// Testing the generic sorting ArrayList

package c08;

import java.util.*;

static class StringCompare implements Compare {

public boolean lessThan(Object l, Object r) {

return ((String)l).toLowerCase().compareTo(

((String)r).toLowerCase()) < 0;

}

public boolean

return ((String)l).toLowerCase().compareTo(

((String)r).toLowerCase()) <= 0;

}

}

SortList sv =

new SortList(new StringCompare());

sv.add("d");

sv.add("A");

sv.add("C");

sv.add("c");

sv.add("b");

sv.add("B");

sv.add("D");

sv.add("a");

sv.sort();

Iterator e = sv.iterator();

while(e.hasNext())

System.out.println(e.next());

}

} ///:~

Може да се види как, щом веднъж е създадена работнагта рамка, лесно може да се използва повторно код като този – просто пишете клас който капсулира “не­ща­та които се променят” и давате обекта на SortList.

Сравнението прави стринговете в долен регистър, така че голямо A се нарежда до малко a и не заема някакво отделно място. Този пример показва, обаче, мал­ка недостатъчност на този подход, а именно нарежда малките и големи раз­но­вид­ности на една буква по реда на появяването им: A a b B c C d D. Това обик­но­вено не е голям проблем, понеже обикновено се работи с по-дълги стрингове и ефектът не проличава. (Колекциите на Java 2 дава функционалност на стрин­го­вете която решава този проблем.)

Наследяването (extends) е използвано тука за създаване на нов тип от ArrayList – тоест, SortList е ArrayList с добавена функционалност. Из­полз­ва­не­то на наследяване тук е мощен метод, но поражда проблеми. Оказва се, че ня­кои методи са final (описано в глава 7), токо че не може да се подтиснат. Ако ис­кате да създадете сортиран ArrayList който приема и поражда само String обек­ти удряте на камък, понеже add( ) и elementAt( ) са final, а точно те са ме­то­дите които трябва да се подтиснат, за да приемат само String обекти. Няма къс­мет тука.

От друга страна, да видим с композиция: слагането на обект вътре в нов клас. На­место да пренаписваме горния код за да изпълним това, може просто да из­полз­ваме SortList вътре в новия клас. В този случай вътрешният клас за реа­ли­зация на Compare ще бъде създаден анонимно:

//: c08:StrSortList.java

// Automatically sorted ArrayList that

// accepts and produces only Strings

package c08;

import java.util.*;

private SortList v = new SortList(

// Anonymous inner class:

new Compare() {

public boolean

lessThan(Object l, Object r) {

return

((String)l).toLowerCase().compareTo(

}

public boolean

return

((String)r).toLowerCase()) <= 0;

}

}

);

public void add(String s) {

v.add(s);

sorted = false;

}

public String get(int index) {

v.sort();

sorted = true;

}

return (String)v.get(index);

public Iterator iterator() {

if(!sorted) {

v.sort();

sorted = true;

}

return v.iterator();

// Test it:

public static void main(String[] args) {

StrSortList sv = new StrSortList();

sv.add("d");

sv.add("A");

sv.add("C");

sv.add("c");

sv.add("b");

sv.add("B");

sv.add("D");

sv.add("a");

Iterator e = sv.iterator();

while(e.hasNext())

System.out.println(e.next());

}

} ///:~

Предимството на този дизайн е че ще взема само String обекти и ще произ­веж­да само String обекти и проверката става по време на компилация а не по време на изпълнението. Разбира се това се отнася само за add( ) и elementAt( ); elements( ) все още дава Iterator който няма определен тип по време на ком­пи­ла­ция. Проверката на типа за Iterator и в StrSortList се прави, разбира се, това ста­ва по време на изпълнение и се изхвърля изключение ако нещо не е наред. То­ва е цената: установявате ли нещо със сигурност по време на компилация или вероятно по време на изпълнение? (Тоест, “вероятно не когато тествате ко­да” и “вероятно когато потребителят прави нещо, с което не сте тествали.”) Ка­то имате възможностите за избор и суматохата, по-лесно е да използвате на­сле­дя­ване и да издържите на кастинга – още веднъж, ако параметризирани типове се добавят към Java някой ден те ще решат този проблем.

Може да се види че в този клас има флаг наречен sorted. Бихте могли да сор­ти­ра­те ArrayList всеки път когато се вика add( ) и той винаги ще се поддържа сор­ти­ран. Но обикновено се добавят множество елементи към ArrayList преди за­поч­ване на четенето му. Така сортирането след всеки add( ) ще бъде по-малко ефек­тивно отколкото дза се изчака някой да иска да чете ArrayList и тога ва да се сортира, както е направено тук. Техниката на отлагане на даден процес до­ка­то той стане абсолютно необходим се нарича мързеливо изчисление. (Има ана­ло­гична техника наречена мързелива инициализация която чака дадено поле да ста­не необходимо за използване, та тогава го инициализира.)