third_party/rust_crates/vendor/cassowary/src/lib.rs - fuchsia - Git at Google

 //! This crate contains an implementation of the Cassowary constraint solving algorithm, based upon the work by
 //! G.J. Badros et al. in 2001. This algorithm is designed primarily for use constraining elements in user interfaces.
 //! Constraints are linear combinations of the problem variables. The notable features of Cassowary that make it
 //! ideal for user interfaces are that it is incremental (i.e. you can add and remove constraints at runtime
 //! and it will perform the minimum work to update the result) and that the constraints can be violated if
 //! necessary,
 //! with the order in which they are violated specified by setting a "strength" for each constraint.
 //! This allows the solution to gracefully degrade, which is useful for when a
 //! user interface needs to compromise on its constraints in order to still be able to display something.
 //!
 //! ## Constraint syntax
 //!
 //! This crate aims to provide syntax for describing linear constraints as naturally as possible, within
 //! the limitations of Rust's type system. Generally you can write constraints as you would naturally, however
 //! the operator symbol (for greater-than, less-than, equals) is replaced with an instance of the
 //! `WeightedRelation` enum wrapped in "pipe brackets".
 //!
 //! For example, for the constraint
 //! `(a + b) * 2 + c >= d + 1` with strength `s`, the code to use is
 //!
 //! ```ignore
 //! (a + b) * 2.0 + c |GE(s)| d + 1.0
 //! ```
 //!
 //! # A simple example
 //!
 //! Imagine a layout consisting of two elements laid out horizontally. For small window widths the elements
 //! should compress to fit, but if there is enough space they should display at their preferred widths. The
 //! first element will align to the left, and the second to the right. For  this example we will ignore
 //! vertical layout.
 //!
 //! First we need to include the relevant parts of `cassowary`:
 //!
 //! ```
 //! use cassowary::{ Solver, Variable };
 //! use cassowary::WeightedRelation::*;
 //! use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED };
 //! ```
 //!
 //! And we'll construct some conveniences for pretty printing (which should hopefully be self-explanatory):
 //!
 //! ```ignore
 //! use std::collections::HashMap;
 //! let mut names = HashMap::new();
 //! fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) {
 //!     println!("Changes:");
 //!     for &(ref var, ref val) in changes {
 //!         println!("{}: {}", names[var], val);
 //!     }
 //! }
 //! ```
 //!
 //! Let's define the variables required - the left and right edges of the elements, and the width of the window.
 //!
 //! ```ignore
 //! let window_width = Variable::new();
 //! names.insert(window_width, "window_width");
 //!
 //! struct Element {
 //!     left: Variable,
 //!     right: Variable
 //! }
 //! let box1 = Element {
 //!     left: Variable::new(),
 //!     right: Variable::new()
 //! };
 //! names.insert(box1.left, "box1.left");
 //! names.insert(box1.right, "box1.right");
 //!
 //! let box2 = Element {
 //!     left: Variable::new(),
 //!     right: Variable::new()
 //! };
 //! names.insert(box2.left, "box2.left");
 //! names.insert(box2.right, "box2.right");
 //! ```
 //!
 //! Now to set up the solver and constraints.
 //!
 //! ```ignore
 //! let mut solver = Solver::new();
 //! solver.add_constraints(&[window_width |GE(REQUIRED)| 0.0, // positive window width
 //!                          box1.left |EQ(REQUIRED)| 0.0, // left align
 //!                          box2.right |EQ(REQUIRED)| window_width, // right align
 //!                          box2.left |GE(REQUIRED)| box1.right, // no overlap
 //!                          // positive widths
 //!                          box1.left |LE(REQUIRED)| box1.right,
 //!                          box2.left |LE(REQUIRED)| box2.right,
 //!                          // preferred widths:
 //!                          box1.right - box1.left |EQ(WEAK)| 50.0,
 //!                          box2.right - box2.left |EQ(WEAK)| 100.0]).unwrap();
 //! ```
 //!
 //! The window width is currently free to take any positive value. Let's constrain it to a particular value.
 //! Since for this example we will repeatedly change the window width, it is most efficient to use an
 //! "edit variable", instead of repeatedly removing and adding constraints (note that for efficiency
 //! reasons we cannot edit a normal constraint that has been added to the solver).
 //!
 //! ```ignore
 //! solver.add_edit_variable(window_width, STRONG).unwrap();
 //! solver.suggest_value(window_width, 300.0).unwrap();
 //! ```
 //!
 //! This value of 300 is enough to fit both boxes in with room to spare, so let's check that this is the case.
 //! We can fetch a list of changes to the values of variables in the solver. Using the pretty printer defined
 //! earlier we can see what values our variables now hold.
 //!
 //! ```ignore
 //! print_changes(&names, solver.fetch_changes());
 //! ```
 //!
 //! This should print (in a possibly different order):
 //!
 //! ```ignore
 //! Changes:
 //! window_width: 300
 //! box1.right: 50
 //! box2.left: 200
 //! box2.right: 300
 //! ```
 //!
 //! Note that the value of `box1.left` is not mentioned. This is because `solver.fetch_changes` only lists
 //! *changes* to variables, and since each variable starts in the solver with a value of zero, any values that
 //! have not changed from zero will not be reported.
 //!
 //! Now let's try compressing the window so that the boxes can't take up their preferred widths.
 //!
 //! ```ignore
 //! solver.suggest_value(window_width, 75.0);
 //! print_changes(&names, solver.fetch_changes);
 //! ```
 //!
 //! Now the solver can't satisfy all of the constraints. It will pick at least one of the weakest constraints to
 //! violate. In this case it will be one or both of the preferred widths. For efficiency reasons this is picked
 //! nondeterministically, so there are two possible results. This could be
 //!
 //! ```ignore
 //! Changes:
 //! window_width: 75
 //! box1.right: 0
 //! box2.left: 0
 //! box2.right: 75
 //! ```
 //!
 //! or
 //!
 //! ```ignore
 //! Changes:
 //! window_width: 75
 //! box2.left: 50
 //! box2.right: 75
 //! ```
 //!
 //! Due to the nature of the algorithm, "in-between" solutions, although just as valid, are not picked.
 //!
 //! In a user interface this is not likely a result we would prefer. The solution is to add another constraint
 //! to control the behaviour when the preferred widths cannot both be satisfied. In this example we are going
 //! to constrain the boxes to try to maintain a ratio between their widths.
 //!
 //! ```
 //! # use cassowary::{ Solver, Variable };
 //! # use cassowary::WeightedRelation::*;
 //! # use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED };
 //! #
 //! # use std::collections::HashMap;
 //! # let mut names = HashMap::new();
 //! # fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) {
 //! #     println!("Changes:");
 //! #     for &(ref var, ref val) in changes {
 //! #         println!("{}: {}", names[var], val);
 //! #     }
 //! # }
 //! #
 //! # let window_width = Variable::new();
 //! # names.insert(window_width, "window_width");
 //! # struct Element {
 //! #    left: Variable,
 //! #    right: Variable
 //! # }
 //! # let box1 = Element {
 //! #     left: Variable::new(),
 //! #     right: Variable::new()
 //! # };
 //! # names.insert(box1.left, "box1.left");
 //! # names.insert(box1.right, "box1.right");
 //! # let box2 = Element {
 //! #     left: Variable::new(),
 //! #     right: Variable::new()
 //! # };
 //! # names.insert(box2.left, "box2.left");
 //! # names.insert(box2.right, "box2.right");
 //! # let mut solver = Solver::new();
 //! # solver.add_constraints(&[window_width |GE(REQUIRED)| 0.0, // positive window width
 //! #                          box1.left |EQ(REQUIRED)| 0.0, // left align
 //! #                          box2.right |EQ(REQUIRED)| window_width, // right align
 //! #                          box2.left |GE(REQUIRED)| box1.right, // no overlap
 //! #                          // positive widths
 //! #                          box1.left |LE(REQUIRED)| box1.right,
 //! #                          box2.left |LE(REQUIRED)| box2.right,
 //! #                          // preferred widths:
 //! #                          box1.right - box1.left |EQ(WEAK)| 50.0,
 //! #                          box2.right - box2.left |EQ(WEAK)| 100.0]).unwrap();
 //! # solver.add_edit_variable(window_width, STRONG).unwrap();
 //! # solver.suggest_value(window_width, 300.0).unwrap();
 //! # print_changes(&names, solver.fetch_changes());
 //! # solver.suggest_value(window_width, 75.0);
 //! # print_changes(&names, solver.fetch_changes());
 //! solver.add_constraint(
 //!     (box1.right - box1.left) / 50.0 |EQ(MEDIUM)| (box2.right - box2.left) / 100.0
 //!     ).unwrap();
 //! print_changes(&names, solver.fetch_changes());
 //! ```
 //!
 //! Now the result gives values that maintain the ratio between the sizes of the two boxes:
 //!
 //! ```ignore
 //! Changes:
 //! box1.right: 25
 //! box2.left: 25
 //! ```
 //!
 //! This example may have appeared somewhat contrived, but hopefully it shows the power of the cassowary
 //! algorithm for laying out user interfaces.
 //!
 //! One thing that this example exposes is that this crate is a rather low level library. It does not have
 //! any inherent knowledge of user interfaces, directions or boxes. Thus for use in a user interface this
 //! crate should ideally be wrapped by a higher level API, which is outside the scope of this crate.
 use std::sync::Arc;
 use std::collections::HashMap;
 use std::collections::hash_map::{Entry};

 mod solver_impl;
 mod operators;

 static VARIABLE_ID: ::std::sync::atomic::AtomicUsize = ::std::sync::atomic::ATOMIC_USIZE_INIT;

 /// Identifies a variable for the constraint solver.
 /// Each new variable is unique in the view of the solver, but copying or cloning the variable produces
 /// a copy of the same variable.
 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
 pub struct Variable(usize);

 impl Variable {
     /// Produces a new unique variable for use in constraint solving.
     pub fn new() -> Variable {
         Variable(VARIABLE_ID.fetch_add(1, ::std::sync::atomic::Ordering::Relaxed))
     }
 }

 /// A variable and a coefficient to multiply that variable by. This is a sub-expression in
 /// a constraint equation.
 #[derive(Copy, Clone, Debug)]
 pub struct Term {
     pub variable: Variable,
     pub coefficient: f64
 }

 impl Term {
     /// Construct a new Term from a variable and a coefficient.
     fn new(variable: Variable, coefficient: f64) -> Term {
         Term {
             variable: variable,
             coefficient: coefficient
         }
     }
 }

 /// An expression that can be the left hand or right hand side of a constraint equation.
 /// It is a linear combination of variables, i.e. a sum of variables weighted by coefficients, plus an optional constant.
 #[derive(Clone, Debug)]
 pub struct Expression {
     pub terms: Vec<Term>,
     pub constant: f64
 }

 impl Expression {
     /// Constructs an expression of the form _n_, where n is a constant real number, not a variable.
     pub fn from_constant(v: f64) -> Expression {
         Expression {
             terms: Vec::new(),
             constant: v
         }
     }
     /// Constructs an expression from a single term. Forms an expression of the form _n x_
     /// where n is the coefficient, and x is the variable.
     pub fn from_term(term: Term) -> Expression {
         Expression {
             terms: vec![term],
             constant: 0.0
         }
     }
     /// General constructor. Each `Term` in `terms` is part of the sum forming the expression, as well as `constant`.
     pub fn new(terms: Vec<Term>, constant: f64) -> Expression {
         Expression {
             terms: terms,
             constant: constant
         }
     }
     /// Mutates this expression by multiplying it by minus one.
     pub fn negate(&mut self) {
         self.constant = -self.constant;
         for t in &mut self.terms {
             *t = -*t;
         }
     }
 }

 impl From<f64> for Expression {
     fn from(v: f64) -> Expression {
         Expression::from_constant(v)
     }
 }

 impl From<Variable> for Expression {
     fn from(v: Variable) -> Expression {
         Expression::from_term(Term::new(v, 1.0))
     }
 }

 impl From<Term> for Expression {
     fn from(t: Term) -> Expression {
         Expression::from_term(t)
     }
 }

 /// Contains useful constants and functions for producing strengths for use in the constraint solver.
 /// Each constraint added to the solver has an associated strength specifying the precedence the solver should
 /// impose when choosing which constraints to enforce. It will try to enforce all constraints, but if that
 /// is impossible the lowest strength constraints are the first to be violated.
 ///
 /// Strengths are simply real numbers. The strongest legal strength is 1,001,001,000.0. The weakest is 0.0.
 /// For convenience constants are declared for commonly used strengths. These are `REQUIRED`, `STRONG`,
 /// `MEDIUM` and `WEAK`. Feel free to multiply these by other values to get intermediate strengths.
 /// Note that the solver will clip given strengths to the legal range.
 ///
 /// `REQUIRED` signifies a constraint that cannot be violated under any circumstance. Use this special strength
 /// sparingly, as the solver will fail completely if it find that not all of the `REQUIRED` constraints
 /// can be satisfied. The other strengths represent fallible constraints. These should be the most
 /// commonly used strenghts for use cases where violating a constraint is acceptable or even desired.
 ///
 /// The solver will try to get as close to satisfying the constraints it violates as possible, strongest first.
 /// This behaviour can be used (for example) to provide a "default" value for a variable should no other
 /// stronger constraints be put upon it.
 pub mod strength {
     /// Create a constraint as a linear combination of STRONG, MEDIUM and WEAK strengths, corresponding to `a`
     /// `b` and `c` respectively. The result is further multiplied by `w`.
     pub fn create(a: f64, b: f64, c: f64, w: f64) -> f64 {
         (a * w).max(0.0).min(1000.0) * 1_000_000.0 +
             (b * w).max(0.0).min(1000.0) * 1000.0 +
             (c * w).max(0.0).min(1000.0)
     }
     pub const REQUIRED: f64 = 1_001_001_000.0;
     pub const STRONG: f64 = 1_000_000.0;
     pub const MEDIUM: f64 = 1_000.0;
     pub const WEAK: f64 = 1.0;

     /// Clips a strength value to the legal range
     pub fn clip(s: f64) -> f64 {
         s.min(REQUIRED).max(0.0)
     }
 }

 /// The possible relations that a constraint can specify.
 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
 pub enum RelationalOperator {
     /// `<=`
     LessOrEqual,
     /// `==`
     Equal,
     /// `>=`
     GreaterOrEqual
 }

 impl std::fmt::Display for RelationalOperator {
     fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
         match *self {
             RelationalOperator::LessOrEqual => write!(fmt, "<=") ?,
             RelationalOperator::Equal => write!(fmt, "==") ?,
             RelationalOperator::GreaterOrEqual => write!(fmt, ">=") ?,
         };
         Ok(())
     }
 }

 #[derive(Debug)]
 struct ConstraintData {
     expression: Expression,
     strength: f64,
     op: RelationalOperator
 }

 /// A constraint, consisting of an equation governed by an expression and a relational operator,
 /// and an associated strength.
 #[derive(Clone, Debug)]
 pub struct Constraint(Arc<ConstraintData>);

 impl Constraint {
     /// Construct a new constraint from an expression, a relational operator and a strength.
     /// This corresponds to the equation `e op 0.0`, e.g. `x + y >= 0.0`. For equations with a non-zero
     /// right hand side, subtract it from the equation to give a zero right hand side.
     pub fn new(e: Expression, op: RelationalOperator, strength: f64) -> Constraint {
         Constraint(Arc::new(ConstraintData {
             expression: e,
             op: op,
             strength: strength
         }))
     }
     /// The expression of the left hand side of the constraint equation.
     pub fn expr(&self) -> &Expression {
         &self.0.expression
     }
     /// The relational operator governing the constraint.
     pub fn op(&self) -> RelationalOperator {
         self.0.op
     }
     /// The strength of the constraint that the solver will use.
     pub fn strength(&self) -> f64 {
         self.0.strength
     }
 }

 impl ::std::hash::Hash for Constraint {
     fn hash<H: ::std::hash::Hasher>(&self, hasher: &mut H) {
         use ::std::ops::Deref;
         hasher.write_usize(self.0.deref() as *const _ as usize);
     }
 }

 impl PartialEq for Constraint {
     fn eq(&self, other: &Constraint) -> bool {
         use ::std::ops::Deref;
         self.0.deref() as *const _ == other.0.deref() as *const _
     }
 }

 impl Eq for Constraint {}

 /// This is part of the syntactic sugar used for specifying constraints. This enum should be used as part of a
 /// constraint expression. See the module documentation for more information.
 pub enum WeightedRelation {
     /// `==`
     EQ(f64),
     /// `<=`
     LE(f64),
     /// `>=`
     GE(f64)
 }
 impl From<WeightedRelation> for (RelationalOperator, f64) {
     fn from(r: WeightedRelation) -> (RelationalOperator, f64) {
         use WeightedRelation::*;
         match r {
             EQ(s) => (RelationalOperator::Equal, s),
             LE(s) => (RelationalOperator::LessOrEqual, s),
             GE(s) => (RelationalOperator::GreaterOrEqual, s),
         }
     }
 }

 /// This is an intermediate type used in the syntactic sugar for specifying constraints. You should not use it
 /// directly.
 pub struct PartialConstraint(Expression, WeightedRelation);

 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 enum SymbolType {
     Invalid,
     External,
     Slack,
     Error,
     Dummy
 }

 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 struct Symbol(usize, SymbolType);

 impl Symbol {
     fn invalid() -> Symbol { Symbol(0, SymbolType::Invalid) }
     fn type_(&self) -> SymbolType { self.1 }
 }

 #[derive(Clone)]
 struct Row {
     cells: HashMap<Symbol, f64>,
     constant: f64
 }

 fn near_zero(value: f64) -> bool {
     const EPS: f64 = 1E-8;
     if value < 0.0 {
         -value < EPS
     } else {
         value < EPS
     }
 }

 impl Row {
     fn new(constant: f64) -> Row {
         Row {
             cells: HashMap::new(),
             constant: constant
         }
     }
     fn add(&mut self, v: f64) -> f64 {
         self.constant += v;
         self.constant
     }
     fn insert_symbol(&mut self, s: Symbol, coefficient: f64) {
         match self.cells.entry(s) {
             Entry::Vacant(entry) => if !near_zero(coefficient) {
                 entry.insert(coefficient);
             },
             Entry::Occupied(mut entry) => {
                 *entry.get_mut() += coefficient;
                 if near_zero(*entry.get_mut()) {
                     entry.remove();
                 }
             }
         }
     }

     fn insert_row(&mut self, other: &Row, coefficient: f64) -> bool {
         let constant_diff = other.constant * coefficient;
         self.constant += constant_diff;
         for (s, v) in &other.cells {
             self.insert_symbol(*s, v * coefficient);
         }
         constant_diff != 0.0
     }

     fn remove(&mut self, s: Symbol) {
         self.cells.remove(&s);
     }

     fn reverse_sign(&mut self) {
         self.constant = -self.constant;
         for (_, v) in &mut self.cells {
             *v = -*v;
         }
     }

     fn solve_for_symbol(&mut self, s: Symbol) {
         let coeff = -1.0 / match self.cells.entry(s) {
             Entry::Occupied(entry) => entry.remove(),
             Entry::Vacant(_) => unreachable!()
         };
         self.constant *= coeff;
         for (_, v) in &mut self.cells {
             *v *= coeff;
         }
     }

     fn solve_for_symbols(&mut self, lhs: Symbol, rhs: Symbol) {
         self.insert_symbol(lhs, -1.0);
         self.solve_for_symbol(rhs);
     }

     fn coefficient_for(&self, s: Symbol) -> f64 {
         self.cells.get(&s).cloned().unwrap_or(0.0)
     }

     fn substitute(&mut self, s: Symbol, row: &Row) -> bool {
         if let Some(coeff) = self.cells.remove(&s) {
             self.insert_row(row, coeff)
         } else {
             false
         }
     }
 }

 /// The possible error conditions that `Solver::add_constraint` can fail with.
 #[derive(Debug, Copy, Clone)]
 pub enum AddConstraintError {
     /// The constraint specified has already been added to the solver.
     DuplicateConstraint,
     /// The constraint is required, but it is unsatisfiable in conjunction with the existing constraints.
     UnsatisfiableConstraint,
     /// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
     /// additional details as a string.
     InternalSolverError(&'static str)
 }

 /// The possible error conditions that `Solver::remove_constraint` can fail with.
 #[derive(Debug, Copy, Clone)]
 pub enum RemoveConstraintError {
     /// The constraint specified was not already in the solver, so cannot be removed.
     UnknownConstraint,
     /// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
     /// additional details as a string.
     InternalSolverError(&'static str)
 }

 /// The possible error conditions that `Solver::add_edit_variable` can fail with.
 #[derive(Debug, Copy, Clone)]
 pub enum AddEditVariableError {
     /// The specified variable is already marked as an edit variable in the solver.
     DuplicateEditVariable,
     /// The specified strength was `REQUIRED`. This is illegal for edit variable strengths.
     BadRequiredStrength
 }

 /// The possible error conditions that `Solver::remove_edit_variable` can fail with.
 #[derive(Debug, Copy, Clone)]
 pub enum RemoveEditVariableError {
     /// The specified variable was not an edit variable in the solver, so cannot be removed.
     UnknownEditVariable,
     /// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
     /// additional details as a string.
     InternalSolverError(&'static str)
 }

 /// The possible error conditions that `Solver::suggest_value` can fail with.
 #[derive(Debug, Copy, Clone)]
 pub enum SuggestValueError {
     /// The specified variable was not an edit variable in the solver, so cannot have its value suggested.
     UnknownEditVariable,
     /// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
     /// additional details as a string.
     InternalSolverError(&'static str)
 }

 #[derive(Debug, Copy, Clone)]
 struct InternalSolverError(&'static str);

 pub use solver_impl::Solver;
	//! This crate contains an implementation of the Cassowary constraint solving algorithm, based upon the work by
	//! G.J. Badros et al. in 2001. This algorithm is designed primarily for use constraining elements in user interfaces.
	//! Constraints are linear combinations of the problem variables. The notable features of Cassowary that make it
	//! ideal for user interfaces are that it is incremental (i.e. you can add and remove constraints at runtime
	//! and it will perform the minimum work to update the result) and that the constraints can be violated if
	//! necessary,
	//! with the order in which they are violated specified by setting a "strength" for each constraint.
	//! This allows the solution to gracefully degrade, which is useful for when a
	//! user interface needs to compromise on its constraints in order to still be able to display something.
	//!
	//! ## Constraint syntax
	//!
	//! This crate aims to provide syntax for describing linear constraints as naturally as possible, within
	//! the limitations of Rust's type system. Generally you can write constraints as you would naturally, however
	//! the operator symbol (for greater-than, less-than, equals) is replaced with an instance of the
	//! `WeightedRelation` enum wrapped in "pipe brackets".
	//!
	//! For example, for the constraint
	//! `(a + b) * 2 + c >= d + 1` with strength `s`, the code to use is
	//!
	//! ```ignore
	//! (a + b) * 2.0 + c \|GE(s)\| d + 1.0
	//! ```
	//!
	//! # A simple example
	//!
	//! Imagine a layout consisting of two elements laid out horizontally. For small window widths the elements
	//! should compress to fit, but if there is enough space they should display at their preferred widths. The
	//! first element will align to the left, and the second to the right. For this example we will ignore
	//! vertical layout.
	//!
	//! First we need to include the relevant parts of `cassowary`:
	//!
	//! ```
	//! use cassowary::{ Solver, Variable };
	//! use cassowary::WeightedRelation::*;
	//! use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED };
	//! ```
	//!
	//! And we'll construct some conveniences for pretty printing (which should hopefully be self-explanatory):
	//!
	//! ```ignore
	//! use std::collections::HashMap;
	//! let mut names = HashMap::new();
	//! fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) {
	//! println!("Changes:");
	//! for &(ref var, ref val) in changes {
	//! println!("{}: {}", names[var], val);
	//! }
	//! }
	//! ```
	//!
	//! Let's define the variables required - the left and right edges of the elements, and the width of the window.
	//!
	//! ```ignore
	//! let window_width = Variable::new();
	//! names.insert(window_width, "window_width");
	//!
	//! struct Element {
	//! left: Variable,
	//! right: Variable
	//! }
	//! let box1 = Element {
	//! left: Variable::new(),
	//! right: Variable::new()
	//! };
	//! names.insert(box1.left, "box1.left");
	//! names.insert(box1.right, "box1.right");
	//!
	//! let box2 = Element {
	//! left: Variable::new(),
	//! right: Variable::new()
	//! };
	//! names.insert(box2.left, "box2.left");
	//! names.insert(box2.right, "box2.right");
	//! ```
	//!
	//! Now to set up the solver and constraints.
	//!
	//! ```ignore
	//! let mut solver = Solver::new();
	//! solver.add_constraints(&[window_width \|GE(REQUIRED)\| 0.0, // positive window width
	//! box1.left \|EQ(REQUIRED)\| 0.0, // left align
	//! box2.right \|EQ(REQUIRED)\| window_width, // right align
	//! box2.left \|GE(REQUIRED)\| box1.right, // no overlap
	//! // positive widths
	//! box1.left \|LE(REQUIRED)\| box1.right,
	//! box2.left \|LE(REQUIRED)\| box2.right,
	//! // preferred widths:
	//! box1.right - box1.left \|EQ(WEAK)\| 50.0,
	//! box2.right - box2.left \|EQ(WEAK)\| 100.0]).unwrap();
	//! ```
	//!
	//! The window width is currently free to take any positive value. Let's constrain it to a particular value.
	//! Since for this example we will repeatedly change the window width, it is most efficient to use an
	//! "edit variable", instead of repeatedly removing and adding constraints (note that for efficiency
	//! reasons we cannot edit a normal constraint that has been added to the solver).
	//!
	//! ```ignore
	//! solver.add_edit_variable(window_width, STRONG).unwrap();
	//! solver.suggest_value(window_width, 300.0).unwrap();
	//! ```
	//!
	//! This value of 300 is enough to fit both boxes in with room to spare, so let's check that this is the case.
	//! We can fetch a list of changes to the values of variables in the solver. Using the pretty printer defined
	//! earlier we can see what values our variables now hold.
	//!
	//! ```ignore
	//! print_changes(&names, solver.fetch_changes());
	//! ```
	//!
	//! This should print (in a possibly different order):
	//!
	//! ```ignore
	//! Changes:
	//! window_width: 300
	//! box1.right: 50
	//! box2.left: 200
	//! box2.right: 300
	//! ```
	//!
	//! Note that the value of `box1.left` is not mentioned. This is because `solver.fetch_changes` only lists
	//! changes to variables, and since each variable starts in the solver with a value of zero, any values that
	//! have not changed from zero will not be reported.
	//!
	//! Now let's try compressing the window so that the boxes can't take up their preferred widths.
	//!
	//! ```ignore
	//! solver.suggest_value(window_width, 75.0);
	//! print_changes(&names, solver.fetch_changes);
	//! ```
	//!
	//! Now the solver can't satisfy all of the constraints. It will pick at least one of the weakest constraints to
	//! violate. In this case it will be one or both of the preferred widths. For efficiency reasons this is picked
	//! nondeterministically, so there are two possible results. This could be
	//!
	//! ```ignore
	//! Changes:
	//! window_width: 75
	//! box1.right: 0
	//! box2.left: 0
	//! box2.right: 75
	//! ```
	//!
	//! or
	//!
	//! ```ignore
	//! Changes:
	//! window_width: 75
	//! box2.left: 50
	//! box2.right: 75
	//! ```
	//!
	//! Due to the nature of the algorithm, "in-between" solutions, although just as valid, are not picked.
	//!
	//! In a user interface this is not likely a result we would prefer. The solution is to add another constraint
	//! to control the behaviour when the preferred widths cannot both be satisfied. In this example we are going
	//! to constrain the boxes to try to maintain a ratio between their widths.
	//!
	//! ```
	//! # use cassowary::{ Solver, Variable };
	//! # use cassowary::WeightedRelation::*;
	//! # use cassowary::strength::{ WEAK, MEDIUM, STRONG, REQUIRED };
	//! #
	//! # use std::collections::HashMap;
	//! # let mut names = HashMap::new();
	//! # fn print_changes(names: &HashMap<Variable, &'static str>, changes: &[(Variable, f64)]) {
	//! # println!("Changes:");
	//! # for &(ref var, ref val) in changes {
	//! # println!("{}: {}", names[var], val);
	//! # }
	//! # }
	//! #
	//! # let window_width = Variable::new();
	//! # names.insert(window_width, "window_width");
	//! # struct Element {
	//! # left: Variable,
	//! # right: Variable
	//! # }
	//! # let box1 = Element {
	//! # left: Variable::new(),
	//! # right: Variable::new()
	//! # };
	//! # names.insert(box1.left, "box1.left");
	//! # names.insert(box1.right, "box1.right");
	//! # let box2 = Element {
	//! # left: Variable::new(),
	//! # right: Variable::new()
	//! # };
	//! # names.insert(box2.left, "box2.left");
	//! # names.insert(box2.right, "box2.right");
	//! # let mut solver = Solver::new();
	//! # solver.add_constraints(&[window_width \|GE(REQUIRED)\| 0.0, // positive window width
	//! # box1.left \|EQ(REQUIRED)\| 0.0, // left align
	//! # box2.right \|EQ(REQUIRED)\| window_width, // right align
	//! # box2.left \|GE(REQUIRED)\| box1.right, // no overlap
	//! # // positive widths
	//! # box1.left \|LE(REQUIRED)\| box1.right,
	//! # box2.left \|LE(REQUIRED)\| box2.right,
	//! # // preferred widths:
	//! # box1.right - box1.left \|EQ(WEAK)\| 50.0,
	//! # box2.right - box2.left \|EQ(WEAK)\| 100.0]).unwrap();
	//! # solver.add_edit_variable(window_width, STRONG).unwrap();
	//! # solver.suggest_value(window_width, 300.0).unwrap();
	//! # print_changes(&names, solver.fetch_changes());
	//! # solver.suggest_value(window_width, 75.0);
	//! # print_changes(&names, solver.fetch_changes());
	//! solver.add_constraint(
	//! (box1.right - box1.left) / 50.0 \|EQ(MEDIUM)\| (box2.right - box2.left) / 100.0
	//! ).unwrap();
	//! print_changes(&names, solver.fetch_changes());
	//! ```
	//!
	//! Now the result gives values that maintain the ratio between the sizes of the two boxes:
	//!
	//! ```ignore
	//! Changes:
	//! box1.right: 25
	//! box2.left: 25
	//! ```
	//!
	//! This example may have appeared somewhat contrived, but hopefully it shows the power of the cassowary
	//! algorithm for laying out user interfaces.
	//!
	//! One thing that this example exposes is that this crate is a rather low level library. It does not have
	//! any inherent knowledge of user interfaces, directions or boxes. Thus for use in a user interface this
	//! crate should ideally be wrapped by a higher level API, which is outside the scope of this crate.
	use std::sync::Arc;
	use std::collections::HashMap;
	use std::collections::hash_map::{Entry};

	mod solver_impl;
	mod operators;

	static VARIABLE_ID: ::std::sync::atomic::AtomicUsize = ::std::sync::atomic::ATOMIC_USIZE_INIT;

	/// Identifies a variable for the constraint solver.
	/// Each new variable is unique in the view of the solver, but copying or cloning the variable produces
	/// a copy of the same variable.
	#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
	pub struct Variable(usize);

	impl Variable {
	/// Produces a new unique variable for use in constraint solving.
	pub fn new() -> Variable {
	Variable(VARIABLE_ID.fetch_add(1, ::std::sync::atomic::Ordering::Relaxed))
	}
	}

	/// A variable and a coefficient to multiply that variable by. This is a sub-expression in
	/// a constraint equation.
	#[derive(Copy, Clone, Debug)]
	pub struct Term {
	pub variable: Variable,
	pub coefficient: f64
	}

	impl Term {
	/// Construct a new Term from a variable and a coefficient.
	fn new(variable: Variable, coefficient: f64) -> Term {
	Term {
	variable: variable,
	coefficient: coefficient
	}
	}
	}

	/// An expression that can be the left hand or right hand side of a constraint equation.
	/// It is a linear combination of variables, i.e. a sum of variables weighted by coefficients, plus an optional constant.
	#[derive(Clone, Debug)]
	pub struct Expression {
	pub terms: Vec<Term>,
	pub constant: f64
	}

	impl Expression {
	/// Constructs an expression of the form _n_, where n is a constant real number, not a variable.
	pub fn from_constant(v: f64) -> Expression {
	Expression {
	terms: Vec::new(),
	constant: v
	}
	}
	/// Constructs an expression from a single term. Forms an expression of the form _n x_
	/// where n is the coefficient, and x is the variable.
	pub fn from_term(term: Term) -> Expression {
	Expression {
	terms: vec![term],
	constant: 0.0
	}
	}
	/// General constructor. Each `Term` in `terms` is part of the sum forming the expression, as well as `constant`.
	pub fn new(terms: Vec<Term>, constant: f64) -> Expression {
	Expression {
	terms: terms,
	constant: constant
	}
	}
	/// Mutates this expression by multiplying it by minus one.
	pub fn negate(&mut self) {
	self.constant = -self.constant;
	for t in &mut self.terms {
	t = -t;
	}
	}
	}

	impl From<f64> for Expression {
	fn from(v: f64) -> Expression {
	Expression::from_constant(v)
	}
	}

	impl From<Variable> for Expression {
	fn from(v: Variable) -> Expression {
	Expression::from_term(Term::new(v, 1.0))
	}
	}

	impl From<Term> for Expression {
	fn from(t: Term) -> Expression {
	Expression::from_term(t)
	}
	}

	/// Contains useful constants and functions for producing strengths for use in the constraint solver.
	/// Each constraint added to the solver has an associated strength specifying the precedence the solver should
	/// impose when choosing which constraints to enforce. It will try to enforce all constraints, but if that
	/// is impossible the lowest strength constraints are the first to be violated.
	///
	/// Strengths are simply real numbers. The strongest legal strength is 1,001,001,000.0. The weakest is 0.0.
	/// For convenience constants are declared for commonly used strengths. These are `REQUIRED`, `STRONG`,
	/// `MEDIUM` and `WEAK`. Feel free to multiply these by other values to get intermediate strengths.
	/// Note that the solver will clip given strengths to the legal range.
	///
	/// `REQUIRED` signifies a constraint that cannot be violated under any circumstance. Use this special strength
	/// sparingly, as the solver will fail completely if it find that not all of the `REQUIRED` constraints
	/// can be satisfied. The other strengths represent fallible constraints. These should be the most
	/// commonly used strenghts for use cases where violating a constraint is acceptable or even desired.
	///
	/// The solver will try to get as close to satisfying the constraints it violates as possible, strongest first.
	/// This behaviour can be used (for example) to provide a "default" value for a variable should no other
	/// stronger constraints be put upon it.
	pub mod strength {
	/// Create a constraint as a linear combination of STRONG, MEDIUM and WEAK strengths, corresponding to `a`
	/// `b` and `c` respectively. The result is further multiplied by `w`.
	pub fn create(a: f64, b: f64, c: f64, w: f64) -> f64 {
	(a * w).max(0.0).min(1000.0) * 1_000_000.0 +
	(b * w).max(0.0).min(1000.0) * 1000.0 +
	(c * w).max(0.0).min(1000.0)
	}
	pub const REQUIRED: f64 = 1_001_001_000.0;
	pub const STRONG: f64 = 1_000_000.0;
	pub const MEDIUM: f64 = 1_000.0;
	pub const WEAK: f64 = 1.0;

	/// Clips a strength value to the legal range
	pub fn clip(s: f64) -> f64 {
	s.min(REQUIRED).max(0.0)
	}
	}

	/// The possible relations that a constraint can specify.
	#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
	pub enum RelationalOperator {
	/// `<=`
	LessOrEqual,
	/// `==`
	Equal,
	/// `>=`
	GreaterOrEqual
	}

	impl std::fmt::Display for RelationalOperator {
	fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
	match *self {
	RelationalOperator::LessOrEqual => write!(fmt, "<=") ?,
	RelationalOperator::Equal => write!(fmt, "==") ?,
	RelationalOperator::GreaterOrEqual => write!(fmt, ">=") ?,
	};
	Ok(())
	}
	}

	#[derive(Debug)]
	struct ConstraintData {
	expression: Expression,
	strength: f64,
	op: RelationalOperator
	}

	/// A constraint, consisting of an equation governed by an expression and a relational operator,
	/// and an associated strength.
	#[derive(Clone, Debug)]
	pub struct Constraint(Arc<ConstraintData>);

	impl Constraint {
	/// Construct a new constraint from an expression, a relational operator and a strength.
	/// This corresponds to the equation `e op 0.0`, e.g. `x + y >= 0.0`. For equations with a non-zero
	/// right hand side, subtract it from the equation to give a zero right hand side.
	pub fn new(e: Expression, op: RelationalOperator, strength: f64) -> Constraint {
	Constraint(Arc::new(ConstraintData {
	expression: e,
	op: op,
	strength: strength
	}))
	}
	/// The expression of the left hand side of the constraint equation.
	pub fn expr(&self) -> &Expression {
	&self.0.expression
	}
	/// The relational operator governing the constraint.
	pub fn op(&self) -> RelationalOperator {
	self.0.op
	}
	/// The strength of the constraint that the solver will use.
	pub fn strength(&self) -> f64 {
	self.0.strength
	}
	}

	impl ::std::hash::Hash for Constraint {
	fn hash<H: ::std::hash::Hasher>(&self, hasher: &mut H) {
	use ::std::ops::Deref;
	hasher.write_usize(self.0.deref() as *const _ as usize);
	}
	}

	impl PartialEq for Constraint {
	fn eq(&self, other: &Constraint) -> bool {
	use ::std::ops::Deref;
	self.0.deref() as const _ == other.0.deref() as const _
	}
	}

	impl Eq for Constraint {}

	/// This is part of the syntactic sugar used for specifying constraints. This enum should be used as part of a
	/// constraint expression. See the module documentation for more information.
	pub enum WeightedRelation {
	/// `==`
	EQ(f64),
	/// `<=`
	LE(f64),
	/// `>=`
	GE(f64)
	}
	impl From<WeightedRelation> for (RelationalOperator, f64) {
	fn from(r: WeightedRelation) -> (RelationalOperator, f64) {
	use WeightedRelation::*;
	match r {
	EQ(s) => (RelationalOperator::Equal, s),
	LE(s) => (RelationalOperator::LessOrEqual, s),
	GE(s) => (RelationalOperator::GreaterOrEqual, s),
	}
	}
	}

	/// This is an intermediate type used in the syntactic sugar for specifying constraints. You should not use it
	/// directly.
	pub struct PartialConstraint(Expression, WeightedRelation);

	#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
	enum SymbolType {
	Invalid,
	External,
	Slack,
	Error,
	Dummy
	}

	#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
	struct Symbol(usize, SymbolType);

	impl Symbol {
	fn invalid() -> Symbol { Symbol(0, SymbolType::Invalid) }
	fn type_(&self) -> SymbolType { self.1 }
	}

	#[derive(Clone)]
	struct Row {
	cells: HashMap<Symbol, f64>,
	constant: f64
	}

	fn near_zero(value: f64) -> bool {
	const EPS: f64 = 1E-8;
	if value < 0.0 {
	-value < EPS
	} else {
	value < EPS
	}
	}

	impl Row {
	fn new(constant: f64) -> Row {
	Row {
	cells: HashMap::new(),
	constant: constant
	}
	}
	fn add(&mut self, v: f64) -> f64 {
	self.constant += v;
	self.constant
	}
	fn insert_symbol(&mut self, s: Symbol, coefficient: f64) {
	match self.cells.entry(s) {
	Entry::Vacant(entry) => if !near_zero(coefficient) {
	entry.insert(coefficient);
	},
	Entry::Occupied(mut entry) => {
	*entry.get_mut() += coefficient;
	if near_zero(*entry.get_mut()) {
	entry.remove();
	}
	}
	}
	}

	fn insert_row(&mut self, other: &Row, coefficient: f64) -> bool {
	let constant_diff = other.constant * coefficient;
	self.constant += constant_diff;
	for (s, v) in &other.cells {
	self.insert_symbol(s, v coefficient);
	}
	constant_diff != 0.0
	}

	fn remove(&mut self, s: Symbol) {
	self.cells.remove(&s);
	}

	fn reverse_sign(&mut self) {
	self.constant = -self.constant;
	for (_, v) in &mut self.cells {
	v = -v;
	}
	}

	fn solve_for_symbol(&mut self, s: Symbol) {
	let coeff = -1.0 / match self.cells.entry(s) {
	Entry::Occupied(entry) => entry.remove(),
	Entry::Vacant(_) => unreachable!()
	};
	self.constant *= coeff;
	for (_, v) in &mut self.cells {
	v = coeff;
	}
	}

	fn solve_for_symbols(&mut self, lhs: Symbol, rhs: Symbol) {
	self.insert_symbol(lhs, -1.0);
	self.solve_for_symbol(rhs);
	}

	fn coefficient_for(&self, s: Symbol) -> f64 {
	self.cells.get(&s).cloned().unwrap_or(0.0)
	}

	fn substitute(&mut self, s: Symbol, row: &Row) -> bool {
	if let Some(coeff) = self.cells.remove(&s) {
	self.insert_row(row, coeff)
	} else {
	false
	}
	}
	}

	/// The possible error conditions that `Solver::add_constraint` can fail with.
	#[derive(Debug, Copy, Clone)]
	pub enum AddConstraintError {
	/// The constraint specified has already been added to the solver.
	DuplicateConstraint,
	/// The constraint is required, but it is unsatisfiable in conjunction with the existing constraints.
	UnsatisfiableConstraint,
	/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
	/// additional details as a string.
	InternalSolverError(&'static str)
	}

	/// The possible error conditions that `Solver::remove_constraint` can fail with.
	#[derive(Debug, Copy, Clone)]
	pub enum RemoveConstraintError {
	/// The constraint specified was not already in the solver, so cannot be removed.
	UnknownConstraint,
	/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
	/// additional details as a string.
	InternalSolverError(&'static str)
	}

	/// The possible error conditions that `Solver::add_edit_variable` can fail with.
	#[derive(Debug, Copy, Clone)]
	pub enum AddEditVariableError {
	/// The specified variable is already marked as an edit variable in the solver.
	DuplicateEditVariable,
	/// The specified strength was `REQUIRED`. This is illegal for edit variable strengths.
	BadRequiredStrength
	}

	/// The possible error conditions that `Solver::remove_edit_variable` can fail with.
	#[derive(Debug, Copy, Clone)]
	pub enum RemoveEditVariableError {
	/// The specified variable was not an edit variable in the solver, so cannot be removed.
	UnknownEditVariable,
	/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
	/// additional details as a string.
	InternalSolverError(&'static str)
	}

	/// The possible error conditions that `Solver::suggest_value` can fail with.
	#[derive(Debug, Copy, Clone)]
	pub enum SuggestValueError {
	/// The specified variable was not an edit variable in the solver, so cannot have its value suggested.
	UnknownEditVariable,
	/// The solver entered an invalid state. If this occurs please report the issue. This variant specifies
	/// additional details as a string.
	InternalSolverError(&'static str)
	}

	#[derive(Debug, Copy, Clone)]
	struct InternalSolverError(&'static str);

	pub use solver_impl::Solver;