Mesh.cpp

#include "Mesh.h"
#include <queue>

Mesh::Mesh(const char* filename)
{
	int nVerts, nTris, n, k = 0;
	double x, y, z;
	minHeap.push_back(0);

	ifstream file(filename);

	string line;
	getline(file, line);
	getline(file, line);
	stringstream str(line);
	str >> nVerts >> nTris >> n;

	while (k++ < nVerts)
	{
		getline(file, line);
		stringstream str2(line);

		str2 >> x >> y >> z;
		addVertex(x, y, z); // Not Implemented.
	}
	k = 0;
	while (k++ < nTris)
	{
		getline(file, line);
		stringstream str2(line);

		str2 >> n >> x >> y >> z;
		addTriangle((size_t)x, (size_t)y, (size_t)z); // Not Implemented.
	}

	file.close();

	buildHeap(); // Not Implemented.
}


size_t Mesh::addVertex(double x, double y, double z) {
    size_t Idx = verts.size();
    Vertex newVertex(Idx,x,y,z);
    verts.push_back(newVertex);
    return Idx;
	
}
size_t Mesh::addTriangle(size_t v1, size_t v2, size_t v3) {

	size_t newTriIdx = tris.size(); // İndeks = Mevcut boyut [cite: 97]

    // Üçgeni oluşturup listeye at
    tris.push_back(Triangle(newTriIdx, v1, v2, v3));

    // Vertexlerin "Hangi üçgene üyeyim?" (triList) [cite_start]bilgisini güncelle [cite: 66]
    verts[v1].triList.push_back(newTriIdx);
    verts[v2].triList.push_back(newTriIdx);
    verts[v3].triList.push_back(newTriIdx);

    // Helper fonksiyonu kullanarak kenarları oluştur
    addEdgeIfMissing(v1, v2);
    addEdgeIfMissing(v2, v3);
    addEdgeIfMissing(v1, v3);

    return newTriIdx;
}

void Mesh::buildHeap() {
    minHeap.clear();

    // DUMMY (GUARD) EKLE - Test 8 bunu bekliyor!
    minHeap.push_back(0); 

    // Kenarları ekle (1. indexten itibaren yerleşirler)
    for (size_t i = 0; i < edges.size(); ++i) {
        minHeap.push_back(i);
    }

    // 1-Tabanlı Floyd Algoritması (Size/2'den 1'e kadar)
    if (minHeap.size() > 1) {
        for (int i = (minHeap.size() - 1) / 2; i >= 1; --i) {
            bubbleDownWithArgument(minHeap, i);
        }
    }

}

Edge& Mesh::getEdge(size_t v1, size_t v2) {

	// v1'in geçerli bir vertex olup olmadığını kontrol ediyoruz.
    if (v1 < verts.size()) {
        // Sadece v1'e bağlı olan kenarları kontrol etmek yeterlidir (Optimizasyon).
        // edgeList, bu vertex'e bağlı kenarların indekslerini tutar.
        for (size_t eIdx : verts[v1].edgeList) {
            
            // İndeksi kullanarak gerçek Edge objesine ulaşıyoruz
            Edge& currentEdge = edges[eIdx];

            // Bu kenar v1 ile v2'yi mi bağlıyor?
            // Kenar yönsüz olduğu için (v1-v2) veya (v2-v1) olabilir.
            if ((currentEdge.v1i == v1 && currentEdge.v2i == v2) || 
                (currentEdge.v1i == v2 && currentEdge.v2i == v1)) {
                return currentEdge; // Bulduk, döndür.
            }
        }
    }

    // PDF Madde 3.4.3: "If no such edge exists, return the edge with the index 0."
    return edges[0];
}    

void Mesh::printVertex(size_t v) {
    // Eğer böyle bir vertex yoksa hiçbir şey yazdırma [cite: 133]
    if (v >= verts.size()) return;

    // Koordinatları "x y z " formatında yazdır (Sonda boşluk var) [cite: 132]
    std::cout << verts[v].coords[0] << " " 
         << verts[v].coords[1] << " " 
         << verts[v].coords[2] << " "  ;

}

void Mesh::printTriangle(size_t t) {
// Eğer böyle bir üçgen yoksa hiçbir şey yazdırma [cite: 136]
    if (t >= tris.size()) return;

    // Köşeleri "3 v1 v2 v3 " formatında yazdır.
    // Baştaki "3" sayısı, OFF formatında bunun bir üçgen olduğunu belirtir.
    // (Sonda boşluk bırakmayı unutma) [cite: 135]
    std::cout << "3 " 
         << tris[t].v1i << " " 
         << tris[t].v2i << " " 
         << tris[t].v3i << " " ;
}

bool Mesh::isVertsNeighbour(size_t v1, size_t v2) {

// 1. GÜVENLİK KONTROLÜ
    // PDF Madde 3.4.5: "Should return false if either vertices does not exist."
    // Eğer v1 veya v2 geçerli bir indeks değilse false dön.
    if (v1 >= verts.size() || v2 >= verts.size()) {
        return false;
    }

    // 2. LİSTEYİ TARA
    // v1'in komşu listesinde (vertList) v2 var mı diye bakıyoruz.
    // (Bunun tersini, yani v2'nin listesinde v1 var mı diye de bakabilirdik, sonuç değişmez)
    for (size_t neighbor : verts[v1].vertList) {
        if (neighbor == v2) {
            return true; // Bulduk, komşular.
        }
    }

    // Listeyi bitirdik ama bulamadık.
    return false;
}

size_t Mesh::getDegree(size_t v) {

	// 1. GÜVENLİK KONTROLÜ
    // PDF Madde 3.4.8: "If not such vertex exists, return 0."
    // Verilen v indeksi sınırlar dışında mı?
    if (v >= verts.size()) {
        return 0;
    }

    // 2. DERECEYİ DÖNDÜR
    // Vertex'in komşu listesinin (vertList) uzunluğu bize dereceyi verir.
    return verts[v].vertList.size();
}

int Mesh::getJumpCount(size_t v1, size_t v2)
{
	// 1. Temel Kontroller (Start == Target ise mesafe 0)
    if (v1 == v2) return 0;
    if (v1 >= verts.size() || v2 >= verts.size()) return -1;

    // 2. Değişkenlerin Hazırlanması (Görseldeki gibi)
    // vector<int> distance; -> Biz boyutu baştan verip -1 (sonsuz/visited değil) yapıyoruz.
    vector<int> distance(verts.size(), -1);
    
    // distance[start] = 0;
    distance[v1] = 0;

    // Queue<Vertex> q; -> Biz indeks tutuyoruz.
    std::queue<size_t> q;
    
    // q.enqueue(start);
    q.push(v1);

    // 3. BFS Döngüsü
    // while (!q.isEmpty())
    while (!q.empty()) {
        
        // q.dequeue(u);
        size_t u = q.front();
        q.pop();

        // Eğer hedefi bulduysak mesafeyi döndür (Erken çıkış)
        if (u == v2) return distance[u];

        // for each v adjacent to u (u'nun tüm komşuları için)
        for (size_t v : verts[u].vertList) {
            
            // if (v not visited) -> Bizim mantığımızda distance == -1 ise ziyaret edilmemiştir.
            if (distance[v] == -1) {
                
                // distance[v] = distance[u] + 1;
                distance[v] = distance[u] + 1;
                
                // q.enqueue(v);
                q.push(v);
                
                // mark v as visited (distance artık -1 olmadığı için visited sayılır)
            }
        }
    }

    // Hedefe ulaşılamadıysa
    return -1;
}

double Mesh::getGeodesicDistance(size_t v1, size_t v2) {
	// 1. TEMEL KONTROLLER
    if (v1 == v2) return 0.0;
    // PDF Madde 3.5.1: Dijkstra kullanılmalı [cite: 145]
    if (v1 >= verts.size() || v2 >= verts.size()) return -1.0;

    // 2. HAZIRLIK
    // Mesafeleri sonsuz yap
    vector<double> distance(verts.size(), std::numeric_limits<double>::infinity());
    distance[v1] = 0.0;

    // Priority Queue (Varsayılan MAX-HEAP)
    // Ekstra 'greater' veya 'vector' tanımlarına gerek yok!
    std::priority_queue<std::pair<double, size_t>> pq;

    // Başlangıç noktasını EKSİ mesafe ile atıyoruz (-0.0)
    pq.push({-0.0, v1});

    // 3. DÖNGÜ
    while (!pq.empty()) {
        
        // --- KRİTİK NOKTA 1: Çekerken Düzelt ---
        // Kuyruktan gelen değer negatiftir (örn: -10).
        // Onu tekrar eksiyle çarpıp pozitife (10) çeviriyoruz.
        double d = -pq.top().first; 
        size_t u = pq.top().second;
        pq.pop();

        // Çöp Kayıt Kontrolü (Lazy Deletion)
        if (d > distance[u]) continue;

        // Hedef bulundu mu?
        if (u == v2) return d;

        // Komşuları Gez
        for (size_t v : verts[u].vertList) {
            
            // Kenar ağırlığı (Öklid mesafesi)
            double weight = dist(verts[u].coords, verts[v].coords);

            // Relaxation (Gevşetme)
            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                
                // --- KRİTİK NOKTA 2: Atarken Negatif Yap ---
                // Mesafeyi negatif yapıp kuyruğa atıyoruz.
                // Örnek: Mesafe 5 ise -5 atıyoruz. Mesafe 100 ise -100 atıyoruz.
                // Max-Heap mantığına göre -5 > -100 olduğu için -5 en tepeye çıkar.
                // Böylece algoritma küçük mesafeyi önce işler.
                pq.push({-distance[v], v});
            }
        }
    }

    // Yol Yoksa
    return -1.0;
}

void Mesh::updateVertex(size_t v, double x, double y, double z) {
// 1. GÜVENLİK KONTROLÜ
    if (v >= verts.size()) return;

    // 2. KOORDİNATLARI GÜNCELLE
    // PDF Madde 3.5.2: "Updates the position of the vertex..."
    verts[v].coords[0] = x;
    verts[v].coords[1] = y;
    verts[v].coords[2] = z;

    // 3. BAĞLI KENARLARIN UZUNLUKLARINI GÜNCELLE
    // PDF Madde 3.5.2: "...update the length of the edges connected to it"
    // Sadece bu vertex'e bağlı kenarları (edgeList) gezmemiz yeterli.
    for (size_t eIdx : verts[v].edgeList) {
        Edge& e = edges[eIdx];
        
        // Kenarın uzunluğunu yeniden hesapla (Arithmetic.h -> dist)
        // e.v1i ve e.v2i kenarın iki ucundaki noktalardır.
        // Biri zaten 'v' (güncellediğimiz nokta), diğeri komşusu.
        e.length = dist(verts[e.v1i].coords, verts[e.v2i].coords);
    }

    // 4. HEAP YAPISINI GÜNCELLE
    // PDF Madde 3.5.2: "...as well as update the minHeap"
    // Kenar uzunlukları değiştiği için sıralama bozuldu.
    // Tek tek düzeltmek yerine en garantisi heap'i baştan kurmaktır.
    buildHeap();
}

Edge& Mesh::getKthShortestEdge(size_t k) {
    // 1. SINIR KONTROLÜ (DÜZELTİLDİ: k=0 GEÇERLİDİR!)
    // k sayısı toplam kenar sayısına eşit veya büyükse hata döndür.
    if (k >= edges.size()) {
        return edges[0];
    }

    // 2. KOPYA OLUŞTUR (İçinde Dummy 0 var)
    vector<size_t> tempHeap = minHeap;

    // 3. (k) KEZ EN KÜÇÜĞÜ AT
    // Mantık: k=0 ise döngüye girme, direkt en tepedekini ver.
    // k=1 ise 1 kere at, sıradakini ver.
    for (size_t i = 0; i < k; i++) {
        
        // Sadece dummy kaldıysa bitmiştir
        if (tempHeap.size() <= 1) return edges[0];

        // Root'u (Index 1) sil:
        tempHeap[1] = tempHeap.back(); // Son elemanı 1'e taşı
        tempHeap.pop_back();           // Sonuncuyu sil

        // Eğer heap'te eleman kaldıysa 1. indexten düzelt
        if (tempHeap.size() > 1) {
            bubbleDownWithArgument(tempHeap, 1);
        }
    }

    // 4. SONUÇ ROOT'TA (Index 1) DURUYOR
    if (tempHeap.size() > 1) {
        return edges[tempHeap[1]]; 
    }

    return edges[0];

}

// Implement your helper functions here.
void Mesh::addEdgeIfMissing(size_t v1, size_t v2) {
    // 1. Zaten komşular mı kontrol et? (vertList içinde ara)
    // PDF Madde 3.4.5 mantığı [cite: 129]
    for (size_t neighbor : verts[v1].vertList) {
        if (neighbor == v2) return; // Zaten ekli, çık.
    }

    // 2. Değilse birbirlerinin komşu listesine ekle
    verts[v1].vertList.push_back(v2);
    verts[v2].vertList.push_back(v1);

    // 3. Yeni Edge (Kenar) oluştur
    size_t edgeIdx = edges.size(); // PDF Madde 3.3.1 edges vektörü [cite: 96]
    Edge newEdge(edgeIdx, v1, v2);

    // 4. Uzunluğu hesapla (Arithmetic.h -> dist)
    // PDF Madde 3.2: dist fonksiyonu pointer alır, array pointer'a dönüşür. [cite: 87]
    newEdge.length = dist(verts[v1].coords, verts[v2].coords);
    
    edges.push_back(newEdge);

    // 5. Vertexlerin Edge Listesini Güncelle
    verts[v1].edgeList.push_back(edgeIdx);
    verts[v2].edgeList.push_back(edgeIdx);
}



void Mesh::bubbleDownWithArgument(vector<size_t>& heap, size_t i) {
   size_t length = heap.size(); // Dummy dahil boyut
    size_t tmp = heap[i];        // Taşınacak eleman
    size_t child;

    // Döngü: Sol çocuk (2*i) heap sınırları içinde mi?
    while ((child = 2 * i) < length) {
        
        // Sağ çocuk var mı VE Sağ çocuk Sol çocuktan daha mı kısa?
        if (child != length - 1 && 
            edges[heap[child + 1]].length < edges[heap[child]].length) {
            child++; // Sağ çocuğu seç
        }

        // Eğer seçilen çocuk, bizim elemandan (tmp) daha kısaysa yer değiştir
        if (edges[heap[child]].length < edges[tmp].length) {
            heap[i] = heap[child]; // Çocuğu yukarı çek
            i = child;             // Aşağı inmeye devam et
        } else {
            break; // Yer doğru, çık
        }
    }
    heap[i] = tmp; // Elemanı yerine koy
}