Enum dan set

Tipe enum ordinal dan bitset set[T] untuk operasi himpunan yang efisien.

Daftar isi

Nilai yang terbatas pada daftar pilihan tetap muncul di hampir semua program, misalnya hari dalam seminggu atau status sebuah proses. Topik ini membahas enum sebagai tipe untuk daftar pilihan seperti itu, lalu set[T] sebagai bitset yang menyimpan kumpulan pilihan tersebut dan mendukung operasi himpunan secara langsung. Setelah membacanya, keanggotaan, gabungan, irisan, dan selisih himpunan dapat ditulis dengan operator bawaan tanpa perulangan manual.

Enum sebagai tipe ordinal#

Tipe enum mendefinisikan daftar nilai yang tetap dan berurutan. Karena urutannya jelas, enum termasuk tipe ordinal, yaitu tipe yang nilainya dapat dipetakan ke bilangan bulat dan dihitung maju atau mundur. Fungsi ord mengembalikan nomor urut, succ dan pred berpindah satu langkah, $ mengubah nilai menjadi teks namanya, dan inc memajukan variabel enum di tempatnya.

nim hari_enum.nim

# Enum sebagai tipe ordinal
type
  Hari = enum
    senin, selasa, rabu, kamis, jumat, sabtu, minggu

echo ord(senin)
echo ord(minggu)
echo succ(selasa)
echo pred(minggu)
echo $jumat
echo high(Hari)

var hariIni: Hari = rabu
inc(hariIni)
echo hariIni

text Keluaran

0
6
rabu
sabtu
jumat
minggu
kamis

Perulangan for juga menerima enum sebagai rentangnya, sehingga seluruh hari dapat dicetak tanpa daftar manual, dan low serta high mengembalikan nilai pertama dan terakhirnya. Nilai enum dapat diberi nomor urut eksplisit, dan manual menetapkan bahwa nomor itu harus naik, sedangkan enum dengan celah nomor tidak lagi ordinal sehingga succ dan pred tidak tersedia untuknya.

Urutan inilah yang membuat enum cocok menjadi tipe dasar set[T], karena keanggotaan bitset memetakan setiap nilai ordinal ke satu bit. Operator perbandingan bekerja atas nomor urut masing-masing nilai, sehingga senin < rabu bernilai benar. Fungsi low dan high melengkapi succ serta pred dengan batas rentang tipe.

Nama tampilan tiap nilai dapat ditetapkan sendiri sebagai string, dan itulah teks yang dicetak oleh $ maupun echo. Contoh berikut menggunakan status pesanan dengan empat tahap.

nim status_pesanan.nim

# Enum dengan nama tampilan khusus
type
  StatusPesanan = enum
    diterima = "diterima"
    diproses = "sedang diproses"
    dikirim = "sedang dikirim"
    selesai = "selesai"

for status in StatusPesanan:
  echo status

text Keluaran

diterima
sedang diproses
sedang dikirim
selesai

Bitset set[T] dan operasi himpunan#

Tipe set[T] menyimpan kumpulan elemen dari tipe dasar ordinal, dan penerapannya berupa bitset, yaitu rangkaian bit yang setiap bitnya mewakili keanggotaan tepat satu elemen. Konstruksinya menggunakan kurung kurawal, baik berupa daftar seperti {sabtu, minggu} maupun rentang seperti {senin..jumat}. Tiga operator himpunan utama tersedia sebagai operator bawaan, dan maknanya dipetakan ke notasi matematika sebagai berikut.

A + B = A \cup B, \qquad A * B = A \cap B, \qquad A - B = A \setminus B

Selain ketiganya, in menguji keanggotaan, card menghitung banyak elemen, dan <= menguji hubungan subset. Program berikut menyusun tiga jadwal mingguan lalu menghitung keluarannya.

nim jadwal_set.nim

# Bitset set[Hari] untuk jadwal
type
  Hari = enum
    senin, selasa, rabu, kamis, jumat, sabtu, minggu

  Jadwal = set[Hari]

const
  piket: Jadwal = {senin, rabu, jumat}
  kerja: Jadwal = {senin..jumat}
  libur: Jadwal = {sabtu, minggu}

echo piket + {selasa}
echo kerja * piket
echo kerja - piket
echo sabtu in kerja
echo card(kerja)
echo libur <= kerja

text Keluaran

{senin, selasa, rabu, jumat}
{senin, rabu, jumat}
{selasa, kamis}
false
5
false

Baris pertama menggabungkan jadwal piket dengan {selasa}, sehingga hasilnya mencakup empat hari. Irisan kerja * piket menghasilkan hari piket yang memang hari kerja, sedangkan selisih kerja - piket menghasilkan hari kerja di luar jadwal piket. Keanggotaan sabtu in kerja bernilai salah karena sabtu bukan hari kerja, card kerja menghitung lima hari, dan libur <= kerja bernilai salah karena libur bukan subset dari kerja.

Bentuk lain dari operator keanggotaan juga tersedia, yaitu notin untuk menegasinya dan proc contains yang menerima himpunan lebih dahulu. Operator < menandai subset sejati, yaitu subset yang tidak sama dengan himpunannya. Pada tipe dasar char, pola yang sama diterapkan pada kelompok huruf seperti {'a', 'e', 'i', 'o', 'u'} yang kardinalitasnya lima.

Batasan tipe dasar dan demo interaktif#

Tipe dasar set tidak boleh sembarang ordinal. Manual menetapkan rentang maksimum berupa MaxSetElements yang berukuran $2^{16}$ nilai, sehingga tipe dasar dengan rentang yang lebih panjang ditolak kompilator.

nim Contoh: rentang dasar yang terlalu besar

# tidak-dijalankan
# rentang int jauh melebihi batas 2^16 elemen
var s: set[int] = {1, 2, 3}
echo s

Kompilator menolak potongan di atas dengan pesan Error: set is too large; use std/sets for ordinal types with more than 2^16 elements, dan modul std/sets memang disediakan untuk himpunan yang lebih besar dari itu. Untuk enum, char, dan rentang kecil lainnya, batas tersebut tidak pernah menjadi hambatan.

Biaya kerjanya pun berbeda dari daftar biasa. Karena keanggotaan disimpan sebagai bit, gabungan, irisan, dan selisih dikerjakan sebagai operasi bitwise antar bit, bukan perbandingan elemen satu per satu. Demo berikut menghitung operasi himpunan atas dua jadwal mingguan dengan logika yang sama: tandai hari pada jadwal A dan jadwal B, pilih operasinya, kemudian amati hasilnya di bagian bawah.

Kode sumber demo

<!DOCTYPE html>
<html lang="id">
<head>
<meta charset="utf-8">
<title>Kalkulator jadwal: operasi himpunan</title>
<style>
  body { font-family: system-ui, sans-serif; margin: 12px; color: #22354f; }
  fieldset { border: 1px solid #b8c4d4; border-radius: 8px; margin: 0 0 10px 0; }
  legend { font-weight: 600; font-size: 13px; }
  label.hari { display: inline-block; margin: 2px 8px 2px 0; font-size: 13px; }
  .opsi { margin-bottom: 10px; font-size: 13px; }
  .opsi label { margin-right: 12px; }
  #hasil { border: 1px dashed #b07d2b; border-radius: 8px; min-height: 34px;
           padding: 6px 10px; font-family: monospace; font-size: 14px; }
  .chip { display: inline-block; background: #e8f0fb; border: 1px solid #4a7ab5;
          border-radius: 12px; padding: 1px 8px; margin: 2px 4px 2px 0; font-size: 12px; }
</style>
</head>
<body>
  <fieldset>
    <legend>Jadwal A</legend>
    <label class="hari"><input type="checkbox" name="a" value="sen">Senin</label>
    <label class="hari"><input type="checkbox" name="a" value="sel">Selasa</label>
    <label class="hari"><input type="checkbox" name="a" value="rab">Rabu</label>
    <label class="hari"><input type="checkbox" name="a" value="kam">Kamis</label>
    <label class="hari"><input type="checkbox" name="a" value="jum">Jumat</label>
    <label class="hari"><input type="checkbox" name="a" value="sab">Sabtu</label>
    <label class="hari"><input type="checkbox" name="a" value="min">Minggu</label>
  </fieldset>

  <fieldset>
    <legend>Jadwal B</legend>
    <label class="hari"><input type="checkbox" name="b" value="sen">Senin</label>
    <label class="hari"><input type="checkbox" name="b" value="sel">Selasa</label>
    <label class="hari"><input type="checkbox" name="b" value="rab">Rabu</label>
    <label class="hari"><input type="checkbox" name="b" value="kam">Kamis</label>
    <label class="hari"><input type="checkbox" name="b" value="jum">Jumat</label>
    <label class="hari"><input type="checkbox" name="b" value="sab">Sabtu</label>
    <label class="hari"><input type="checkbox" name="b" value="min">Minggu</label>
  </fieldset>

  <div class="opsi">
    <label><input type="radio" name="op" value="gabungan" checked>gabungan A + B</label>
    <label><input type="radio" name="op" value="irisan">irisan A * B</label>
    <label><input type="radio" name="op" value="selisih">selisih A - B</label>
  </div>

  <div id="hasil">{ } (kosong)</div>

<script>
  // urutan hari untuk tampilan hasil
  var hari = ['sen', 'sel', 'rab', 'kam', 'jum', 'sab', 'min'];
  var label = {sen: 'Senin', sel: 'Selasa', rab: 'Rabu', kam: 'Kamis',
               jum: 'Jumat', sab: 'Sabtu', min: 'Minggu'};

  // membaca set dari checkbox yang dicentang pada satu jadwal
  function baca(nama) {
    var s = new Set();
    document.querySelectorAll('input[name=' + nama + ']:checked')
      .forEach(function (cb) { s.add(cb.value); });
    return s;
  }

  // gabungan, irisan, dan selisih setara dengan +, *, dan - pada Nim
  function gabungan(a, b) { return new Set(Array.from(a).concat(Array.from(b))); }
  function irisan(a, b) {
    return new Set(Array.from(a).filter(function (x) { return b.has(x); }));
  }
  function selisih(a, b) {
    return new Set(Array.from(a).filter(function (x) { return !b.has(x); }));
  }

  function perbarui() {
    var a = baca('a'), b = baca('b');
    var op = document.querySelector('input[name=op]:checked').value;
    var hasil = op === 'gabungan' ? gabungan(a, b)
              : op === 'irisan' ? irisan(a, b)
              : selisih(a, b);
    var kotak = document.getElementById('hasil');
    kotak.innerHTML = '';
    if (hasil.size === 0) {
      kotak.textContent = '{ } (kosong)';
      return;
    }
    hari.forEach(function (h) {
      if (hasil.has(h)) {
        var c = document.createElement('span');
        c.className = 'chip';
        c.textContent = label[h];
        kotak.appendChild(c);
      }
    });
  }

  document.querySelectorAll('input').forEach(function (el) {
    el.addEventListener('change', perbarui);
  });
  perbarui();
</script>
</body>
</html>

Kesalahan umum#

Kesalahan pertama berupa memperlakukan set seperti seq, misalnya mengharapkan urutan elemen mengikuti urutan penulisan. Isi set selalu diurutkan menurut nomor ordinal tipe dasarnya, sehingga penulisan {jumat, senin} dan {senin, jumat} menghasilkan set yang persis sama. Kesalahan kedua berupa memilih tipe dasar yang bukan ordinal, misalnya float, karena tidak ada bit yang dapat memetakan nilai pecahan. Kesalahan ketiga berupa menuntut rentang dasar yang lebih besar dari batasnya, sebagaimana contoh set[int] di atas, dan perbaikannya beralih ke modul std/sets.

Ringkasan#

Enum adalah tipe ordinal dengan fungsi ord, succ, pred, dan $, dapat diulang dengan for, serta dapat diberi nama tampilan sendiri.
set[T] adalah bitset untuk tipe dasar ordinal yang kecil, dengan konstruktor daftar {sabtu, minggu} dan rentang {senin..jumat}.
Operator +, *, dan - mengerjakan gabungan, irisan, dan selisih, sedangkan in, card, dan <= menguji keanggotaan, kardinalitas, dan subset.
Operasi himpunan dikerjakan sebagai operasi bitwise, dan tipe dasar dengan rentang lebih dari $2^{16}$ nilai menggunakan modul std/sets.

Referensi#

Nim Manual — nim-lang.org — Bagian enum types dan set type mengatur nilai ordinal, batas ukuran set, dan tabel operatornya.
Nim Tutorial (Part I) — nim-lang.org — Bagian sets memperkenalkan konstruktor kurung kurawal dan operator himpunan bawaan.