imp - About The Project

Definition

You are tasked to generate a website used in the Theory of Algorithms course of the Computer Science Engineering BSc major at Budapest University of Technology and Economics (BME), given by the Department of Computer Science and Information Theory, professor Kitti Varga.

The website will be used during the lectures of the course to demonstrate the algorithms and data structures used in the course.

The website will contain Python code snippets of the following algorithms and data structures:

• Searching (linear vs binary search)
• Sorting (selection sort, bubble sort, insertion sort, merge sort, quick sort)
• BFS
• DFS
• Dijkstra's algorithm
• Heap
• Binary Search Tree
• Red-Black Tree
• 2-3 Tree
• Hash

Globally the website shall have a language switcher (English, Hungarian). Switching language will change the language of the website and also the code snippets themselves.

Layout and Functionality

On the main page of the website, you will put the following things:

• Header: It contains the title of the website, which is Imp (short for implementation).
• A grid of cards with a search bar on top: Each card is a button related to an algorithm or data structure listed above.
• The card's title is the name of the algorithm or data structure.
• The card's description is a brief explanation of the algorithm or data structure.
• When clicking the card it takes the user to the page of that specific algorithm or data structure.
• Footer: It contains contact information: Kitti Varga (vkitti@math.bme.hu), Viktória Nemkin (nemkin@cs.bme.hu). A link to the GitHub repository of the website (https://github.com/bmeszit/imp) and information on how to contribute to the project (contact the owners or visit the GitHub repository).

On the page of each algorithm or data structure, you will put the following things:

• Header: It contains the title of the page, which is the name of the algorithm or data structure.
• The same brief description as on the card.
• Code snippets: A tabbed view of one or more python codes. In some cases (such as sort) there will be multiple implementations of the algorithm. Each implementation should be a tab.
  • Initially, the website loads premade implementations, however these are editable to the user.
  • The user can edit each snippet, create new tabs and delete any tab (previously existing or newly made as well).
  • Each edit is saved to the local storage in the browser.
  • There is a reset button, that deletes all current tabs and loads the original tabs with their original code again.
  • The name of the tab is the name of the python file (and is named after the name of the implementation).
  • For each tab the following buttons exist:
    • Run: It runs the code using the python in the browser
    • Reset: There should be a small button to reset the implementation if the user wants to back to the original code.
    • Copy: Copy the implementation to clipboard.
    • Download: Download the edited implementation as a file (using the file name taken from the name of the tab).
• An input field and an output field. For the currently open tab the user can press RUN, which will execute the code in the input field and display the result in the output field. The input field is always pre-filled with some sample input data, but is editable to the user. The contents of the input field are also saved to the local storage in the browser and will be reset when the page reset button is pressed.
• There is a measure button on the page which takes the user to a new page.

The image below shows an schech of the layout.

On the measure page of the implementation:

• The user can select from a dropdown of the types of inputs they want to run the implementations (the codes in the tabs on).
• For each algorithm there are generators supplied (these can overlap between algorithms). For example, graph algorithms are supplied with graph generators, where the user can pick between sparse, dense, etc graphs.
• The generators are written such that they will generate multiple random instances in a range of sizes that is built in. (This is done to ensure that the user does not accidentally freeze the browser.)
• The browser will then execute the implementations on the generated instances and display the results in two plots.
  • Both plots are scatter plots with the x axis representing the input size and the y axis representing either the runtime or the max memory used.
  • The first plot shows the cpu runtime measured for each implementation relative to the input size.
  • The second plot shows the maximum memory allocated measured for each implementation relative to the input size.
  • For each plot, the best fitting polynomial curve is calculated using a regression algorithm.
  • In the legend, the coefficients are shown. For example if the best curve is cn^k, then the legend says cn^k.
• Next to the plots there is a button that says scale to c=1. This divides all y coordinates by the c corresponding to the best fitting curve describing them. Furthermore, in the background curves corresponding to log(n), n, n*log(n), n^2, n^2*log(n), n^3 are plotted to provide a reference for the growth rates of different algorithms. These curves are labeled with the corresponding Big O notation.

This is an example of how we started the project and how we made python work in the browser.

<!doctype html>
<html lang="hu">
<head>
  <meta charset="utf-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1" />
  <title>Rendezési algoritmusok – futásidő és szerkeszthető implementáció</title>
  <style>
    body { font-family: sans-serif; margin: 20px 20px 100px 20px; }
    textarea { width: 100%; max-width: 800px; height: 200px; }
    input, button, select, textarea { margin: 4px; }
    canvas { border: 1px solid #ccc; margin-top: 10px; }
    /* --- Responsive chart --- */
    #chart {
      width: 100%;
      max-width: 800px;
      /* keep ~800x360 = 20:9 aspect */
      aspect-ratio: 20 / 9;
      height: auto;           /* let aspect-ratio control height */
      display: block;         /* avoid inline-canvas whitespace quirks */
    }

    /* NEW: containers that we toggle responsively */
    #chartWrapper { display: block; }
    #textResults { display: none; max-width: 800px; border: 1px solid #ddd; padding: 10px; margin-top: 10px; border-radius: 6px; background: #fafafa; }

    /* Switch around 500px: on small screens show text list, hide chart */
    @media (max-width: 600px) {
      #chartWrapper { display: none; }
      #textResults { display: block; }
    }

    .error { color: red; white-space: pre-wrap; }

    /* Egyszerű tabok */
    .tabs { margin-top: 18px; }
    .tab-buttons { display: flex; gap: 6px; flex-wrap: wrap; }
    .tab-buttons button { padding: 6px 10px; border: 1px solid #aaa; background: #f6f6f6; cursor: pointer; }
    .tab-buttons button.active { background: #eaeaea; font-weight: 700; }
    .tab-panel { display: none; border: 1px solid #ddd; padding: 8px; margin-top: 6px; }
    .tab-panel.active { display: block; }
    .impl-editor { width: 100%; height: 400px; font-family: ui-monospace, SFMono-Regular, Menlo, Monaco, Consolas, "Liberation Mono", "Courier New", monospace; font-size: 13px; }
    .row { display: flex; align-items: center; gap: 8px; flex-wrap: wrap; }
    .kpis span { margin-right: 16px; }
    code.inline {
      width: 100%; max-width: 800px; 
      display: block;
      white-space: pre-wrap;
      background: #f2f2f2;
      padding: 8px;
      margin: 5px;
      border: 1px solid #ddd;
      border-radius: 4px;
      line-height: 1.4;
    }

    #loading { display:none; font-weight:bold; color:blue; margin-left:10px; }
    #pyodide-loading { font-weight:bold; color:green; margin:10px 0; }
    
    *, *::before, *::after { box-sizing: border-box; }

    .tab-panel .impl-editor {
      width: 100%;
      margin: 0;
      display: block;
      box-sizing: border-box;
    }

    .tab-panel { width: 100%; max-width: 800px; }
  </style>
  <script src="https://cdn.jsdelivr.net/pyodide/v0.24.1/full/pyodide.js"></script>
</head>
<body>
  <h1>Rendezési algoritmusok futásidőmérése</h1>
  <p>Írj be vesszővel elválasztott számokat, futtasd több algoritmussal, mérd meg a futásidők alakulását!</p>
  
  <p>Az algoritmusok Python implementációit lent találod, ezek <strong>szerkeszthetők</strong> és a futtatás ezeket használja.</p>
  
  <div id="pyodide-loading">Python környezet betöltése...</div>

  <h2>Bemenet</h2>
  <div>
    <input id="size" type="text" value="200" /> db elem:
    <button id="btnRandom">Véletlen generálása</button>
    <button id="btnInc">Növekvő generálása</button>
    <button id="btnDec">Csökkenő generálása</button><br>
    <button id="btnClear">Bemenet törlése</button><br>
    <textarea id="numbers" placeholder="pl.: 12, 5, 3, 9, 1, 7"></textarea><br>

    <label>Ismételd a méréseket ennyiszer és átlagold: <input type="text" id="repeats" value="10" /></label>
    <button id="btnSort">Futtatás indít</button>
    <span id="loading">Számol...</span><br/>
    <span id="err" class="error"></span>
  </div>

  <h2>Eredmények</h2>
  <div class="kpis">
    <span>Elemek száma: <strong id="kCount">–</strong></span>
  </div>

  <!-- NEW: wrap the chart so we can hide/show the whole block -->
  <div id="chartWrapper">
    <!-- width/height attributes are fine; JS will override to device pixels -->
    <canvas id="chart" width="800" height="360" aria-label="Futásidők grafikonja" role="img"></canvas>
    <div id="legend"></div>
  </div>

  <!-- NEW: textual list of results (visible on small screens) -->
  <div id="textResults" aria-live="polite" aria-atomic="true">
    <div id="textResultsInner">–</div>
  </div>

  <h2>Implementációk (szerkeszthető)</h2>
  
  <p style="margin-top:-8px">Mindegyik szerkesztőben egy
  <code class="inline">def rendezes(T):
  # TODO
  return T</code>
  alakú függvényt várunk Pythonban implementálva. A weboldal a szerkesztett változatot fordítja és futtatja.
  </p>
  
  <div class="tabs" id="tabs">
    <div class="tab-buttons" id="tabButtons"></div>
    <div id="tabPanels"></div>
  </div>

  <script>
    const $ = (sel) => document.querySelector(sel);
    const ERR = $('#err');
    const LOADING = $('#loading');
    const PYODIDE_LOADING = $('#pyodide-loading');

    let pyodide = null;

    // store latest chart results to enable redraw on resize
    let LAST_RESULTS = [];

    // Angol kulcs → magyar label
    const ALGO_LABELS = {
      Selection: "Kiválasztásos",
      Bubble: "Buborék",
      Insertion: "Beszúrásos",
      Merge: "Összefésüléses",
      Quick: "Gyors",
      Personal: "Saját"
    };

    // ======= Alap implementációk szövegként (szerkeszthető) Python =======
    const DEFAULT_IMPLS = {
      Selection: `def rendezes(T):
  n = len(T)
  for j in range(0, n-1):
    min_ertek = T[j]
    min_hely = j
    for i in range(j+1, n):
      if T[i] < min_ertek:
        min_ertek = T[i]
        min_hely = i
    T[j], T[min_hely] = T[min_hely], T[j]
  return T`,
      Bubble: `def rendezes(T):
  n = len(T)
  for j in range(n-1, 0, -1):
    for i in range(0, j):
      if T[i] > T[i+1]:
        T[i], T[i+1] = T[i+1], T[i]
  return T`,
      Insertion: `def rendezes(T):
  n = len(T)
  for j in range(1, n):
    i = j
    while T[i-1] > T[i] and i > 0:
      T[i-1], T[i] = T[i], T[i-1]
      i = i-1
  return T`,
      Merge: `def osszefesul(A, B):
  k = len(A)
  l = len(B)
  C = [None]*(k+l)
  
  i=0
  j=0
  h=0
  
  while i<k and j<l:
    if A[i] < B[j]:
      C[h] = A[i]
      i = i+1
      h = h+1
    else:
      C[h] = B[j]
      j = j+1
      h = h+1
  
  if i==k:
    while j<l:
      C[h]=B[j]
      j=j+1
      h=h+1
  elif j==l:
    while i<k:
      C[h]=A[i]
      i=i+1
      h=h+1
  return C

def rendezes(T):
  n = len(T)
  
  if n>1:
    A = rendezes(T[0 : n//2])
    B = rendezes(T[n//2 : n])
    T = osszefesul(A, B)
  return T`,
      Quick: `def particional(T, eleje, vege):
  pivot_ertek = T[vege]
  pivot_hely = vege
  i = eleje
  for j in range(eleje, vege):
    if T[j] < pivot_ertek:
      T[i], T[j] = T[j], T[i]
      i = i+1
  T[i], T[pivot_hely] = T[pivot_hely], T[i]
  return i

def helyben_rendez(T, eleje, vege):
  if not eleje<vege:
    return
  
  pivot_hely = particional(T, eleje, vege)
  helyben_rendez(T, eleje, pivot_hely-1)
  helyben_rendez(T, pivot_hely+1, vege)

def rendezes(T):
  n = len(T)
  helyben_rendez(T, 0, n-1)
  return T`,
      Personal: `def rendezes(T):
  T = sorted(T)
  return T`
    };

    const ALGO_LIST = Object.keys(DEFAULT_IMPLS);

    // Tab felület építése
    const tabButtons = $('#tabButtons');
    const tabPanels = $('#tabPanels');

    const editors = {}; // name -> textarea element

    function buildTabs(){
      ALGO_LIST.forEach((name, idx) => {
        const btn = document.createElement('button');
        btn.title = name;
        btn.textContent = ALGO_LABELS[name] || name;
        btn.dataset.name = name;
        btn.addEventListener('click', () => activateTab(name));
        tabButtons.appendChild(btn);

        const panel = document.createElement('div');
        panel.className = 'tab-panel';
        panel.id = 'panel-' + name;
        panel.innerHTML = `
          <div class="row">
            <button data-act="reset">Állítsd vissza az alapértelmezettre</button>
          </div>
          <textarea class="impl-editor" spellcheck="false"></textarea>
        `;
        tabPanels.appendChild(panel);

        const ta = panel.querySelector('textarea');
        ta.value = DEFAULT_IMPLS[name];
        editors[name] = ta;

        panel.querySelector('[data-act="reset"]').addEventListener('click', () => {
          ta.value = DEFAULT_IMPLS[name];
        });
      });
      activateTab(ALGO_LIST[0]);
    }

    function activateTab(name){
      [...tabButtons.children].forEach(b =>
        b.classList.toggle('active', b.dataset.name === name)
      );
      [...tabPanels.children].forEach(p =>
        p.classList.toggle('active', p.id === 'panel-' + name)
      );
    }

    buildTabs();

    function parseNumbers(raw) {
      const arr = raw.split(/[ ,\n]+/).map(s => s.trim()).filter(Boolean).map(Number);
      if (arr.some(n => Number.isNaN(n))) throw new Error('Csak számokat adj meg, vesszővel elválasztva.');
      return arr;
    }

    async function compileImpl(source, algoName) {
      try {
        // Pass the source via a variable (avoids quoting hassles)
        pyodide.globals.set('SRC_CODE', source);

        await pyodide.runPythonAsync(`
    ns = {}
    exec(SRC_CODE, ns)
    fn = ns.get('rendezes', None)
    if fn is None:
        raise Exception("Nem található a def rendezes(T) függvény!")
    # Optional: keep a back-reference so helpers in ns stay alive & private
    fn.__globals__['_ns_keepalive'] = ns
    `);

        const fn = pyodide.globals.get('fn');
        // Clean up temp globals
        pyodide.globals.delete('SRC_CODE');
        pyodide.globals.delete('fn');
        return fn;
      } catch (e) {
        const algoLabel = ALGO_LABELS[algoName] || algoName;
        const msg = (e && e.message) ? e.message : String(e);
        throw new Error(algoLabel + " - Hiba: " + msg);
      }
    }

    async function averageRun(fn, data, repeats, algoName) {
      let total = 0;
      for (let i = 0; i < repeats; i++) {
        const copy = [...data];
        const t0 = performance.now();
        try {
          const out = fn(copy);
          const t1 = performance.now();
          total += (t1 - t0);
        } catch (e) {
          const algoLabel = ALGO_LABELS[algoName] || algoName;
          const errorMsg = algoLabel + ' - Hiba: ' + (e.message || e);
          throw new Error(errorMsg);
        }
      }
      return total / repeats;
    }

    // --- Responsive canvas helpers ---
    function resizeCanvas() {
      const c = $('#chart');
      const wrapper = $('#chartWrapper');
      // If chart (or its wrapper) is hidden, skip costly sizing
      if (!c || !wrapper || wrapper.offsetParent === null) return;

      const ctx = c.getContext('2d');
      const dpr = window.devicePixelRatio || 1;

      // CSS size (logical pixels)
      const { width: cssW, height: cssH } = c.getBoundingClientRect();

      // Set internal pixel buffer to match CSS size * DPR
      c.width  = Math.max(1, Math.floor(cssW * dpr));
      c.height = Math.max(1, Math.floor(cssH * dpr));

      // Set transform so drawing uses CSS pixel units
      ctx.setTransform(dpr, 0, 0, dpr, 0, 0);

      // Redraw if we have data
      if (LAST_RESULTS.length) {
        drawChart(LAST_RESULTS);
      }
    }

    function drawChart(results){
      LAST_RESULTS = results || [];
      const c = $('#chart');
      const ctx = c.getContext('2d');

      const cw = Math.max(1, c.clientWidth);
      const ch = Math.max(1, c.clientHeight);

      ctx.clearRect(0, 0, cw, ch);
      if (!LAST_RESULTS.length) return;

      const rawMax = Math.max(...LAST_RESULTS.map(r => r.timeMs));
      const maxV = rawMax * 1.1;   // add ~10% headroom at the top 👈

      const count = LAST_RESULTS.length;
      const padding = 12;
      const usableW = cw - padding * 2;
      const usableH = ch - padding * 3;

      const barW = Math.max(10, Math.floor(usableW / (count * 1.8)));
      ctx.textBaseline = 'alphabetic';
      ctx.font = '12px sans-serif';

      LAST_RESULTS.forEach((r, i) => {
        const ratio = maxV ? (r.timeMs / maxV) : 0;
        const h = ratio * usableH;

        const x = padding + i * (barW * 1.8) + barW * 0.4;
        const y = padding + (usableH - h);

        ctx.fillStyle = '#4682b4';
        ctx.fillRect(x, y, barW, h);

        ctx.fillStyle = '#000';
        const label = ALGO_LABELS[r.name] || r.name;
        ctx.fillText(r.timeMs.toFixed(2) + 'ms', x, Math.max(10, y - 2));
        const txtY = padding + usableH + 16;
        ctx.fillText(label, x, Math.min(ch - 2, txtY));
      });
    }
    // --- end responsive helpers ---

    // NEW: render text list version of results
    function renderTextResults(results) {
      const host = $('#textResultsInner');
      if (!results || !results.length) {
        host.textContent = '–';
        return;
      }
      const ol = document.createElement('ul');
      ol.style.margin = '8px 0 0 18px';
      ol.style.padding = '0';
      results.forEach(r => {
        const li = document.createElement('li');
        const label = ALGO_LABELS[r.name] || r.name;
        li.textContent = `${label}: ${r.timeMs.toFixed(2)} ms`;
        ol.appendChild(li);
      });
      host.innerHTML = '';
      host.appendChild(ol);
    }

    async function buildAlgorithms(){
      const compiled = {};
      for (const name of ALGO_LIST) {
        compiled[name] = await compileImpl(editors[name].value, name);
      }
      return compiled;
    }

    async function runAll(data, repeats, compiled){
      const results=[];
      const ref=[...data].sort((x,y)=>x-y);
      for(const name of ALGO_LIST){
        const fn = compiled[name];
        const avg = await averageRun(fn, data, repeats, name);
        const outPy = fn([...data]);
        const out = outPy.toJs ? outPy.toJs() : Array.from(outPy);
        const verify = true;
        if(verify){
          const ok = out.length===ref.length && out.every((v,i)=>v===ref[i]);
          if (!ok) {
            const label = ALGO_LABELS[name] || name;
            const errorMsg = label + ' - Hibás rendezés: az eredmény nem helyes!';
            throw new Error(errorMsg);
          }
        }
        results.push({name,timeMs:avg});
      }
      return results;
    }

    $('#btnRandom').addEventListener('click',()=>{
      const n=parseInt($('#size').value)||200;
      const arr=Array.from({length:n},()=>Math.floor(Math.random()*n*10));
      $('#numbers').value=arr.join(',');
    });

    $('#btnInc').addEventListener('click',()=>{
      const n=parseInt($('#size').value)||200;
      const arr=Array.from({length:n},(_,i)=>i+1);
      $('#numbers').value=arr.join(',');
    });

    $('#btnDec').addEventListener('click',()=>{
      const n=parseInt($('#size').value)||200;
      const arr=Array.from({length:n},(_,i)=>n-i);
      $('#numbers').value=arr.join(',');
    });

    $('#btnClear').addEventListener('click',()=>{
      $('#numbers').value='';
      $('#kCount').textContent='–';
      LAST_RESULTS = [];
      const c=$('#chart');
      const ctx=c.getContext('2d');
      // ensure we clear with current transform
      ctx.clearRect(0,0,c.clientWidth,c.clientHeight);
      $('#legend').innerHTML='';
      $('#textResultsInner').textContent='–';
      ERR.textContent='';
      LOADING.style.display='none';
    });

    $('#btnSort').addEventListener('click', async ()=>{
      if (!pyodide) {
        ERR.textContent = 'Python környezet még nem töltődött be, kérlek várj...';
        return;
      }

      ERR.textContent='';
      LOADING.style.display='inline';

      setTimeout(async ()=>{
        try {
          const compiled = await buildAlgorithms();
          const numbers = parseNumbers($('#numbers').value);
          let repeats = parseInt($('#repeats').value) || 3;
          repeats = Math.max(1, Math.min(20, repeats));
          $('#repeats').value = repeats;

          if(numbers.length===0) throw new Error('Adj meg legalább egy számot.');
          if(numbers.length > 500) throw new Error('Legfeljebb 500 db számot adj meg!');

          const results = await runAll(numbers, repeats, compiled);

          // make sure canvas matches current size before drawing
          resizeCanvas();
          drawChart(results);
          renderTextResults(results); // NEW: update text list too

          $('#kCount').textContent = String(numbers.length);
        } catch(e){
          ERR.textContent = (e && e.message) ? e.message : String(e);
        } finally {
          LOADING.style.display='none';
        }
      }, 20);
    });


    // Pyodide inicializálás
    async function initPyodide() {
      try {
        pyodide = await loadPyodide();
        PYODIDE_LOADING.textContent = 'Python környezet készen áll!';
        PYODIDE_LOADING.style.color = 'green';
        setTimeout(() => {
          PYODIDE_LOADING.style.display = 'none';
        }, 2000);
      } catch (e) {
        PYODIDE_LOADING.textContent = 'Hiba a Python környezet betöltésekor: ' + e.message;
        PYODIDE_LOADING.style.color = 'red';
      }
    }

    initPyodide();

    // Initial canvas sizing + listeners for responsiveness
    window.addEventListener('load', resizeCanvas);
    window.addEventListener('resize', () => {
      // throttle-free is OK here; chart is lightweight
      resizeCanvas();
    });
    window.addEventListener('orientationchange', resizeCanvas);
  </script>
</body>
</html>