net.cscott.sdr.calls
Class Breather

java.lang.Object
  net.cscott.sdr.calls.Breather

public class Breather
extends Object

The Breather class contains methods to reassemble and breathe formations.

The insert() method pushes sub-formations into a meta-formation after performing (say) a four person call — ie, starting with a tidal wave, Matcher will pull out two four-person waves as a mini-wave as the meta-formation. We do a crossfire (say) from the mini-waves to get boxes. Now insert(Formation,Map) will shove the boxes into the mini-wave meta-formation to get parallel ocean waves.

The breathe() method is a part of insert() which is useful in its own right: it takes a Formation (or a list of Breather.FormationPieces) and breathes it in or out to normalize the spacing between dancers. For example, after "trailers extend" from boxes, we need to make room for the resulting mini-wave in the center. If the ends then u-turn back and everyone extends again, the formation has to squeeze in again to erase the space.

Theory of breathing

First: identify collisions. Collided dancers are inserted into a miniwave which replaces them in the remainder of the algorithm. Second: resolve overlaps. Dancers which overlap have their boundaries adjusted so that they share a boundary, ideally at the midpoint of the overlap. We now use a mixed integer programming solver to perform an optimal adjustment, keeping handholds and making stars when possible. Third: Sort and order the boundary coordinates, and then allocate space between boundaries so that it is "just enough" to fit the dancers between them. If a dancer spans multiple boundary points, their allocation is divided equally between them. We use linear programming here to find an optimal expansion. Finally, the output formations are relocated so that they are centered between their new boundaries.

Version:

$Id: Breather.java,v 1.10 2006-10-30 22:09:29 cananian Exp $

Author:

C. Scott Ananian

Nested Class Summary

static class

Breather.FormationPiece A component to be breathed into a complete formation.

Method Summary

static Formation	breathe(Formation f) Create a canonical formation by compressing the given one.
static Formation	breathe(List<Breather.FormationPiece> pieces) Take a set of input formation pieces and substitute the given output formation pieces for them, breathing the result together so that the formation is compact.
static Formation	insert(Formation meta, Map<Dancer,Formation> components) Insert formations into a meta-formation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

insert

public static Formation insert(Formation meta,
                               Map<Dancer,Formation> components)

Insert formations into a meta-formation. This reassembles the formation after we've decomposed it into (say) boxes to do a four-person call.

Tests:

Insert COUPLEs, then TANDEMs into a RH_OCEAN_WAVE. Then, for a challenge, insert TANDEMs into a DIAMOND to give a t-bone column:

js> FormationList = FormationList.js(this); undefined;
js> function xofy(meta, f) {
  >   var i=0
  >   var m=new java.util.LinkedHashMap()
  >   for (d in Iterator(meta.sortedDancers())) {
  >     var mm=new java.util.LinkedHashMap()
  >     for (dd in Iterator(f.sortedDancers())) {
  >       mm.put(dd, StandardDancer.values()[i++])
  >     }
  >     m.put(d, f.map(mm))
  >     print(m.get(d).toStringDiagram())
  >   }
  >   return m
  > }
js> meta = FormationList.RH_OCEAN_WAVE ; meta.toStringDiagram()
^    v    ^    v
js> m = xofy(meta, FormationList.COUPLE); undefined
1B^  1G^
2B^  2G^
3B^  3G^
4B^  4G^
js> Breather.insert(meta, m).toStringDiagram()
1B^  1G^  2Gv  2Bv  3B^  3G^  4Gv  4Bv
js> m = xofy(meta, FormationList.TANDEM); undefined
1B^

1G^
2B^

2G^
3B^

3G^
4B^

4G^
js> Breather.insert(meta, m).toStringDiagram()
1B^  2Gv  3B^  4Gv

1G^  2Bv  3G^  4Bv
js> meta = FormationList.RH_DIAMOND ; meta.toStringDiagram("|", Formation.dancerNames)
|  >
|
|^    v
|
|  <
js> m = xofy(meta, FormationList.TANDEM); undefined
1B^

1G^
2B^

2G^
3B^

3G^
4B^

4G^
js> Breather.insert(meta, m).toStringDiagram()
1G>  1B>

2B^  3Gv

2G^  3Bv

4B<  4G<

breathe

public static Formation breathe(Formation f)

Create a canonical formation by compressing the given one. This is just an invokation of breathe(List) with trivial Breather.FormationPieces consisting of a single dancer each.

Tests:

From couples back to back, step out; then breathe in:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.BACK_TO_BACK_COUPLES ; f.toStringDiagram()
^    ^

v    v
js> for (d in Iterator(f.dancers())) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE, false));
  > }; f.toStringDiagram()
^    ^



v    v
js> Breather.breathe(f).toStringDiagram()
^    ^

v    v

From facing couples, take half a step in; breathe out:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.FACING_COUPLES ; f.toStringDiagram()
v    v

^    ^
js> for (d in Iterator(f.dancers())) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE_HALF, false));
  > }; f.toStringDiagram()
v    v
^    ^
js> Breather.breathe(f).toStringDiagram()
v    v

^    ^

From single three quarter tag, step out; then breathe in:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.RH_SINGLE_THREE_QUARTER_TAG ; f.toStringDiagram()
  ^

^    v

  v
js> for (d in Iterator(f.tagged(TaggedFormation.Tag.END))) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE, false));
  > }; f.toStringDiagram()
  ^


^    v


  v
js> Breather.breathe(f).toStringDiagram()
  ^

^    v

  v

From single quarter tag, take half a step in; breathe out:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.RH_SINGLE_QUARTER_TAG ; f.toStringDiagram()
  v

^    v

  ^
js> for (d in Iterator(f.tagged(TaggedFormation.Tag.END))) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE, false));
  > }; f.toStringDiagram()
  v
^    v
  ^
js> Breather.breathe(f).toStringDiagram()
  v

^    v

  ^

From right-hand diamond, take half a step in; breathe out:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.RH_DIAMOND ; f.toStringDiagram("|", Formation.dancerNames)
|  >
|
|^    v
|
|  <
js> for (d in Iterator(f.tagged(TaggedFormation.Tag.POINT))) {
  >   f=f.move(d,f.location(d).sideStep(Fraction.valueOf(1,2), true));
  > }; f.toStringDiagram("|", Formation.dancerNames)
|  >
|
|^    v
|  <
js> Breather.breathe(f).toStringDiagram("|", Formation.dancerNames)
|  >
|
|^    v
|
|  <

From right-hand diamond, take 1 1/2 steps in; breathe out to stars:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.RH_DIAMOND ; f.toStringDiagram("|", Formation.dancerNames)
|  >
|
|^    v
|
|  <
js> for (d in Iterator(f.tagged(TaggedFormation.Tag.POINT))) {
  >   f=f.move(d,f.location(d).sideStep(Fraction.valueOf(3,2), true));
  > }; f.toStringDiagram("|", Formation.dancerNames)
|  >
|^ <  v
js> Breather.breathe(f).toStringDiagram("|", Formation.dancerNames)
|  >
|^    v
|  <

Facing dancers step forward; resolve collision.

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.FACING_DANCERS ; f.toStringDiagram()
v

^
js> for (d in Iterator(f.dancers())) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE, false));
  > }; f
net.cscott.sdr.calls.TaggedFormation[
  location={<phantom@7f>=0,0,n, <phantom@7e>=0,0,s}
  selected=[<phantom@7f>, <phantom@7e>]
  tags={<phantom@7f>=TRAILER, <phantom@7e>=TRAILER}
]
js> Breather.breathe(f).toStringDiagram()
^    v

Facing couples step forward with a left-shoulder pass; resolve collision and breathe.

js> importPackage(net.cscott.sdr.util) // for Fraction
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.FACING_COUPLES ; f.toStringDiagram()
v    v

^    ^
js> for (d in Iterator(f.dancers())) {
  >   f=f.move(d,f.location(d).forwardStep(Fraction.ONE, false).addFlags(Position.Flag.PASS_LEFT));
  > }; undefined
js> Breather.breathe(f).toStringDiagram()
v    ^    v    ^

From EvalPrim test:

js> importPackage(net.cscott.sdr.util) // for Fraction
js> m = new java.util.HashMap(); undefined
js> function di(p) { m.put(new PhantomDancer(), p); }
js> di(new Position(Fraction.mONE, Fraction.ONE, ExactRotation.NORTH));
js> di(new Position(Fraction.mONE, Fraction.ZERO, ExactRotation.NORTH));
js> di(new Position(Fraction.ONE, Fraction.ZERO, ExactRotation.SOUTH));
js> di(new Position(Fraction.ONE, Fraction.mONE, ExactRotation.SOUTH));
js> f = new Formation(m); f.toStringDiagram();
^
^    v
     v
js> [f.location(d) for (d in Iterator(f.sortedDancers()))].join('  ')
-1,1,n  -1,0,n  1,0,s  1,-1,s
js> ff = Breather.breathe(f); ff.toStringDiagram()
^

^    v

     v
js> [ff.location(d) for (d in Iterator(ff.sortedDancers()))].join('  ')
-1,2,n  -1,0,n  1,0,s  1,-2,s

From 'do half of an ends cross run':

js> importPackage(net.cscott.sdr.util) // for Fraction
js> m = new java.util.HashMap(); undefined
js> SD = StandardDancer; undefined
js> m.put(SD.COUPLE_4_GIRL, new Position(Fraction.valueOf(-5,2), Fraction.ONE, ExactRotation.WEST)); undefined
js> m.put(SD.COUPLE_1_GIRL, new Position(Fraction.valueOf(3,2), Fraction.ONE, ExactRotation.WEST)); undefined
js> m.put(SD.COUPLE_4_BOY, new Position(Fraction.valueOf(-3), Fraction.ZERO, ExactRotation.NORTH, Position.Flag.ROLL_RIGHT)); undefined
js> m.put(SD.COUPLE_3_BOY, new Position(Fraction.mONE, Fraction.ZERO, ExactRotation.SOUTH, Position.Flag.ROLL_RIGHT)); undefined
js> m.put(SD.COUPLE_1_BOY, new Position(Fraction.ONE, Fraction.ZERO, ExactRotation.NORTH, Position.Flag.ROLL_RIGHT)); undefined
js> m.put(SD.COUPLE_2_BOY, new Position(Fraction.valueOf(3), Fraction.ZERO, ExactRotation.SOUTH, Position.Flag.ROLL_RIGHT)); undefined
js> m.put(SD.COUPLE_3_GIRL, new Position(Fraction.valueOf(-3,2), Fraction.mONE, ExactRotation.EAST)); undefined
js> m.put(SD.COUPLE_2_GIRL, new Position(Fraction.valueOf(5,2), Fraction.mONE, ExactRotation.EAST)); undefined
js> f = new Formation(m); f.toStringDiagram();
 4G<       1G<
4B^  3Bv  1B^  2Bv
   3G>       2G>
js> [f.location(d) for (d in Iterator(f.sortedDancers()))].join('  ')
-2 1/2,1,w  1 1/2,1,w  -3,0,n,[ROLL_RIGHT]  -1,0,s,[ROLL_RIGHT]  1,0,n,[ROLL_RIGHT]  3,0,s,[ROLL_RIGHT]  -1 1/2,-1,e  2 1/2,-1,e
js> ff = Breather.breathe(f); ff.toStringDiagram()
 4G<       1G<

4B^  3Bv  1B^  2Bv

   3G>       2G>
js> [ff.location(d) for (d in Iterator(ff.sortedDancers()))].join('  ')
-2 1/3,2,w  1 2/3,2,w  -3,0,n,[ROLL_RIGHT]  -1,0,s,[ROLL_RIGHT]  1,0,n,[ROLL_RIGHT]  3,0,s,[ROLL_RIGHT]  -1 2/3,-2,e  2 1/3,-2,e

breathe

public static Formation breathe(List<Breather.FormationPiece> pieces)

Take a set of input formation pieces and substitute the given output formation pieces for them, breathing the result together so that the formation is compact. (The map giving the correspondence between dancers in the new formation and the input formations is given by the individual Breather.FormationPiece objects.) We also resolve collisions to right or left hands, depending on whether the pass-left flag is set for the Positions involved.

Tests:

Triangle point breathes to center of the base:

js> importPackage(net.cscott.sdr.util)
js> FormationList = FormationList.js(this); undefined;
js> f2 = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_2_BOY, Position.getGrid(1,-1,"n")),
  >         Tools.p(StandardDancer.COUPLE_2_GIRL, Position.getGrid(3,-1,"n"))))
net.cscott.sdr.calls.Formation[
  location={COUPLE 2 BOY=1,-1,n, COUPLE 2 GIRL=3,-1,n}
  selected=[COUPLE 2 BOY, COUPLE 2 GIRL]
]
js> f2.toStringDiagram()
 2B^  2G^
js> fp2 = new Breather.FormationPiece(f2, FormationList.RH_MINIWAVE); undefined
js> // point on far side
js> f1 = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_1_BOY, Position.getGrid(3,1,"e"))))
net.cscott.sdr.calls.Formation[
  location={COUPLE 1 BOY=3,1,e}
  selected=[COUPLE 1 BOY]
]
js> fp1 = new Breather.FormationPiece(f1, FormationList.SINGLE_DANCER); undefined
js> Breather.breathe(Tools.l(fp1, fp2)).toStringDiagram()
    ^

   ^    v
js> // now just slightly off-center
js> f1 = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_1_BOY, Position.getGrid(1,1,"e")
  >                                    .forwardStep(Fraction.ONE_HALF, false))))
net.cscott.sdr.calls.Formation[
  location={COUPLE 1 BOY=1 1/2,1,e}
  selected=[COUPLE 1 BOY]
]
js> fp1 = new Breather.FormationPiece(f1, FormationList.SINGLE_DANCER); undefined
js> Breather.breathe(Tools.l(fp1, fp2)).toStringDiagram()
    ^

   ^    v
js> // point butting up against centerline
js> // NOTE doesn't float to center.  Is this correct?
js> f1 = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_1_BOY, Position.getGrid(1,1,"e"))))
net.cscott.sdr.calls.Formation[
  location={COUPLE 1 BOY=1,1,e}
  selected=[COUPLE 1 BOY]
]
js> fp1 = new Breather.FormationPiece(f1, FormationList.SINGLE_DANCER); undefined
js> Breather.breathe(Tools.l(fp1, fp2)).toStringDiagram()
   ^

   ^    v

Middle of a run, runner breathes out slightly to make room:

js> importPackage(net.cscott.sdr.util)
js> f = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_2_BOY, Position.getGrid(0,0,"n")),
  >         Tools.p(StandardDancer.COUPLE_2_GIRL, Position.getGrid(0,1,"e"))))
net.cscott.sdr.calls.Formation[
  location={COUPLE 2 GIRL=0,1,e, COUPLE 2 BOY=0,0,n}
  selected=[COUPLE 2 GIRL, COUPLE 2 BOY]
]
js> f.toStringDiagram()
2G>
2B^
js> f = Breather.breathe(f)
net.cscott.sdr.calls.Formation[
  location={COUPLE 2 GIRL=0,2,e, COUPLE 2 BOY=0,0,n}
  selected=[COUPLE 2 GIRL, COUPLE 2 BOY]
]
js> f.toStringDiagram()
2G>

2B^

Same thing with more dancers:

js> importPackage(net.cscott.sdr.util)
js> f = new Formation(Tools.m(
  >         Tools.p(StandardDancer.COUPLE_3_BOY, Position.getGrid(-3,1,"n")),
  >         Tools.p(StandardDancer.COUPLE_4_GIRL,Position.getGrid(-3,0,"w")),
  >         Tools.p(StandardDancer.COUPLE_3_GIRL,Position.getGrid(-1,1,"e")),
  >         Tools.p(StandardDancer.COUPLE_4_BOY, Position.getGrid(-1,0,"s")),
  >         Tools.p(StandardDancer.COUPLE_2_BOY, Position.getGrid(1,1,"n")),
  >         Tools.p(StandardDancer.COUPLE_1_GIRL,Position.getGrid(1,0,"w")),
  >         Tools.p(StandardDancer.COUPLE_2_GIRL,Position.getGrid(3,1,"e")),
  >         Tools.p(StandardDancer.COUPLE_1_BOY, Position.getGrid(3,0,"s")))
  >     ).recenter();
net.cscott.sdr.calls.Formation[
  location={COUPLE 3 BOY=-3,1/2,n, COUPLE 3 GIRL=-1,1/2,e, COUPLE 2 BOY=1,1/2,n, COUPLE 2 GIRL=3,1/2,e, COUPLE 4 GIRL=-3,-1/2,w, COUPLE 4 BOY=-1,-1/2,s, COUPLE 1 GIRL=1,-1/2,w, COUPLE 1 BOY=3,-1/2,s}
  selected=[COUPLE 3 BOY, COUPLE 3 GIRL, COUPLE 2 BOY, COUPLE 2 GIRL, COUPLE 4 GIRL, COUPLE 4 BOY, COUPLE 1 GIRL, COUPLE 1 BOY]
]
js> f.toStringDiagram()
3B^  3G>  2B^  2G>
4G<  4Bv  1G<  1Bv
js> f = Breather.breathe(f)
net.cscott.sdr.calls.Formation[
  location={COUPLE 3 BOY=-3,1,n, COUPLE 3 GIRL=-1,1,e, COUPLE 2 BOY=1,1,n, COUPLE 2 GIRL=3,1,e, COUPLE 4 GIRL=-3,-1,w, COUPLE 4 BOY=-1,-1,s, COUPLE 1 GIRL=1,-1,w, COUPLE 1 BOY=3,-1,s}
  selected=[COUPLE 3 BOY, COUPLE 3 GIRL, COUPLE 2 BOY, COUPLE 2 GIRL, COUPLE 4 GIRL, COUPLE 4 BOY, COUPLE 1 GIRL, COUPLE 1 BOY]
]
js> f.toStringDiagram()
3B^  3G>  2B^  2G>

4G<  4Bv  1G<  1Bv