Генеричке класе – решен пример¶

Користећи генеричке класе из библиотеке, можемо једноставно да направимо своје апстрактне типове података, прилагођене потребама проблема који решавамо.

Пример: Написати генеричку класу CollectionWithCursor<T>, која симулира колекцију података одређеног типа. Класа функционише као да се унутар колекције користи курсор, који омогућава убацивање нових и избацивање постојећих елемената из колекције само на позицији курсора. Конкретније, класа треба да садржи следеће јавне методе:

• void Insert(T x) за убацивање елемента на позицији курсора, који остаје иза елемента,

• void Backspace() за брисање елемента пре курсора,

• void Delete() за брисање елемента после курсора,

• void GoLeft() за померање курсора за једно место лево, и

• void GoRight() за померање курсора за једно место десно.

Поред набројаног, треба омогућити кориснику да очита тренутни број елемената у колекцији (својство Count), позицију курсора (својство CursorPosition) и вредност сваког елемента (индексер). Довољно је да својства и индексер имају само приступник get. Сложеност сваке операције треба да је у просеку \(O(1)\).

Написати и програм који демонстрира функционалност класе.

Приметимо најпре да употреба листе (List<T>) за смештање елемената колекције не би била ефикасно решење, јер уметање на средини или на почетку листе није брза операција.

Да би уметање и брисање било ефикасно, можемо да користимо повезану листу (LinkedList<T>), која пружа све што је потребно за имплементацију описане класе. Решење базирано на класи LinkedList би било својеврстан омотач (енгл. wrapper) око повезане листе, који редукује њен интерфејс. Конкретније, уметање и брисање не би било дозвољено код било ког елемента листе (што повезана листа иначе може ефикасно да изведе), већ само на позицији курсора.

О редукцији интерфејса:

Када смо стек имплементирали помоћу листе, такође смо редуковали интерфејс употребљене класе. Наиме, листа омогућава многе операције које стек не подржава (очитавање и мењање било ког елемента, уметање или избацивање на било којој позицији, итд). Неке од тих операција су ефикасне, а неке и нису.

У општем случају, редукција интерфејса може да се врши из следећих разлога:

• да поједностави употребу класе кориснику, остављајући му само ону функционалност која му је довољна, не замарајући га оним што му је сувишно (концепт апстракције);

• да олакша читање кода, јер употреба класе – омотача са смањеном функционалношћу појашњава њену намену, односно начин употребе;

• да олакша касније побољшавање имплементације, јер сакривањем кориснику непотребних делова класе употребљене у имплементацији остаје мање метода које треба подржати у новој имплементацији. Побољшање може да се односи на ефикасност, краткоћу и јасноћу, или на друге особине кода.

Пошто смо редуковање интерфејса већ илустровали на примеру листе и стека, овде смо одлучили да илуструјемо другачије решење, а имплементација класе CollectionWithCursor помоћу класе LinkedList<T> ће се појавити као један од задатака за вежбу.

У решењу датом у наставку, елементи колекције се чувају у две листе. Једна листа чува елементе лево, а друга десно од курсора. При томе десна листа елементе чува у обрнутом редоследу, да би се уметање и брисање вршило само на крајевима листи, који се налазе непосредно уз курсор. На тај начин можемо да гарантујемо тражену ефикасност операција. Пошто листа (List) заузима мање меморије него повезана листа (LinkedList), овде понуђено решење је меморијски ефикасније.

Препуштамо читаоцу да даље самостално проанализира класу и демо програм.

Програм који демонстрира употребу класе CollectionWithCursor, исписује

br. elemenata: 6, pozicija kursora: 4, elementi: a b c d e f.
br. elemenata: 5, pozicija kursora: 4, elementi: a b c i f.
br. elemenata: 6, pozicija kursora: 5, elementi: a b c i k f.