البرمجة باستخدام إطار جافا للتجميعات JFC

سنناقش خلال هذا المقال أمثلةً برمجيةً تَستخدِم أصنافًا من إطار جافا للتجميعات Java Collection Framework؛ وهذا الإطار سهل الاستخدام بالموازنة مع ما ستواجهه من صعوبة إذا أردت برمجة بنى بيانات data structures جديدةٍ من الصفر.

جداول الرموز

سنبدأ بتطبيقٍ مهمٍ على الخرائط maps. فعندما يقرأ المُصرِّف الشيفرة المصدرية source code لأي برنامج، فسيواجه تعريفاتٍ لمتغيراتٍ variables، أو لبرامجٍ فرعية subroutines، أو لأصناف classes، وقد يَستخدِم البرنامج أسماء أي من تلك الأشياء لاحقًا، ولذلك يجب أن يتذكَّر المُصرِّف تعريف كل اسم؛ وبالتالي عندما يُقابِل المُصرِّف بعد ذلك اسمًا خلال البرنامج، فإنه يُطبِق تعريف definition ذلك الاسم. يُعدّ ذلك تطبيقًا مباشرًا على الخرائط من النوع Map؛ بحيث يُمثِّل كل اسمٍ مفتاحًا key ضمن الخريطة؛ في حين يُمثِّل تعريف ذلك الاسم قيمته value. عند اِستخدَام خريطةٍ لذلك الغرض، يُطلَق عليها اسم جدول الرموز symbol table.

يتعامل المُصرِّف عمومًا مع أنواعٍ مختلفةٍ من الأسماء، كما أنه يُخزِّن نوعًا مختلفًا من المعلومات لكل نوعٍ من الأسماء، ولهذا تَكون القيم values المُخزَّنة بجدول الرموز symbol table معقدةً نوعًا ما، لذلك سنَستخدِم مثالًا مُبسطًا ضمن سياقٍ آخر. لنفترض أننا نريد كتابة برنامجٍ يُحصِّل قيمة التعبيرات expressions المُدْخَلة من قِبَل المُستخدِم، وأن التعبيرات قد تحتوي على مُتغيِّراتٍ إلى جانب العوامل operators والأعداد والأقواس. هذا يعني أننا سنحتاج إلى طريقةٍ ما لإسناد assign القيم للمتغيرات؛ بحيث نتمكَّن من استرجاع قيمة مُتغيِّرٍ معينٍ عندما يُشير إليه تعبيرٌ ما فيما بعد.

يُمكِننا تخزين تلك البيانات بجدول رموز symbol table من النوع Map<String,Double>‎؛ بحيث تُمثِّل مفاتيحه أسماء المتغيرات؛ بينما تُمثِّل قِيمهُ values القيم المُسندة لتلك المتغيرات، والتي ستكون من النوع double. تذكَّر أنه لا يُمكِن استخدام نوعٍ أساسي primitive types، مثل double على أنه معامل نوعٍ type parameter، وإنما يجب استخدام صنف تغليف wrapper، مثل Double (انظر مقال مفهوم البرمجة المعممة Generic Programming).

سنَستخدِم برنامجًا بسيطًا يُمكِّن المُستخدِم من كتابة أوامرٍ مشابهة لما يَلي:

let x = 3 + 12
print 2 + 2
print 10*x +17
let rate = 0.06
print 1000*(1+rate)

يُعد هذا البرنامج مُفسِّرًا interpreter للغةٍ بسيطةٍ جدًا، حيث يُفهم من البرنامج أمرين بسيطين، هما print و let؛ فعند تنفيذ الأمر print، يُحصِّل الحاسوب قيمة التعبير، ثم يعرض قيمته. إذا احتوى التعبير على مُتغيِّر، سيبحث الحاسوب عن قيمة ذلك المتغير بجدول الرموز symobl table؛ أم الأمر let فهو يسمح للمُستخدِم بإسناد قيمةٍ معينةٍ إلى متغير، ويجب أن يُخزِّن الحاسوب عندها قيمة المُتغيِّر بجدول الرموز. لاحِظ أن المتغيرات هنا ليست متغيراتٌ ببرنامج جافا ذاته، حيث ينفّذ البرنامج فقط ما يُمكِن عدّه برنامجًا بسيطًا أدْخله الُمستخدِم، ونقصد بالمتغيرات تلك المتغيرات الموجودة ببرنامج المُستخدِم. بما أنه يجب على المُستخدِم أن يكون قادرًا على اختيار أسماء متغيراته، فلا يمكن برنامج جافا نفسه أن يعرف مُقدمًا المُتغيِّرات التي سيُدخِلها المُستخدِم.

كنا قد كتبنا البرنامج SimpleParser2.java في مقال تصميم محلل نموذجي تعاودي بسيط Recursive Descent Parser في جافا لتحصيل قيم تعبيراتٍ expressions لا تحتوي على متغيرات. سنكتب الآن البرنامج التوضيحي SimpleInterpreter.java المبني على البرنامج القديم، ولهذا لن نناقش سوى الأجزاء المُتعلِّقة بجدول الرموز symbol table.

يَستخدِم البرنامج خريطةً من النوع HashMap لتمثيل جدول الرموز. من الممكن استخدام الصنف TreeMap، ولكننا في الواقع لا نحتاج إلى تخزين المُتغيِّرات على نحوٍ مرتب؛ لأن البرنامج لا يَسترجعها وفقًا لترتيبها الأبجدي. عرَّفنا مُتغيِّرًا اسمه symbolTable من النوع HashMap<String,Double>‎ ليُمثِّل الجدول الرمزي على النحو التالي:

symbolTable = new HashMap<>();

يُنشِيء الأمر السابق خريطةً فارغةً لا تحتوي على أية ارتباطات مفتاح/قيمة. ليتمكَّن البرنامج من تنفيذ الأمر let، سيَستدعِي تابع جدول الرموز put()‎ لرَبْط قيمةٍ معينةٍ باسم مُتغيّرٍ معين. إذا كان اسم المُتغيِّر مُخزَّنًا بمُتغيّرٍ varName من النوع String مثلًا، وكانت قيمته مُخزَّنةً بمُتغيِّر val من النوع double، فسيضيف الأمر التالي الارتباط المقابل لذلك المُتغيِّر بجدول الرموز symbol table:

symbolTable.put( varName, val );

ستَجِد ما سَبَق مُعرّفًا بالتابع doLetCommand()‎ بالبرنامج SimpleInterpreter.java. لاحِظ أن القيمة المُخزَّنة فعليًا بجدول الرموز هي كائنٌ object من النوع Double، رغم أننا مرَّرنا المُتغير val من النوع double للتابع put؛ وذلك لأن جافا تُجرِي تحويلًا تلقائيًا من النوع double إلى النوع Double إذا اقتضت الضرورة.

تُوفِّر جافا الثابتين Math.PI و Math.E لتمثيل الثابتين الرياضين π و e على الترتيب، ولنتيح لمُستخدِم البرنامج الإشارة إليهما، أضفنا مُتغيِّرين pi و e إلى جدول الرموز symbol table باستخدام الأوامر التالية:

symbolTable.put( "pi", Math.PI );
symbolTable.put( "e", Math.E );

عندما يواجه البرنامج مُتغيرًا أثناء تحصيله لقيمة تعبيرٍ ما، فإنه يَستدعِي تابع جدول الرموز get()‎ لاسترجاع قيمة ذلك المُتغيِّر؛ حيث تُعيد الدالة symbolTable.get(varName)‎ قيمةً من النوع Double، ولكنها أيضًا قد تُعيد القيمة الفارغة null إذا لم تُسند من قبل أي قيمةٍ للمُتغيِّر varName بجدول الرموز. من المهم فحَص تلك الاحتمالية؛ لأنها تَعني أن المُستخدِم يُحاوِل الإشارة إلى مُتغيّرٍ لم يُعرِّفه بعد، ولا بُدّ أن يَعُدّها البرنامج خطأً error. يُمكِننا كتابة ذلك على النحو التالي:

Double val = symbolTable.get(varName); :
if (val == null) {
   ... // بلغ عن اعتراض : متغير غير مُعرَّف
}
// ‫القيمة المربوطة بالمتغير varName هي ()val.doubleValue

ستَجِد ما سَبَق ضمن التابع primaryValue()‎ بالبرنامج SimpleInterpreter.java.

ربما تَكون قد أدركت الآن أهمية الخرائط وسهولة استخدامها.

أطقم ضمن خريطة

يُمكِن للكائنات الواقعة ضمن تجميعةٍ collection، أو خريطةٍ map أن تَكون من أي نوع، ويُمكِنها أن تكون هي ذاتها تجميعة. سنفحص الآن مثالًا على تخزين أطقمٍ sets داخل خريطة.

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

يُمكِننا التفكِير بالفهرس مثلُ خريطةٍ من النوع Map تَربُط كل مصطلحٍ بقائمة مراجع الصفحات الخاصة به؛ أي سيَعمَل المصطلح بمثابة مفتاحٍ للخريطة؛ بينما ستكون قيمته قائمةً بمراجع الصفحات الخاصة بالمصطلح. من الممكن لخريطةٍ من النوع Map أن تكون من الصنف TreeMap أو HashMap، لكن سيُسهِل الصنف TreeMap استرجاع المصطلحات وفقًا للترتيب المطلوب.

والآن، ينبغي أن نختار طريقة تمثيل قائمة مراجع الصفحات. إذا فكرنا قليلًا، سنَجِد أنها لا تُعدّ قائمة list بحسب مفهوم أصناف جافا المُعمَّمة، وإنما هي أقرب لأن تكون طقمًا set منها لقائمة؛ فلا يُمكِن لقائمة مراجع الصفحات أن تحتوي على عناصرٍ مُكرَّرة مثلًا؛ كما تُطبَع قوائم مراجع الصحفات دائمًا مُرتَّبة ترتيبًا تصاعديًا، ولهذا فإن استخدام طقمٍ مُرتَّب sorted set هو الحل الأمثل. سنَستخدِم إذًا طقمًا من النوع TreeSet لتمثيل كل قائمة صفحات، وستَكون القيم المُخزَّنة ضمن الطقم من النوع int. وكما ذكرنا مُسبقًا، لا يُمكِن لبنى البيانات المُعمَّمة generic data structures أن تَحمِل شيئًا ليس بكائن object، ولهذا يجب أن نَستخدِم صنف التغليف Integer.

تلخيصًا لما سَبَق، سنَستخدِم خريطةً من النوع TreeMap لتمثيل الفهرس، بحيث تَعمَل أسماء المصطلحات بمثابة مفاتيح keys من النوع String، وتكون القيم values أطقمًا من النوع TreeSet تحتوي على أعدادٍ صحيحةٍ مُمثِلةٍ لأرقام الصفحات؛ أي ستكون الأطقم من النوع TreeSet<Integer>‎، وستَكون الخريطة المُمثِلة لكل لفهرس (مفاتيح من النوع String وقيم من النوع TreeSet<Integer>‎) من النوع:

TreeMap< String, TreeSet<Integer> >

يُعدّ هذا النوع مثالًا عاديًا على النوع TreeMap<K,V>‎، حيث K=String و V=TreeSet<Integer>‎. قد تبدو الأسماء المُركَّبة للأنواع (كما في المثال السابق) مُربِكةً نوعًا ما، ولكن إذا فكرت ببنية البيانات المطلوبة، ستَجِد أن الاسم منطقي تمامًا.

سنبدأ لإنشاء الفهرس بخريطةٍ map فارغةٍ من النوع TreeMap، ثم سنَمُرّ عبر الكتاب بحيث نُضيف إلى الخريطة أي مَرجعٍ نريده ضمن الفهرس، وسنطبع أخيرًا بيانات الخريطة. سنؤجل حديثنا عن طريقة العثور على المراجع المطلوب إضافتها، ونُركِّز أولًا على الكيفية التي سنَستخدِم بها خريطةً من النوع TreeMap. سنُنشِئ بدايةً الخريطة باستخدام الأوامر التالية:

TreeMap<String,TreeSet<Integer>>  index; // صرِّح عن المتغير
index = new TreeMap<>();  // أنشِئ كائن الخريطة

ملاحظة: يُمكِنك حذف معاملات الأنواع من الباني حتى لو كانت مُركَّبة.

لنفترض الآن أننا قد وجدنا إشارةً لمصطلحٍ ما (من النوع String) بصفحةٍ ما pageNum (من النوع int)، وأننا نحتاج الآن إلى إضافتها إلى الفهرس. ينبغي إذًا استدعاء index.get(term)‎ لنسترجِع قائمة مراجع الصفحات الخاصة بذلك المصطلح؛ حيث سيُعيد التابع القيمة الفارغة null، أو طقمًا يحتوي على مراجع الصفحات التي أضفناها مُسبقًا. إذا كانت القيمة المعادة تُساوِي null، فإن هذا المرجع هو الأول لذلك المصطلح، ولهذا ينبغي أن نُضيِف المصطلح للفهرس مصحوبًا بطقمٍ يحتوي على مرجع الصفحة الذي وجدناه للتو؛ أما إذا كانت القيمة المُعادة غير فارغة، فسيكون لدينا بالفعل طقمًا يحتوي على عدَّة مراجع، وبالتالي ينبغي فقط أن نُضيف إليه مرجع الصفحة الجديد. ألقِ نظرةً على الشيفرة التالية المسؤولة عن تحقيق ما ذُكر للتو:

/**
 * أضف مرجع صفحة إلى الفهرس
 */
void addReference(String term, int pageNum) {
   TreeSet<Integer> references; // الطقم المتضمن لأرقام الصفحات التي 
                                // ‫ظهر بها `term` حتى الآن

    references = index.get(term);
   if (references == null){
         // 1
       TreeSet<Integer> firstRef = new TreeSet<>();
       firstRef.add( pageNum );  // pageNum is "autoboxed" to give an Integer!
       index.put(term,firstRef);
   }
   else {
        // 2
      references.add( pageNum );
   }
}

[1] هذا هو المرجع الأول الذي نعثُر عليه لتلك الكلمة، ولذلك أنشِئ طقمًا جديدًا يحتوي على رقم الصفحة، وأضِفه إلى الفهرس index بمفتاحٍ يُساوِي الكلمة ذاتها.
[2] تحتوي references على طقمٍ بمراجع الصفحات التي وجدناها حتى الآن لهذه الكلمة. أضِف رقم الصفحة الجديد إلى الطقم، حيث ربطنا هذا الطقم بتلك الكلمة من قبل بالفهرس index.

يتبقَّى لنا الآن طباعة الفهرس، ولهذا سنحتاج إلى المرور عبر المصطلحات الموجودة بالفهرس واحدًا تلو الآخر، لنَطبَع كُلًا منها مع مراجع الصفحات الخاصة بها. يُمكِننا استخدام مُكرّرٍ من النوع Iterator للمرور عبر عناصر الفهرس، إلا أن استخدام حلقة تكرار for-each سيَكون أسهل نوعًا ما؛ حيث ستُمكِّننا من المرور عبر الارتباطات المُخزَّنة بالخريطة، والتي تمثِّل أزواجًا (مفتاح/قيمة key/value pair)؛ حيث يُشير المفتاح إلى مصطلحٍ معين؛ بينما تُشير القيمة إلى طقمٍ يحتوي على مراجع الصفحات التي أشارت لذلك المصطلح.

سنَطبَع بداخل كل حلقة تكرار مجموعة الأعداد الصحيحة الموجودة بالطقم، وهو ما يُمكِننا فعله باستخدام حلقة for-each أخرى، ونكون بذلك قد اِستخدَمنا حلقتي تكرار for-each متداخلتين nested. يُمكِنك أن تُجرِّب فعل الأمر نفسه باستخدام المُكرِّرات iterators، لتُدرِك السهولة التي وفَّرتها لك حلقة التكرار for-each. ألقِ نظرةً على الشيفرة التالية المسؤولة عن طباعة فهرس المصطلحات:

/**
 * اطبع جميع محتويات الفهرس
 */
void printIndex() {

    for ( Map.Entry<String,TreeSet<Integer>>  entry :  index.entrySet() ) {

        String term = entry.getKey();
        TreeSet<Integer> pageSet = entry.getValue();

        System.out.print( term + ": " );
        for ( int page : pageSet ) {
            System.out.print( page + " " );
        }
        System.out.println();

    }

}

ربما يَكون اسم النوع Map.Entry<String,TreeSet<Integer>>‎ المُبين بالأعلى هو أكثر الأشياء تعقيدًا بالشيفرة، ولكن تذكَّر أن الارتباطات المُخزَّنة بخريطةٍ من النوع Map<K,V>‎ تكون من النوع Map.Entry<K,V>‎، ولهذا نَسخَنا ببساطةٍ معاملات النوع Map.Entry<String,TreeSet<Integer>>‎ من تعليمة التصريح عن index. لاحِظ أيضًا أننا اِستخدَمنا مُتغيرًا مُتحكِّمًا بالحلقة loop control variable، اسمه page من النوع int للمرور عبر عناصر الطقم pageSet من النوع TreeSet<Integer>‎. ربما توقَّعت أن يكون المُتغيِّر page من النوع Integer، وليس int، حيث يُمكِنك استخدام النوع Integer هنا، ولكن يُمكِنك أيضًا استخدام النوع int؛ حيث تَسمَح خاصية التحويل التلقائي للأنواع type conversion بإسناد قيمةٍ من النوع Integer إلى مُتغيّرٍ من النوع int.

تُعدّ الشيفرة السابقة صغيرةً بالموازنة مع كمية العمليات وتعقيدها. سنتعرَّض بتمرين 10.6 لمسألةٍ مماثلةٍ تمامًا لمسألة الفهرس بالأعلى.

ربما من الأفضل قليلًا طباعة قائمة المراجع بحيث تَفصِل فاصلةٌ بين الأعداد الصحيحة المُمثِلة لأرقام الصفحات، حيث يستخدِم التابع printIndex()‎ المُعرَّف بالشيفرة السابقة مسافةً فارغةً للفصل بين أرقام الصفحات، وربما لاحظت ذلك كونه يَطبَع مسافةً فارغةً إضافيةً بعد آخر مرجع صفحة ضمن القائمة، ولكنها غير ظاهرةٍ عمومًا، وبالتالي لا يُمثِل ذلك أية مشكلة. في المقابل، إذا طَبَعَنا فاصلةً بدلًا من المسافة الفارغة، فسيَكون ظهور الفاصلة بالنهاية أمرًا سخيفًا. ينبغي إذًا أن نَعرِض القائمة على النحو "17,42,105" وليس "‎‏17,42,105‎,‎‏"، ولكن كيف يُمكِننا تَجنُّب طباعة الفاصلة الأخيرة؟ لسوء الحظ، ليس من السهل فعل ذلك إذا كنا نَستخدِم حلقة التكرار for-each؛ وربما من الأفضل استخدام مُكرّرٍ iterator لحل تلك المشكلة على النحو التالي:

Iterator<Integer>  iter = pageSet.iterator();
int firstPage = iter.next();  // نعرِف أن الطقم يحتوي على عنصرٍ واحدٍ على الأقل بهذا البرنامج

System.out.print(firstPage);
while ( iter.hasNext() ) {
   int nextPage = iter.next();
   System.out.print("," + nextPage);
}

يُمكِننا بدلًا من ذلك الاعتماد على حقيقة كون الصنف TreeSet يَتضمَّن تابعًا اسمه first()‎، وهو مسؤولٌ عن إعادة أول عنصرٍ ضمن الطقم، وهو العنصر الأصغر بحسب ما يَعنيه الترتيب المُستخدَم للموازنة بين عناصر ذلك الطقم. يُمكِننا إذًا حل المشكلة باستخدام ذلك التابع مع حلقة التكرار for-each على النحو التالي:

int firstPage = pageSet.first();  // اعثر على أول رقم صفحة بالطقم

for ( int page : pageSet ) {
   if ( page != firstPage )
      System.out.print(","); // اطبع فاصلةً إذا لم تكن هذه هي الصفحة الأولى

   System.out.print(page);
}

أخيرًا، تَستخدِم الشيفرة التالية عرضًا view لجزءٍ من الشجرة (انظر المقال السابق):

int firstPage = pageSet.first();  // استرجع العنصر الأول الذي نعرف بوجوده
System.out.print(firstPage);      // اطبع العنصر الأول بدون فاصلة

for ( int page : pageSet.tailSet( firstPage+1 ) ) // معالجة باقي العناصر.
   System.out.print( "," + page );

استخدام الموازنة

هناك نقطةٌ نريد مناقشتها بخصوص مسألة الفهرس السابقة؛ وهي تتمحور حول إمكانية وجود أحرفٍ بالحالة الكبيرة upper case والصغيرة lower case في المصطلحات الموجودة بالفهرس، فسيتسبَّب ذلك بحدوث مشكلة؛ لأن المصطلحات لن تَكون مُرتَّبة ترتيبًا أبجديًا بعد الآن. لا يعتمد الصنف String في الواقع على الترتيب الأبجدي، وإنما على شيفرة اليونيكود Unicode codes لمحارف السلسلة النصية.

تُعدّ شيفرة الأحرف الأبجدية بحالتها الكبيرة أقل من شيفرة الأحرف بحالتها الصغيرة، ولذلك تَسبِق المُصطلحات البادئة بالحرف "Z" مثلًا تلك البادئة بالحرف "a". في المقابل، إذا تَضمَّنت المصطلحات أحرفًا بالحالة الصغيرة فقط أو بالحالة الكبيرة فقط، فستَكون مُرتَّبةً بحسب الترتيب الأبجدي. لنفترض أننا نريد السماح بكلتا الحالتين، وفي نفس الوقت نريد للعناصر أن تكون مُرتَّبة ترتيبًا أبجديًا؛ فلا يُمكِن في هذه الحالة الاعتماد على الترتيب الافتراضي للصنف String، وإنما ينبغي أن نُخصِّص تابعًا آخرًا للموازنة بين المفاتيح الموجودة بالخريطة، وهو ما يُمثِّل الاستخدام الأمثل للواجهة Comparator.

لا بُدّ لأي كائنٍ يُنفِّذ الواجهة Comparator<T>‎ أن يُعرِّف define التابع التالي للموازنة بين كائنين من النوع T:

public int compare( T obj1, T obj2 )

يُعيد التابع السابق عددًا صحيحًا سالبًا، أو صفرًا، أو موجبًا، إذا كان obj1 أقل من obj2، أو يُساوِيه، أو أكبر منه على الترتيب. إذا أردنا الموازنة بين سلسلتين نصيتين من النوع String بحيث نتجاهل حالة أحرف السلاسل، وهو ما يُنفِّذه بالفعل التابع compareToIgnoreCase()‎ المُعرِّف بالصنف String؛ فسنحتاج إذًا إلى كائنٍ من النوع Comparator<String>‎؛ ليُمكِّن الصنف TreeMap من إجراء موازنةٍ غير تلك الموازنة الافتراضية. بما أن الواجهة Comparator هي بالأساس واجهة دالة functional interface، يُمكِننا أن نُخصِّص قيمتها باستخدام تعبير لامدا lambda expression على النحو التالي:

(a,b) -> a.compareToIgnoreCase(b)

تبقَّى لنا الآن تمرير الكائن المنتمي للنوع Comparator إلى باني الصنف TreeMap، وبذلك نكون قد حَلِلنا مشكلة الفهرس:

index = new TreeMap<>( (a,b) -> a.compareToIgnoreCase(b) );

بما أن تعبير لامدا lambda expression المُستخدَم مجرد استدعاءٍ لتابعٍ موجودٍ بالفعل ضمن الصنف String، فإنه من الممكن أيضًا تخصيصه باستخدام مرجع تابعي method reference (انظر مقال تعبيرات لامدا (Lambda Expressions) في جافا) على النحو التالي:

index = new TreeMap<>( String::compareToIgnoreCase );

ستؤدي الشيفرة بالأعلى الغرض منها، ولكنها تُعانِي من مشكلةٍ واحدة. لنفترض أن البرنامج قد اِستدَعى التابع addReference("aardvark",56)‎، ثم اِستدَعى addReference("Aardvark",102)‎ لاحقًا. نلاحظ تشابه الكلمتان "aardvark" و"Aardvark" تمامًا مع اختلافٍ واحدٍ فقط يتعلَّق بحالة حرفهما الأول، وبالتالي عندما نُحوِّل أحرف الكلمة الأولى إلى حالتها الصغيرة، ستُصبِح الكلمتان متطابقتين. والآن، عندما نُدْخِلهما إلى الفهرس، هل سيتعامل معهما على أساس كونهما مصطلحين مختلفين أم لا؟

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

عد الكلمات

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

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

من الأفضل إذًا الاحتفاظ بعدّادٍ counter لكل كلمة؛ وعندما يُقابِل البرنامج كلمةً معينةً لأول مرة، فسيَضبُط عداد الكلمة إلى القيمة 1، ثم يُزيدها بمقدار الواحد بكل مرةٍ يُقابِل فيها تلك الكلمة لاحقًا. تَستعرِض الشيفرة التالية تعريف الصنف المُتداخِل الساكن static nested الذي سيَستخدِمه البرنامج للاحتفاظ بالمعلومات الخاصة بكل كلمة:

// 1
private static class WordData { 
   String word;
   int count;
   WordData(String w) {
         // 2
      word = w;
      count = 1;  // The initial value of count is 1.
   }
} // WordData نهاية الصنف

[1] يُمثِّل هذا الصنف البيانات التي نحتاجها عن كل كلمة؛ أي الكلمة ذاتها، وعدد مرات حدوثها.
[2] الباني المسؤول عن إنشاء كائنٍ من النوع WordData عندما تحدُث الكلمة للمرة الأولى.

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

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

بما أننا سنحتاج إلى طباعة الكلمات بترتيبها الأبجدي بعد الانتهاء من قراءة الملف، فسيكون الصنف TreeMap أنسب من الصنف HashMap. سيُحوِّل البرنامج كل الكلمات إلى حالتها الصغيرة lower case؛ ويمكننا بالتالي الاعتماد على الترتيب الافتراضي الذي يَستخدِمه الصنف String. تُنشِئ التعليمة التالية مُتغيِّرًا اسمه words من النوع TreeMap<String,WordData>‎، المُمثِل للخريطة المُستخدَمة لتخزين البيانات:

TreeMap<String,WordData> words = new TreeMap<>();

عندما يقرأ البرنامج كلمةً من ملف، فإنه يَستدعِي words.get(word)‎ ليَفحَص إذا كانت الكلمة موجودةً بالفعل ضمن الخريطة؛ فإذا أعاد التابع القيمة الفارغة null، فيَعنِي ذلك أنها المرة الأولى التي يرى فيها البرنامج تلك الكلمة، وسينشِئ بالتالي كائنًا من النوع WordData، ويُدْخِله بالخريطة باستدعاء التعليمة words.put(word, new WordData(word))‎.

في المقابل، إذا أعاد التابع words.get(word)‎ قيمةً غير فارغة، فإنها ستَكون بطبيعة الحال كائنًا من النوع WordData، وسيُزيِد البرنامج قيمة عدّاد counter الكائن بمقدار الواحد. يَستخدِم البرنامج التابع readNextWord()‎، الذي كتبناه بتمرين 7.6، لقراءة كلمةٍ واحدةٍ من الملف، حيث يُعيد القيمة null عند وصوله إلى نهاية الملف. ألقِ نظرةً على الشيفرة الخاصة بقراءة الملف وحساب المعلومات المطلوبة:

String word = readNextWord();
while (word != null) {
   word = word.toLowerCase();  //‫ حوِّل word إلى حالة الأحرف الصغيرة
   WordData data = words.get(word);
   if (data == null)
      words.put( word, new WordData(word) );
   else
      data.count++;
   word = readNextWord();
}

بعد انتهاء البرنامج من قراءة الكلمات وطباعتها بحسب ترتيبها الأبجدي، يجب أن يُرتِّبها بحسب عدد مرات تكرارها، ثم يَطبَعها مُجددًا. سنَستخدِم خوارزميةً مُعمَّمة generic algorithm للترتيب، حيث يُمكِننا مثلًا أن ننسخ كائنات الصنف WordData إلى قائمةٍ أخرى، ثم نُطبِق عليها خوارزميةً مُعمَّمة، مثل التابع Collections.sort(list,comparator)‎، والذي يَستقبِل كائنًا من النوع comparator بمثابة معاملٍ parameter ثانٍ، كما يُمكِننا تمريره بصيغة تعبير لامدا lambda expression.

يُخزِّن مُتغيِّر الخريطة words كائنات الصنف WordData التي نرغب بترتيبها. سنَستدعِي إذًا التابع words.values()‎ لنَسترجِع تجميعةً من النوع Collection مُكوَّنةً من جميع القيم الموجودة بالخريطة. بما أن باني الصنف ArrayList يَستقبِل تجميعةً، ويَنسخَ عناصرها إلى القائمة التي يُنشِئها، فإننا سنَستخدِم الأوامر التالية لإنشاء قائمةٍ من النوع ArrayList<WordData>‎ تحتوي على البيانات الخاصة بالكلمات، ولنُرتِّبها بعد ذلك بحسب عدد مرات حدوث كل كلمة:

ArrayList<WordData> wordsByFrequency = new ArrayList<>( words.values() );
Collections.sort( wordsByFrequency, (a,b) -> b.count - a.count );

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

ينبغي الآن طبَاعة بيانات جميع كائنات الصنف WordData مرتين، بحيث تَكون مُرتَّبة ترتيبًا أبجديًا بالمرة الأولى، ومُرتَّبة بحسب عدد مرات حدوث كل كلمة بالمرة الثانية. ستَجِد البيانات مُرتَّبةً ترتيبًا أبجديًا بالفعل ضمن الخريطة (ضمن قيم values الخريطة بصورةٍ أدق) المُنتمية للنوع TreeMap، ويُمكِننا بالتالي استخدام حلقة التكرار for-each لطباعة بيانات التجميعة المُعادة من الاستدعاء words.values()‎، وسترى أنها مُرتّبةً أبجديًا بالفعل. سنَستخدِم بالإضافة إلى ذلك حلقة تكرار for-each أخرى، لطباعة بيانات القائمة wordsByFrequency، وسترى أن الكلمات مُرتّبةً بحسب عدد مرات حدوث كل كلمة ترتيبًا تنازليًا. ألقِ نظرةً على الشيفرة التالية:

TextIO.putln("List of words in alphabetical order" 
      + " (with counts in parentheses):\n");
for ( WordData data : words.values() )
   TextIO.putln("   " + data.word + " (" + data.count + ")");

TextIO.putln("\n\nList of words by frequency of occurrence:\n");
for ( WordData data : wordsByFrequency )
   TextIO.putln("   " + data.word + " (" + data.count + ")");

يُمكِنك الإطلاع على شيفرة البرنامج بالكامل بالملف WordCount.java. لاحظ اعتماد البرنامج على إمكانيات الصنف TextIO.java الذي ناقشناه في مقال المدخلات والمخرجات النصية في جافا فيما يتعلَّق بقراءة الملفات والكتابة بها.

بالمناسبة، إذا طَبقت البرنامج WordCount على ملفٍ كبيرٍ نسبيًا، وفَحصت الخَرْج الناتج عنه، فستُلاحِظ شيئًا بخصوص التابع Collections.sort()‎؛ حيث نَعلَم أن قائمة الكلمات الثانية مُرتّبةً بحسب عدد مرات حدوث كل كلمة، ولكن إذا دققت النظر إلى أي مجموعةٍ معينةٍ من الكلمات التي صَدَف وأن تكرَّرت نفس العدد من المرات، فستُلاحِظ أنها مُرتَّبةٌ أبجديًا. في الواقع، كانت الكلمات مُرتَّبة أبجديًا بالفعل قبل تطبيق التابع Collections.sort()‎ لإعادة ترتيبها بحسب عدد مرات حدوثها. ونظرًا لأن التابع Collections.sort()‎ لا يُغيِّر ترتيب الكلمات التي تكرَّرت نفس العدد من المرات، ستظل مجموعة الكلمات التي تكررت نفس العدد من المرات مُرتَّبة أبجديًا.

تُعدّ إذًا خوارزمية الترتيب sorting المُستخدَمة بالتابع Collections.sort()‎ مُستقرةً stable؛ أي أنها تَستوفِي الشرط التالي: إذا كانت الخوارزمية تُرتِّب قائمةً وفقًا لخاصيةٍ معينةٍ مُتعلِّقةٍ بعناصرها، فلا ينبغي أن تُغيِّر ترتيب العناصر التي تَملُك نفس القيمة لتلك الخاصية. إذا أتى العنصر B بعد العنصر A مثلًا ضمن قائمةٍ قبل ترتيبها، وكانت قيمة الخاصية التي سيُجرَى على أساسها ترتيب العناصر مُتساويةً للعنصرين A و B، فيجب أن يأتي العنصر B بعد العنصر A بعد ترتيب القائمة.

لا تَقَع خوارزميتا الترتيب الانتقائي SelectionSort والترتيب السريع QuickSort ضمن تصنيفات الترتيب المستقرة stable؛ بينما تَقَع خوارزمية الترتيب بالإدراج insertion sort ضمنه، ولكنها ليست سريعةً كفاية؛ وتتميز خوارزمية الترتيب بالدمج merge sort التي يَستخدِمها التابع Collections.sort()‎ بالسرعة والاستقرار.

نأمل أن تَكون الأمثلة التوضيحية التي تعرَّضنا لها خلال هذا المقال قد اقنعتك بأهمية إطار جافا للتجميعات Java Collection Framework ومدى فعاليتها.

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