תכנות מתקדם ב-Java/תכנות גנרי

בעייה שבוודאי נתקלתם בה עד כה היא התלות של שיטות ותוכניות בטיפוס הנתונים הניתן להם. למשל: אם נממש רשימה מקושרת שיודעת להחזיק נתונים מטיפוס int, הרשימה הזאת לא תהייה שימושית אם נרצה לאחסן בה מחרוזות, ונאלץ לשכתב את המחלקה. תכנות גנרי הוא הדרך לכתיבת תוכניות שאינן תלויות בטיפוסי המשתנים.

תזכורת - רשימה מקושרת

רשימה מקושרת - מבנה נתונים פשוט, בו נתקלנו כבר בפרק מבני נתונים. המחלקה אותה ראינו שם תומכת אך ורק במידע מטיפוס int, וכעת נראה שתי גישות אפשריות לשנות אותה כך שתתאים לכל טיפוס משתנה.

גישה ראשונה - שימוש במחלקה Object

הגישה הראשונה, שאינה דורשת תמיכה כלשהי של השפה, היא פשוט שימוש במחלקה Object כטיפוס משתנה, במקום הטיפוס המקורי (במקרה שלנו, int). המחלקה הפנימית Node תשתנה קלות, ובמקום להחזיק מידע מטיפוס int, היא תחזיק מידע מטיפוס Object, באופן הבא:

private class Node {

	public Node(Object data) {
		_data = data;
		_next = null;
	}

	Object _data;
	Node _next;
}

נשווה כאן את השיטה contains, שבודקת האם איבר נתון נמצא ברשימה. בתוכנית המקורית, הקוד נראה כך:

public boolean contains(int data) {
	Node runner = _head;
	while (runner != null) {
		if (runner._data == data) {
			return true;
		}
		runner = runner._next;
	}
	return false;
}

כעת, הקוד יראה כך:

public boolean contains(Object data) {
	Node runner = _head;
	while (runner != null) {
		if (runner._data.equals(data)) {
			return true;
		}
		runner = runner._next;
	}
	return false;
}

השינוי הוא קטן מאוד: במקום int השתמשנו ב-Object. שינוי נוסף הוא שימוש בפקודה equals להשוואה במקום בסימן "==". הסיבה: באובייקטים רבים השוואה בעזרת == בודקת אם מדובר בדיוק באותו אובייקט (כאשר אובייקט בעל תוכן זהה לא תמיד יחשב זהה), ולכן יש להשוות בעזרת equals.

הקוד המלא של התוכנית הגנרית

/**
 * Implements a generic singly-linked list
 * 
 * @author Johnny Zoo
 */
public class GenericLinkedList {

	/**
	 * Implements a node in the list
	 */
	private class Node {

		public Node(Object data) {
			_data = data;
			_next = null;
		}

		Object _data;
		Node _next;
	}

	// Head of the list
	private Node _head;

	/**
	 * Simple constructor
	 */
	public GenericLinkedList() {
		_head = null;
	}

	/**
	 * @return True if the list is empty, else if not
	 */
	public boolean isEmpty() {
		return (_head == null);
	}

	/**
	 * Add new element to the list
	 * 
	 * @param data
	 *            Data to add
	 */
	public void addElement(Object data) {
		if (isEmpty()) {
			_head = new Node(data);
		} else {
			Node newNode = new Node(data);
			newNode._next = _head;
			_head = newNode;
		}
	}

	/**
	 * Returns the element at the given index
	 * 
	 * @param loc
	 *            Index of data to retrieve
	 * @return The data that the element at the given index holds
	 */
	public Object elementAt(int loc) {
		Node runner = _head;
		if (loc < 0)
			throw new IndexOutOfBoundsException();
		for (int i = 0; i < loc; i++) {
			runner = runner._next;
			if (runner == null)
				throw new IndexOutOfBoundsException();
		}
		return runner._data;
	}

	/**
	 * Removes a given element from the list
	 * 
	 * @param data
	 *            Data to remove
	 * @return True if this data removed, false if not
	 */
	public boolean removeElement(Object data) {
		if (isEmpty())
			return false;
		Node runner = _head;
		// If the data is in the head - we can just remove the head
		if (runner._data.equals(data)) {
			_head = _head._next;
			return true;
		}
		// The data is not in the first node
		else {
			Node prev = _head;
			runner = _head._next;
			while (runner != null) {
				if (runner._data.equals(data)) {
					// Now the previous node points on the one after
					// the one we removed
					prev._next = runner._next;
					return true;
				}
				runner = runner._next;
				prev = prev._next;
			}
		}
		// The element we wanted to remove is not in list
		return false;
	}

	/**
	 * Search the list for a given element
	 * 
	 * @param data
	 *            Data to find
	 * @return True if this element is in list, false if not
	 */
	public boolean contains(Object data) {
		Node runner = _head;
		while (runner != null) {
			if (runner._data.equals(data)) {
				return true;
			}
			runner = runner._next;
		}
		return false;
	}
}

אם כך, ביצענו שינוי קטן במחלקה, ועכשיו, בזכות העובדה שכל המחלקות הקיימות ב-Java (פרט למשתנים הפרימיטיביים) יורשות את המחלקה Object, נוכל להכניס למחלקה זו כל סוג איבר שעולה על רוחנו. נראה תוכנית קטנה שמשתמשת במבנה זה:

GenericLinkedList gl = new GenericLinkedList();
gl.addElement(new Integer(1));
gl.addElement(new Integer(2));
gl.addElement(new Integer(3));
int sum = 0;
for (int i = 0; i < 3; i++) {
	sum += (Integer) gl.elementAt(i);
}
System.out.println("Sum: " + sum);

ייתכן ששמתם לב לבעייה: השימוש במחלקה Object מחייב אותנו לבצע המרה בכל פעם שאנו רוצים להשתמש באיבר שנמצא במבנה הנתונים שלנו. כמו כן, לא ניתן להגביל (בלי לפגוע בגנריות) את סוג המשתנים שנוכל להכניס. שינוי קטן בדוגמה הקודמת יכול להמחיש את הבעייה בצורה טובה יותר:

gl.addElement(new Integer(1));
gl.addElement(new Integer(2));
gl.addElement("Three");
int sum = 0;
for (int i = 0; i < 3; i++) {
	sum += (Integer) gl.elementAt(i);
}
System.out.println("Sum: " + sum);

כאשר הכנסנו איבר לא מתאים, הוא נכנס בלי שום בעייה, והתוצאה - קריסה בזמן הריצה.

אם כך, השגה של גנריות באמצעות שיטה זו היא אפשרית, אך סובלת מכמה בעיות:

• קוד מסורבל ועמוס בהמרות של משתנים.
• סכנה: הכנסה של משתנים מסוג לא מתאים תתגלה רק בזמן הריצה ותביא לקריסת התוכנית.

גישה שנייה - תבניות

גישה טובה יותר לעניין נוכל להשיג בעזרת הכנסה של כלי חדש - שימוש בתבניות. תבניות הן דרך ליצור מחלקה שמתייחסת לטיפוס משתנים שנקבע עבור כל מופע בנפרד. למשל: אם מימשנו רשימה מקושרת גנרית בעזרת תבניות, נוכל ליצור רשימה מקושרת שמכילה איברים מטיפוס Integer ורשימה מקושרת אחרת שמכילה איברים מטיפוס String, וזאת מבלי לסבול מהחסרונות המימוש שראינו קודם (בעזרת המחלקה Object).

סימון ודוגמת שימוש במחלקה גנרית

כשנרצה להשתמש באובייקט גנרי ולשייך אותו לטיפוס מסויים, נעשה זאת בעזרת סוגריים משולשים שבתוכם שם הטיפוס. למשל, אם יש לנו מחלקה גנרית בשם LinkdedList שמממשת רשימה מקושרת, ונרצה ליצור מופע שלה בו תחזיק הרשימה משתנים מטיפוס String, נעשה זאת בצורה הבאה: LinkedList<String> list = new LinkedList<String>(); מעתה ואילך, המהדר יוכל לדעת שהמשתנה list מחזיק משתנים מטיפוס String. בפרט, כשניגש לאיברים ברשימה, היחס אליהם יהיה כאל משתנים מטיפוס String, מה שאומר שלא נזדקק להמרות, ושלא נוכל להכניס איברים שאינם מטיפוס String (או יורשים אותו).

יצירת מחלקה גנרית

השלב הבא הוא יצירה של מחלקות גנריות. גם זו מטלה פשוטה למדי: כאשר נכריז על המחלקה, נוסיף לשמה סוגריים משולשים עם מילה כלשהי שתייצג את טיפוס המשתנה, באופן הבא: public class MyClass<T> כעת, בקוד של אותה המחלקה, נוכל לכתוב שם זה (בדוגמה שלנו - T) במקום טיפוס משתנה מסויים. שימו לב: אין חובה, אך נהוג להשתמש בT למטרה זו. אחרי ההקדמה הזו, נראה את המחלקה GenericLinkedList. השינוי הראשון הוא בהגדרת המחלקה, שעכשיו תיראה כך:

public class GenericLinkedList<T>

המחלקה הפנימית Node, עם תבניות:

private class Node {

	public Node(T data) {
		_data = data;
		_next = null;
	}

	T _data;
	Node _next;
}

והשיטה contains תיראה כך:

public boolean contains(T data) {
	Node runner = _head;
	while (runner != null) {
		if (runner._data.equals(data)) {
			return true;
		}
		runner = runner._next;
	}
	return false;
}

גם עכשיו, השינוי הוא קטן מאוד.

הקוד המלא של התוכנית הגנרית (כעת, בעזרת תבניות)

/**
 * Implements a generic singly-linked list
 * 
 * @author Johnny Zoo
 */
public class GenericLinkedList<T> {

	/**
	 * Implements a node in the list
	 */
	private class Node {

		public Node(T data) {
			_data = data;
			_next = null;
		}

		T _data;
		Node _next;
	}

	// Head of the list
	private Node _head;

	/**
	 * Simple constructor
	 */
	public GenericLinkedList() {
		_head = null;
	}

	/**
	 * @return True if the list is empty, else if not
	 */
	public boolean isEmpty() {
		return (_head == null);
	}

	/**
	 * Add new element to the list
	 * 
	 * @param data
	 *            Data to add
	 */
	public void addElement(T data) {
		if (isEmpty()) {
			_head = new Node(data);
		} else {
			Node newNode = new Node(data);
			newNode._next = _head;
			_head = newNode;
		}
	}

	/**
	 * Returns the element at the given index
	 * 
	 * @param loc
	 *            Index of data to retrieve
	 * @return The data that the element at the given index holds
	 */
	public T elementAt(int loc) {
		Node runner = _head;
		if (loc < 0)
			throw new IndexOutOfBoundsException();
		for (int i = 0; i < loc; i++) {
			runner = runner._next;
			if (runner == null)
				throw new IndexOutOfBoundsException();
		}
		return runner._data;
	}

	/**
	 * Removes a given element from the list
	 * 
	 * @param data
	 *            Data to remove
	 * @return True if this data removed, false if not
	 */
	public boolean removeElement(T data) {
		if (isEmpty())
			return false;
		Node runner = _head;
		// If the data is in the head - we can just remove the head
		if (runner._data.equals(data)) {
			_head = _head._next;
			return true;
		}
		// The data is not in the first node
		else {
			Node prev = _head;
			runner = _head._next;
			while (runner != null) {
				if (runner._data.equals(data)) {
					// Now the previous node points on the one after
					// the one we removed
					prev._next = runner._next;
					return true;
				}
				runner = runner._next;
				prev = prev._next;
			}
		}
		// The element we wanted to remove is not in list
		return false;
	}

	/**
	 * Search the list for a given element
	 * 
	 * @param data
	 *            Data to find
	 * @return True if this element is in list, false if not
	 */
	public boolean contains(T data) {
		Node runner = _head;
		while (runner != null) {
			if (runner._data.equals(data)) {
				return true;
			}
			runner = runner._next;
		}
		return false;
	}
}

דוגמת שימוש קצרה במחלקה:

GenericLinkedList<Integer> gl = new GenericLinkedList<Integer>();
gl.addElement(new Integer(1));
gl.addElement(new Integer(2));
gl.removeElement(new Integer(2));
gl.addElement(new Integer(3));
int sum = 0;
for (int i = 0; i < 2; i++) {
	sum += (Integer) gl.elementAt(i);
}
System.out.println("Sum: " + sum);

נשים לב שהפעם, אם ננסה להכניס איבר מטיפוס לא מתאים, נקבל שגיאת הידור - מצב שמבחינתו עדיף בהרבה על שגיאת זמן ריצה.

תבניות מיוחדות

לפעמים נרצה לדעת שטיפוס אותו תכיל המחלקה הגנרית שלנו הוא בעל תכונות מסויימות. למשל: נניח שמימשנו מבנה נתונים משוכלל, שדורש שהאיברים בו יהיו ברי השוואה, כלומר - יממשו את השיטה compareTo, שמאפשרת השוואה בין שני אובייקטים. לשם כך, נבנה Interface בשם Comparable שמכיל את השיטה public int compareTo(Object other) (הערה: זהו ממשק שקיים בג'אווה, אם תרצו להשתמש בו - אין צורך לכתוב אותו מחדש). כעת, כדי לדאוג לכך שאיברי המחלקה הגנרית יממשו את Comparable, נגדיר אותה באופן הבא: public class MyDataStructure<E implements Comparable> { ... ובכך נבטיח שטיפוס הנתונים במחלקה יממש את Comparable, ונוכל להשתמש ללא חשש בשיטה compareTo. נניח כעת שנרצה לשפר את Comparable ולהפוך אותו לגנרי. השיטה compareTo תיראה כעת כך: public int compareTo(T other) והגדרת המחלקה הגנרית שלנו תיראה כך: public class MyDataStructure<E extends Comparable<E>> { ...

שיטות גנריות

יצירה של שיטה גנרית בודדת סטטית היא אפשרית, ויש לה תחביר מיוחד. נראה דוגמה קצרה:

public static <T> void printAll(T[] arr) {
	for(int i=0; i < arr.length; i++) {
		System.out.println(arr[i]);
	}
}

פולימורפיזם

במחלקות גנריות לא קיים פולימורפיזם באופן המוכר לנו. לדוגמה: נניח ויש לנו שתי מחלקות, המחלקה Base, והמחלקה Derived שמרחיבה אותה. נניח כי יצרנו רשימה גנרית שמכילה איברים מהמחלקה Derived בעזרת הפקודה: GenericLinkedList<Derived> derivedList = new GenericLinkedList<Derived>(); ומצביע נוסף לאותה הרשימה: GenericLinkedList<Base> baseList = derivedList; במקרה כזה נקבל שגיאת הידור. הסיבה להגבלה הזו נעוצה בכך שאפשר היה להתייחס לאותה הרשימה בשתי צורות: בעזרת המשתנה derivedList נוכל להתייחס אליה כרשימה שמכילה איברים מטיפוס Derived, בעוד שעם baseList נוכל להתייחס אליה כרשימה שמכילה איברים מטיפוס Base. זה יכול היה להוביל למצבים לא נעימים, למשל: בעזרת baseList נוכל להכניס לרשימה איברים מטיפוס Base, ולאחר מכן, כאשר נשלוף אותם בעזרת derivedList, נקבל איברים שאמורים להיות מטיפוס Derived אך בפועל הם מטיפוס Base.

בשביל מצבים בהם נצטרך להתייחס למחלקה גנרית מבלי לדעת בזמן הריצה את סוגה, הומצא ה-Wildcard: כאשר במקום שם מחלקה נכתוב "?", נוכל להרחיב אותה כרצוננו. למשל, קטע הקוד הבא הוא חוקי לחלוטין:

GenericLinkedList<?> list = new GenericLinkedList<String>();
list = new GenericLinkedList<Integer>();

עם זאת, גם כאן טמונה סכנה אפשרית. נראה זאת בעזרת דוגמה נוספת:

public static void addNumbers(GenericLinkedList<?> list) {
	list.addElement(new Integer(1));
	list.addElement(new Integer(2));
	list.addElement(new Integer(3));
}

יש לנו שיטה שמקבלת רשימה גנרית מטיפוס כלשהו, ומנסה להוסיף לה איברים. זוהי פעולה מסוכנת: יכול להיות שהרשימה היא מטיפוס שונה לגמרי. למעשה, הפעולות היחידות שמותר לנו לבצע הן כאלה שלא מושפעות מטיפוס המשתנים באותה מחלקה. למשל, זוהי שיטה חוקית:

public static void printFirstElement(GenericLinkedList<?> list) {
	System.out.println(list.elementAt(0));
}

אופן שימוש זה הוא מוגבל מאוד. כדי להוסיף מעט שימושיות לעניין, נוכל להשתמש גם כאן ב-extends, כמו בסעיף הקודם, אך עדיין - החופש שמאפשרת אי-ידיעת הטיפוס הגנרי עולה במחיר של שימוש מוגבל למדי.

המוגבלויות של השימוש בתבניות

עם היתרון הגדול של התבניות, הן סובלות משתי מוגבלויות:

• לא ניתן ליצור תבנית של טיפוס פרימיטיבי. במקרה הצורך, ניתן להשתמש במחלקות העוטפות שמספקת ג'אווה:

int=>Integer boolean=>Boolean long=>Long float=>Float double=>Double char=>Character

(String הוא אובייקט ועל כן נשאר אותו דבר)

• לא ניתן לפנות לבנאי של טיפוס גנרי. למשל, השורה T t = new T(); אינה חוקית. מסיבה זו, גם אתחול של מערך אינו חוקי. המגבלה הזו קיימת מכיוון שלא ניתן להבטיח שטיפוס הנתונים שנכניס לתבנית הזו מכיל בנאי ריק (או בכל צורה אחרת).

קישורים חיצוניים

הפרק הקודם: חריגות זמן ריצה

תכנות גנרי

הפרק הבא: מבני נתונים מתקדמים