<commit_before>use geometry::Point;
use geometry::Rect;
use geometry::Size;

/**
 Elements that may be contained by a quadtree node.
 Either child nodes, a single rect, or nothing.
 */
enum Elements {
    /// Children are top left, top right, bottom right, and bottom left, respectively.
    Children(~QuadTree, ~QuadTree, ~QuadTree, ~QuadTree),
    /// A single rectangle.
    Member(Rect),
    /// Nothing.
    NoElements,
}

/**
 A quadtree node that can contain either one rectangle,
 or exactly four child nodes.
 */
pub struct QuadTree {
    rect: Rect,
    elements: Elements,
}

impl QuadTree {
    /**
     Create an empty quadtree with a zero-sized root node.
     */
    pub fn new() -> QuadTree {
        let origin = Point { x: 0 as f32, y: 0 as f32 };
        let size = Size { width: 0 as f32, height: 0 as f32 };
        let nodeRect = Rect { origin: origin, size: size };
        let node = QuadTree { rect: nodeRect, elements: NoElements };

        node
    }

    /**
     Create a quadtree with a root node with the same origin and a square
     size with side length matching the longer dimension of `rect`.
     */
    pub fn newAutosized(rect: Rect) -> QuadTree {
        let largerDimen = if rect.size.width > rect.size.height {
            rect.size.width
        } else {
            rect.size.height
        };

        let square = Rect { origin: rect.origin, size: Size { width: largerDimen, height: largerDimen } };

        QuadTree { rect: square, elements: Member(rect), }
    }

    /**
     Create a quadtree with a root node with the given origin, size, and member rectangle.
     If `insertRect` is not entirely contained within the rectangle defined by `origin` and `size`,
     higher level nodes will be created to form a quadtree with a child of the rect specified
     and other children such that the rect is in the tree.
     */
    pub fn newWithSize(origin: Point, size: Size, insertRect: Rect) -> QuadTree {
        let nodeRect = Rect { origin: origin, size: size };
        let node = QuadTree { rect: nodeRect, elements: NoElements };

        let (success, tree) = node.insertRect(insertRect);

        assert!(success, "Failed inserting a node into an empty quadtree.");

        tree
    }

    /**
     Insert a rectangle into the quadtree. If `toInsert` overlaps another rectangle
     already in the tree, the return value will be (false, self). 
     If the root node is zero-sized, the resulting tree will have a square root node
     large enough to hold `toInsert`.
     */
    pub fn insertRect(self, toInsert: Rect) -> (bool, QuadTree) {
        if self.rect.size.width == 0.0 {
            return (true, QuadTree::newAutosized(toInsert))
        }

        fail!("insertRect not implemented for non-zero sized trees!");

        (false, self)
    }

    /**
     Find all of the rects in `self`, or its children, that are in nodes
     intersected by the given rect.
     */<commit_msg>Allow creating a quadtree with a size but without a rectangle.<commit_after>use geometry::Point;
use geometry::Rect;
use geometry::Size;

/**
 Elements that may be contained by a quadtree node.
 Either child nodes, a single rect, or nothing.
 */
enum Elements {
    /// Children are top left, top right, bottom right, and bottom left, respectively.
    Children(~QuadTree, ~QuadTree, ~QuadTree, ~QuadTree),
    /// A single rectangle.
    Member(Rect),
    /// Nothing.
    NoElements,
}

/**
 A quadtree node that can contain either one rectangle,
 or exactly four child nodes.
 */
pub struct QuadTree {
    rect: Rect,
    elements: Elements,
}

impl QuadTree {
    /**
     Create an empty quadtree with a zero-sized root node.
     */
    pub fn new() -> QuadTree {
        let origin = Point { x: 0 as f32, y: 0 as f32 };
        let size = Size { width: 0 as f32, height: 0 as f32 };
        let nodeRect = Rect { origin: origin, size: size };
        let node = QuadTree { rect: nodeRect, elements: NoElements };

        node
    }

    /**
     Create a quadtree with a root node with the same origin and a square
     size with side length matching the longer dimension of `rect`.
     */
    pub fn newAutosized(rect: Rect) -> QuadTree {
        let largerDimen = if rect.size.width > rect.size.height {
            rect.size.width
        } else {
            rect.size.height
        };

        let square = Rect { origin: rect.origin, size: Size { width: largerDimen, height: largerDimen } };

        QuadTree { rect: square, elements: Member(rect), }
    }

    /**
     Create a quadtree with a root node with the given origin, size, and member rectangle.
     If `insertRect` is not entirely contained within the rectangle defined by `origin` and `size`,
     higher level nodes will be created to form a quadtree with a child of the rect specified
     and other children such that the rect is in the tree.
     */
    pub fn newWithSize(origin: Point, size: Size, insertRect: Option<Rect>) -> QuadTree {
        let nodeRect = Rect { origin: origin, size: size };
        let node = QuadTree { rect: nodeRect, elements: NoElements };

        let tree = 
        match insertRect {
            Some(rect) => {
                let (success, tree) = node.insertRect(rect);
                assert!(success, "Failed inserting a node into an empty quadtree.");

                tree
            }
            None => node,
        };

        tree
    }

    /**
     Insert a rectangle into the quadtree. If `toInsert` overlaps another rectangle
     already in the tree, the return value will be (false, self). 
     If the root node is zero-sized, the resulting tree will have a square root node
     large enough to hold `toInsert`.
     */
    pub fn insertRect(self, toInsert: Rect) -> (bool, QuadTree) {
        if self.rect.size.width == 0.0 {
            return (true, QuadTree::newAutosized(toInsert))
        }

        fail!("insertRect not implemented for non-zero sized trees!");

        (false, self)
    }

    /**
     Find all of the rects in `self`, or its children, that are in nodes
     intersected by the given rect.
     */
{'fraction_non_alphanumeric': 0.09453712790317305, 'fraction_numerical': 0.004579653254824992, 'mean_word_length': 2.319761129207383, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3678012', 'n_tokens_mistral': 1741, 'n_tokens_neox': 1664, 'n_words': 718}