aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/components/main/css/matching.rs2
-rw-r--r--src/components/main/layout/aux.rs2
-rw-r--r--src/components/main/layout/block.rs2
-rw-r--r--src/components/main/layout/box_builder.rs2
-rw-r--r--src/components/main/layout/float.rs2
-rw-r--r--src/components/main/layout/flow.rs86
-rw-r--r--src/components/main/layout/inline.rs2
-rw-r--r--src/components/main/layout/layout_task.rs2
-rw-r--r--src/components/script/dom/document.rs2
-rw-r--r--src/components/script/dom/htmldocument.rs2
-rw-r--r--src/components/script/dom/node.rs48
-rw-r--r--src/components/script/html/hubbub_html_parser.rs2
-rw-r--r--src/components/util/tree.rs331
13 files changed, 287 insertions, 198 deletions
diff --git a/src/components/main/css/matching.rs b/src/components/main/css/matching.rs
index b1712d286eb..fedc0c856fd 100644
--- a/src/components/main/css/matching.rs
+++ b/src/components/main/css/matching.rs
@@ -11,7 +11,7 @@ use layout::incremental;
use script::dom::node::{AbstractNode, LayoutView};
use newcss::complete::CompleteSelectResults;
use newcss::select::{SelectCtx, SelectResults};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
pub trait MatchMethods {
fn restyle_subtree(&self, select_ctx: &SelectCtx);
diff --git a/src/components/main/layout/aux.rs b/src/components/main/layout/aux.rs
index d63df74c53d..459106e3b39 100644
--- a/src/components/main/layout/aux.rs
+++ b/src/components/main/layout/aux.rs
@@ -9,7 +9,7 @@ use layout::incremental::RestyleDamage;
use newcss::complete::CompleteSelectResults;
use script::dom::node::{AbstractNode, LayoutView};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
/// Data that layout associates with a node.
pub struct LayoutData {
diff --git a/src/components/main/layout/block.rs b/src/components/main/layout/block.rs
index e78bc87f158..ef191d4697a 100644
--- a/src/components/main/layout/block.rs
+++ b/src/components/main/layout/block.rs
@@ -18,7 +18,7 @@ use geom::rect::Rect;
use gfx::display_list::DisplayList;
use gfx::geometry::Au;
use gfx::geometry;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
pub struct BlockFlowData {
/// Data common to all flows.
diff --git a/src/components/main/layout/box_builder.rs b/src/components/main/layout/box_builder.rs
index 5ea78c8a0fe..b49c368833d 100644
--- a/src/components/main/layout/box_builder.rs
+++ b/src/components/main/layout/box_builder.rs
@@ -30,7 +30,7 @@ use script::dom::element::*;
use script::dom::node::{AbstractNode, CommentNodeTypeId, DoctypeNodeTypeId};
use script::dom::node::{ElementNodeTypeId, LayoutView, TextNodeTypeId};
use servo_util::range::Range;
-use servo_util::tree::{TreeNodeRef, TreeNode, TreeUtils};
+use servo_util::tree::{TreeNodeRef, TreeNode};
pub struct LayoutTreeBuilder {
root_flow: Option<FlowContext>,
diff --git a/src/components/main/layout/float.rs b/src/components/main/layout/float.rs
index 2a2758d4aab..64d0c1c5cd3 100644
--- a/src/components/main/layout/float.rs
+++ b/src/components/main/layout/float.rs
@@ -15,7 +15,7 @@ use geom::rect::Rect;
use gfx::display_list::DisplayList;
use gfx::geometry::Au;
use gfx::geometry;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
pub struct FloatFlowData {
/// Data common to all flows.
diff --git a/src/components/main/layout/flow.rs b/src/components/main/layout/flow.rs
index 6dc7e9409dc..1da6655ef70 100644
--- a/src/components/main/layout/flow.rs
+++ b/src/components/main/layout/flow.rs
@@ -43,7 +43,7 @@ use geom::rect::Rect;
use gfx::display_list::DisplayList;
use gfx::geometry::Au;
use script::dom::node::{AbstractNode, LayoutView};
-use servo_util::tree::{TreeNode, TreeNodeRef, TreeUtils};
+use servo_util::tree::{TreeNode, TreeNodeRef};
/// The type of the formatting context and data specific to each context, such as line box
/// structures or float lists.
@@ -164,8 +164,50 @@ impl TreeNodeRef<FlowData> for FlowContext {
TableFlow(info) => callback(info),
}
}
+
+ fn parent_node(node: &FlowData) -> Option<FlowContext> {
+ node.parent
+ }
+
+ fn first_child(node: &FlowData) -> Option<FlowContext> {
+ node.first_child
+ }
+
+ fn last_child(node: &FlowData) -> Option<FlowContext> {
+ node.last_child
+ }
+
+ fn prev_sibling(node: &FlowData) -> Option<FlowContext> {
+ node.prev_sibling
+ }
+
+ fn next_sibling(node: &FlowData) -> Option<FlowContext> {
+ node.next_sibling
+ }
+
+ fn set_parent_node(node: &mut FlowData, new_parent_node: Option<FlowContext>) {
+ node.parent = new_parent_node
+ }
+
+ fn set_first_child(node: &mut FlowData, new_first_child: Option<FlowContext>) {
+ node.first_child = new_first_child
+ }
+
+ fn set_last_child(node: &mut FlowData, new_last_child: Option<FlowContext>) {
+ node.last_child = new_last_child
+ }
+
+ fn set_prev_sibling(node: &mut FlowData, new_prev_sibling: Option<FlowContext>) {
+ node.prev_sibling = new_prev_sibling
+ }
+
+ fn set_next_sibling(node: &mut FlowData, new_next_sibling: Option<FlowContext>) {
+ node.next_sibling = new_next_sibling
+ }
}
+impl TreeNode<FlowContext> for FlowData { }
+
/// Data common to all flows.
///
/// FIXME: We need a naming convention for pseudo-inheritance like this. How about
@@ -196,48 +238,6 @@ pub struct FlowData {
is_inorder: bool,
}
-impl TreeNode<FlowContext> for FlowData {
- fn parent_node(&self) -> Option<FlowContext> {
- self.parent
- }
-
- fn first_child(&self) -> Option<FlowContext> {
- self.first_child
- }
-
- fn last_child(&self) -> Option<FlowContext> {
- self.last_child
- }
-
- fn prev_sibling(&self) -> Option<FlowContext> {
- self.prev_sibling
- }
-
- fn next_sibling(&self) -> Option<FlowContext> {
- self.next_sibling
- }
-
- fn set_parent_node(&mut self, new_parent_node: Option<FlowContext>) {
- self.parent = new_parent_node
- }
-
- fn set_first_child(&mut self, new_first_child: Option<FlowContext>) {
- self.first_child = new_first_child
- }
-
- fn set_last_child(&mut self, new_last_child: Option<FlowContext>) {
- self.last_child = new_last_child
- }
-
- fn set_prev_sibling(&mut self, new_prev_sibling: Option<FlowContext>) {
- self.prev_sibling = new_prev_sibling
- }
-
- fn set_next_sibling(&mut self, new_next_sibling: Option<FlowContext>) {
- self.next_sibling = new_next_sibling
- }
-}
-
pub struct BoxIterator {
priv boxes: ~[RenderBox],
priv index: uint,
diff --git a/src/components/main/layout/inline.rs b/src/components/main/layout/inline.rs
index 3a4f8122dfe..d6a6c5dc2a2 100644
--- a/src/components/main/layout/inline.rs
+++ b/src/components/main/layout/inline.rs
@@ -21,7 +21,7 @@ use newcss::values::{CSSTextAlignLeft, CSSTextAlignCenter, CSSTextAlignRight, CS
use newcss::units::{Em, Px, Pt};
use newcss::values::{CSSLineHeightNormal, CSSLineHeightNumber, CSSLineHeightLength, CSSLineHeightPercentage};
use servo_util::range::Range;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
use extra::container::Deque;
use extra::ringbuf::RingBuf;
diff --git a/src/components/main/layout/layout_task.rs b/src/components/main/layout/layout_task.rs
index 73f9e5c9556..c107d6a3e3f 100644
--- a/src/components/main/layout/layout_task.rs
+++ b/src/components/main/layout/layout_task.rs
@@ -41,7 +41,7 @@ use script::script_task::{ReflowCompleteMsg, ScriptChan, SendEventMsg};
use servo_msg::constellation_msg::{ConstellationChan, PipelineId};
use servo_net::image_cache_task::{ImageCacheTask, ImageResponseMsg};
use servo_net::local_image_cache::LocalImageCache;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
use servo_util::time::{ProfilerChan, profile};
use servo_util::time;
use extra::url::Url;
diff --git a/src/components/script/dom/document.rs b/src/components/script/dom/document.rs
index 043eec3646a..5ba1b10a90d 100644
--- a/src/components/script/dom/document.rs
+++ b/src/components/script/dom/document.rs
@@ -18,7 +18,7 @@ use dom::htmltitleelement::HTMLTitleElement;
use js::jsapi::{JS_AddObjectRoot, JS_RemoveObjectRoot, JSObject, JSContext, JSVal};
use js::glue::RUST_OBJECT_TO_JSVAL;
-use servo_util::tree::{TreeNodeRef, TreeUtils};
+use servo_util::tree::TreeNodeRef;
use std::cast;
use std::ptr;
diff --git a/src/components/script/dom/htmldocument.rs b/src/components/script/dom/htmldocument.rs
index 52c15fc36cf..b839f0c4960 100644
--- a/src/components/script/dom/htmldocument.rs
+++ b/src/components/script/dom/htmldocument.rs
@@ -13,7 +13,7 @@ use dom::window::Window;
use js::jsapi::{JSObject, JSContext};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
use std::libc;
use std::ptr;
diff --git a/src/components/script/dom/node.rs b/src/components/script/dom/node.rs
index bee3dac63d7..1f53bb2ac09 100644
--- a/src/components/script/dom/node.rs
+++ b/src/components/script/dom/node.rs
@@ -24,7 +24,7 @@ use std::uint;
use js::jsapi::{JSObject, JSContext};
use js::rust::Compartment;
use netsurfcss::util::VoidPtrLike;
-use servo_util::tree::{TreeNode, TreeNodeRef, TreeUtils};
+use servo_util::tree::{TreeNode, TreeNodeRef};
//
// The basic Node structure
@@ -177,41 +177,39 @@ impl<View> Clone for AbstractNode<View> {
}
}
-impl<View> TreeNode<AbstractNode<View>> for Node<View> {
- fn parent_node(&self) -> Option<AbstractNode<View>> {
- self.parent_node
+impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
+ fn parent_node(node: &Node<View>) -> Option<AbstractNode<View>> {
+ node.parent_node
}
- fn first_child(&self) -> Option<AbstractNode<View>> {
- self.first_child
+ fn first_child(node: &Node<View>) -> Option<AbstractNode<View>> {
+ node.first_child
}
- fn last_child(&self) -> Option<AbstractNode<View>> {
- self.last_child
+ fn last_child(node: &Node<View>) -> Option<AbstractNode<View>> {
+ node.last_child
}
- fn prev_sibling(&self) -> Option<AbstractNode<View>> {
- self.prev_sibling
+ fn prev_sibling(node: &Node<View>) -> Option<AbstractNode<View>> {
+ node.prev_sibling
}
- fn next_sibling(&self) -> Option<AbstractNode<View>> {
- self.next_sibling
+ fn next_sibling(node: &Node<View>) -> Option<AbstractNode<View>> {
+ node.next_sibling
}
- fn set_parent_node(&mut self, new_parent_node: Option<AbstractNode<View>>) {
- self.parent_node = new_parent_node
+ fn set_parent_node(node: &mut Node<View>, new_parent_node: Option<AbstractNode<View>>) {
+ node.parent_node = new_parent_node
}
- fn set_first_child(&mut self, new_first_child: Option<AbstractNode<View>>) {
- self.first_child = new_first_child
+ fn set_first_child(node: &mut Node<View>, new_first_child: Option<AbstractNode<View>>) {
+ node.first_child = new_first_child
}
- fn set_last_child(&mut self, new_last_child: Option<AbstractNode<View>>) {
- self.last_child = new_last_child
+ fn set_last_child(node: &mut Node<View>, new_last_child: Option<AbstractNode<View>>) {
+ node.last_child = new_last_child
}
- fn set_prev_sibling(&mut self, new_prev_sibling: Option<AbstractNode<View>>) {
- self.prev_sibling = new_prev_sibling
+ fn set_prev_sibling(node: &mut Node<View>, new_prev_sibling: Option<AbstractNode<View>>) {
+ node.prev_sibling = new_prev_sibling
}
- fn set_next_sibling(&mut self, new_next_sibling: Option<AbstractNode<View>>) {
- self.next_sibling = new_next_sibling
+ fn set_next_sibling(node: &mut Node<View>, new_next_sibling: Option<AbstractNode<View>>) {
+ node.next_sibling = new_next_sibling
}
-}
-impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
// FIXME: The duplication between `with_base` and `with_mut_base` is ugly.
fn with_base<R>(&self, callback: &fn(&Node<View>) -> R) -> R {
self.transmute(callback)
@@ -222,6 +220,8 @@ impl<View> TreeNodeRef<Node<View>> for AbstractNode<View> {
}
}
+impl<View> TreeNode<AbstractNode<View>> for Node<View> { }
+
impl<'self, View> AbstractNode<View> {
// Unsafe accessors
diff --git a/src/components/script/html/hubbub_html_parser.rs b/src/components/script/html/hubbub_html_parser.rs
index 2409d4c0a6a..005f6d6dbbd 100644
--- a/src/components/script/html/hubbub_html_parser.rs
+++ b/src/components/script/html/hubbub_html_parser.rs
@@ -63,7 +63,7 @@ use servo_msg::constellation_msg::SubpageId;
use servo_net::image_cache_task::ImageCacheTask;
use servo_net::image_cache_task;
use servo_net::resource_task::{Done, Load, Payload, ResourceTask};
-use servo_util::tree::TreeUtils;
+use servo_util::tree::TreeNodeRef;
use servo_util::url::make_url;
use extra::url::Url;
use extra::future::{Future, from_port};
diff --git a/src/components/util/tree.rs b/src/components/util/tree.rs
index eebf91fa10f..3b4aba07cc5 100644
--- a/src/components/util/tree.rs
+++ b/src/components/util/tree.rs
@@ -4,204 +4,293 @@
//! Helper functions for garbage collected doubly-linked trees.
-/// The basic trait. This function is meant to encapsulate a clonable reference to a tree node.
-pub trait TreeNodeRef<N> : Clone {
+// Macros to make add_child etc. less painful to write.
+// Code outside this module should instead implement TreeNode
+// and use its default methods.
+priv macro_rules! get(
+ ($node:expr, $fun:ident) => (
+ TreeNodeRef::$fun::<Node,Self>($node)
+ )
+)
+
+priv macro_rules! set(
+ ($node:expr, $fun:ident, $val:expr) => (
+ TreeNodeRef::$fun::<Node,Self>($node, $val)
+ )
+)
+
+pub struct ChildIterator<Ref> {
+ priv current: Option<Ref>,
+}
+
+impl<Node, Ref: TreeNodeRef<Node>> Iterator<Ref> for ChildIterator<Ref> {
+ fn next(&mut self) -> Option<Ref> {
+ if self.current.is_none() {
+ return None;
+ }
+
+ // FIXME: Do we need two clones here?
+ let x = self.current.get_ref().clone();
+ self.current = x.with_base(|n| TreeNodeRef::next_sibling::<Node, Ref>(n));
+ Some(x.clone())
+ }
+}
+
+// FIXME: Do this without precomputing a vector of refs.
+// Easy for preorder; harder for postorder.
+pub struct TreeIterator<Ref> {
+ priv nodes: ~[Ref],
+ priv index: uint,
+}
+
+impl<Ref> TreeIterator<Ref> {
+ priv fn new(nodes: ~[Ref]) -> TreeIterator<Ref> {
+ TreeIterator {
+ nodes: nodes,
+ index: 0,
+ }
+ }
+}
+
+impl<Ref: Clone> Iterator<Ref> for TreeIterator<Ref> {
+ fn next(&mut self) -> Option<Ref> {
+ if self.index >= self.nodes.len() {
+ None
+ } else {
+ let v = self.nodes[self.index].clone();
+ self.index += 1;
+ Some(v)
+ }
+ }
+}
+
+/// A type implementing TreeNodeRef<Node> is a clonable reference to an underlying
+/// node type Node.
+///
+/// We have to define both ref and node operations in the same trait, which makes
+/// the latter more annoying to call (as static methods). But we provide non-static
+/// proxies in trait TreeNode below.
+pub trait TreeNodeRef<Node>: Clone {
+
+ // Fundamental operations on refs.
+
/// Borrows this node as immutable.
- fn with_base<R>(&self, callback: &fn(&N) -> R) -> R;
+ fn with_base<R>(&self, callback: &fn(&Node) -> R) -> R;
/// Borrows this node as mutable.
- fn with_mut_base<R>(&self, callback: &fn(&mut N) -> R) -> R;
-}
+ fn with_mut_base<R>(&self, callback: &fn(&mut Node) -> R) -> R;
+
+
+ // Fundamental operations on nodes.
-/// The contents of a tree node.
-pub trait TreeNode<NR> {
/// Returns the parent of this node.
- fn parent_node(&self) -> Option<NR>;
+ fn parent_node(node: &Node) -> Option<Self>;
/// Returns the first child of this node.
- fn first_child(&self) -> Option<NR>;
+ fn first_child(node: &Node) -> Option<Self>;
/// Returns the last child of this node.
- fn last_child(&self) -> Option<NR>;
+ fn last_child(node: &Node) -> Option<Self>;
/// Returns the previous sibling of this node.
- fn prev_sibling(&self) -> Option<NR>;
+ fn prev_sibling(node: &Node) -> Option<Self>;
/// Returns the next sibling of this node.
- fn next_sibling(&self) -> Option<NR>;
+ fn next_sibling(node: &Node) -> Option<Self>;
/// Sets the parent of this node.
- fn set_parent_node(&mut self, new_parent: Option<NR>);
+ fn set_parent_node(node: &mut Node, new_parent: Option<Self>);
/// Sets the first child of this node.
- fn set_first_child(&mut self, new_first_child: Option<NR>);
+ fn set_first_child(node: &mut Node, new_first_child: Option<Self>);
/// Sets the last child of this node.
- fn set_last_child(&mut self, new_last_child: Option<NR>);
+ fn set_last_child(node: &mut Node, new_last_child: Option<Self>);
/// Sets the previous sibling of this node.
- fn set_prev_sibling(&mut self, new_prev_sibling: Option<NR>);
+ fn set_prev_sibling(node: &mut Node, new_prev_sibling: Option<Self>);
/// Sets the next sibling of this node.
- fn set_next_sibling(&mut self, new_next_sibling: Option<NR>);
-}
-
-/// A set of helper functions useful for operating on trees.
-pub trait TreeUtils {
- /// Returns true if this node is disconnected from the tree or has no children.
- fn is_leaf(&self) -> bool;
-
- /// Adds a new child to the end of this node's list of children.
- ///
- /// Fails unless `new_child` is disconnected from the tree.
- fn add_child(&self, new_child: Self);
-
- /// Removes the given child from this node's list of children.
- ///
- /// Fails unless `child` is a child of this node. (FIXME: This is not yet checked.)
- fn remove_child(&self, child: Self);
-
- /// Iterates over all children of this node.
- fn each_child(&self, callback: &fn(Self) -> bool) -> bool;
-
- /// Iterates over this node and all its descendants, in preorder.
- fn traverse_preorder(&self, callback: &fn(Self) -> bool) -> bool;
+ fn set_next_sibling(node: &mut Node, new_next_sibling: Option<Self>);
- /// Iterates over this node and all its descendants, in postorder.
- fn traverse_postorder(&self, callback: &fn(Self) -> bool) -> bool;
- /// Like traverse_preorder but calls 'prune' first on each node. If it returns true then we
- /// skip the whole subtree but continue iterating.
- ///
- /// 'prune' is a separate function a) for compatibility with the 'for' protocol,
- /// b) so that the postorder version can still prune before traversing.
- fn traverse_preorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
+ // The tree utilities, operating on refs mostly.
- /// Like traverse_postorder but calls 'prune' first on each node. If it returns true then we
- /// skip the whole subtree but continue iterating.
- ///
- /// NB: 'prune' is called *before* traversing children, even though this is a
- /// postorder traversal.
- fn traverse_postorder_prune(&self, prune: &fn(&Self) -> bool, callback: &fn(Self) -> bool) -> bool;
-}
-
-impl<NR:TreeNodeRef<N>,N:TreeNode<NR>> TreeUtils for NR {
+ /// Returns true if this node is disconnected from the tree or has no children.
fn is_leaf(&self) -> bool {
do self.with_base |this_node| {
- this_node.first_child().is_none()
+ (get!(this_node, first_child)).is_none()
}
}
- fn add_child(&self, new_child: NR) {
+ /// Adds a new child to the end of this node's list of children.
+ ///
+ /// Fails unless `new_child` is disconnected from the tree.
+ fn add_child(&self, new_child: Self) {
do self.with_mut_base |this_node| {
do new_child.with_mut_base |new_child_node| {
- assert!(new_child_node.parent_node().is_none());
- assert!(new_child_node.prev_sibling().is_none());
- assert!(new_child_node.next_sibling().is_none());
+ assert!((get!(new_child_node, parent_node)).is_none());
+ assert!((get!(new_child_node, prev_sibling)).is_none());
+ assert!((get!(new_child_node, next_sibling)).is_none());
- match this_node.last_child() {
- None => this_node.set_first_child(Some(new_child.clone())),
+ match get!(this_node, last_child) {
+ None => set!(this_node, set_first_child, Some(new_child.clone())),
Some(last_child) => {
do last_child.with_mut_base |last_child_node| {
- assert!(last_child_node.next_sibling().is_none());
- last_child_node.set_next_sibling(Some(new_child.clone()));
- new_child_node.set_prev_sibling(Some(last_child.clone()));
+ assert!((get!(last_child_node, next_sibling)).is_none());
+ set!(last_child_node, set_next_sibling, Some(new_child.clone()));
+ set!(new_child_node, set_prev_sibling, Some(last_child.clone()));
}
}
}
- this_node.set_last_child(Some(new_child.clone()));
- new_child_node.set_parent_node(Some((*self).clone()));
+ set!(this_node, set_last_child, Some(new_child.clone()));
+ set!(new_child_node, set_parent_node, Some((*self).clone()));
}
}
}
- fn remove_child(&self, child: NR) {
+ /// Removes the given child from this node's list of children.
+ ///
+ /// Fails unless `child` is a child of this node. (FIXME: This is not yet checked.)
+ fn remove_child(&self, child: Self) {
do self.with_mut_base |this_node| {
do child.with_mut_base |child_node| {
- assert!(child_node.parent_node().is_some());
+ assert!((get!(child_node, parent_node)).is_some());
- match child_node.prev_sibling() {
- None => this_node.set_first_child(child_node.next_sibling()),
+ match get!(child_node, prev_sibling) {
+ None => set!(this_node, set_first_child, get!(child_node, next_sibling)),
Some(prev_sibling) => {
do prev_sibling.with_mut_base |prev_sibling_node| {
- prev_sibling_node.set_next_sibling(child_node.next_sibling());
+ set!(prev_sibling_node, set_next_sibling, get!(child_node, next_sibling));
}
}
}
- match child_node.next_sibling() {
- None => this_node.set_last_child(child_node.prev_sibling()),
+ match get!(child_node, next_sibling) {
+ None => set!(this_node, set_last_child, get!(child_node, prev_sibling)),
Some(next_sibling) => {
do next_sibling.with_mut_base |next_sibling_node| {
- next_sibling_node.set_prev_sibling(child_node.prev_sibling());
+ set!(next_sibling_node, set_prev_sibling, get!(child_node, prev_sibling));
}
}
}
- child_node.set_prev_sibling(None);
- child_node.set_next_sibling(None);
- child_node.set_parent_node(None);
+ set!(child_node, set_prev_sibling, None);
+ set!(child_node, set_next_sibling, None);
+ set!(child_node, set_parent_node, None);
}
}
}
- fn each_child(&self, callback: &fn(NR) -> bool) -> bool {
- let mut maybe_current = self.with_base(|n| n.first_child());
- while !maybe_current.is_none() {
- let current = maybe_current.get_ref().clone();
- if !callback(current.clone()) {
- break;
- }
-
- maybe_current = current.with_base(|n| n.next_sibling());
+ /// Iterates over all children of this node.
+ fn children(&self) -> ChildIterator<Self> {
+ ChildIterator {
+ current: self.with_base(|n| get!(n, first_child)),
}
+ }
- true
+ /// Iterates over this node and all its descendants, in preorder.
+ fn traverse_preorder(&self) -> TreeIterator<Self> {
+ self.traverse_preorder_prune(|_| false)
}
- fn traverse_preorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
- // prune shouldn't mutate, so don't clone
- if prune(self) {
- return true;
- }
+ /// Iterates over this node and all its descendants, in postorder.
+ fn traverse_postorder(&self) -> TreeIterator<Self> {
+ self.traverse_postorder_prune(|_| false)
+ }
- if !callback((*self).clone()) {
- return false;
- }
+ /// Like traverse_preorder but calls 'prune' first on each node. If it returns true then we
+ /// skip the whole subtree but continue iterating.
+ fn traverse_preorder_prune(&self, prune: &fn(&Self) -> bool) -> TreeIterator<Self> {
+ let mut nodes = ~[];
+ gather(self, &mut nodes, false, prune);
+ TreeIterator::new(nodes)
+ }
- for self.each_child |kid| {
- // FIXME: Work around rust#2202. We should be able to pass the callback directly.
- if !kid.traverse_preorder_prune(|a| prune(a), |a| callback(a)) {
- return false;
- }
- }
+ /// Like traverse_postorder but calls 'prune' first on each node. If it returns true then we
+ /// skip the whole subtree but continue iterating.
+ ///
+ /// NB: 'prune' is called *before* traversing children, even though this is a
+ /// postorder traversal.
+ fn traverse_postorder_prune(&self, prune: &fn(&Self) -> bool) -> TreeIterator<Self> {
+ let mut nodes = ~[];
+ gather(self, &mut nodes, true, prune);
+ TreeIterator::new(nodes)
+ }
+}
- true
+priv fn gather<Node, Ref: TreeNodeRef<Node>>(cur: &Ref, refs: &mut ~[Ref],
+ postorder: bool, prune: &fn(&Ref) -> bool) {
+ // prune shouldn't mutate, so don't clone
+ if prune(cur) {
+ return;
}
- fn traverse_postorder_prune(&self, prune: &fn(&NR) -> bool, callback: &fn(NR) -> bool) -> bool {
- // prune shouldn't mutate, so don't clone
- if prune(self) {
- return true;
- }
+ if !postorder {
+ refs.push(cur.clone());
+ }
+ for kid in cur.children() {
+ // FIXME: Work around rust#2202. We should be able to pass the callback directly.
+ gather(&kid, refs, postorder, |a| prune(a))
+ }
+ if postorder {
+ refs.push(cur.clone());
+ }
+}
- for self.each_child |kid| {
- // FIXME: Work around rust#2202. We should be able to pass the callback directly.
- if !kid.traverse_postorder_prune(|a| prune(a), |a| callback(a)) {
- return false;
- }
- }
- callback((*self).clone())
+/// Access the fields of a node without a static TreeNodeRef method call.
+/// If you make an impl TreeNodeRef<Node> for Ref then you should also make
+/// impl TreeNode<Ref> for Node with an empty body.
+pub trait TreeNode<Ref: TreeNodeRef<Self>> {
+ /// Returns the parent of this node.
+ fn parent_node(&self) -> Option<Ref> {
+ TreeNodeRef::parent_node::<Self,Ref>(self)
}
- fn traverse_preorder(&self, callback: &fn(NR) -> bool) -> bool {
- self.traverse_preorder_prune(|_| false, callback)
+ /// Returns the first child of this node.
+ fn first_child(&self) -> Option<Ref> {
+ TreeNodeRef::first_child::<Self,Ref>(self)
}
- fn traverse_postorder(&self, callback: &fn(NR) -> bool) -> bool {
- self.traverse_postorder_prune(|_| false, callback)
+ /// Returns the last child of this node.
+ fn last_child(&self) -> Option<Ref> {
+ TreeNodeRef::last_child::<Self,Ref>(self)
+ }
+
+ /// Returns the previous sibling of this node.
+ fn prev_sibling(&self) -> Option<Ref> {
+ TreeNodeRef::prev_sibling::<Self,Ref>(self)
}
-}
+ /// Returns the next sibling of this node.
+ fn next_sibling(&self) -> Option<Ref> {
+ TreeNodeRef::next_sibling::<Self,Ref>(self)
+ }
+
+ /// Sets the parent of this node.
+ fn set_parent_node(&mut self, new_parent: Option<Ref>) {
+ TreeNodeRef::set_parent_node::<Self,Ref>(self, new_parent)
+ }
+
+ /// Sets the first child of this node.
+ fn set_first_child(&mut self, new_first_child: Option<Ref>) {
+ TreeNodeRef::set_first_child::<Self,Ref>(self, new_first_child)
+ }
+
+ /// Sets the last child of this node.
+ fn set_last_child(&mut self, new_last_child: Option<Ref>) {
+ TreeNodeRef::set_last_child::<Self,Ref>(self, new_last_child)
+ }
+
+ /// Sets the previous sibling of this node.
+ fn set_prev_sibling(&mut self, new_prev_sibling: Option<Ref>) {
+ TreeNodeRef::set_prev_sibling::<Self,Ref>(self, new_prev_sibling)
+ }
+
+ /// Sets the next sibling of this node.
+ fn set_next_sibling(&mut self, new_next_sibling: Option<Ref>) {
+ TreeNodeRef::set_next_sibling::<Self,Ref>(self, new_next_sibling)
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-04 14:52:31 +0000