<commit_before>/*
   Copyright 2009 <NAME>

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/


package org.gavrog.joss.meshes

import java.io._

import scala.Math
import scala.collection.mutable._
import scala.io.Source
import Sums._
import Vectors._

object Mesh {
  trait Chamber {
    def s0: Chamber
    def s1: Chamber
    def s2: Chamber
    
    def vertex: Vertex
    def tVertex: TextureVertex
    def normal: Normal
    def cell: Cell

    def s0_=(ch: Chamber)
    def s1_=(ch: Chamber)
    def s2_=(ch: Chamber)

    def tVertex_=(t: TextureVertex)
    def normal_=(n: Normal)

    def mesh = vertex.mesh
    
    def vertexNr = if (vertex != null) vertex.nr else 0
    def tVertexNr = if (tVertex != null) tVertex.nr else 0
    def normalNr = if (normal != null) normal.nr else 0
    
    def face = if (cell.isInstanceOf[Face]) cell.asInstanceOf[Face] else null
    
    def nextAtFace   = s0.s1
    def prevAtFace   = s1.s0
    def nextAtVertex = s1.s2
    def prevAtVertex = s2.s1
    def opposite     = s0.s2
    
    def start        = vertex
    def end          = s0.vertex
    
    def onTextureBorder = tVertex != s2.tVertex || s0.tVertex != s0.s2.tVertex
    
    def orbit(next: Chamber => Chamber) = {
      def from(c: Chamber): Stream[Chamber] =
        if (c == this) Stream.empty else Stream.cons(c, from(next(c)))
      Stream.cons(this, from(next(this)))
    }
    
    def cellChambers = orbit(_.nextAtVertex)
    def vertexChambers = orbit(_.nextAtFace)
    
    //override def toString = "Chamber(%s -> %s)" format (start, end)
  }
  
  trait Vertex {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def pos    : Vec3

    def pos_=(p: Vec3)

    def cellChambers = chamber.cellChambers
    def degree       = cellChambers.size
    def faces        = cellChambers.map(_.cell)
    def neighbors    = cellChambers.map(_.s0.vertex)
    def x = pos.x
    def y = pos.y
    def z = pos.z

    def pos_=(p: (Double, Double, Double)) { pos = Vec3(p._1, p._2, p._3) }

    override def toString = "Vertex(%d)" format (nr)
  }
  
  trait TextureVertex {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def pos    : Vec2

    def pos_=(p: Vec2)
    def chamber_=(c: Chamber)

    def cellChambers = chamber.cellChambers
    def faces        = cellChambers.filter(_.tVertex == this).map(_.cell)
    def onBorder     = cellChambers.exists(_.onTextureBorder)

    def degree = cellChambers.sum(c =>
      if (c.tVertex == this || c.s2.tVertex == this)
        if (c.tVertex == c.s2.tVertex && c.s0.tVertex != c.s2.s0.tVertex) 2
        else 1
      else 0
    )

    def x = pos.x
    def y = pos.y
    def z = 0.0
    
    def pos_=(p: (Double, Double)) { pos = Vec2(p._1, p._2) }
    
    override def toString = "TextureVertex(%d)" format (nr)
  }

  trait Normal {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def value  : Vec3

    def value_=(p: Vec3)
    def chamber_=(c: Chamber)

    def x = value.x
    def y = value.y
    def z = value.z

    def value_=(p: (Double, Double, Double)) { value = Vec3(p._1, p._2, p._3) }

    override def toString = "Normal(%d)" format (nr)
  }

  trait Cell {
    def mesh   : Mesh
    def chamber: Chamber
    
    def vertexChambers = chamber.vertexChambers
    def vertices = vertexChambers.map(_.vertex)
    def degree   = vertexChambers.size
    
    def formatVertices(v0: Int, vt0: Int, vn0: Int) =
      vertexChambers.map(ch =>
        "%d/%s/%s" format (ch.start.nr + v0,
                           if (ch.tVertex != null) ch.tVertex.nr + vt0 else "",
                           if (ch.normal  != null) ch.normal.nr  + vn0 else "")
      ).mkString(" ")

    def formatVertices: String = formatVertices(0, 0, 0)
  }
  
  trait Face extends Cell {
    def obj           : Object
    def group         : Group
    def material      : Material
    def smoothingGroup: Int
    
    def obj_=           (o: Object)
    def group_=         (g: Group)
    def material_=      (m: Material)
    def smoothingGroup_=(s: Int)
    
    def textureVertices = vertexChambers.map(_.tVertex)
    def normals = vertexChambers.map(_.normal)

    override def toString = "Face(%s; group = '%s', material = '%s')" format
      (formatVertices, group.name, material.name)
  }
  trait Hole extends Cell {
    override def toString = "Hole(%s)" format formatVertices
  }

  class Edge(v: Vertex, w: Vertex) {
    val (from, to) = if (v.nr <= w.nr) (v, w) else (w, v)
    
    override def equals (other: Any) = other.isInstanceOf[Edge] && {
      val e = other.asInstanceOf[Edge]
      e.from.nr == from.nr && e.to.nr == to.nr
    }
    
    override def hashCode = from.nr * 37 + to.nr
  }
  
  case class Object(name: String) {
    override def toString = "Object(" + name + ")"
  }
  
  case class Group(name: String) {
    override def toString = "Group(" + name + ")"
  }
  
  case class Material(name: String) {
    override def toString = "Material(" + name + ")"
  }

  case class Component(mesh: Mesh, chambers: Set[Chamber]) {
    lazy val vertices = new HashSet[Vertex] ++ chambers.map (_.vertex)
    lazy val faces = new HashSet[Face] ++ chambers.map(_.face).filter(null !=)
    def coarseningClassifications = faces.elements.next.vertices
      .map(mesh.classifyForCoarsening(_)).filter(null !=)
  }
  
  case class Chart(mesh: Mesh, chambers: Set[Chamber]) {
    lazy val vertices = new HashSet[TextureVertex] ++ chambers.map (_.tVertex)
    lazy val faces = new HashSet[Face] ++ chambers.map (_.face)
  }
  
  case class VertexClassification(wasVertex:     Set[Vertex],
                                  wasEdgeCenter: Set[Vertex],
                                  wasFaceCenter: Set[Vertex])
  {
    def cost(v: Vertex) = {
      var n = 0
      if (wasFaceCenter(v)) {
        for (c <- v.cellChambers) {
          val d = c.s2
          if (c.tVertex != d.tVertex) n += 3
          if (c.face != null) {
        	if (c.face.material != d.face.material) n += 1
        	if (c.face.group != d.face.group) n += 1
          }
        }
      }
      n
    }

    def cost: Int = wasFaceCenter.sum(cost(_))
    def isStrict = cost == 0
  }

  def matchTopologies(ch1: Chamber, ch2: Chamber,
                      uvs: Boolean): Map[Chamber, Chamber] = {
    val seen1 = new HashSet[Chamber]
    val seen2 = new HashSet[Chamber]
    val queue = new Queue[(Chamber, Chamber)]
    val map   = new HashMap[Chamber, Chamber]
    seen1 += ch1
    seen2 += ch2
    queue += (ch1, ch2)
    map(ch1) = ch2
    
    def neighbors(c: Chamber) =
      List(c.s0, c.s1, if (uvs && c.onTextureBorder) null else c.s2)
    
    while (queue.length > 0) {
      val (d1, d2) = queue.dequeue
      for ((e1, e2) <- neighbors(d1).zip(neighbors(d2))) {
        if ((e1 == null) != (e2 == null)) return null
        if (e1 != null) {
	        if (seen1(e1) != seen2(e2)) return null
	        if (e1.cell.getClass != e2.cell.getClass) return null
	        if (seen1(e1)) {
	          if (map(e1) != e2) return null
	        } else {
	          queue += (e1, e2)
	          seen1 += e1
	          seen2 += e2
	          map(e1) = e2
	        }
         }
      }
    }
    map
  }
  
  def distance[T <: { def x: Double; def y: Double; def z: Double }](
    map: Map[Chamber, Chamber], v: Chamber => T) =
  {
    val verts = new HashSet[(T, T)]
    for ((c, d) <- map) verts += ((v(c), v(d)))
    
    var dist: Double = 0
    for ((v, w) <- verts) {
      val (dx, dy, dz) = (w.x - v.x, w.y - v.y, w.z - v.z)
      dist += dx * dx + dy * dy + dz * dz
    }
    dist
  }
  
  def closest[T <: { def x: Double; def y: Double; def z: Double }](
    maps: Seq[Map[Chamber, Chamber]], v: Chamber => T) =
  {
    var best: Map[Chamber, Chamber] = null
    var dist = Double.MaxValue
    
    for (map <- maps) {
      val d = distance(map, v)
      if (d < dist) {
        dist = d
        best = map
      }
    }
    best
  }

  //TODO avoid code duplication in the following
  def allMatches(c1: Component, c2: Component): Seq[Map[Chamber, Chamber]] = {
    val result = new ArrayBuffer[Map[Chamber, Chamber]]
    if (c1.chambers.size != c2.chambers.size) return result
    
    val degree = new HashMap[Vertex, Int]
    val count = new HashMap[Int, Int]
    for (v <- c1.vertices) {
      degree(v) = v.degree
      count(degree(v)) = count.getOrElse(degree(v), 0) + 1
    }
    for (v <- c2.vertices) degree(v) = v.degree

    val bestD = count.keys.toList.sort((a, b) => count(a) < count(b))(0)

    val ch1 = c1.chambers.find(ch => degree(ch.vertex) == bestD).get
    for (ch2 <- c2.chambers if degree(ch2.vertex) == bestD)
      matchTopologies(ch1, ch2, false) match {
        case null => ()
        case map  => result += map
      }
    
    result
  }
  
  def allMatches(c1: Chart, c2: Chart): Seq[Map[Chamber, Chamber]] = {
    val result = new ArrayBuffer[Map[Chamber, Chamber]]
    if (c1.chambers.size != c2.chambers.size) return result
    
    val degree = new HashMap[TextureVertex, Int]
    val count = new HashMap[Int, Int] { this(0) = c1.chambers.size }
    for (t <- c1.vertices) {
      degree(t) = if (t.onBorder) t.degree else 0
      count(degree(t)) = count.getOrElse(degree(t), 0) + 1
    }
    for (t <- c2.vertices) degree(t) = if (t.onBorder) t.degree else 0
    
    val bestD = count.keys.toList.sort((a, b) => count(a) < count(b))(0)

    val ch1 = c1.chambers.find(ch => degree(ch.tVertex) == bestD).get
    for (ch2 <- c2.chambers if degree(ch2.tVertex) == bestD)
      matchTopologies(ch1, ch2, false) match {
        case null => ()
        case map  => result += map
      }
    
    result
  }
}

class Mesh extends MessageSource {
  import Mesh._

  private val _vertices = new ArrayBuffer[Vertex]
  private val _normals  = new ArrayBuffer[Normal]
  private val _texverts = new ArrayBuffer[TextureVertex]
  private val _faces    = new ArrayBuffer[Face]
  private val _holes    = new ArrayBuffer[Hole]
  private val _chambers = new ArrayBuffer[Chamber]
  private val _objects  = new LinkedHashMap[String, Object]
  private val _groups   = new LinkedHashMap[String, Group]
  private val _mats     = new LinkedHashMap[String, Material]
  private val _edges    = new HashMap[Edge, Chamber]
  
  private val _s0 = new HashMap[Chamber, Chamber]
  private val _s1 = new HashMap[Chamber, Chamber]
  private val _s2 = new HashMap[Chamber, Chamber]
  
  private val _chamber_at_vertex  = new HashMap[Vertex, Chamber]
  private val _chamber_at_tvertex = new HashMap[TextureVertex, Chamber]
  private val _chamber_at_cell    = new HashMap[Cell, Chamber]
  
  private val _vertex_pos  = new HashMap[Vertex, Vec3]
  private val _texture_pos = new HashMap[TextureVertex, Vec2]
  private val _normal_val  = new HashMap[Normal, Vec3]
  
  private val _object_for_face          = new HashMap[Face, Object]
  private val _group_for_face           = new HashMap[Face, Group]
  private val _material_for_face        = new HashMap[Face, Material]
  private val _smoothing_group_for_face = new HashMap[Face, Int]

  object vertex_position {
    def apply(v: Vertex) = _vertex_pos(v)
    def update(v: Vertex, p: Vec3) { _vertex_pos(v) = p }
  }
  
  object texture_position {
    def apply(t: TextureVertex) = _texture_pos(t)
    def update(t: TextureVertex, p: Vec2) { _texture_pos(t) = p }
  }
  
  object normal_value {
    def apply(n: Normal) = _normal_val(n)
    def update(n: Normal, p: Vec3) { _normal_val(n) = p }
  }
  
  val mtllib = new HashMap[String, String]

  def this(source: Source) {
    this()
    
    val faces = new ArrayBuffer[(Seq[Int], Seq[Int], Seq[Int],
                                 Object, Group, Material, Int)]
    var obj     : Object   = null
    var group   : Group    = null
    var material: Material = null
    var smoothingGroup = 0
    val mtllib = new HashMap[String, String]
    
    for(raw <- source.getLines; line = raw.trim
        if line.length > 0 && !line.startsWith("#")) {
      val fields: Seq[String] = line.split("\\s+")
      val cmd = fields(0)
      val pars = fields.slice(1, fields.length)

      cmd match {
      case "mtllib" => {
        try {
          var curmtl: String = null
          for(raw <- Source.fromFile(pars(0)).getLines;
              line = raw.trim
              if line.length > 0 && !line.startsWith("#")) {
            val fields: Seq[String] = line.split("\\s+")
            if (fields(0) == "newmtl") {
              curmtl = fields(1)
              mtllib(curmtl) = ""
            }
            else mtllib(curmtl) += line + "\n"
          }
        } catch {
          case e: FileNotFoundException => System.err.println(
            "WARNING: material file %s not found." format pars(0))
        }
      }
      case "v"  => {
        addVertex(pars(0).toDouble, pars(1).toDouble, pars(2).toDouble)
      }
      case "vn" => {
        addNormal(pars(0).toDouble, pars(1).toDouble, pars(2).toDouble)
      }
      case "vt" => {
        addTextureVertex(pars(0).toDouble, pars(1).toDouble)
      }
      case "o" => {
        if (pars.size > 0) obj = this obj pars(0)
      }
      case "g"  => {
        if (pars.size > 0) group = this group pars(0)
      }
      case "usemtl"  => {
        if (pars.size > 0) material = this material pars(0)
      }
      case "s" => {
        if (pars.size > 0) smoothingGroup = pars(0).toInt
      }
      case "f"  => {
        val n  = pars.length
        val fc = new ArrayBuffer[Int]
        val ft = new ArrayBuffer[Int]
        val fn = new ArrayBuffer[Int]
        pars.foreach { s =>
          val parts = (s + "/0/0").split("/").map(
            (s: String) => if (s.length == 0) 0 else s.toInt)
          fc += parts(0)
          ft += parts(1)
          fn += parts(2)
        }
        if (obj == null) obj = this.obj("_default")
        if (group == null) group = this.group("_default")
        if (material == null) material = this.material("_default")
        faces += (fc, ft, fn, obj, group, material, smoothingGroup)<commit_msg>Mesh: can read obj files with negative vertex indices.<commit_after>/*
   Copyright 2009 <NAME>

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/


package org.gavrog.joss.meshes

import java.io._

import scala.Math
import scala.collection.mutable._
import scala.io.Source
import Sums._
import Vectors._

object Mesh {
  trait Chamber {
    def s0: Chamber
    def s1: Chamber
    def s2: Chamber
    
    def vertex: Vertex
    def tVertex: TextureVertex
    def normal: Normal
    def cell: Cell

    def s0_=(ch: Chamber)
    def s1_=(ch: Chamber)
    def s2_=(ch: Chamber)

    def tVertex_=(t: TextureVertex)
    def normal_=(n: Normal)

    def mesh = vertex.mesh
    
    def vertexNr = if (vertex != null) vertex.nr else 0
    def tVertexNr = if (tVertex != null) tVertex.nr else 0
    def normalNr = if (normal != null) normal.nr else 0
    
    def face = if (cell.isInstanceOf[Face]) cell.asInstanceOf[Face] else null
    
    def nextAtFace   = s0.s1
    def prevAtFace   = s1.s0
    def nextAtVertex = s1.s2
    def prevAtVertex = s2.s1
    def opposite     = s0.s2
    
    def start        = vertex
    def end          = s0.vertex
    
    def onTextureBorder = tVertex != s2.tVertex || s0.tVertex != s0.s2.tVertex
    
    def orbit(next: Chamber => Chamber) = {
      def from(c: Chamber): Stream[Chamber] =
        if (c == this) Stream.empty else Stream.cons(c, from(next(c)))
      Stream.cons(this, from(next(this)))
    }
    
    def cellChambers = orbit(_.nextAtVertex)
    def vertexChambers = orbit(_.nextAtFace)
    
    //override def toString = "Chamber(%s -> %s)" format (start, end)
  }
  
  trait Vertex {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def pos    : Vec3

    def pos_=(p: Vec3)

    def cellChambers = chamber.cellChambers
    def degree       = cellChambers.size
    def faces        = cellChambers.map(_.cell)
    def neighbors    = cellChambers.map(_.s0.vertex)
    def x = pos.x
    def y = pos.y
    def z = pos.z

    def pos_=(p: (Double, Double, Double)) { pos = Vec3(p._1, p._2, p._3) }

    override def toString = "Vertex(%d)" format (nr)
  }
  
  trait TextureVertex {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def pos    : Vec2

    def pos_=(p: Vec2)
    def chamber_=(c: Chamber)

    def cellChambers = chamber.cellChambers
    def faces        = cellChambers.filter(_.tVertex == this).map(_.cell)
    def onBorder     = cellChambers.exists(_.onTextureBorder)

    def degree = cellChambers.sum(c =>
      if (c.tVertex == this || c.s2.tVertex == this)
        if (c.tVertex == c.s2.tVertex && c.s0.tVertex != c.s2.s0.tVertex) 2
        else 1
      else 0
    )

    def x = pos.x
    def y = pos.y
    def z = 0.0
    
    def pos_=(p: (Double, Double)) { pos = Vec2(p._1, p._2) }
    
    override def toString = "TextureVertex(%d)" format (nr)
  }

  trait Normal {
    def mesh   : Mesh
    def nr     : Int
    def chamber: Chamber
    def value  : Vec3

    def value_=(p: Vec3)
    def chamber_=(c: Chamber)

    def x = value.x
    def y = value.y
    def z = value.z

    def value_=(p: (Double, Double, Double)) { value = Vec3(p._1, p._2, p._3) }

    override def toString = "Normal(%d)" format (nr)
  }

  trait Cell {
    def mesh   : Mesh
    def chamber: Chamber
    
    def vertexChambers = chamber.vertexChambers
    def vertices = vertexChambers.map(_.vertex)
    def degree   = vertexChambers.size
    
    def formatVertices(v0: Int, vt0: Int, vn0: Int) =
      vertexChambers.map(ch =>
        "%d/%s/%s" format (ch.start.nr + v0,
                           if (ch.tVertex != null) ch.tVertex.nr + vt0 else "",
                           if (ch.normal  != null) ch.normal.nr  + vn0 else "")
      ).mkString(" ")

    def formatVertices: String = formatVertices(0, 0, 0)
  }
  
  trait Face extends Cell {
    def obj           : Object
    def group         : Group
    def material      : Material
    def smoothingGroup: Int
    
    def obj_=           (o: Object)
    def group_=         (g: Group)
    def material_=      (m: Material)
    def smoothingGroup_=(s: Int)
    
    def textureVertices = vertexChambers.map(_.tVertex)
    def normals = vertexChambers.map(_.normal)

    override def toString = "Face(%s; group = '%s', material = '%s')" format
      (formatVertices, group.name, material.name)
  }
  trait Hole extends Cell {
    override def toString = "Hole(%s)" format formatVertices
  }

  class Edge(v: Vertex, w: Vertex) {
    val (from, to) = if (v.nr <= w.nr) (v, w) else (w, v)
    
    override def equals (other: Any) = other.isInstanceOf[Edge] && {
      val e = other.asInstanceOf[Edge]
      e.from.nr == from.nr && e.to.nr == to.nr
    }
    
    override def hashCode = from.nr * 37 + to.nr
  }
  
  case class Object(name: String) {
    override def toString = "Object(" + name + ")"
  }
  
  case class Group(name: String) {
    override def toString = "Group(" + name + ")"
  }
  
  case class Material(name: String) {
    override def toString = "Material(" + name + ")"
  }

  case class Component(mesh: Mesh, chambers: Set[Chamber]) {
    lazy val vertices = new HashSet[Vertex] ++ chambers.map (_.vertex)
    lazy val faces = new HashSet[Face] ++ chambers.map(_.face).filter(null !=)
    def coarseningClassifications = faces.elements.next.vertices
      .map(mesh.classifyForCoarsening(_)).filter(null !=)
  }
  
  case class Chart(mesh: Mesh, chambers: Set[Chamber]) {
    lazy val vertices = new HashSet[TextureVertex] ++ chambers.map (_.tVertex)
    lazy val faces = new HashSet[Face] ++ chambers.map (_.face)
  }
  
  case class VertexClassification(wasVertex:     Set[Vertex],
                                  wasEdgeCenter: Set[Vertex],
                                  wasFaceCenter: Set[Vertex])
  {
    def cost(v: Vertex) = {
      var n = 0
      if (wasFaceCenter(v)) {
        for (c <- v.cellChambers) {
          val d = c.s2
          if (c.tVertex != d.tVertex) n += 3
          if (c.face != null) {
        	if (c.face.material != d.face.material) n += 1
        	if (c.face.group != d.face.group) n += 1
          }
        }
      }
      n
    }

    def cost: Int = wasFaceCenter.sum(cost(_))
    def isStrict = cost == 0
  }

  def matchTopologies(ch1: Chamber, ch2: Chamber,
                      uvs: Boolean): Map[Chamber, Chamber] = {
    val seen1 = new HashSet[Chamber]
    val seen2 = new HashSet[Chamber]
    val queue = new Queue[(Chamber, Chamber)]
    val map   = new HashMap[Chamber, Chamber]
    seen1 += ch1
    seen2 += ch2
    queue += (ch1, ch2)
    map(ch1) = ch2
    
    def neighbors(c: Chamber) =
      List(c.s0, c.s1, if (uvs && c.onTextureBorder) null else c.s2)
    
    while (queue.length > 0) {
      val (d1, d2) = queue.dequeue
      for ((e1, e2) <- neighbors(d1).zip(neighbors(d2))) {
        if ((e1 == null) != (e2 == null)) return null
        if (e1 != null) {
	        if (seen1(e1) != seen2(e2)) return null
	        if (e1.cell.getClass != e2.cell.getClass) return null
	        if (seen1(e1)) {
	          if (map(e1) != e2) return null
	        } else {
	          queue += (e1, e2)
	          seen1 += e1
	          seen2 += e2
	          map(e1) = e2
	        }
         }
      }
    }
    map
  }
  
  def distance[T <: { def x: Double; def y: Double; def z: Double }](
    map: Map[Chamber, Chamber], v: Chamber => T) =
  {
    val verts = new HashSet[(T, T)]
    for ((c, d) <- map) verts += ((v(c), v(d)))
    
    var dist: Double = 0
    for ((v, w) <- verts) {
      val (dx, dy, dz) = (w.x - v.x, w.y - v.y, w.z - v.z)
      dist += dx * dx + dy * dy + dz * dz
    }
    dist
  }
  
  def closest[T <: { def x: Double; def y: Double; def z: Double }](
    maps: Seq[Map[Chamber, Chamber]], v: Chamber => T) =
  {
    var best: Map[Chamber, Chamber] = null
    var dist = Double.MaxValue
    
    for (map <- maps) {
      val d = distance(map, v)
      if (d < dist) {
        dist = d
        best = map
      }
    }
    best
  }

  //TODO avoid code duplication in the following
  def allMatches(c1: Component, c2: Component): Seq[Map[Chamber, Chamber]] = {
    val result = new ArrayBuffer[Map[Chamber, Chamber]]
    if (c1.chambers.size != c2.chambers.size) return result
    
    val degree = new HashMap[Vertex, Int]
    val count = new HashMap[Int, Int]
    for (v <- c1.vertices) {
      degree(v) = v.degree
      count(degree(v)) = count.getOrElse(degree(v), 0) + 1
    }
    for (v <- c2.vertices) degree(v) = v.degree

    val bestD = count.keys.toList.sort((a, b) => count(a) < count(b))(0)

    val ch1 = c1.chambers.find(ch => degree(ch.vertex) == bestD).get
    for (ch2 <- c2.chambers if degree(ch2.vertex) == bestD)
      matchTopologies(ch1, ch2, false) match {
        case null => ()
        case map  => result += map
      }
    
    result
  }
  
  def allMatches(c1: Chart, c2: Chart): Seq[Map[Chamber, Chamber]] = {
    val result = new ArrayBuffer[Map[Chamber, Chamber]]
    if (c1.chambers.size != c2.chambers.size) return result
    
    val degree = new HashMap[TextureVertex, Int]
    val count = new HashMap[Int, Int] { this(0) = c1.chambers.size }
    for (t <- c1.vertices) {
      degree(t) = if (t.onBorder) t.degree else 0
      count(degree(t)) = count.getOrElse(degree(t), 0) + 1
    }
    for (t <- c2.vertices) degree(t) = if (t.onBorder) t.degree else 0
    
    val bestD = count.keys.toList.sort((a, b) => count(a) < count(b))(0)

    val ch1 = c1.chambers.find(ch => degree(ch.tVertex) == bestD).get
    for (ch2 <- c2.chambers if degree(ch2.tVertex) == bestD)
      matchTopologies(ch1, ch2, false) match {
        case null => ()
        case map  => result += map
      }
    
    result
  }
}

class Mesh extends MessageSource {
  import Mesh._

  private val _vertices = new ArrayBuffer[Vertex]
  private val _normals  = new ArrayBuffer[Normal]
  private val _texverts = new ArrayBuffer[TextureVertex]
  private val _faces    = new ArrayBuffer[Face]
  private val _holes    = new ArrayBuffer[Hole]
  private val _chambers = new ArrayBuffer[Chamber]
  private val _objects  = new LinkedHashMap[String, Object]
  private val _groups   = new LinkedHashMap[String, Group]
  private val _mats     = new LinkedHashMap[String, Material]
  private val _edges    = new HashMap[Edge, Chamber]
  
  private val _s0 = new HashMap[Chamber, Chamber]
  private val _s1 = new HashMap[Chamber, Chamber]
  private val _s2 = new HashMap[Chamber, Chamber]
  
  private val _chamber_at_vertex  = new HashMap[Vertex, Chamber]
  private val _chamber_at_tvertex = new HashMap[TextureVertex, Chamber]
  private val _chamber_at_cell    = new HashMap[Cell, Chamber]
  
  private val _vertex_pos  = new HashMap[Vertex, Vec3]
  private val _texture_pos = new HashMap[TextureVertex, Vec2]
  private val _normal_val  = new HashMap[Normal, Vec3]
  
  private val _object_for_face          = new HashMap[Face, Object]
  private val _group_for_face           = new HashMap[Face, Group]
  private val _material_for_face        = new HashMap[Face, Material]
  private val _smoothing_group_for_face = new HashMap[Face, Int]

  object vertex_position {
    def apply(v: Vertex) = _vertex_pos(v)
    def update(v: Vertex, p: Vec3) { _vertex_pos(v) = p }
  }
  
  object texture_position {
    def apply(t: TextureVertex) = _texture_pos(t)
    def update(t: TextureVertex, p: Vec2) { _texture_pos(t) = p }
  }
  
  object normal_value {
    def apply(n: Normal) = _normal_val(n)
    def update(n: Normal, p: Vec3) { _normal_val(n) = p }
  }
  
  val mtllib = new HashMap[String, String]

  def this(source: Source) {
    this()
    
    val faces = new ArrayBuffer[(Seq[Int], Seq[Int], Seq[Int],
                                 Object, Group, Material, Int)]
    var obj     : Object   = null
    var group   : Group    = null
    var material: Material = null
    var smoothingGroup = 0
    val mtllib = new HashMap[String, String]
    
    for(raw <- source.getLines; line = raw.trim
        if line.length > 0 && !line.startsWith("#")) {
      val fields: Seq[String] = line.split("\\s+")
      val cmd = fields(0)
      val pars = fields.slice(1, fields.length)

      cmd match {
      case "mtllib" => {
        try {
          var curmtl: String = null
          for(raw <- Source.fromFile(pars(0)).getLines;
              line = raw.trim
              if line.length > 0 && !line.startsWith("#")) {
            val fields: Seq[String] = line.split("\\s+")
            if (fields(0) == "newmtl") {
              curmtl = fields(1)
              mtllib(curmtl) = ""
            }
            else mtllib(curmtl) += line + "\n"
          }
        } catch {
          case e: FileNotFoundException => System.err.println(
            "WARNING: material file %s not found." format pars(0))
        }
      }
      case "v"  => {
        addVertex(pars(0).toDouble, pars(1).toDouble, pars(2).toDouble)
      }
      case "vn" => {
        addNormal(pars(0).toDouble, pars(1).toDouble, pars(2).toDouble)
      }
      case "vt" => {
        addTextureVertex(pars(0).toDouble, pars(1).toDouble)
      }
      case "o" => {
        if (pars.size > 0) obj = this obj pars(0)
      }
      case "g"  => {
        if (pars.size > 0) group = this group pars(0)
      }
      case "usemtl"  => {
        if (pars.size > 0) material = this material pars(0)
      }
      case "s" => {
        if (pars.size > 0) smoothingGroup = pars(0).toInt
      }
      case "f"  => {
        val n  = pars.length
        val fc = new ArrayBuffer[Int]
        val ft = new ArrayBuffer[Int]
        val fn = new ArrayBuffer[Int]
        pars.foreach { s =>
          val parts = (s + "/0/0").split("/").map(
            (s: String) => if (s.length == 0) 0 else s.toInt)
          fc += parts(0) + (if (parts(0) < 0) numberOfVertices + 1 else 0)
          ft += parts(1) + (if (parts(1) < 0) numberOfTextureVertices + 1 else 0)
          fn += parts(2) + (if (parts(2) < 0) numberOfNormals + 1 else 0)
        }
        if (obj == null) obj = this.obj("_default")
        if (group == null) group = this.group("_default")
        if (material == null) material = this.material("_default")
        faces += (fc, ft, fn, obj, group, material, smoothingGroup)
{'fraction_non_alphanumeric': 0.1261930010604454, 'fraction_numerical': 0.01395682961037184, 'mean_word_length': 2.1893955924067203, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3937439', 'n_tokens_mistral': 10136, 'n_tokens_neox': 9915, 'n_words': 2806}