जंग में रिकर्सिव डेटा स्ट्रक्चर

Question

मैं जंग में एक दृश्यग्राफ जैसी डेटा संरचना को कार्यान्वित करने की कोशिश कर रहा हूं।

मैं इस सेल्सियस के लिए एक बराबर चाहते हैं ++ कोड:

struct Node 
{ 
    Node* parent; // should be mutable, and nullable (no parent) 
    std::vector<Node*> child; 

    virtual ~Node() 
    { 
     for(auto it = child.begin(); it != child.end(); ++it) 
     { 
      delete *it; 
     } 
    } 

    void addNode(Node* newNode) 
    { 
     if (newNode->parent) 
     { 
      newNode->parent.child.erase(newNode->parent.child.find(newNode)); 
     } 
     newNode->parent = this; 
     child.push_back(newNode); 
    } 
} 

सुरक्षित जंग में व्यक्त: माता-पिता अपने बच्चों के स्वामित्व लेने के साथ

नोड्स सुलभ होने के साथ
• किसी प्रकार के संदर्भ के माध्यम से बाहर

EDIT

उपयोगी पैटर्न के लिए सभी को धन्यवाद, मुझे नहीं पता था। मुझे लगता है कि मैं इस समस्या को हल करने के लिए उनका उपयोग कर सकता हूं, मुझे उन्हें पचाने के लिए कुछ समय चाहिए।

मैं एक और बाधा को निर्दिष्ट करने में विफल रहा है:

• मैं घटनाओं कि स्पर्श एक Node संभावित करने के लिए पूरे वृक्ष उत्परिवर्तित चाहते हैं।

तो मुझे लगता है कि डीके का उदाहरण मेरे मन में सबसे नज़दीक है।

Answer 1

समस्या यह है कि यह डेटा संरचना स्वाभाविक रूप से असुरक्षित है; यह है जो जंग में प्रत्यक्ष समतुल्य है जो unsafe का उपयोग नहीं करता है। यह डिजाइन द्वारा है।

यदि आप इसे सुरक्षित जंग कोड में अनुवाद करना चाहते हैं, तो आपको इसके बारे में और अधिक विशिष्ट होना चाहिए कि आप वास्तव में क्या चाहते हैं। मुझे पता है कि आपने उपर्युक्त कुछ गुण सूचीबद्ध किए हैं, लेकिन अक्सर लोग जंग में आने वाले लोग कहते हैं, "मुझे इस सी/सी ++ कोड में जो कुछ भी है, वह मुझे चाहिए", जिसके लिए सीधा जवाब "अच्छा है, आप नहीं कर सकते।"

आप भी हैं, अपरिहार्य रूप से, यह बदलने के लिए कि आप इस पर कैसे पहुंचते हैं। आपके द्वारा दिए गए उदाहरण में किसी भी स्वामित्व अर्थशास्त्र, उत्परिवर्तनीय एलियासिंग और चक्र के बिना पॉइंटर्स हैं; जिनमें से सभी जंग आपको सी ++ की तरह अनदेखा करने की अनुमति नहीं देंगे।

सबसे आसान समाधान केवल parent पॉइंटर से छुटकारा पाने के लिए है, और बाहरी रूप से (फाइल सिस्टम पथ की तरह) को बनाए रखना है। यह भी उधार के साथ अच्छी तरह से खेलता है कहीं भी कोई चक्र देखते हैं क्योंकि:

pub struct Node1 { 
    children: Vec<Node1>, 
} 

आप जरूरत माता पिता संकेत दिए गए हैं, तो आप आधे रास्ते आईडी बजाय जाते हैं तो हो सकता है और का उपयोग करें:

use std::collections::BTreeMap; 

type Id = usize; 

pub struct Tree { 
    descendants: BTreeMap<Id, Node2>, 
    root: Option<Id>, 
} 

pub struct Node2 { 
    parent: Id, 
    children: Vec<Id>, 
} 

BTreeMap प्रभावी रूप से है सीधे मेमोरी पतों का उपयोग करके उधार लेने और एलियासिंग मुद्दों को छोड़कर आपकी "पता स्थान" को छोड़कर।

बेशक

, यह एक दिया Id विशेष पेड़ से बंधा नहीं किया जा रहा की समस्या का परिचय है, जिसका अर्थ है कि नोड इसे नष्ट कर दिया जा सकता है के अंतर्गत आता है, और अब आप प्रभावी रूप से एक dangling सूचक है क्या है।लेकिन, यह वह कीमत है जिसका आप एलियासिंग और उत्परिवर्तन के लिए भुगतान करते हैं। यह भी कम प्रत्यक्ष है।

या, आप पूरे हॉग और उपयोग संदर्भ गिनती और गतिशील उधार जाँच जा सकते हैं:

use std::cell::RefCell; 
use std::rc::{Rc, Weak}; 

// Note: do not derive Clone to make this move-only. 
pub struct Node3(Rc<RefCell<Node3_>>); 

pub type WeakNode3 = Weak<RefCell<Node3>>; 

pub struct Node3_ { 
    parent: Option<WeakNode3>, 
    children: Vec<Node3>, 
} 

impl Node3 { 
    pub fn add(&self, node: Node3) { 
     // No need to remove from old parent; move semantics mean that must have 
     // already been done. 
     (node.0).borrow_mut().parent = Some(Rc::downgrade(&self.0)); 
     self.children.push(node); 
    } 
} 

यहाँ, आप Node3 प्रयोग करेंगे पेड़ के भागों के बीच एक नोड का स्थानान्तरण करने, और WeakNode3 बाहरी संदर्भों के लिए। या, आप Node3 क्लोनेबल बना सकते हैं और यह सुनिश्चित करने के लिए add में तर्क को वापस जोड़ सकते हैं कि कोई दिया गया नोड गलती से गलत माता-पिता के बच्चे को नहीं रखता है।

इस सख्ती से दूसरा विकल्प की तुलना में बेहतर नहीं है, क्योंकि इस डिजाइन बिल्कुल नहीं कर सकते हैं स्थिर उधार-चेकिंग से लाभ। दूसरा कम से कम आपको ग्राफ़ को दो स्थानों से संकलित समय पर एक बार में परिवर्तित करने से रोक सकता है; यहां, अगर ऐसा होता है, तो आप बस दुर्घटनाग्रस्त हो जाएंगे।

बिंदु यह है: आप केवल सब कुछ नहीं हो सकते हैं। आपको यह तय करना होगा कि आप कौन से परिचालन वास्तव में को समर्थन करने की आवश्यकता है। उस बिंदु पर, आमतौर पर यह उन प्रकारों को चुनने का मामला होता है जो आपको आवश्यक गुण देते हैं।

Answer 2

जंग आपको उन चीजों को करने से मना कर स्मृति सुरक्षा सुनिश्चित करने की कोशिश करता है जो संभावित रूप से असुरक्षित हो सकते हैं। चूंकि यह विश्लेषण संकलन-समय पर किया जाता है, इसलिए संकलक केवल कुशलता के एक उप-समूह के बारे में कारण बता सकता है जिसे सुरक्षित माना जाता है।

जंग में, आप आसानी संग्रहीत कर सकती है या तो माता-पिता के लिए एक संदर्भ (मूल उधार, इस प्रकार उत्परिवर्तन रोकने के द्वारा) या बच्चे नोड्स की सूची (जो आप अधिक स्वतंत्रता देता है, उन्हें मालिक द्वारा), लेकिन दोनों नहीं (unsafe का उपयोग किए बिना)। यह addNode के कार्यान्वयन के लिए विशेष रूप से समस्याग्रस्त है, जिसके लिए दिए गए नोड के माता-पिता को उत्परिवर्तनीय पहुंच की आवश्यकता होती है। हालांकि, यदि आप parent पॉइंटर को एक परिवर्तनीय संदर्भ के रूप में संग्रहीत करते हैं, तो, क्योंकि किसी विशेष ऑब्जेक्ट का केवल एक ही विस्थापन संदर्भ एक समय में उपयोग योग्य हो सकता है, माता-पिता तक पहुंचने का एकमात्र तरीका एक बच्चे नोड के माध्यम से होगा, और आप चाहते हैं केवल एक ही बच्चे नोड रखने में सक्षम हो, अन्यथा आपके पास एक ही पैरेंट नोड के दो उत्परिवर्तनीय संदर्भ होंगे।

यदि आप असुरक्षित कोड से बचना चाहते हैं, तो कई विकल्प हैं, लेकिन उन्हें सभी को कुछ बलिदान की आवश्यकता होगी।

---

सबसे आसान समाधान बस parent क्षेत्र को दूर करने के लिए है। हम नोड के माता-पिता को याद रखने के लिए एक अलग डेटा संरचना को परिभाषित कर सकते हैं, जबकि हम नोड में इसे संग्रहीत करने के बजाए पेड़ को पार करते हैं।

पहले, आइए Node को परिभाषित करते हैं:

#[derive(Debug)] 
struct Node<T> { 
    data: T, 
    children: Vec<Node<T>>, 
} 

impl<T> Node<T> { 
    fn new(data: T) -> Node<T> { 
     Node { data: data, children: vec![] } 
    } 

    fn add_child(&mut self, child: Node<T>) { 
     self.children.push(child); 
    } 
} 

(मैं एक data क्षेत्र जोड़ा क्योंकि एक पेड़ नोड्स पर डेटा के बिना सुपर उपयोगी नहीं है!)

चलो अब के रूप में हम नेविगेट माता-पिता को ट्रैक करने के लिए एक और struct को परिभाषित करते हैं:

#[derive(Debug)] 
struct NavigableNode<'a, T: 'a> { 
    node: &'a Node<T>, 
    parent: Option<&'a NavigableNode<'a, T>>, 
} 

impl<'a, T> NavigableNode<'a, T> { 
    fn child(&self, index: usize) -> NavigableNode<T> { 
     NavigableNode { 
      node: &self.node.children[index], 
      parent: Some(self) 
     } 
    } 
} 

impl<T> Node<T> { 
    fn navigate<'a>(&'a self) -> NavigableNode<T> { 
     NavigableNode { node: self, parent: None } 
    } 
} 

यह समाधान ठीक काम करता है अगर तुम पेड़ उत्परिवर्तित के रूप में आप यह नेविगेट और आप माता-पिता रख सकते की जरूरत नहीं है NavigableNode ऑब्जेक्ट्स (जो एक रिकर्सिव एल्गोरिदम के लिए ठीक काम करता है, लेकिन अगर आप NavigableNode को किसी अन्य डेटा स्ट्रक्चर में स्टोर करना चाहते हैं और इसे चारों ओर रखते हैं तो बहुत अच्छा काम नहीं करता है)। दूसरे प्रतिबंध को माता-पिता को स्टोर करने के लिए उधारित सूचक के अलावा कुछ और उपयोग करके कम किया जा सकता है; यदि आप अधिकतम genericity चाहते हैं, आप Borrow trait का उपयोग प्रत्यक्ष मूल्यों, उधार संकेत दिए गए, Box तों, Rc की, आदि

---

अब अनुमति देने के लिए, के zippers के बारे में बात कर सकते हैं। कार्यात्मक प्रोग्रामिंग में, ज़िप्पर का उपयोग डेटा संरचना (सूची, पेड़, मानचित्र इत्यादि) के किसी विशेष तत्व पर "फोकस" करने के लिए किया जाता है ताकि उस तत्व को एक्सेस करने में स्थिर समय लगे, जबकि उस डेटा संरचना के सभी डेटा को बनाए रखा जाए। यदि आपको अपने पेड़ पर नेविगेट करने की आवश्यकता है और नेविगेशन के दौरान को उत्परिवर्तित करने के दौरान, पेड़ को नेविगेट करने की क्षमता को बनाए रखने के दौरान, तो आप एक पेपर को एक जिपर में बदल सकते हैं और जिपर के माध्यम से संशोधन कर सकते हैं।

#[derive(Debug)] 
struct NodeZipper<T> { 
    node: Node<T>, 
    parent: Option<Box<NodeZipper<T>>>, 
    index_in_parent: usize, 
} 

impl<T> NodeZipper<T> { 
    fn child(mut self, index: usize) -> NodeZipper<T> { 
     // Remove the specified child from the node's children. 
     // A NodeZipper shouldn't let its users inspect its parent, 
     // since we mutate the parents 
     // to move the focused nodes out of their list of children. 
     // We use swap_remove() for efficiency. 
     let child = self.node.children.swap_remove(index); 

     // Return a new NodeZipper focused on the specified child. 
     NodeZipper { 
      node: child, 
      parent: Some(Box::new(self)), 
      index_in_parent: index, 
     } 
    } 

    fn parent(self) -> NodeZipper<T> { 
     // Destructure this NodeZipper 
     let NodeZipper { node, parent, index_in_parent } = self; 

     // Destructure the parent NodeZipper 
     let NodeZipper { 
      node: mut parent_node, 
      parent: parent_parent, 
      index_in_parent: parent_index_in_parent, 
     } = *parent.unwrap(); 

     // Insert the node of this NodeZipper back in its parent. 
     // Since we used swap_remove() to remove the child, 
     // we need to do the opposite of that. 
     parent_node.children.push(node); 
     let len = parent_node.children.len(); 
     parent_node.children.swap(index_in_parent, len - 1); 

     // Return a new NodeZipper focused on the parent. 
     NodeZipper { 
      node: parent_node, 
      parent: parent_parent, 
      index_in_parent: parent_index_in_parent, 
     } 
    } 

    fn finish(mut self) -> Node<T> { 
     while let Some(_) = self.parent { 
      self = self.parent(); 
     } 

     self.node 
    } 
} 

impl<T> Node<T> { 
    fn zipper(self) -> NodeZipper<T> { 
     NodeZipper { node: self, parent: None, index_in_parent: 0 } 
    } 
} 

इस ज़िपर का उपयोग करने के लिए आपको पेड़ की जड़ नोड का स्वामित्व है, की जरूरत है:

यहाँ कैसे हम Node ऊपर परिभाषित के लिए एक ज़िपर को लागू कर सकता है। नोड्स के स्वामित्व को लेकर, जिपर कॉपी या क्लोनिंग नोड्स से बचने के लिए चीजों को चारों ओर स्थानांतरित कर सकता है। जब हम एक जिपर ले जाते हैं, तो हम वास्तव में पुराने जिपर को छोड़ देते हैं और एक नया बनाते हैं (हालांकि हम self को म्यूट करके इसे भी कर सकते हैं, लेकिन मैंने सोचा कि यह स्पष्ट था, साथ ही यह आपको चेन विधि कॉल करने देता है)।

---

ऊपर दिए गए विकल्पों संतोषजनक नहीं हैं, और आप पूरी तरह एक नोड में एक नोड के माता-पिता की दुकान चाहिए, तो अगला सबसे अच्छा विकल्प Rc<RefCell<Node<T>>> उपयोग करने के लिए माता पिता के लिए और बच्चों को संदर्भित करने के लिए है। Rc साझा स्वामित्व को सक्षम बनाता है, लेकिन रनटाइम पर संदर्भ गणना करने के लिए ओवरहेड जोड़ता है। RefCell आंतरिक परिवर्तनशीलता को सक्षम बनाता है, लेकिन रनटाइम पर सक्रिय बोरो का ट्रैक रखने के लिए ओवरहेड जोड़ता है। और RefCell का उपयोग कर कार्यान्वयन के लिए See DK.'s answer।

Answer 3

कुछ मामलों में, आप क्षेत्र का भी उपयोग कर सकते हैं। एक क्षेत्र गारंटी देता है कि इसमें संग्रहीत मूल्यों के समान जीवनकाल ही क्षेत्र के समान होगा। इसका अर्थ यह है कि अधिक मूल्य जोड़ना किसी भी मौजूदा जीवनकाल को अमान्य नहीं करेगा, लेकिन क्षेत्र को स्थानांतरित करेगा। इस प्रकार, यदि आपको पेड़ पेड़ की आवश्यकता है तो ऐसा समाधान व्यवहार्य नहीं है।

यह नोड्स से स्वामित्व को हटाकर समस्या हल करता है।

यहां एक उदाहरण है जो इंटीरियर उत्परिवर्तन का उपयोग करता है ताकि इसे बनाए जाने के बाद नोड को उत्परिवर्तित किया जा सके। अन्य मामलों में, यदि आप पेड़ का निर्माण एक बार और फिर बस नेविगेट किया जाता है तो आप इस उत्परिवर्तन को हटा सकते हैं।

extern crate typed_arena; 

use std::cell::{Cell, RefCell}; 
use std::fmt; 

use typed_arena::Arena; 

struct Tree<'a, T: 'a> { 
    nodes: Arena<Node<'a, T>>, 
} 

impl<'a, T> Tree<'a, T> { 
    fn new() -> Tree<'a, T> { 
     Self { nodes: Arena::new() } 
    } 

    fn new_node(&'a self, data: T) -> &'a mut Node<'a, T> { 
     self.nodes.alloc(Node { 
      data, 
      tree: self, 
      parent: Cell::new(None), 
      children: RefCell::new(Vec::new()), 
     }) 
    } 
} 

struct Node<'a, T: 'a> { 
    data: T, 
    tree: &'a Tree<'a, T>, 
    parent: Cell<Option<&'a Node<'a, T>>>, 
    children: RefCell<Vec<&'a Node<'a, T>>>, 
} 

impl<'a, T> Node<'a, T> { 
    fn add_node(&'a self, data: T) -> &'a Node<'a, T> { 
     let child = self.tree.new_node(data); 
     child.parent.set(Some(self)); 
     self.children.borrow_mut().push(child); 
     child 
    } 
} 

impl<'a, T> fmt::Debug for Node<'a, T> 
where 
    T: fmt::Debug, 
{ 
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 
     write!(f, "{:?}", self.data)?; 
     write!(f, " (")?; 
     for c in self.children.borrow().iter() { 
      write!(f, "{:?}, ", c)?; 
     } 
     write!(f, ")") 
    } 
} 

fn main() { 
    let tree = Tree::new(); 
    let head = tree.new_node(1); 
    let left = head.add_node(2); 
    let right = head.add_node(3); 

    println!("{:?}", head); // 1 (2(), 3(),) 
}