القوائم lists والمجموعات sets في جافا

اطلعنا بالمقال السابق على الخواص العامة لعناصر التجميعات بلغة جافا، وحان الآن الوقت لنفحص بعضًا من تلك الأصناف، ونتعرَّف على طريقة استخدامها، حيث يُمكِننا تقسيم تلك الأصناف في العموم إلى مجموعتين رئيسيتين، هما القوائم lists والأطقم sets؛ حيث تتكوَّن أي قائمةٍ من متتاليةٍ من العناصر المُرتَّبة خطيًا، بمعنى أنها مُرتَبة وفقًا لترتيب معين لا يُشترَط له أن يَكون ترتيبًا تصاعديًا؛ أما الطقم set فهو تجميعةٌ لا تحتوي أي عناصرٍ مُكرَّرة، وربما تكون العناصر مُرتّبةً بترتيبٍ مُحدَّد أو لا. سنناقش سريًعا نوعًا آخرًا من التجميعات إضافةً الى النوعين السابقين، يُعرَف باسم أرتال الأولوية priority queue؛ وهي بنيةٌ بيانيةٌ data structures مثل الأرتال ولكن عناصرها ذات أولوية.

أصناف تمثيل القوائم

تعرّفنا في مقال مفهوم المصفوفات الديناميكية (ArrayLists) في جافا ومقال بنى البيانات المترابطة Linked Data Structures على طريقتين لتمثيل القوائم، هما المصفوفات الديناميكية dynamic array والقوائم المترابطة linked list. تُوفِّر جافا الصنفين java.util.ArrayList و java.util.LinkedList ضمن إطار عمل جافا للتجميعات Java Collection Framework لتمثيلهما بصيغةٍ مُعمَّمة generic، حيث يُنفِّذ كلاهما الواجهة List<T>‎، وبالتالي الواجهة Collection<T>‎ أيضًا. يُمثِل كائنٌ من النوع ArrayList<T>‎ متتاليةً مُرتَّبةً من الكائنات المُنتمية إلى النوع T، والمُخزَّنة ضمن مصفوفةٍ يزداد حجمها تلقائيًا عند الضرورة،؛ بينما يُمثِل كائنٌ من النوع LinkedList<T>‎ متتاليةً مُرتّبةً من الكائنات المُنتمية إلى النوع T، والمُخزَّنة -بخلاف المصفوفة- بعُقدٍ nodes تَربُطها مؤشرات pointers ببعضها بعضًا.

يدعم الصنفان السابقان عمليات القوائم الأساسية المُعرَّفة بالواجهة List<T>‎، كما يُعرَّف أي نوع بيانات مُجرَّد abstract data type بعملياته وليس طريقة تمثيله representation. قد تتساءل: لماذا نحتاج إلى تعريف صنفين بدلًا من تعريف صنف قائمةٍ وحيد له نفس طريقة التمثيل؟ المشكلة هي أننا لن نتمكَّن من تمثيل القوائم بطريقةٍ واحدة، وتكون كفاءة جميع عمليات القوائم على ذلك التمثيل بنفس الدرجة؛ حيث تَكون كفاءة عمليات معينة أفضل دائمًا عند تطبيقها على القوائم المترابطة linked lists بالموازنة مع المصفوفات؛ بينما ستَكون كفاءة عمليات أخرى أفضل عند تطبيقها على المصفوفات. يعتمد أي تطبيق application عمومًا على مجموعةٍ معينة من عمليات القوائم أكثر من غيرها، ولذلك ينبغي اختيار التمثيل الذي تَبلغ فيه كفاءة تلك العمليات أقصى ما يُمكِن.

يُعدّ الصنف LinkedList المُمثِّل للقوائم المترابطة مثلًا أكثر كفاءةً بالتطبيقات التي تعتمد بكثرة على إضافة العناصر إلى بداية القائمة ومنتصفها، أو حذفها من نفس تلك المواضع؛ حيث تتطلَّب نفس تلك العمليات عند تطبيقها على مصفوفة تحريك عددٍ كبيرٍ من العناصر مسافة موضعٍ واحدٍ إلى الأمام أو الخلف لإتاحة مساحةٍ للعنصر الجديد المطلوب إضافته، أو لملئ الفراغ الذي تسبَّب به حذف عنصر. إن زمن التشغيل المطلوب لإضافة عنصرٍ إلى بداية أو منتصف مصفوفة وفقًا لمصطلحات التحليل المقارب asymptotic analysis (انظر مقال تحليل الخوارزميات في جافا) يُساوِي Θ(n)‎، حيث تمثّل n عدد عناصر المصفوفة؛ أما بالنسبة للقوائم المترابطة، تقتصر عمليتي الإضافة والحذف على ضبط عددٍ قليل من المؤشرات، ويكون زمن التشغيل المطلوب لإضافة عقدةٍ node إلى أي موضعٍ ضمن القائمة أو حذفها من أي موضع مساوٍ إلى Θ(1)‎، أي تَستغرِق العملية مقدارً ثابتًا من الزمن بغض النظر عن عدد العناصر الموجود بالقائمة.

من الجهة الأخرى، يُعدّ الصنف ArrayList المُمثِل للمصفوفات أكثر كفاءةً عندما تَكون عملية الجَلْب العشوائي random access للعناصر أمرًا ضروريًا؛ وهي ببساطة عملية قراءة قيمة العنصر الموجود بموضعٍ معين k ضمن القائمة، وتُستخدَم تلك العملية عند محاولة قراءة أو تعديل القيمة المُخزَّنة بموضعٍ معين ضمن القائمة. تُعدّ تلك العمليات أمرًا في غاية البساطة بالنسبة للمصفوفة، وتحديدًا بالنسبة لزمن التشغيل الذي يساويΘ(1)‎؛ أما بالنسبة للقوائم المترابطة linked list، فتَعنِي تلك العمليات البدء من بداية القائمة، ثم التحرك من عقدةٍ إلى أخرى على طول القائمة بعدد خطواتٍ يصل إلى k، ويَكون زمن التشغيل هو Θ(k)‎.

تتساوى كفاءة عملية الترتيب sorting وإضافة عنصرٍ إلى نهاية القائمة لكلا النوعين السابقين.

تٌنفِّذ جميع أصناف القوائم توابع الواجهة Collection<T>‎، التي ناقشناها بالمقال السابق، مثل size()‎ و isEmpty()‎ و add(T)‎ و remove(Object)‎ و clear()‎؛ حيث يضيف التابع add(T)‎ الكائن إلى نهاية القائمة؛ بينما يحاول التابع remove(Object)‎ العثور أولًا على الكائن المطلوب حَذْفه باستخدام خوارزمية البحث الخطي linear search، التي لا تتميز بالكفاءة نهائيًا لأي نوعٍ من القوائم لأنها تتضمَّن المرور عبر جميع عناصر القائمة من بدايتها إلى نهايتها لحين العثور على الكائن. تحتوي الواجهة List<T>‎ على عدة توابعٍ أخرى للوصول إلى عناصر القائمة عبر مواضعها العددية. لنفترض أن list كائنٌ من النوع List<T>‎، سيُصبِح لدينا التوابع التالية:

list.get(index)‎: يُعيد الكائن الموجود بالموضع index ضمن القائمة، حيث أن index هو عددٌ صحيح. لاحِظ أن العناصر مُرقَّمةٌ على النحو التالي: 0، 1، 2، .. إلى list.size()-1، وبالتالي، لا بُدّ أن تَقَع القيمة المُمرَّرة مثل مُعامِلٍ ضمن ذلك النطاق، وإلا سيَحدُث اعتراضٌ من النوع IndexOutOfBoundsException.
list.set(index,obj)‎: يَستبدِل الكائن obj بالكائن الموجود حاليًا بالموضع index ضمن القائمة، وبالتالي لا يُغيِّر التابع عدد عناصر القائمة، كما أنه لا يُحرِّك أيًا من عناصرها الأخرى. يجب أن يكون الكائن obj من النوع T.
list.add(index,obj)‎: يُدخِل الكائن obj إلى الموضع index ضمن القائمة؛ أي يُزيِد التابع عدد عناصر القائمة بمقدار الواحد؛ كما أنه يُحرِّك جميع العناصر الواقعة بعد الموضع index مسافة موضعٍ واحدٍ إلى الأمام لإتاحة مساحةٍ للعنصر الجديد. يجب أن يَكون الكائن obj من النوع T، كما يجب أن تتراوح قيمة index بين 0 و list.size()‎، وإذا كان index يُساوي list.size()‎، فسيُضيِف التابع الكائن obj إلى نهاية القائمة.
list.remove(index)‎: يَحذِف الكائن الموجود بالموضع index، ثم يعيده قيمةً للتابع؛ حيث يُحرِّك التابع العناصر الواقعة بعد ذلك الموضع مسافة موضعٍ واحدٍ إلى الخلف لملء الفراغ الذي تسبَّب به حذف العنصر، ويَقِل بذلك عدد عناصر القائمة بمقدار الواحد. يجب أن تتراوح قيمة index بين 0 و list.size()-1.
list.indexOf(obj)‎: يُعيد قيمةً عدديةً من النوع int تُمثِّل موضع الكائن obj بالقائمة في حال وجوده بها؛ بينما يُعيد القيمة -1 إذا لم يَكُن موجودًا. يُمكِن للكائن obj أن يَكون من أي نوع وليس فقط T. إذا كان الكائن obj موجودًا أكثر من مرةٍ ضمن القائمة، فسيُعيد التابع موضع أول حدوثٍ له.

لاحِظ أن التوابع المذكورة أعلاه مُعرَّفةٌ لكلا الصنفين ArrayList<T>‎ و LinkedList<T>‎ على الرغم من أن كفاءة بعضها، مثل get و set مقتصرةٌ على الصنف ArrayList.

يُعرِّف الصنف LinkedList<T>‎ عدة توابع إضافية أخرى غير مُعرَّفةٍ بالصنف ArrayList. إذا كان linkedlist كائنًا من النوع LinkedList<T>‎، فسنحصل على التوابع التالية:

linkedlist.getFirst()‎: يُعيد قيمةً من النوع T تُمثِّل أول عنصرٍ ضمن القائمة دون إجراء أيّ تعديلٍ عليها. سيحدث اعتراضٌ exception من النوع NoSuchElementException، إذا كانت القائمة فارغةً، وينطبق ذلك على التوابع الثلاثة التالية أيضًا.
linkedlist.getLast()‎: يُعيد قيمةً من النوع T تُمثِّل آخر عنصرٍ ضمن القائمة دون إجراء أيّ تعديلٍ عليها.
linkedlist.removeFirst()‎: يحذف الصنف أول عنصرٍ ضمن القائمة، ويُعيده قيمةً للتابع. التابعان linkedlist.remove()‎ و linkedlist.pop()‎ مُعرَّفان أيضًا، ولهما نفس دلالة التابع removeFirst()‎.
linkedlist.removeLast()‎: يَحذِف آخر عنصرٍ ضمن القائمة، ويُعيده قيمةً للتابع.
linkedlist.addFirst(obj)‎: يُضيف الكائن obj إلى بداية القائمة، والذي يجب أن يكون من النوع T. التابع linkedlist.push(obj)‎ مُعرَّفٌ أيضًا، وله نفس الدلالة.
linkedlist.addLast(obj)‎: يُضيف الكائن obj إلى نهاية القائمة، والذي يجب أن يكون من النوع T. يعمل بصورة مشابهة تمامًا للتابع linkedlist.add(obj)‎؛ فهو بالنهاية مُعرَّفٌ فقط للتأكد من الحصول على أسماء توابعٍ مُتسقّة consistent.

ستلاحِظ وجود بعض التكرار ضمن الصنف LinkedList، لتسهيل استخدامه كما لو كان مكدسًا stack، أو رتلًا queue (انظر مقال المكدس Stack والرتل Queue وأنواع البيانات المجردة ADT). يُمكِننا على سبيل المثال استخدام قائمةٍ مترابطة من النوع LinkedList مثل مكدسٍ باستخدام التوابع push()‎ و pop()‎، أو مثل رتلٍ باستخدام التوابع add()‎ و remove()‎ لتنفيذ عمليتي الإدراج enqueue والسحب dequeue.

إذا كان الكائن list قائمةً من النوع List<T>‎، فسيعيد التابع list.iterator()‎ المُعرَّف بالواجهة Collection<T>‎ مُكرّرًا iterator من النوع Iterator، والذي يُمكِننا استخدامه لاجتياز traverse القائمة من البداية حتى النهاية. يتوفَّر أيضًا نوعٌ آخر من مُكرِّرات القوائم ListIterator يتميز بخواصٍ إضافية. لاحِظ أن الواجهة ListIterator<T>‎ مُوسعَّةٌ من الواجهة Iterator<T>‎، ويُعيد التابع list.listIterator()‎ كائنًا من النوع ListIterator<T>‎.

تتضمَّن الواجهة ListIterator توابع المُكرِّرات العادية، مثل hasNext()‎ و next()‎ و remove()‎، ولكنها تحتوي أيضًا على توابعٍ أخرى، مثل hasPrevious()‎ و previous()‎ و add(obj)‎ و set(obj)‎، والتي تُساعد على التحرُّك إلى الخلف ؛ وإضافة عنصرٍ بالموضع الحالي للمُكرِّر؛ واستبدال أحد عناصر القائمة على الترتيب. فكِّر بالمُكرِّرات كما لو كانت تُشير إلى موضعٍ بين عنصرين ضمن القائمة، أو إلى بداية القائمة، أو نهايتها لتتمكَّن من فِهم طريقة عمل التوابع السابقة. تُظهر الصورة التالية العناصر على هيئة مربعات، بحيث تُشير تلك الأسهم إلى المواضع المحتملة للمُكرِّر iterator:

إذا كان iter مُكرِّرًا من النوع ListIterator<T>‎، فسيحركه التابع iter.next()‎ مسافة موضعٍ واحدٍ إلى يمين القائمة، ويعيد العنصر الذي مرّ به المُكرِّر أثناء تحركه؛ ويُحرِّك التابع iter.previous()‎ المُكرِّر مسافة موضعٍ واحد إلى يسار القائمة، ويعيد العنصر الذي مرّ به. يَحذِف التابع iter.remove()‎ أحدث عنصرٍ مرّ به المُكرِّر أثناء تحركُّه أي بعد استدعاء التابع iter.next()‎ أو التابع iter.previous()‎. يَعمَل التابع iter.set(obj)‎ بنفس الطريقة، أي يستبدل obj بنفس العنصر الذي يفترض للتابع iter.remove()‎ أن يَحذِفه عند استدعائه. يتوفَّر أيضًا التابع iter.add(obj)‎ المسؤول عن إضافة الكائن obj من النوع T إلى الموضع الحالي للمُكرِّر، والذي من الممكن أن يكون في بداية القائمة، أو نهايتها، أو بين عنصرين موجودين مُسبَقًا ضمن القائمة.

تُعدّ القوائم المُستخدَمة بالواجهة LinkedList<T>‎ قوائمًا مترابطةً مزدوجة doubly linked lists، حيث تحتوي كل عقدةٍ node ضمن القائمة على مؤشرين pointers، يُشير أحدهما إلى العقدة التالية بالقائمة، بينما يشير الآخر إلى العقدة السابقة، ويُمكِّننا هذا من تنفيذ التابعين next()‎ و previous()‎ بأحسن كفاءةٍ ممكنة. كما يحتوي الصنف LinkedList<T>‎ على مؤشر ذيل tail pointer للإشارة إلى آخر عقدةٍ ضمن القائمة، ويُمكِّننا ذلك من تنفيذ التابعين addLast()‎ و getLast()‎ بكفاءة.

سنَدرِس الآن مثالًا عن كيفية استخدام مُكرِّرٍ من النوع ListIterator. لنفترض أننا نريد معالجة قائمةٍ من العناصر مع مراعاة الإبقاء عليها مُرتَّبةً ترتيبًا تصاعديًا. عند إضافة عنصرٍ إلى القائمة، سيَعثُر المُكرِّر من النوع ListIterator أولًا على الموضع الذي ينبغي إضافة العنصر إليه، ثم سيَضعُه به. يبدأ المُكرِّر ببساطةٍ من بداية القائمة، ثم يتحرَّك إلى الأمام بحيث يَمُر بجميع العناصر التي تقل قيمتها عن قيمة العنصر المطلوب إضافته، ويُضيِف التابع add()‎ العنصر إلى القائمة عند هذه النقطة. إذا كان stringList مُتغيِّرًا من النوع List<String>‎ مثلًا، وكان newItem السلسلة النصية التي نريد إضافتها إلى القائمة، وبِفَرض كانت السلاسل النصية الموجودة حاليًا ضمن القائمة مُرتَّبةً ترتيبًا تصاعديًا بالفعل، يُمكِننا إذًا استخدام الشيفرة التالية لوضع العنصر newItem بموضعه الصحيح ضمن القائمة بحيث نُحافِظ على ترتيبها:

ListIterator<String> iter = stringList.listIterator();

// 1

while (iter.hasNext()) {
   String item = iter.next();
   if (newItem.compareTo(item) <= 0) {
         // 2
      iter.previous();
      break;
   } 
}

iter.add(newItem);

حيث أن:

[1] تعني حرِّك المُكرِّر بحيث يُشير إلى موضع القائمة الذي ينبغي إضافة newItem إليه؛ فإذا كان newItem أكبر من جميع عناصر القائمة، فستنتهي حلقة التكرار while عندما تُصبِح قيمة iter.hasNext()‎ مُساويةً للقيمة false، أي عندما يَصِل المُكرِّر إلى نهاية القائمة.
[2] تشير إلى يجب أن يأتي newItem قبل item. حرِّك المُكرِّر خطوةً للوراء، بحيث يُشير إلى موضع الإدخال الصحيح، وأنهي الحلقة.

قد يكون stringList من النوع ArrayList<String>‎، أو النوع LinkedList<String>‎. لاحِظ أن كفاءة الخوارزمية المُستخدَمة لإدخال newItem إلى القائمة مُتساويةٌ لكليهما، كما أنها ستَعمَل مع أي أصنافٍ أخرى طالما كانت تُنفِّذ الواجهة List<String>‎. قد تجد أنه من الأسهل تصميم خوارزمية الإدراج باستخدام الفهرسة indexing على هيئة توابعٍ، مثل get(index)‎ و add(index,obj)‎، ولكن ستكون كفائتها سيئةً للغاية بالنسبة للقوائم المترابطة LinkedList؛ لأنها لا تَعمَل بكفاءةٍ عند الجلب العشوائي random access. ملاحظة: ستَعمَل خوارزمية الإدراج insertion حتى لو كانت القائمة فارغة.

الترتيب

نظرًا لأن عملية ترتيب sorting القوائم من أكثر العمليات شيوعًا، كان من الضروري حقًا أن تُعرِّف الواجهة List تابعًا مسؤولًا عن تلك العملية، إلا أنه غير موجود؛ ربما لأن عملية ترتيب قوائم أنواعٍ معينة من الكائنات ليس لها معنى. بالرغم من ذلك، يتضمَّن الصنف java.util.Collections توابعًا ساكنة static methods للترتيب، كما يحتوي على توابعٍ ساكنةٍ أخرى للعمل مع التجميعات collections؛ وهي توابعٌ من النوع المُعمَّم generic، أي أنها تعمل مع تجميعات أنواعٍ مختلفة من الكائنات. لنفترض أن list قائمةً من النوع List<T>‎، يُمكِن للأمر التالي ترتيب القائمة تصاعديًا:

Collections.sort(list);

يجب أن تُنفِّذ عناصر القائمة الواجهة Comparable<T>‎. سيعمل التابع Collections.sort()‎ على قوائم السلاسل النصية من النوع String، وكذلك لقوائم أي نوعٍ من الأصناف المُغلِّفة، مثل Integer و Double. يتوفَّر أيضًا تابع ترتيبٍ آخرٍ يَستقبِل معاملًا ثانيًا إضافيًا من النوع Comparator:

Collections.sort(list,comparator);

يُوازن المعامل الثاني comparator بين عناصر القائمة في تلك الحالة. كما ذكرنا بالمقال السابق، تُعرِّف كائنات الصنف Comparator التابع compare()‎ الذي يُمكِننا من استخدِامه لموازنة كائنين. سنفحص مثالًا على استخدام الصنف Comparator في مقال قادم.

يَعتمِد التابع Collections.sort()‎ على خوارزمية الترتيب بالدمج merge sort بزمن تشغيل run time يساوي Θ(n*log(n))‎ لكُلٍّ من الحالة الأسوأ worst-case والحالة الوسطى average-case، حيث n هو حجم القائمة. على الرغم من أن زمن التشغيل لتلك الخوارزمية أبطأ قليلًا في المتوسط من خوارزمية الترتيب السريع QuickSort (انظر مقال التعاود recursion في جافا لمزيد من التفاصيل)، إلا أن زمن تشغليها في الحالة الأسوأ أفضل بكثير. تتميز خوارزمية الترتيب بالدمج MergeSort علاوةً على ذلك بخاصية الاستقرار stability، التي سنناقشها بمقال لاحق.

يتضمَّن الصنف Collection تابعين آخرين مفيدين على الأقل لتعديل القوائم؛ حيث يُنظِم التابع الآتي:

 Collections.shuffle(list)‎

عناصر القائمة بحيث تكون مُرتبةً ترتيبًا عشوائيًا؛ بينما يعكس التابع Collections.reverse(list)‎ ترتيب عناصر القائمة، بحيث ينتقل آخر عنصرٍ في القائمة إلى مقدمتها، وثاني آخر عنصرٍ إلى الموضع الثاني بالقائمة، وهكذا.

نظرًا لأن الصنف List يُوفِّر لنا بالفعل تابع ترتيب ذا كفاءة عالية، فلا حاجة لكتابته بنفسك.

أصناف الأطقم TreeSet و HashSet

يُعدّ الطقم set تجميعة كائنات، لا يتكرَّر فيها أي عنصرٍ أكثر من مرة. تُنفِّذ الأطقم جميع توابع الواجهة Collection<T>‎ بطريقةٍ تَضمن عدم تكرار أي عنصرٍ مرتين؛ فإذا كان set كائن تجميعةٍ من النوع Set<T>‎، وكان يَحتوي على عنصرٍ obj، فلن يكون لاستدعاء التابع set.add(obj)‎ أي تأثيرٍ على set. توفِّر جافا صنفين لتنفيذ الواجهة Set<T>‎، هما java.util.TreeSet و java.util.HashSet.

بالإضافة إلى كون الصنف TreeSet من النوع Set، فإن عناصره تكون مُرتّبةً دائمًا ترتيبًا تصاعديًا، أي ستجتاز مُكرِّرات الأطقم من النوع TreeSet العناصر دائمًا بحسب ترتيبها التصاعدي.

لا يُمكِن للأطقم من النوع TreeSet أن تحتوي على أية كائنات عشوائيًا؛ حيث لا بُدّ من معرفة الطريقة التي ينبغي على أساسها ترتيب تلك الكائنات؛ أي ينبغي لأي كائنٍ موجودٍ ضمن طقم من النوع TreeSet<T>‎ أن يُنفِّذ الواجهة Comparable<T>‎، بحيث يَكون للاستدعاء obj1.compareTo(obj2)‎ لأي كائنين obj1 و obj2 ضمن الطقم معنى. يُمكِننا بدلًا من ذلك تمرير كائنٍ من النوع Comparator<T>‎ مثل معاملٍ للباني constructor عند إنشاء طقمٍ من النوع TreeSet، ويُستخدَم في تلك الحالة التابع compare()‎ المُعرَّف ضمن Comparator لموازنة الكائنات المضافة إلى الطقم.

لا تَستخدِم الأطقم من النوع TreeSet التابع equals()‎ من أجل اختبار تساوي كائنين معينين، وإنما تَستخدِم التابع compareTo()‎، أو التابع compare()‎، وهذا قد يُحدِث مشكلة؛ لأن التابع compareTo()‎ (كما ناقشنا بالمقال السابق) قد يُعامِل كائنين غير متساويين كما لو كانا كذلك لغرض الموازنة comparison، مما يَعنِي إمكانية وقوع أحدهما فقط ضمن طقمٍ من النوع TreeSet. لنفترض مثلًا أن لدينا طقمًا يحتوي على مجموعةٍ من عناوين البريد، وكان التابع compareTo()‎ مُعرَّفٌ بحيث يوازن فقط الأرقام البريدية لتلك العناوين، وبالتالي يُمكِن للطقم أن يحتوي على عنوانٍ واحدٍ فقط لكل رقمٍ بريدي، وهو بالتأكيد أمرٌ غير منطقي.

يجب إذًا الانتباه دومًا لدلالة الأطقم من النوع TreeSet، والتأكُّد من أن التابع compareTo()‎ مُعرَّفٌ بطريقةٍ منطقية للكائنات المُتوقَّع إضافتها لهذا النوع من الأطقم، ويَنطبِق ذلك على السلاسل النصية من النوع String، والأعداد الصحيحة من النوع Integer، وغيرها من الأنواع الأخرى المبنية مُسبَقًا built-in؛ حيث يُعامِل التابع compareTo()‎ الكائنات بتلك الأنواع على أنها متساوية إذا كانت فعلًا كذلك.

تُخزَّن عناصر الأطقم من النوع TreeSet داخل ما يُشبِه أشجار الترتيب الثنائية binary sort tree (انظر مقال الأشجار الثنائية Binary Trees في جافا)، حيث تكون بنية البيانات data structure مُتزِّنةً؛ أي تكون جميع أوراق leaves الشجرة الثنائية على نفس البعد تقريبًا من جذر الشجرة root، مما يضمَن تنفيذ جميع العمليات الأساسية، مثل الإدْخال والحذف والبحث بكفاءة، وبزمن تشغيلٍ للحالة الأسوأ worst-case run time مساوٍ Θ(log(n))‎، حيث n هو عدد عناصر الطقم.

كما ذكرنا مُسبقًا، تكون عناصر الأطقم من النوع TreeSet مُرتّبةً وغير مُكرَّرة، وهذا يجعلها مناسبةً لبعض التطبيقات. تَضمَّن تمرين 7.6 على سبيل المثال كتابة برنامجٍ يقرأ ملفًا ثم يَطبَع قائمة الكلمات الموجودة ضمن ذلك الملف بعد حذف جميع الكلمات المُكرَّرة، وبحيث تَكون مُرتّبةً أبجديًا. كنا قد اِستخدَمنا مصفوفةً من النوع ArrayList، وعليه كان من الضروري التأكُّد من كون عناصر المصفوفة مُرتّبةً وغير مُكرَّرة. يُمكننا في الواقع استخدام طقمٍ من النوع TreeSet لتخزين العناصر بدلًا من استخدام قائمة، وسيُبسِّط ذلك الحل كثيرًا؛ لأنه سيَحذِف العناصر المُكرَّرة تلقائيًا، كما سيجتاز مُكرِّر الطقم العناصر على نحوٍ مُرتّبٍ تلقائيًا. يُمكِننا كتابة الحل باستخدام الصنف TreeSet على النحو التالي:

TreeSet<String> words = new TreeSet<String>();

// طالما ما يزال هناك بيانات أخرى بملف الدخل
while there is more data in the input file:
    // ‫أسنِد الكلمة التالية بالملف إلى word
   Let word = the next word from the file
   // ‫حوِّل word إلى الحالة الصغيرة
   Convert word to lower case
   // ‫أضِف word إذا لم تكن موجودةً بالفعل
   words.add(word)   

for ( String w : words ) // words في w من أجل كل سلسلة نصية
   Output w  // تُطبَع الكلمات مُرتبة

يُمكِنك أيضًا الاطلاع على الشيفرة الكاملة للبرنامج بالملف WordListWithTreeSet.java.

لنفحص مثالًا آخرًا، بفرض أن coll تجميعةٌ من السلاسل النصية من النوع String، يُمكِننا استخدام طقمٍ من النوع TreeSet لترتيب عناصر التجميعة coll، ولحَذْف أي عناصر مُكرَّرة بكتابة الشيفرة التالية:

TreeSet<String> set = new TreeSet<String>();
set.addAll(coll);

تُضيِف التعليمة الثانية جميع عناصر التجميعة إلى طقم، وبما أنه من النوع Set، فسيتجاهل العناصر المُكرَّرة تلقائيًا، ونظرًا لكونه من النوع TreeSet تحديدًا، ستكون العناصر مُرتَّبة. إذا أردت تخزين بيانات طقمٍ معينٍ داخل بنية بيانات data structure مختلفة، يُمكِنك ببساطة نسخها من الطقم. تَنسَخ الشيفرة التالية عناصر طقمٍ إلى مصفوفةٍ من النوع ArrayList:

TreeSet<String> set = new TreeSet<String>();
set.addAll(coll);
ArrayList<String> list = new ArrayList<String>();
list.addAll(set);

تَستقبل بناة constructors جميع الأصناف المُمثِلة للتجميعات ضمن لغة جافا تجميعةً من النوع Collection؛ وعند استدعاء إحداها، ستُضَاف جميع عناصر التجميعة المُمرَّرة إلى التجميعة الجديدة المُنشَئة. إذا كان coll من النوع Collection<String>‎ مثلًا، يُنشِئ الاستدعاء new TreeSet<String>(coll)‎ طقمًا من النوع TreeSet يحتوي على نفس العناصر الموجودة بالتجميعة coll بعد حذف أي عناصرٍ مُكرَّرة، كما أنها تكون مُرتَّبة. يُمكِننا بناءً على ذلك إعادة كتابة الأسطر الأربعة السابقة على النحو التالي:

ArrayList<String> list = new ArrayList<>( new TreeSet<>(coll) );

تُنشِيء التعليمة السابقة قائمةً مُرتبةً من العناصر غير المُكرَّرة ضمن التجميعة coll. يُبيّن المثال السابق مدى فعالية البرمجة المُعمَّمة generic programming. لاحِظ أنه من غير الضروري كتابة معامل النوع String بالبانيين السابقين؛ لأن المُصرِّف compiler قادرٌ على استنتاجهما بالفعل.

تُخزِّن الأطقم من النوع HashSet عناصرها ضمن بنيةٍ بيانية تُعرَف باسم جدول hash table، وسنتناول تلك البنية البيانية في المقال الموالي. تَعمَل عمليات البحث والإضافة والحذف على الجداول بكفاءة عالية، وأعلى حتى من الصنف TreeSet. بخلاف الصنف TreeSet، لا تُخزِّن الأطقم من النوع HashSet عناصرها وفقًا لأي ترتيبٍ مُحدَّد، وبالتالي لا تَكون مُضطّرةً لتنفيذ الواجهة Comparable؛ ولكن ينبغي في المقابل أن تُعرِّف شيفرة تعمية hash code مناسبة كما سنرى بالمقال التالي.

يُحدِّد التابع equals()‎ فيما إذا كان من الممكن عدّ كائنين بطقمٍ من النوع HashSet متساويين، حيث تَمرّ مُكرِّرات أطقم النوع HashSet عبر عناصرها مرورًا عشوائيًا، بل قد يتغيَّر ترتيب مرورها بالعناصر مع إضافة عنصرٍ جديد. اِستخدِم الصنف HashSet بدلًا من الصنف TreeSet إذا لم تَكْن العناصر قابلة للموازنة، أو إذا لم يَكْن ترتيبها مُهمًا، أو إذا كنت مهتمًا بكفاءة العمليات على العناصر أكثر من أي شيءٍ آخر.

ملاحظة: يُطلق على عناصر الأطقم وفقًا لنظرية المجموعات set theory الحسابية أعضاء members أو عناصر elements. وتتضمَّن العمليات الهامة على تلك الأطقم ما يلي: إضافة عنصرٍ إلى مجموعة، وحذف عنصرٍ من مجموعة، وفحص فيما إذا كانت قيمةٌ ما عنصرًا ضمن مجموعة. إذا كان لدينا طقمين، يُمكِننا إجراء العمليات التالية عليهما: توحيد union طقمين، وتقاطع intersection بين طقمين، والفرق بين طقمين. تُوفِّر جافا تلك العمليات للأطقم من النوع Set، ولكن بأسماءٍ مختلفة. بفرض أن لدينا طقمين A و B، فإن:

A.add(x)‎: يُضيف العنصر x إلى الطقم A.
A.remove(x)‎: يحذف العنصر x من الطقم A.
A.contains(x)‎: يفحص إذا كانت x عنصرًا بالطقم A.
A.addAll(B)‎: يحسب اتحاد الطقمين A و B.
A.retainAll(B)‎: يحسب التقاطع بين الطقمين A و B.
A.removeAll(B)‎: يحسب الفرق بين الطقمين A - B.

تختلف الأطقم بمفهومها الحسابي عن الأطقم بلغة جافا بالنقاط التالية:

يجب أن تكون الأطقم نهائية finite، بينما تكون المجموعات الحسابية عادةً لا نهائية.
قد تحتوي المجموعات الحسابية على عناصر عشوائية، بينما تكون الأطقم من نوعٍ محدد مثل Set<T>‎، ولا يُمكِنها أن تحتوي على أية عناصر غير مُنتمية للنوع T.
تُعدِّل العملية A.addAll(B)‎ قيمة A، بينما تَحسب عملية الاتحاد بين الطقمين A وB طقمًا جديدًا دون أن تُعدِّل من قيمة أيٍّ من الطقمين الأصليين.

سنتعرض بالتمرين 10.2 لمثالٍ عن العمليات الحسابية على الأطقم.

أرتال الأولوية

يُعدّ رتل الأولوية priority queue نوعًا بيانيًا مجردًا abstract data type يُمثِّل تجميعة عناصر، حيث يُسنَد إلى كل عنصرٍ منها أولوية priority معينة، وهو ما يَسمَح بالموازنة بينها. تتضمَّن العمليات على أرتال الأولوية ما يلي:

عملية add المسؤولة عن إضافة عنصرٍ إلى التجميعة.
عملية remove المسؤولة عن حذف العنصر ذو الأولوية الأقل من التجميعة وإعادته قيمةً لعملية الحذف ذاتها.
عملية الحذف remove بحيث تَحذف العنصر ذا الأولوية الأقل، ولكن من الممكن نظريًا حذف العنصر ذي الأولوية القصوى.

يُمكنِنا تنفيذ رتل الأولوية باستخدام قائمةٍ مترابطة linked list لتخزين العناصر بحيث تكون مُرتبةً تصاعديًا وفقًا لترتيب أولوياتها. تَحذِف remove في تلك الحالة أول عنصرٍ ضمن القائمة وتُعيده؛ بينما يجب على عملية add إضافة العنصر الجديد بموضعه الصحيح ضمن القائمة، وهو ما يستغرق زمن تشغيل وسطي قدره Θ(n)‎، حيث n هي عدد عناصر القائمة. يُمكِننا أيضًا تنفيذ رتل الأولوية بطريقةٍ أكثر كفاءةً بحيث يكون زمن تشغيل عمليتي add و remove مُساويًا Θ(log(n))‎؛ وتعتمد تلك الطريقة على استخدام بنية بياناتٍ تُعرَف باسم الكومة heap، وهي مختلفةٌ عن قسم الكومة بالذاكرة الذي تُنشأ فيه الكائنات objects.

يُنفِّذ الصنف PriorityQueue<T>‎ ذو المعاملات غير مُحدَّدة النوع parameterized رتل أولوية للكائنات من النوع T، كما يُنفِّذ الواجهة Collection<T>‎. فإذا كان pq رتل أولويةٍ من النوع PriorityQueue، فسيحتوي على جميع التوابع methods المُعرَّفة ضمن تلك الواجهة interface. سنستعرِض فيما يلي أكثرها أهمية:

pq.add(obj)‎: يُضيف obj إلى رتل الأولوية. يجب أن يكون obj كائنًا من النوع T.
pq.remove()‎: يَحذِف أقل العناصر أولوية، ويعيدها أي تكون القيمة المُعادة كائنٌ من النوع T، وإذا كان الرتل فارغًا، يَحدُث اعتراض exception.
pq.isEmpty()‎: يَفْحَص إذا كان رتل الأولوية فارغًا.

سنفحص الآن الطريقة التي تتحدَّد على أساسها أولوية العناصر ضمن رتل أولوية، وهي تشبه عملية الترتيب، ولهذا يجب أن نكون قادرين على موازنة أي عنصرين داخل الرتل. قد نواجه موقفًا من اثنين: إما أن تكون العناصر مُنفِّذة للواجهة Comparable، ويُستخدَم عندها التابع compareTo()‎ المُعرَّف بتلك الواجهة لموازنة العناصر؛ أو أن نُمرِّر كائنًا من النوع Comparator مثل معاملٍ لباني الصنف PriorityQueue ويُستخدَم في تلك الحالة التابع compare المُعرَّف بالنوع Comparator للموازنة.

يُمكِننا استخدام الأصناف المُنفِّذة للواجهة Comparable، مثل String و Integer و Date مع أرتال الأولوية. فعلى سبيل المثال، قد نَستخدِم رتل أولوية من السلاسل النصية PriorityQueue<String>‎ لنُرتِّبها ترتيبًا أبجديًا على النحو التالي: سنُضيِف جميع السلاسل النصية إلى رتل الأولوية، ثم نَحذِفها واحدةً تلو الأخرى. وبما أن عناصر أرتال الأولوية تُحذَف بحسب أولويتها، فستَجِد أنها تُحذَف بحسب ترتيبها الأبجدي.

كنا قد أوضحنا سابقًا استخدام طقمٍ من النوع TreeSet لترتيب تجميعةٍ من العناصر، وكذلك لحذف المُكرَّر منها، ويُمكِننا بالمثل استخدام الصنف PriorityQueue لترتيب عناصر تجميعة، ولكن بدون حذف أي عنصرٍ حتى المُكرَّر منها. إذا كانت coll مثلًا تجميعةً من النوع Collection<String>‎، فستطبع الشيفرة التالية جميع عناصرها بما في ذلك المُكرَّر منها:

PriorityQueue<String> pq = new PriorityQueue<>();
pq.addAll( coll );
while ( ! pq.isEmpty() ) {
    System.out.println( pq.remove() );
}

ملاحظة: لا يُمكِن اِستخدَام مُكرِّر iterator أو حلقة for-each لطباعة العناصر بالمثال السابق، لأنها لا تجتاز عناصر أرتال الأولوية priority queue وفقًا لترتيبها التصاعدي.

يُنشِئ البرنامج التوضيحي WordListWithPriorityQueue.java قائمةً مُرتّبةً من الكلمات الموجودة بملفٍ معين دون أن يَحذِف أيّ كلماتٍ مُكرَّرة، حيث يُخزِّن البرنامج الكلمات برتل أولوية. يُمثِل هذا البرنامج تعديلًا بسيطًا على البرنامج الأصلي WordListWithTreeSet.java.

تُستخدَم أرتال الأولوية في تطبيقاتٍ أخرى غير الترتيب، مثل تنظيم عملية تنفيذ الحاسوب لعدة وظائف jobs ذات أولوياتٍ مختلفة، وبحيث يكون ترتيب التنفيذ من الوظائف ذات الأقل أولوية فالأعلى. يُمكِننا بناءً على ذلك تخزين الوظائف برتل أولوية؛ وعندما يَحذِف الحاسوب وظيفةً من الرتل لينفِّذها، سيَحذِفها وفقًا للترتيب التصاعدي لأولويتها.

ترجمة -بتصرّف- للقسم Section 2: Lists and Sets من فصل Chapter 10: Generic Programming and Collection Classes من كتاب Introduction to Programming Using Java.