2 ms·
But Rc is only useful for creating tree-like data-structures. One non-tree cross-link or back-link and you'll have to redesign your entire code.
by amelius 4y ago
But Rc is only useful for creating tree-like data-structures.
One non-tree cross-link or back-link and you'll have to redesign your entire code.
- scotty79 4y agoIf you further wrap Rc in an Option you can set crosslinks and backlinks to None when you are dropping your data to get rid of the problem of crosslinks or backlinks making reference-counting leak memory. Then you just need to be mindful to not loose handle to a cycle of your nodes before you break the cycle by setting some crosslinks to None. You can fairly easily refactor your almost-tree code to adapt it to that additional Option wrap. Of course you might instead opt to introduce some garbage collector crate into your project. They usually provide garbage collected Rc equivalent, which makes swapping it out very easy. Rc's are really very useful first approach to making anything complex in Rust. I usually have something like struct NodeStruct { my_data: i32, link: Node } and struct Node(Rc<NodeStruct>); or struct Node(Option<Rc<NodeStruct>>); if I need cross-links. Great thing is you can then add 'methods' to your type with impl Node {} Or define operators and other traits with: impl Add<Node> for Node {} Sometimes, when I need mutability I even wrap the NodeStruct in RefCell. It seems like a lot of wrappers but thanks to them you can have very nice code that uses this type that has pretty much 'normal modren language' semantics + value semantics and is still blazing fast. When you implement Ord, Eq, Hash they all go through all the wrappers and let you treat your final type Node as a comparable, sortable, hashable and cheaply clonable value. Dereferencing also goes through all or most of the wrappers automatically.
- puffoflogic 4y agoSibling and parent pointers are almost universally a sign that an abstract data structure (and associated algorithm) has been mistaken for concrete. The exception that comes to mind first is Knuth's dancing links, and its obscurity is an indication of the rarity of actually needing these pointers. In any case, it's also a poster child for using indices rather than pointers.
- scotty79 4y agoCurrently I'm working on constructing proofs of tautologies directly from the system of axioms using substitution and modus ponens rule. https://en.m.wikipedia.org/wiki/List_of_Hilbert_systems https://en.m.wikipedia.org/wiki/List_of_Hilbert_systems Main objects in my program are expression trees. I manipulate them, cut them, merge them, compare them, splice one into the other. Rc's enable me to have full flexibility and share tremendous amount of data across objects in my program. Rust is absolutely wonderful language for this problem thanks to Rc's, enums, value semantics, auto-deriving traits and ability to implement traits for existing types and of course speed. I'm not implementing specific algorithms. I'm making them up as I go although I used some simple ones like topological sort or A* that eventually turned into just breadth search because I have no idea how far I am from the solution.
- amelius 4y ago> I'm not implementing specific algorithms. I'm making them up as I go It's mindboggling to me that people are using a systems programming language for mathematical research, especially if they don't know yet what the final algorithms will look like. But all the more power to you for trying.