# immutable half-edge data structure

8 messages
Open this post in threaded view
|

## immutable half-edge data structure

 I realize there are many advantages to immutable data structures and scala provides many different classes with immutable functionality like the List.  However, I can't seem to wrap my head around some more complex data structures that are interconnected at so many instances. One in particular is with polygonal models using the half-edge data structure. http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtmlI've implemented this several times before, but working with these structures with immutable classes seems incredibly complex especially if they're referenced by index instead of class reference. For a polygonal mesh, a vertex has an coordinate and a reference to one of the edges it touches a face and a reference to one of it's edges a edge has a reference to the next edge on the same face, the edge on the adjacent face, the first vertex of the edge, and a reference to the the face itself that it lies on If each one of these references is stored as an integer keyed to a hashmap, each would probably need a reference to the mesh holding the hashmaps of vertices, faces, and edges as well.  That seems to make sense, but it makes manipulating the geometry extremely tedious.  As a simple example, one might need to extrude a face on the top of a cube.  So, four new vertices would need to be created, but since no edges are made yet, they're just dummy vertices classes I'll have to recreate later when I have references to the edges and faces and vice versa. I assume this kind of thing is handled already in functional programming when doing anything graph related, but I'd appreciate some advice or references to good reading material on handling these kind of problems in a functional way.  This is more of a general functional programming question, but I'm trying to implement it specifically in scala. Josh
Open this post in threaded view
|

## Re: immutable half-edge data structure

 On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben
Open this post in threaded view
|

## Re: immutable half-edge data structure

 If Scala had write-once vals - I think that would solve the problem with constructing immutable data with cyclical references.Using write-once vals you could construct the data graph and once all references have stabilised to their final states you can then expose it to the world and take advantage of all the benefits that immutability gives you. Note that "lazy vals" don't fill this hole.Ishaaq2009/11/2 Ben Hutchison On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state  However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben
Open this post in threaded view
|

## Re: immutable half-edge data structure

 In reply to this post by Ben Hutchison-3 It is perfectly possible to create cycles with lazy structures.On Mon, Nov 2, 2009 at 3:01 AM, Ben Hutchison wrote: On Sun, Nov 1, 2009 at 10:49 AM, Josh Stratton <[hidden email]> wrote: > I realize there are many advantages to immutable data structures and > scala provides many different classes with immutable functionality > like the List. Immutability is good, but its not appropriate everywhere. This nicely summarizes much of my design aesthetic: http://clojure.org/state  However, I can't seem to wrap my head around some more > complex data structures that are interconnected at so many instances. > One in particular is with polygonal models using the half-edge data > structure. [snip] ... Is the essence of your problem Cyclic References? I think its logically impossible to ever create a cycle solely with wholly immutable objects. One approach I favor is to use mutability locally in a creation method with an "unpublished" object. Mutate it into the state you want to outside world to see, then publish (ie reveal) it only through types that hide the mutation operations. -Ben -- Daniel C. SobralSomething I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.
Open this post in threaded view
|

## Re: immutable half-edge data structure

Open this post in threaded view
|

## Re: immutable half-edge data structure

 On Nov 2, 2009, at 7:40 PM, Ishaaq Chandy wrote:http://www.haskell.org/haskellwiki/Tying_the_KnotHowever, my haskell-foo isn't quite there yet - can someone please translate?I’m sure someone can write a tidier example, but off the cuff, something like the below. Note how the geta “thunk” is, crucially, in the same scope as the value ‘a’ that it returns.object Example {  case class A(val b: B)  case class B(_a: () => A) {    def a = _a()  }    val geta: () => A = () => a  val b = new B(geta)  val a = new A(b)   println(b)  println(a)  println(a.b)  println(b.a)}