Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. HTML5

Penguasaan HTML5: Tree Traversal

by
Read Time:11 minsLanguages:
This post is part of a series called HTML5 Mastery Class.
HTML5 Mastery: Fragments
HTML5 Mastery: Constraint Validation

Indonesian (Bahasa Indonesia) translation by Andy Nur (you can also view the original English article)

HTML5 Mastery series imageHTML5 Mastery series imageHTML5 Mastery series image

Salah satu konsep terpenting di DOM adalah tree traversal. Karena ilmu komputer telah ditetapkan sebagai bidang studinya sendiri, penelitian selama puluhan tahun telah digunakan untuk struktur data dan algoritma. Salah satu struktur yang paling sering digunakan adalah tree (pohon). Tree ada dimana-mana. Versi yang sangat sederhana, namun berguna dan sering digunakan adalah binary tree. Turnamen bisa diwakili sebagai binary tree. DOM tree tidak binary. Sebaliknya itu adalah K-ary tree. Setiap node mungkin memiliki nol ke sub-node N, yang disebut childNodes.

DOM tree meng-host berbagai macam kemungkinan tipe dari node. Mungkin ada Text, Element, Comment dan yang spesial lainnya, seperti ProcessingInstruction atau DocumentType, di antara banyak. Kebanyakan dari mereka tidak akan memiliki childNodes berdasarkan definisi. Mereka adalah titik akhir dan hanya membawa satu informasi saja. Misalnya, node Comment hanya membawa string komentar yang ditentukan. Node Text hanya tersedia untuk menyimpan string konten.

node Element meng-host node lain. Kita dapat secara rekursif turun dari elemen ke elemen untuk melewati semua node yang tersedia di sistem.

Contoh Ilustratif

Contoh yang juga berhubungan dengan artikel sebelumnya mengenai elemen <template> adalah mengisi struktur subtree DOM. Subtree adalah bagian dari tree, yang dimulai pada elemen tertentu. Kita memanggil elemen yang ditentukan root subtree. Jika kita mengambil elemen <html> tree sebagai root subtree, subtree akan hampir identik dengan tree sebenarnya, yang dimulai pada document, yaitu satu tingkat di bawah documentElement.

Mengisi struktur subtree mengharuskan kita untuk mengulangi semua turunan dari root subtree. Pada setiap node kita perlu memeriksa jenis node yang tepat dan kemudian melanjutkannya dengan cara yang sesuai. Misalnya, setiap elemen perlu dianggap sebagai root subtree lagi. Node teks, di sisi lain, harus dievaluasi lebih hati-hati. Mungkin kita juga ingin memeriksa nodes komentar untuk direktif khusus. Selanjutnya, atribut elemen harus diperhatikan juga.

Untuk skenarionya kita menggunakan metode yang disebut applyModel untuk mengisi string template dengan nilai dari sebuah model. Metode ini terlihat sebagai berikut dan tentu saja bisa dioptimalkan lebih lanjut. Meski begitu, untuk tujuan kita tentu sudah cukup.

Mari kita lihat sebuah implementasi untuk skenario yang dijelaskan, yang menggunakan metode applyModel pada berbagai kesempatan. Ini mengambil contoh elemen template dan objek yang disebut model untuk mengembalikan DocumentFragment yang baru. Fragmen baru menggunakan data dari model untuk mengubah semua nilai dari {X} ke hasil evaluasi expression X dengan menggunakan objek yang disediakan.

Kode sebelumnya menggunakan fungsi findAllNodes, yang mana mengambil node dan menyimpan semua turunannya dalam sebuah array. Fungsi ini kemudian dipanggil secara rekursif pada setiap turunan. Pada akhirnya semua hasil digabungkan ke satu array dari keseluruhan subtree, yaitu kita mengubah struktur tree menjadi array 1 dimensi.

Snippet berikut menunjukkan contoh implementasi untuk algoritma yang dijelaskan.

Fungsi untuk mengubah setiap node dalam array ditunjukkan di bawah ini. Fungsi melakukan beberapa manipulasi tergantung pada jenis node-nya. Kita hanya peduli dengan atribut dan node teks.

Meski kodenya mudah dimengerti, ini tidak begitu cantik. Kita memiliki beberapa masalah kinerja, terutama karena kita memiliki banyak operasi DOM yang diperlukan. Hal ini dapat dilakukan dengan lebih efisien menggunakan salah satu helper DOM tree. Perhatikan bahwa metode findAllNodes mengembalikan sebuah array dengan semua node, tidak hanya semua contoh Element di subtree. Jika kita tertarik dengan yang terakhir, kita bisa menggunakan pemanggil querySelectorAll ('*'), yang melakukan iterasi untuk kita.

Perulangan Atas Node

Solusi yang muncul segera adalah dengan menggunakan NodeIterator. Sebuah NodeIterator mengulang atas node. Ini sangat sesuai dengan kriteria kita. Kita bisa membuat NodeIterator baru dengan menggunakan metode createNodeIterator dari objek document. Ada tiga parameter penting:

  1. Root node dari subtree untuk perulangan.
  2. Filter, yang node untuk memilih/mengulang atasnya.
  3. Objek dengan acceptNode untuk pemfilteran khusus.

Sementara argumen pertama hanyalah node DOM biasa, dua lainnya menggunakan konstanta khusus. Misalnya, jika semua node harus dimunculkan, kita harus meneruskan -1 sebagai filter. Atau kita bisa menggunakan NodeFilter.SHOW_ALL. Kita bisa menggabungkan beberapa filter dengan beberapa cara. Sebagai contoh, kombinasi menampilkan semua komentar dan semua elemen dapat diungkapkan dengan NodeFilter.SHOW_COMMENT | NodeFilter.SHOW_ELEMENT.

Argumen ketiga adalah objek yang mungkin terlihat primitif seperti snippet kode berikut. Meski objek yang membungkus fungsinya tampak redundan, ini sudah ditentukan seperti itu. Beberapa browser, semisal. Mozilla Firefox, memberi kita kemungkinan untuk mengurangi objek ke satu fungsi.

Di sini kita menerima setiap node yang diteruskan. Selain itu kita memiliki pilihan untuk menolak sebuah node ((dan turunannya) dengan opsi FILTER_REJECT. Jika kita hanya ingin melewatkan node, namun tetap tertarik pada turunannya, jika ada, kita bisa menggunakan konstanta FILTER_SKIP.

Mengimplementasikan contoh sebelumnya dengan menggunakan NodeIterator cukup mudah. Kita membuat iterator baru dengan menggunakan metode konstruktor di dalam document. Kemudian kita menggunakan metode NextNode untuk mengulangi semua node.

Mari kita lihat contoh yang telah ditransformasikan.

Pencarian DOM benar-benar tersembunyi dari kita. Ini adalah keuntungan yang besar. Kita hanya meminta node yang diinginkan, dan sisanya dilakukan dengan cara yang paling efisien di mesin browser. Namun, di sisi lain kita masih harus memberikan kode untuk mengulang atribut.

Meskipun atribut ditutupi oleh konstanta SHOW_ATTRIBUTE, keduanya tidak terkait dengan elemen node sebagai turunan. Sebagai gantinya mereka tinggal di koleksi NamedNodeMap, yang tidak akan disertakan dalam pencarian oleh NodeIterator. Kita hanya bisa mengulangi atribut jika kita memulai perulangan pada atribut, batasi diri kita pada atribut saja.

Contoh sebelumnya juga bisa meminta perubahan pada filter yang disediakan. Bagaimanapun, ini bukan praktik yang baik, karena kita mungkin ingin menggunakan iterator untuk tujuan yang lain juga. Oleh karena iterator seharusnya benar-benar menyajikan solusi baca-saja, yang tidak bermutasi tree.

Mutasi tree juga tidak didukung dengan baik oleh NodeIterator. Iterator dapat dianggap seperti kursor dalam dokumen, ditempatkan di antara dua node (yang terakhir dan selanjutnya). Oleh karena itu, NodeIterator tidak mengarah ke node manapun.

Berjalan di Tree

Kita ingin melakukkan perulangan atas node dalam subtree. Pilihan lain yang mungkin muncul di benak kita adalah dengan menggunakan TreeWalker. Di sini kita berjalan di tree seperti namanya. Kita menentukan root node dan elemen yang perlu dipertimbangkan dalam route kita dan kemudian kami memprosesnya. Bagian yang menarik adalah bahwa TreeWalker memiliki banyak kesamaan dengan NodeIterator. Kita tidak hanya melihat banyak properti yang membagi, namun juga menggunakan NodeFilter yang sama untuk menyiapkan batasan.

Dalam kebanyakan skenario TreeWalker sebenarnya adalah pilihan yang lebih baik daripada NodeIterator. API dari NodeIterator membengkak karena apa yang diberikannya. TreeWalker berisi lebih banyak metode dan pengaturan, namun setidaknya menggunakannya.

Perbedaan utama antara TreeWalker dan NodeIterator adalah bahwa yang pertama menghadirkan view berorientasi tree dari node dalam subtree, bukan tampilan berorientasi daftar iterator. Sementara NodeIterator memungkinkan kita bergerak maju atau mundur, TreeWalker jug memberi kita pilihan untuk pindah ke node induk, ke salah satu dari turunannya, atau saudara kandungnya.

Berbeda dengan NodeIterator, TreeWalker menunjuk langsung ke sebuah node tertentu di pohon. Jika node yang ditunjuk dipindahkan, maka TreeWalker akan mengikuti. Lebih penting lagi, Jika node yang ditunjuk dihapus dari tree, maka secara efektif kita akan berakhir di luar tree dokumen. Jika kita mengikuti saran untuk NodeIterator dan tidak bermutasi truee selama traversal, kita akan berakhir dengan jalur yang sama.

TreeWalker juga tampaknya menjadi hampir identik dengan NodeIterator untuk tujuan kita. Ada alasan mengapa yang terakhir tidak bisa mendapatkan banyak perhatian. Namun demikian TreeWalker juga tidak begitu dikenal. Mungkin area penggunaan terlalu terbatas, tidak memberi kita kemampuan untuk melewati atribut lagi—terutama dengan opsi ketiga yang kita miliki untuk perulangan DOM tree.

Rentang Seleksi

Akhirnya, ada konstruksi ketiga yang mungkin menarik dalam keadaan tertentu. Jika kita ingin memilih rentang dalam array 1 dimensi maka kita dapat dengan mudah menerapkannya dengan hanya menggunakan dua indeks: i untuk batas awal (kiri) dan f untuk batas akhir (kanan) yang kita miliki, [i, f].

Jika kita mengganti array dengan daftar yang tertaut maka kedua indeks juga bisa diganti dengan dua node konkret, [n_i, n_f]. Keuntungan dalam pilihan ini terletak pada mekanisme pembaruan implisit. Jika kita memasukkan node di antaranya, kita tidak perlu memperbarui batas-batas jangkauan kita. Juga jika batas kiri dihapus dari daftar yang tertaut, kita mendapatkan rentang yang telah meluas ke kiri, seperti [0, n_f].

Sekarang kita tidak memiliki masalah pada 1-dimensi, tetapi pada struktur tree. Memilih berbagai K-ary tree tidaklah sepele. Kita bisa menemukan algoritma kita sendiri, tetapi DOM tree memiliki beberapa masalah khusus. Misalnya, kita memiliki node teks, yang mungkin juga dikenakan rentang. Di DOM tree kita, rentangnya terdiri dari empat properti. Kita memiliki nodel awal, node akhir dan offset untuk keduanya.

Ada juga helper, seperti metode selectNode atau selectNodeContents, yang melakukan panggilan yang benar dari setStart dan setEnd. Misalnya, memanggil selectNodeContents(node) sama dengan snippet kode:

Rentang melampaui pilihan programatik murni. Mereka juga digunakan untuk pemilihan visual yang sesungguhnya di browser. Metode getSelection() dari konteks window menghasilkan objek Selection, yang dapat dengan mudah diubah ke Range dengan memanggil getRangeAt(0). Jika tidak ada yang dipilih, pernyataan sebelumnya akan gagal.

Mari kita pertimbangkan contoh sederhana untuk pilihan yang menghasilkan gambar berikut.

DOM Selection

Di sini kita mulai di node teks dari daftar item pertama dan selesai pada akhir node teks dari elemen strong. Gambar berikut menggambarkan rentang yang tercakup dari perspektif kode sumber.

DOM Range Source

Menampilkan DOM tree untuk disediakan berbagai contoh Range ini juga menarik. Kita melihat bahwa rentang seperti itu mampu mencakup seluruh rangkaian node independen dari nenek moyangnya atau saudara kandungnya.

DOM Range TreeDOM Range TreeDOM Range Tree

Mengekstrak node yang dipilih memberikan kita DocumentFragment, yang dimulai pada daftar item baru dan berakhir setelah elemen strong.

DOM Range ExtractDOM Range ExtractDOM Range Extract

Ekstraksi adalah benar-benar tindakan bermutasi DOM, yaitu memodifikasi truee yang ada. Sekarang kita tersisa dengan dua item berikut, persis seperti yang kita harapkan.

DOM Range Extracted

Karena teks bisa mencakup unsur dan segala sesuatu yang terkandung di dalamnya, renngta juga perlu untuk mencakup kasus-kasus ini. Pada pandangan pertama Range ini direkayasa dengan aneh, karena selalu perlu untuk memperhatikan setidaknya dua kasus: teks dan non-teks (sebagian besar elemen). Namun, seperti yang kita lihat ada alasan yang baik untuk membedakan dua kasus ini, jika kita tidak bisa memilih fragmen teks.

Objek Range kekurangan kemampuan perulangan yang kita alami sebelumnya. Malah kita telah meningkatkan kemampuan serialisasi dan ekspor. Mengubah contoh kita sebelumnya karena itu praktis pada awalnya. Meskipun demikian, dengan memperkenalkan beberapa metode baru, kita dapat menggabungkan fleksibilitas Range dengan perulangan yang disempurnakan.

Kedua metode ini memungkinkan kita menggunakan Range seperti iterator sebelumnya. Sekarang kita hanya bisa pergi ke satu arah; namun, kita bisa dengan mudah menerapkan metode untuk melewati turunan, langsung ke induknya, atau melakukan langkah lain.

Meskipun Range adalah sampah yang dikumpulkan seperti objek JavaScript lainnya, ini masih praktek yang bagus untuk melepaskannya dengan menggunakan fungsi detach. Salah satu alasannya adalah bahwa semua contoh Range sebenarnya tersimpan dalam document, di mana mereka diperbarui jika terjadi mutasi DOM.

Mendefinisikan metode iterator kita sendiri pada Range adalah suatu manfaat. Offset secara otomatis diperbarui dan kita memiliki kemungkinan tambahan, seperti mengkloning pilihan saat ini sebagai DocumentFragment, mengekstrak atau menghapus node yang dipilih. Juga kita bisa mendesain API untuk kebutuhan kita sendiri.

Kesimpulan

Perulangan melalui DOM tree adalah topik yang menarik bagi siapa saja yang memikirkan manipulasi DOM dan pengambilan node yang efisien. Untuk sebagian besar kasus penggunaan, sudah ada API yang sesuai. Apakah kita menginginkan perulangan biasa? Apakah kita ingin memilih rentang? Apakah kita tertarik untuk berjalan di tree? Ada kelebihan dan kekurangan masing-masing metode. Jika kita tahu apa yang kita inginkan, kita bisa membuat pilihan yang tepat.

Sayangnya, struktur pohon tidak sesederhana array 1 dimensi. Mereka dapat dipetakan ke array 1 dimensi, namun pemetaan mengikuti algoritma yang sama dengan perulangan di atas strukturnya. Jika kita menggunakan salah satu struktur yang tersedia, kita memiliki akses ke metode yang telah mengikuti algoritma ini. Oleh karena itu kita mendapatkan cara mudah untuk melakukan beberapa perulangan pada node dalam K-ary tree. Kita juga menghemat beberapa kinerja dengan melakukan lebih sedikit operasi DOM.

Referensi

Advertisement
Did you find this post useful?
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.