//! Generate hatching and dotted patterns in a path.
//!
//! <svg viewBox="0 0 426.95679 426.52454" height="426.52454" width="426.95679">
//!   <path style="fill:none;stroke:#4400aaff;stroke-linecap:round;stroke-opacity:1" d="m 16.917871,135.64793 4.76841,-7.42638 m 15.72455,-24.48953 7.19236,-11.20143 m 17.03683,-26.53329 2.03357,-3.16709 m -43.99289,77.76893 8.64512,-13.46397 m 11.54821,-17.98526 10.54139,-16.41727 m 12.25127,-19.08019 7.6854,-11.96933 m -65.1770704,110.76136 3.09963,-4.8274 m 14.5495904,-22.65963 12.13142,-18.89358 m 7.38155,-11.49608 13.89046,-21.63311 m 8.03079,-12.50722 11.25737,-17.53231 M 7.4520506,178.15229 16.233711,164.47567 m 9.73405,-15.15991 15.61774,-24.32318 m 3.21489,-5.00689 17.23952,-26.84896 m 3.81033,-5.93424 14.82933,-23.0953 m 12.08295,-18.81808 6.19302,-9.64507 m -87.78445,145.97029 12.86975,-20.04347 m 5.07048,-7.89678 56.732,-88.35488 M 93.067691,54.06792 103.88779,37.21663 M 14.890111,185.07637 108.48646,39.30868 m -106.9825894,175.8696 6.1426,-9.56656 M 18.609141,188.53841 113.08513,41.40074 M 4.8823606,219.17067 17.503941,199.51369 m 4.53224,-7.05853 95.647629,-148.96235 m 9.54351,-14.86313 7.69031,-11.97696 M 9.1329106,221.80491 124.10857,42.74089 m 1.10584,-1.72223 14.34702,-22.34415 M 13.383461,224.43915 49.891941,167.58057 M 59.162251,153.14292 143.62441,21.60089 M 17.634011,227.07339 52.435581,172.87314 M 65.108631,153.13604 147.68737,24.52727 M 5.4365906,255.32381 13.562901,242.66784 m 8.07471,-12.57562 34.65211,-53.96748 m 13.40238,-20.87295 8.31907,-12.95619 M 97.266581,112.30708 151.75033,27.45366 M 8.8376206,259.2811 61.260551,177.63723 m 11.90917,-18.54743 7.56957,-11.78894 M 113.60671,96.1129 156.45597,29.37913 m 7.69973,-11.9916 7.9425,-12.3697198 M 13.629031,261.07299 l 54.43399,-84.7759 m 6.63851,-10.33888 8.7659,-13.65207 M 125.66903,86.58105 177.17848,6.3598202 M 18.420461,262.86487 58.610571,200.27248 m 4.44395,-6.92105 23.14103,-36.04003 M 136.10735,79.57838 180.77656,10.01022 M 23.211891,264.65676 58.097511,210.32561 m 13.26663,-20.66157 17.55955,-27.34736 M 145.72273,73.85741 184.29598,13.78314 M 28.003291,266.44865 58.350681,219.18539 m 21.32309,-33.20874 11.97804,-18.65471 m 62.669079,-97.60129 33.4945,-52.1646 M 16.948341,292.91978 58.873831,227.6247 m 29.62346,-46.13579 3.92546,-6.11354 M 162.58722,66.10066 191.33481,21.32896 m -171.353389,276.12116 39.88577,-62.1184 m 50.933989,-79.32498 0.21438,-0.33389 M 170.32891,63.2978 209.29553,2.6108702 M 25.045171,298.81787 61.144811,242.59601 m 47.736709,-74.3455 3.02247,-4.70723 m 17.24689,-26.86043 3.24556,-5.05466 M 177.78227,60.94394 215.94693,1.5060002 M 30.425081,299.69324 62.757681,249.3382 m 28.96487,-45.1101 58.780339,-91.54495 M 184.78195,59.29668 219.61175,5.0524702 M 35.804981,300.56863 64.670691,255.61295 m 24.49552,-38.14951 51.312939,-79.91517 m 4.43283,-6.90372 14.95169,-23.28589 m 28.469,-44.33783 34.19392,-53.2538598 M 41.184881,301.44401 66.834971,261.49634 m 21.61322,-33.66056 41.973929,-65.37054 m 9.16543,-14.27431 5.67737,-8.84199 m 13.67266,-21.2939 10.28687,-16.02086 m 10.81567,-16.84441 0.21148,-0.32935 m 11.63179,-18.11544 8.60293,-13.39827 m 9.33176,-14.53336 15.62335,-24.33192 M 44.495111,305.54271 69.021671,267.34484 m 18.83868,-29.33949 31.051989,-48.36062 m 9.83742,-15.32086 8.32416,-12.96411 m 4.54095,-7.07212 8.43584,-13.13804 m 17.37519,-27.06025 11.15935,-17.37966 m 5.46833,-8.51642 0.95594,-1.48879 m 10.4246,-16.23535 7.61545,-11.86035 M 215.71354,38.8858 228.35627,19.19592 M 35.810801,328.3218 71.498781,272.74106 m 19.43484,-30.26797 18.545179,-28.88242 m 4.36969,-6.80537 9.34892,-14.56009 m 21.56425,-33.58433 11.89295,-18.52217 m 19.2596,-29.99505 13.55212,-21.10618 m 9.51851,-14.8242 7.93137,-12.35238 M 220.29754,41.00072 232.65892,21.74901 M 38.763911,332.9767 73.975901,278.13728 m 15.58755,-24.27619 19.548979,-30.44573 m 8.7471,-13.62281 7.77877,-12.11472 m 58.25286,-90.72345 9.43078,-14.68757 m 9.21363,-14.34938 9.36275,-14.58162 M 223.77927,44.83234 246.19634,9.9198102 M 44.088901,333.93757 76.489421,283.47678 m 11.70385,-18.22769 23.218229,-36.16026 m 9.78596,-15.24072 14.38341,-22.40083 m 52.63269,-81.97057 8.02567,-12.49923 M 206.37052,81.19893 218.72321,61.96074 M 225.24363,51.8058 255.23865,5.0913202 M 50.166661,333.7261 l 29.1109,-45.33754 m 7.8478,-12.22221 29.216639,-45.50222 m 7.51955,-11.711 18.81689,-29.30559 m 34.38877,-53.55733 20.50304,-31.9316 M 211.16916,82.97957 259.18233,8.2034702 M 56.244421,333.51462 l 25.8213,-40.21428 m 5.91775,-9.21634 18.638969,-29.02848 m 11.33638,-17.65537 14.58842,-22.72011 m 5.0953,-7.93547 9.34598,-14.55548 m 46.35021,-72.1862 2.33258,-3.63277 m 22.48888,-35.02436 43.31105,-67.45295 m -199.149059,319.41035 22.5919,-35.1848 m 6.02779,-9.38771 17.543699,-27.32271 m 18.17597,-28.30738 5.69322,-8.86667 m 12.68129,-19.74994 6.15477,-9.58548 M 232.46766,68.31727 263.65778,19.74155 M 65.946681,336.91243 88.007371,302.55492 m 5.89287,-9.17761 16.435209,-25.59631 m 21.91956,-34.13768 2.40453,-3.74485 M 244.02783,59.56746 265.84432,25.59027 M 63.181741,350.47264 91.100661,306.9915 m 5.8981,-9.18576 17.055329,-26.56209 m 22.20917,-34.58874 2.60102,-4.05085 M 249.17631,60.80325 269.54787,29.07641 M 62.078481,361.44493 94.318721,311.23375 m 5.949239,-9.26541 18.31023,-28.5165 m 21.69332,-33.78533 2.89003,-4.50095 M 254.32479,62.03905 277.74639,25.56209 M 65.783721,364.92844 97.722371,315.18695 m 5.814789,-9.056 19.56515,-30.47091 m 0.60177,-0.93721 4.03273,-6.2806 m 16.54296,-25.76413 3.22669,-5.02527 M 259.35075,63.46565 288.78948,17.61755 M 72.087211,364.36542 101.12603,319.14013 m 5.81347,-9.05394 26.01671,-40.51862 m 15.66833,-24.40198 3.59853,-5.60438 m 42.09482,-65.55879 16.14551,-25.14514 M 264.20251,65.16356 295.00926,17.18489 M 79.089411,362.71422 107.23187,318.88493 m 6.66792,-10.38466 24.34458,-37.91444 m 14.88199,-23.17733 4.05268,-6.31166 m 44.62071,-69.49265 4.09624,-6.37952 m 4.2394,-6.60247 6.55205,-10.20422 M 269.05426,66.86149 298.37928,21.19047 M 86.091621,361.063 114.12325,317.40632 m 6.73682,-10.49197 22.81133,-35.52655 m 14.32574,-22.31102 4.52698,-7.05035 m 45.67307,-71.13159 2.27191,-3.5383 m 1.09414,-1.70401 10.58327,-16.48248 M 273.80468,68.71724 299.66331,28.44479 M 91.406731,362.03931 121.01462,315.92772 m 6.69359,-10.42463 21.87593,-34.06974 m 13.36364,-20.81265 4.92143,-7.66467 m 46.36923,-72.2158 11.73478,-18.27584 M 278.3734,70.85594 300.8637,35.82938 M 93.138621,368.5961 107.29716,346.54549 m 10.22876,-15.93035 10.38009,-16.16604 m 5.89013,-9.17333 22.33654,-34.7871 m 11.93778,-18.59199 5.14384,-8.01106 m 46.43428,-72.3171 9.38564,-14.61727 m 53.90792,-83.95662 19.55403,-30.4536 M 92.798531,378.37984 110.07167,351.47851 m 13.01617,-20.27146 10.58512,-16.48536 m 5.23447,-8.1522 24.35014,-37.92309 m 9.403,-14.64431 7.18176,-11.18494 m 43.17229,-67.23686 0.93037,-1.44895 m 6.00743,-9.35603 2.14279,-3.3372 M 287.44428,75.23703 307.24821,44.39424 M 93.152171,387.08317 114.10248,354.455 m 13.38651,-20.84826 10.50517,-16.36084 m 5.19549,-8.0915 26.15125,-40.72817 m 7.99974,-12.45883 9.5233,-14.83168 M 291.73728,77.80517 315.65006,40.56323 M 97.011861,390.32612 119.25926,355.67785 m 11.37353,-17.71322 10.40149,-16.19936 m 5.51866,-8.59479 24.37416,-37.96052 M 296.03029,80.37327 324.05191,36.73219 m -220.45589,352.5938 23.58158,-36.72612 m 4.11996,-6.41648 11.44786,-17.82897 m 6.21521,-9.67963 24.77182,-38.57983 M 300.29741,82.98172 330.29742,36.25946 m -218.29773,349.23267 32.22576,-50.18864 m 6.51485,-10.14629 27.31203,-42.53597 M 304.31608,85.97709 333.86894,39.95123 M 120.36976,381.7106 145.70547,342.25256 m 6.58476,-10.25516 28.57321,-44.50013 m 92.30511,-143.75671 13.53183,-21.07458 M 308.33477,88.97242 334.04904,48.92483 M 124.782,384.093 147.18549,349.20165 m 6.65466,-10.36403 35.73428,-55.65284 m 46.36882,-72.21516 1.93514,-3.01381 m 37.18208,-57.90765 13.25393,-20.64177 m 15.36368,-23.9275 1.06312,-1.65573 m 7.61225,-11.85537 21.3604,-33.26686 M 126.11389,391.2728 150.16858,353.80983 m 5.60544,-8.72997 38.89353,-60.57306 m 36.57074,-56.95556 7.29288,-11.35799 m 38.09409,-59.32803 7.69672,-11.98693 m 24.45201,-38.08176 2.09358,-3.26054 m 5.23982,-8.16055 19.71658,-30.70676 m -208.50969,333.9887 27.49927,-42.82758 m 5.6849,-8.85371 52.15477,-81.22625 m 18.1742,-28.30463 8.35653,-13.01452 m 44.01287,-68.546 1.86799,-2.90922 m 27.97491,-43.56833 2.93522,-4.57134 m 3.87237,-6.03085 21.56255,-33.5817 m -212.69336,340.5044 30.94744,-48.1978 m 5.55894,-8.65755 57.21349,-89.10472 m 8.60265,-13.39784 5.56629,-8.66899 m 79.54238,-123.87993 3.93135,-6.12269 m 3.50818,-5.46367 24.82088,-38.65623 m -216.07779,345.7753 32.1906,-50.1339 m 5.67861,-8.8439 54.14482,-84.32556 m 92.62127,-144.2491 6.02091,-9.37698 m 4.09718,-6.381 28.32265,-44.10991 M 139.07782,408.099 169.37789,360.90941 m 5.87659,-9.15226 49.94232,-77.78053 m 71.70382,-111.67209 27.4233,-42.70925 m 6.21029,-9.67196 30.92904,-48.16912 m -211.31211,338.35319 24.35064,-37.92387 m 5.85877,-9.1245 47.33492,-73.71979 M 299.6699,167.2457 323.23044,130.55235 m 10.75428,-16.74881 31.06161,-48.37559 m -207.25591,332.03602 21.86761,-34.05676 m 6.0729,-9.45798 45.82252,-71.36435 m 71.67605,-111.62884 3.51227,-5.47005 m 30.44726,-47.4188 26.19055,-40.78937 M 161.24184,401.3428 184.81428,364.6309 m 6.28703,-9.79147 35.83827,-55.8148 m 80.31088,-125.0768 1.02014,-1.58876 m 32.0619,-49.93346 20.88416,-32.52516 m -197.78591,317.2874 26.832,-41.78836 m 6.32652,-9.85297 25.73644,-40.08214 M 343.47599,126.78401 365.10492,93.09892 m -199.48526,319.93399 30.12047,-46.90985 m 6.53635,-10.17976 30.87191,-48.08016 M 346.39856,131.48643 371.18085,92.89032 M 167.99084,418.59407 201.2362,366.8175 m 6.72748,-10.47743 23.17367,-36.09084 M 344.64054,143.47849 377.25676,92.68171 M 172.1411,421.38452 207.06653,366.99139 m 6.75556,-10.52116 23.81435,-37.08866 M 333.00361,170.856 383.33271,92.47308 M 182.37479,414.70056 212.89683,367.1653 m 6.95451,-10.831 18.3638,-28.59992 m 95.8752,-149.31679 54.3538,-84.65102 m -193.7208,310.95634 24.14333,-37.60099 m 7.01392,-10.92354 12.91325,-20.11121 m 98.70421,-153.7227 53.5309,-83.36945 M 198.79978,407.62831 225.09536,366.6754 m 7.11168,-11.07581 8.85179,-13.78584 m 100.83693,-157.04422 9.6456,-15.02212 m 10.55584,-16.43975 20.50876,-31.9405 m -180.88781,290.97016 29.60588,-46.10845 m 7.32108,-11.40191 9.93724,-15.47633 m 97.93635,-152.52682 7.90492,-12.3112 m 13.16554,-20.5041 18.56539,-28.91388 M 204.6365,417.04632 237.93722,365.18353 m 7.29823,-11.36632 6.34851,-9.88722 m 99.55768,-155.0519 7.39441,-11.51609 m 13.34463,-20.78305 19.65602,-30.61244 m -183.98183,295.7888 37.07456,-57.74022 m 7.59527,-11.82892 2.36085,-3.67682 m 101.17903,-157.57698 8.07631,-12.57813 m 11.05392,-17.21544 22.02405,-34.30044 M 211.40154,425.01854 251.60996,362.39766 M 360.3875,192.98665 372.22752,174.54694 m 3.02383,-4.70935 27.04965,-42.12735 M 230.25377,404.91202 258.86082,360.35919 M 365.01044,195.04094 407.29252,129.19052 M 235.83891,405.46775 266.415,357.84833 m 15.33285,-23.87951 12.22403,-19.0378 m 74.26166,-115.65568 41.76097,-65.03884 m -170.63804,275.00707 35.01145,-54.52709 m 4.41371,-6.87397 20.78689,-32.37365 m 69.08786,-107.59797 30.629,-47.70184 m -156.41139,252.85037 61.91687,-96.42981 m 63.87725,-99.48292 35.40996,-55.14773 m -157.68652,254.83628 47.343,-73.73236 m 6.72963,-10.48077 9.54903,-14.87174 m 57.89731,-90.1697 40.96021,-63.79177 m -158.8121,256.58928 45.22961,-70.44096 m 11.9926,-18.67736 7.95472,-12.38875 m 50.92941,-79.31784 47.49845,-73.97447 m -158.1344,255.53382 6.34924,-9.88836 m 9.22449,-14.36628 27.68934,-43.1236 m 13.42834,-20.91339 8.23748,-12.82912 m 41.75033,-65.02229 56.18032,-87.49567 m -142.90385,231.81363 27.91611,-43.47677 m 12.64869,-19.69916 13.491,-21.01099 m 23.11816,-36.0044 52.68547,-82.05275 m 9.31483,-14.507 6.95838,-10.83704 m -142.07071,230.51615 29.8416,-46.47554 m 9.16309,-14.27067 91.04352,-141.7919 M 283.60855,405.10359 413.84556,202.27148 m -126.17511,205.76015 13.74482,-21.40628 m 2.18013,-3.39537 114.50084,-178.3245 m -125.54604,204.78047 6.84019,-10.65298 m 10.21186,-15.90402 95.23334,-148.31715 m 5.47649,-8.52911 12.03486,-18.74322 m -108.15005,177.68781 94.35577,-146.9504 m 11.60598,-18.07524 5.29428,-8.24535 m -106.66137,175.36935 14.69993,-22.89379 m 1.17445,-1.8291 77.60382,-120.8608 m -88.88356,147.68201 10.40649,-16.20712 m 7.69533,-11.98479 56.51966,-88.02413 m 5.54183,-8.63091 12.43732,-19.36999 m -87.53496,145.58172 5.64202,-8.78693 m 12.55688,-19.55618 14.45803,-22.51704 m 4.25849,-6.63222 16.87144,-26.27569 m 3.65263,-5.68865 15.25238,-23.75418 m 10.22549,-15.92526 8.33469,-12.9805 m -67.8904,114.98712 10.8902,-16.96048 m 8.47408,-13.1976 13.52984,-21.0715 m 7.81816,-12.17605 11.754,-18.30579 m 15.40495,-23.99178 1.54604,-2.40782 m -64.25453,109.3246 7.32237,-11.40394 m 12.68967,-19.76297 10.18827,-15.8673 m 11.98366,-18.66346 8.25565,-12.8574 m -24.61707,47.59291 6.8467,-10.6631 m 16.34302,-25.45274 4.05302,-6.3122"/>
//! </svg>
//!
//! # Example
//!
//! ```ignore
//! // Generate a path representing a hatching of the original path.
//! let mut path_builder = Path::builder();
//! let mut hatcher = Hatcher::new();
//! hatcher.hatch_path(
//!     original_path.path_iter(),
//!     &options,
//!     &mut RegularHatchingPattern {
//!         interval: hatch.spacing,
//!         callback: &mut|segment: &HatchSegment| {
//!             path_builder.move_to(segment.a.position);
//!             path_builder.line_to(segment.b.position);
//!         }
//!     },
//! );
//! let hatched_path = path_builder.build();
//! ```


use path::PathEvent;
use path::builder::{Build, FlatPathBuilder, PathBuilder};
use geom::LineSegment;
use geom::math::{Point, Vector, point, vector};
use geom::euclid::{Angle, Rotation2D};
use std::marker::PhantomData;

use std::cmp::Ordering;
use std::mem;
use std::f32;

/// Parameters for the hatcher.
#[derive(Copy, Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
pub struct HatchingOptions {
    /// Maximum allowed distance to the path when building an approximation.
    ///
    /// See [Flattening and tolerance](index.html#flattening-and-tolerance).
    ///
    /// Default value: `HatchingOptions::DEFAULT_TOLERANCE`.
    pub tolerance: f32,
    /// Angle between the hatching pattern and the x axis.
    ///
    /// Default value: `HatchingOptions::ANGLE`.
    pub angle: Angle<f32>,
    /// Whether to compute the tangent of the outline where it meets the hatching pattern.
    ///
    /// Default value: `true, .
    pub compute_tangents: bool,

    /// The origin of the rotated uv coordinates.
    pub uv_origin: Point,

    // To be able to add fields without making it a breaking change, add an empty private field
    // which makes it impossible to create a StrokeOptions without calling the constructor.
    _private: (),
}

impl Default for HatchingOptions {
    fn default() -> Self { Self::DEFAULT }
}

impl HatchingOptions {
    /// Default flattening tolerance.
    pub const DEFAULT_TOLERANCE: f32 = 0.1;
    /// Default hatching angle.
    pub const DEFAULT_ANGLE: Angle<f32> = Angle { radians: 0.0 };
    pub const DEFAULT_UV_ORIGIN: Point = Point { x: 0.0, y: 0.0, _unit: PhantomData };

    pub const DEFAULT: Self = HatchingOptions {
        tolerance: Self::DEFAULT_TOLERANCE,
        angle: Self::DEFAULT_ANGLE,
        compute_tangents: true,
        uv_origin: Self::DEFAULT_UV_ORIGIN,
        _private: (),
    };

    #[inline]
    pub fn tolerance(tolerance: f32) -> Self {
        Self::DEFAULT.with_tolerance(tolerance)
    }

    #[inline]
    pub fn angle(angle: Angle<f32>) -> Self {
        Self::DEFAULT.with_angle(angle)
    }

    #[inline]
    pub fn with_tolerance(mut self, tolerance: f32) -> Self {
        self.tolerance = tolerance;
        self
    }

    #[inline]
    pub fn with_angle(mut self, angle: Angle<f32>) -> Self {
        self.angle = angle;
        self
    }

    #[inline]
    pub fn with_tangents(mut self, compute_tangents: bool) -> Self {
        self.compute_tangents = compute_tangents;
        self
    }
}

/// Parameters for generating dot patterns.
#[derive(Copy, Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
pub struct DotOptions {
    /// Maximum allowed distance to the path when building an approximation.
    ///
    /// See [Flattening and tolerance](index.html#flattening-and-tolerance).
    ///
    /// Default value: `HatchingOptions::DEFAULT_TOLERANCE`.
    pub tolerance: f32,
    /// Angle between the hatching pattern and the x axis.
    ///
    /// Default value: `HatchingOptions::ANGLE`.
    pub angle: Angle<f32>,
    /// The origin of the rotated uv coordinates.
    pub uv_origin: Point,

    // To be able to add fields without making it a breaking change, add an empty private field
    // which makes it impossible to create a StrokeOptions without calling the constructor.
    _private: (),
}

impl Default for DotOptions {
    fn default() -> Self { Self::DEFAULT }
}

impl DotOptions {
    /// Default flattening tolerance.
    pub const DEFAULT_TOLERANCE: f32 = 0.1;
    /// Default inclination of the dot pattern.
    pub const DEFAULT_ANGLE: Angle<f32> = Angle { radians: 0.0 };
    pub const DEFAULT_UV_ORIGIN: Point = Point { x: 0.0, y: 0.0, _unit: PhantomData };

    pub const DEFAULT: Self = DotOptions {
        tolerance: Self::DEFAULT_TOLERANCE,
        angle: Self::DEFAULT_ANGLE,
        uv_origin: Self::DEFAULT_UV_ORIGIN,
        _private: (),
    };

    #[inline]
    pub fn tolerance(tolerance: f32) -> Self {
        Self::DEFAULT.with_tolerance(tolerance)
    }

    #[inline]
    pub fn angle(angle: Angle<f32>) -> Self {
        Self::DEFAULT.with_angle(angle)
    }

    #[inline]
    pub fn with_tolerance(mut self, tolerance: f32) -> Self {
        self.tolerance = tolerance;
        self
    }

    #[inline]
    pub fn with_angle(mut self, angle: Angle<f32>) -> Self {
        self.angle = angle;
        self
    }
}

type Edge = LineSegment<f32>;

pub struct HatchSegment {
    /// Left endpoint.
    pub a: HatchEndpoint,
    /// Right endpoint.
    pub b: HatchEndpoint,
    /// Index of the current row.
    pub row: u32,
    /// Rotated position along a direction perpendicular to the hatching pattern.
    ///
    /// This position is relative to `uv_origin` specified in the `HatchingOptions`.
    pub v: f32,
}

pub struct HatchEndpoint {
    /// Position in world space of the point.
    pub position: Point,
    /// Tangent of the path edge at this point (pointing downward).
    pub tangent: Vector,
    /// Rotated position along the direction of the hatching pattern.
    ///
    /// This position is relative to `uv_origin` specified in the `HatchingOptions`.
    pub u: f32,
}

/// The output of `Hatcher::hatch_path`.
///
/// Implement this trait to create custom hatching patterns.
pub trait HatchBuilder {
    /// Called for each hatch segment.
    fn add_segment(&mut self, segment: &HatchSegment);
    /// Specifies the distance between each row of the pattern.
    fn next_offset(&mut self, row_idx: u32) -> f32;
}

pub struct Dot {
    /// World-space position of the dot.
    pub position: Point,
    /// Rotated position along an axis parallel to the rows of the pattern.
    pub u: f32,
    /// Rotated position along an axis parallel to the columns of the pattern.
    pub v: f32,
    /// Index of the current column.
    pub column: u32,
    /// Index of the current row.
    pub row: u32,
}

/// The output of `Hatcher::dot_path`.
///
/// Implement this trait to create custom dot patterns.
pub trait DotBuilder {
    /// Offset of the first dot after a left edge.
    fn first_column_offset(&mut self, _row: u32) -> f32 { 0.0 }
    /// Whether and how much to align the dots for a given row.
    fn alignment(&mut self, _row: u32) -> Option<f32> { None }
    /// Called for each row of dots.
    fn next_row_offset(&mut self, column: u32, row: u32) -> f32;
    /// Distance between each dot in a given row.
    fn next_column_offset(&mut self, column: u32, row: u32) -> f32;

    /// Called for each dot.
    fn add_dot(&mut self, dot: &Dot);
}

/// A `DotBuilder` implementation for dot patterns with constant intervals.
pub struct RegularDotPattern<Cb: FnMut(&Dot)> {
    /// Minimum distance between dots in a given column.
    pub column_interval: f32,
    /// Minimum distance between dots in a given row.
    pub row_interval: f32,
    /// A callback invoked for each dot.
    pub callback: Cb,
}

/// A context object that can fill a path with a hatching or dot pattern.
pub struct Hatcher {
    events: HatchingEvents,
    active_edges: Vec<Edge>,
    transform: Rotation2D<f32>,
    compute_tangents: bool,
    segment: HatchSegment,
    uv_origin: Point,
}

impl Hatcher {
    /// Constructor.
    pub fn new() -> Self {
        Hatcher {
            events: HatchingEvents::new(),
            active_edges: Vec::new(),
            transform: Rotation2D::identity(),
            compute_tangents: true,
            segment: HatchSegment {
                a: HatchEndpoint {
                    position: point(0.0, 0.0),
                    tangent: vector(f32::NAN, f32::NAN),
                    u: 0.0,
                },
                b: HatchEndpoint {
                    position: point(0.0, 0.0),
                    tangent: vector(f32::NAN, f32::NAN),
                    u: 0.0,
                },
                row: 0,
                v: 0.0,
            },
            uv_origin: point(0.0, 0.0),
        }
    }

    /// Generate hatches for a path.
    pub fn hatch_path<Iter>(
        &mut self,
        it: Iter,
        options: &HatchingOptions,
        output: &mut dyn HatchBuilder,
    )
    where
        Iter: Iterator<Item = PathEvent>,
    {
        let mut events = mem::replace(&mut self.events, HatchingEvents::new());
        events.set_path(options.tolerance, options.angle, it);

        self.hatch(&events, options, output);

        self.events = events;
    }

    /// Generate dots for a path.
    pub fn dot_path<Iter>(
        &mut self,
        it: Iter,
        options: &DotOptions,
        output: &mut dyn DotBuilder,
    )
    where
        Iter: Iterator<Item = PathEvent>,
    {
        let mut events = mem::replace(&mut self.events, HatchingEvents::new());
        events.set_path(options.tolerance, options.angle, it);

        self.dot(&events, options, output);

        self.events = events;
    }

    fn hatch(
        &mut self,
        events: &HatchingEvents,
        options: &HatchingOptions,
        output: &mut dyn HatchBuilder
    ) {
        self.transform = Rotation2D::new(-options.angle);
        self.uv_origin = Rotation2D::new(options.angle).transform_point(
            &options.uv_origin
        );
        self.active_edges.clear();
        self.segment.row = 0;
        self.segment.a.tangent = vector(f32::NAN, f32::NAN);
        self.segment.b.tangent = vector(f32::NAN, f32::NAN);
        self.compute_tangents = options.compute_tangents;

        let mut y = events.edges.first().unwrap().from.y + output.next_offset(0);
        let mut y_max = y;

        for edge in &events.edges {
            let y2 = edge.from.y;
            while y < y2 {
                self.hatch_line(y, output);
                let offset = output.next_offset(self.segment.row);
                y += offset;
                if offset <= 0.0 {
                    return;
                }
            }
            y_max = f32::max(y_max, edge.to.y);
            self.update_sweep_line(edge);
        }

        while y < y_max {
            self.hatch_line(y, output);
            let offset = output.next_offset(self.segment.row);
            y += offset;
            if offset <= 0.0 {
                return;
            }
        }
    }

    fn dot(
        &mut self,
        events: &HatchingEvents,
        options: &DotOptions,
        output: &mut dyn DotBuilder
    ) {
        let mut dotted = HatchesToDots {
            builder: output,
            column: 0,
        };

        let options = HatchingOptions {
            tolerance: options.tolerance,
            angle: options.angle,
            uv_origin: options.uv_origin,
            compute_tangents: false,
            _private: (),
        };

        self.hatch(events, &options, &mut dotted);
    }

    fn update_sweep_line(&mut self, edge: &Edge) {
        self.active_edges.retain(|e| {
            compare_positions(e.to, edge.from) != Ordering::Less
        });
        self.active_edges.push(*edge);
    }

    fn hatch_line(&mut self, y: f32, output: &mut dyn HatchBuilder) {
        self.active_edges.sort_by_key(|e| { Ordered(e.solve_x_for_y(y)) });

        let mut inside = false;
        let mut prev_x = f32::NAN;
        let mut prev_tangent = vector(f32::NAN, f32::NAN);
        let mut tangent = vector(f32::NAN, f32::NAN);
        self.segment.v = y - self.uv_origin.y;

        for active_edge in &self.active_edges {
            if active_edge.to.y <= y {
                // TODO: we don't remove the edges during merge events so we can
                // end up with extra edges that end above the sweep line and have
                // to skip them. It would be better to properly manage the sweep
                // line instead!
                continue;
            }
            let x = active_edge.solve_x_for_y(y);
            if self.compute_tangents {
                tangent = self.transform.transform_vector(&active_edge.to_vector()).normalize();
            }

            if inside {
                self.segment.a.position = self.transform.transform_point(&point(prev_x, y));
                self.segment.b.position = self.transform.transform_point(&point(x, y));
                self.segment.a.u = prev_x - self.uv_origin.x;
                self.segment.b.u = x - self.uv_origin.x;
                if self.compute_tangents {
                    self.segment.a.tangent = prev_tangent;
                    self.segment.b.tangent = tangent;
                }

                output.add_segment(&self.segment);
            }

            inside = !inside;
            prev_x = x;
            prev_tangent = tangent;
        }

        self.segment.row += 1;
    }
}

struct HatchingEvents {
    edges: Vec<Edge>,
}

impl HatchingEvents {
    fn new() -> Self {
        HatchingEvents {
            edges: Vec::new()
        }
    }
}

struct EventsBuilder {
    edges: Vec<Edge>,
    angle: Angle<f32>,
    first: Point,
    current: Point,
    nth: u32,
}

impl EventsBuilder {
    fn new(angle: Angle<f32>) -> Self {
        EventsBuilder {
            edges: Vec::new(),
            angle,
            first: point(0.0, 0.0),
            current: point(0.0, 0.0),
            nth: 0,
        }
    }

    fn add_edge(&mut self, from: Point, to: Point) {
        let rotation = Rotation2D::new(self.angle);
        let mut from = rotation.transform_point(&from);
        let mut to = rotation.transform_point(&to);
        if compare_positions(from, to) == Ordering::Greater {
            mem::swap(&mut from, &mut to);
        }
        self.edges.push(Edge { from, to });
    }
}

impl Build for EventsBuilder {
    type PathType = HatchingEvents;

    fn build(mut self) -> HatchingEvents {
        self.build_and_reset()
    }

    fn build_and_reset(&mut self) -> HatchingEvents {
        self.close();

        self.first = point(0.0, 0.0);
        self.current = point(0.0, 0.0);
        self.nth = 0;

        self.edges.sort_by(|a, b| compare_positions(a.from, b.from));

        HatchingEvents {
            edges: mem::replace(&mut self.edges, Vec::new()),
        }
    }
}

impl FlatPathBuilder for EventsBuilder {
    fn move_to(&mut self, to: Point) {
        self.close();
        let next = to;
        if self.nth > 1 {
            let current = self.current;
            let first = self.first;
            self.add_edge(current, first);
        }
        self.first = next;
        self.current = next;
        self.nth = 0;
    }

    fn line_to(&mut self, to: Point) {
        let next = to;
        if next == self.current {
            return;
        }
        let current = self.current;
        self.add_edge(current, next);
        self.current = next;
        self.nth += 1;
    }

    fn close(&mut self) {
        let current = self.current;
        let first = self.first;
        if self.current != self.first && self.nth > 0 {
            self.add_edge(current, first);
        }
        self.nth = 0;
        self.current = self.first;
    }

    fn current_position(&self) -> Point {
        self.current
    }
}

impl HatchingEvents {

    pub fn set_path<Iter>(
        &mut self,
        tolerance: f32,
        angle: Angle<f32>,
        it: Iter
    )
        where Iter: Iterator<Item = PathEvent>
    {
        self.edges.clear();
        let mut builder = EventsBuilder::new(angle);
        builder.edges = mem::replace(&mut self.edges, Vec::new());

        let mut builder = builder.flattened(tolerance);
        for evt in it {
            builder.path_event(evt);
        }
        mem::swap(self, &mut builder.build());
    }
}

#[derive(PartialEq)]
struct Ordered(f32);
impl Eq for Ordered {}

impl PartialOrd for Ordered {
    fn partial_cmp(&self, other: &Ordered) -> Option<Ordering> {
        if self.0 > other.0 {
            return Some(Ordering::Greater);
        }

        if self.0 < other.0 {
            return Some(Ordering::Less);
        }

        Some(Ordering::Equal)
    }
}

impl Ord for Ordered {
    fn cmp(&self, other: &Ordered) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn compare_positions(a: Point, b: Point) -> Ordering {
    if a.y > b.y {
        return Ordering::Greater;
    }
    if a.y < b.y {
        return Ordering::Less;
    }
    if a.x > b.x {
        return Ordering::Greater;
    }
    if a.x < b.x {
        return Ordering::Less;
    }

    Ordering::Equal
}

impl<Cb: FnMut(&Dot)> DotBuilder for RegularDotPattern<Cb> {
    fn alignment(&mut self, _row: u32) -> Option<f32> { Some(self.column_interval) }
    fn next_row_offset(&mut self, _column: u32, _row: u32) -> f32 { self.row_interval }
    fn next_column_offset(&mut self, _column: u32, _row: u32) -> f32 { self.column_interval }
    fn add_dot(&mut self, dot: &Dot) { (self.callback)(dot) }
}

/// A `HatchBuilder` implementation for hatching patterns with constant intervals.
pub struct RegularHatchingPattern<Cb: FnMut(&HatchSegment)> {
    /// The distance between each row of hatches.
    pub interval: f32,
    /// A callback invoked for each segment.
    pub callback: Cb,
}

impl<Cb: FnMut(&HatchSegment)> HatchBuilder for RegularHatchingPattern<Cb> {
    fn next_offset(&mut self, _row: u32) -> f32 { self.interval }
    fn add_segment(&mut self, segment: &HatchSegment) { (self.callback)(segment) }
}

// Converts a hatching pattern into a dotted pattern.
struct HatchesToDots<'l> {
    builder: &'l mut dyn DotBuilder,
    column: u32,
}

impl<'l> HatchBuilder for HatchesToDots<'l> {
    fn next_offset(&mut self, row: u32) -> f32 {
        let val = self.builder.next_row_offset(self.column, row);
        self.column = 0;

        val
    }

    fn add_segment(&mut self, segment: &HatchSegment) {
        let row = segment.row;
        let mut u = self.builder.first_column_offset(row);
        let u_start = segment.a.u;

        if let Some(d) = self.builder.alignment(row) {
            let m = modulo(u_start, d);
            if m != 0.0 {
                u += d - m;
            }
        }

        let a = segment.a.position;
        let ab = (segment.b.position - a).normalize();

        while u_start + u < segment.b.u {
            self.builder.add_dot(&Dot {
                position: a + ab * u,
                u: segment.a.u + u,
                v: segment.v,
                column: self.column,
                row,
            });

            self.column += 1;
            let du = self.builder.next_column_offset(self.column, row);
            if du <= 0.0 {
                return;
            }

            u += du;
        }
    }
}

fn modulo(a: f32, m: f32) -> f32 {
    if a >= 0.0 { a % m } else { m + (a % m) }
}