using System;

using System.Collections.Generic;

​

public class TArray<T> : List<T>{

}

​

public class FVector {

    public float X, Y, Z;

    public FVector( float x, float y, float z ){

        X = x;

        Y = y;

        Z = z;

    }

    public string Print()  {

        return X + "," + Y + "," + Z;

    }

}

​

public static class Ext {

    public static int Num( this TArray<FVector> array ){

        return array.Count;

    }

    public static int Num( this TArray<int> array ){

        return array.Count;

    }

    public static float EaseInOutQuad( float t, float b , float c, float d ) {

        if ((t/=d/2) < 1) return c/2*t*t + b;

        return -c/2 * ((--t)*(t-2) - 1) + b;

    }

    public static float EaseNone(float t,float b , float c, float d) {

        return c*t/d + b;

    }

}

​

​

public class Program

{

    static void Dlog( string log ){

        Console.WriteLine( log );

    }

    void Print( TArray<FVector> Locs, bool showIdx = false ){

        string str = "";

        if( showIdx ){

            for( int i = 0, len = Locs.Num(); i < len; i++ ) {

                str += ( "[" + i.ToString() + "]" ).PadLeft(4, ' ') + " ";

            }

            Console.WriteLine( str );

​

            str = "";

        }

        for( int i = 0, len = Locs.Num(); i < len; i++ ) {

            FVector Loc = Locs[i];

            str += Loc.Z.ToString().PadLeft(3, ' ') + ", ";

        }

        Console.WriteLine( str );

    }

    void FindPeaks( TArray<FVector> Locs, out float MaxZ, out int MaxCnt, out TArray<int> Indexes ) {

        // first, find our peaks

        MaxZ = 0f;

        Indexes = new TArray<int>();

        if( Locs.Num() < 3 ) {

            MaxCnt = 0;

            return;

        }

        for( int i = 1, len = Locs.Num()-1; i< len; i++ ) {

            if( MaxZ < Locs[i].Z ) {

                MaxZ = Locs[i].Z;   // update our max z

                Indexes.Clear();

                Indexes.Add( i );   // remember our indexes

            } else if( MaxZ == Locs[i].Z ) {    // the same?

                Indexes.Add( i );   // remember our indexes

            }

        }

        MaxCnt = Indexes.Num();

        Dlog( "MaxZ("+MaxZ+"), MaxCnt("+MaxCnt+"), idx("+ String.Join( ", ", Indexes ) +")" );

    }

    void FlattenPeaks( TArray<FVector> Locs, TArray<int>Indexes, float MaxZ, int MaxCnt ){

        string dbgStr = "\n *** work on our peaks ***\nchanging idxes ";

        //if we have multiple peaks, flatten whatever is in between

        // then we can work from front-to-1stPeak and back-to-lastPeak.

        for( int idx = Indexes[0]+1, klen = Indexes[MaxCnt-1]; idx < klen; idx++ ){

            Locs[idx].Z = MaxZ;

            dbgStr += idx + ", ";

        }

        Dlog( dbgStr + " to " + MaxZ );

        Print( Locs  );

    }

    void WorkOnTheSlope( TArray<FVector> Locs, TArray<int> workingIdxes ){

        int len = Locs.Num();

        float SPeak = 0;    // start peak

        int idxesLen = workingIdxes.Num();

        string dbgStr = "\n *** work on our hills ***\nidxes: ";

        for( int wi = 0; wi < idxesLen; wi++ ) {

            dbgStr += workingIdxes[wi] + ", ";

        }

        Dlog( dbgStr );

        for( int wi = 0; wi < idxesLen-1; wi++ ) {

            int nxtWi = wi+1;

            int i = workingIdxes[wi];

            int nxtI = workingIdxes[nxtWi];

            float diff = Locs[nxtI].Z - Locs[i].Z;

​

            if( 0 <= diff ) {

                Dlog( "["+i+"]"+ Locs[i].Z.ToString().PadLeft(2, ' ') +" -> ["+nxtI+"]" + Locs[nxtI].Z.ToString().PadLeft(2, ' ')  + "; diff: " + diff );

            } else if( diff < 0 ) { // a downhill?

                Dlog( "["+i+"]"+ Locs[i].Z.ToString().PadLeft(2, ' ') +" -> ["+nxtI+"]" + Locs[nxtI].Z.ToString().PadLeft(2, ' ')  + "; diff: " + diff + "; a downhill" );

                SPeak = Locs[i].Z;  // store currentZ for later use

​

                for( int wj = nxtWi; wj < idxesLen; wj++ ) { // from nxtI all the way till the end

                    //int nxtWj = wj+1;

                    int j = workingIdxes[wj];

                    if( SPeak < Locs[j].Z ) {   // found our next peak

                        float EPeak = Locs[j].Z;    // end peak

                        float div = wj-wi;  // for subtraction

                        Dlog( "\t["+j+"] " + Locs[j].Z + " <- this is our peak, div: " + div );

                        wi = wj-1;  // skip

​

                        for( int wk = nxtWi; wk < wj; wk++ ) { // from nxtI all the way till the end

                            int k = workingIdxes[wk];

                            float newZ = SPeak + (EPeak-SPeak) * (float)(wk+1-nxtWi) / div ;

                            Dlog( "\t\tset ["+k+"] " + Locs[k].Z + " to " + newZ + "; alpha("+((wk+1-nxtWi) / div)+")" );

                            Locs[k].Z = newZ;

                        }

                        break;

                    } else {

                        Dlog( "\t["+j+"] " + Locs[j].Z + " <- nah, current peak is " + SPeak );

                    }

                }

            }

        }

    }

    bool IsEndZHigherThanMaxZ( TArray<FVector> Locs, int len, float MaxZ, float EndZ ){

        if( MaxZ < EndZ ){  // EndZ is higher

            float div = len-1;

            float SZ = Locs[0].Z;

            float EZ = Locs[(int)div].Z;

​

            string dbgStr = "\n *** just uphill ***\npeak("+MaxZ+") is lower than our endZ("+EndZ+"); SZ("+SZ+"), EZ("+EZ+"), div("+div+")";

​

            for( int i = 1; i < len-1; i++ ) {

                dbgStr += "\n["+i+"] " + Locs[i].Z.ToString().PadLeft( 3, ' ' ) + " ratio("+i+"/"+div+")";

​

                //Locs[i].Z = SZ + (EZ-SZ) * (float)i / div;

                //Locs[i].Z = Ext.EaseNone( i, SZ, EZ-SZ, div );

                Locs[i].Z = Ext.EaseInOutQuad( i, SZ, EZ-SZ, div );

                dbgStr += " -> " + Locs[i].Z;

            }

​

            Dlog( dbgStr );

            Print( Locs );

            return true;

        }

        return false;

    }

    TArray<float> Calc( float headLen, float tailLen, float midLen, float totalLen ) {

        if( totalLen <= ( headLen + tailLen ) / 2f ){   // too small

            Dlog( "totalLen("+totalLen+") <= ( headLen + tailLen ) / 2f; " + ( (headLen + tailLen)/2f ) + ")" );

            return new TArray<float>() {

                totalLen

            };

        }

        float halfHdeadLen = headLen / 2f;

        float halfTaildLen = tailLen / 2f;

        TArray<float> dist = new TArray<float>();

        dist.Add( headLen / 2f );

        float _ttlLen = totalLen - headLen / 2f;

        return dist;

    }

    public void Main()

    {

        Calc( 2, 2, 4, 1.5f );

        Calc( 2, 2, 4, 10 );

        TArray<FVector> Locs = new TArray<FVector>();

        if( true ) {    // dn hill

            Locs.Add( new FVector( 0, 0, 8 ) );

            Locs.Add( new FVector( 0, 0, 5.5f ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 2.4f ) );

            Locs.Add( new FVector( 0, 0, 2.3f ) );

            Locs.Add( new FVector( 0, 0, 2.2f ) );

            Locs.Add( new FVector( 0, 0, 2 ) );

            Locs.Add( new FVector( 0, 0, 1 ) );

        } else if( true ) { // dn hill, 1 peak

            Locs.Add( new FVector( 0, 0, 15 ) );

            Locs.Add( new FVector( 0, 0, 17 ) );

            Locs.Add( new FVector( 0, 0, 13 ) );

            Locs.Add( new FVector( 0, 0, 14 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 7 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 10 ) );

            Locs.Add( new FVector( 0, 0, 3 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 1 ) );

        } else if( true ) { // dn hill, 2 or 3 peaks

            Locs.Add( new FVector( 0, 0, 15 ) );

            Locs.Add( new FVector( 0, 0, 17 ) );

            Locs.Add( new FVector( 0, 0, 13 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 9 ) );

            Locs.Add( new FVector( 0, 0, 8 ) );

            if( true ) {

                Locs.Add( new FVector( 0, 0, 20 ) );

                Locs.Add( new FVector( 0, 0, 10 ) );

                Locs.Add( new FVector( 0, 0, 9 ) );

                Locs.Add( new FVector( 0, 0, 8 ) );

            }

            Locs.Add( new FVector( 0, 0, 7 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 14 ) );

            Locs.Add( new FVector( 0, 0, 11 ) );

            Locs.Add( new FVector( 0, 0, 10 ) );

            Locs.Add( new FVector( 0, 0, 4 ) );

            Locs.Add( new FVector( 0, 0, 6.7f ) );

            Locs.Add( new FVector( 0, 0, 6 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 4 ) );

            Locs.Add( new FVector( 0, 0, 7 ) );

            Locs.Add( new FVector( 0, 0, 1 ) );

        } else if( true ){  // up hill

            Locs.Add( new FVector( 0, 0, 1 ) );

            Locs.Add( new FVector( 0, 0, 2 ) );

            Locs.Add( new FVector( 0, 0, 2.2f ) );

            Locs.Add( new FVector( 0, 0, 2.3f ) );

            Locs.Add( new FVector( 0, 0, 2.4f ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 5.5f ) );

            Locs.Add( new FVector( 0, 0, 8 ) );

        } else if( true ) { // up hill, 1 peak

            Locs.Add( new FVector( 0, 0, 1 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 3 ) );

            Locs.Add( new FVector( 0, 0, 10 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 7 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 13 ) );

            Locs.Add( new FVector( 0, 0, 17 ) );

            Locs.Add( new FVector( 0, 0, 15 ) );

        } else if( true ) { // up hill, 2 or 3 peaks

            Locs.Add( new FVector( 0, 0, 0 ) );

            Locs.Add( new FVector( 0, 0, 7 ) );

            Locs.Add( new FVector( 0, 0, 4 ) );

            Locs.Add( new FVector( 0, 0, 5 ) );

            Locs.Add( new FVector( 0, 0, 8 ) );

            Locs.Add( new FVector( 0, 0, 4 ) );

            Locs.Add( new FVector( 0, 0, 10 ) );

            Locs.Add( new FVector( 0, 0, 11 ) );

            Locs.Add( new FVector( 0, 0, 14 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 7 ) );

            if( true ) {

                Locs.Add( new FVector( 0, 0, 8 ) );

                Locs.Add( new FVector( 0, 0, 9 ) );

                Locs.Add( new FVector( 0, 0, 10 ) );

                Locs.Add( new FVector( 0, 0, 20 ) );

            }

            Locs.Add( new FVector( 0, 0, 8 ) );

            Locs.Add( new FVector( 0, 0, 9 ) );

            Locs.Add( new FVector( 0, 0, 20 ) );

            Locs.Add( new FVector( 0, 0, 13 ) );

            Locs.Add( new FVector( 0, 0, 17 ) );

            Locs.Add( new FVector( 0, 0, 15 ) );

        }

        Print( Locs, true );

        int len = Locs.Num();

        float Elevation = Locs[len-1].Z - Locs[0].Z;        

        if( Elevation == 0 ) {

            Dlog( "Elevation: " + Elevation + "; flat" );

        } else if( 0 < Elevation ){ // heading up, uphill

            Dlog( "Elevation: " + Elevation + "; heading up" );

            float MaxZ = 0.0f;

            int MaxCnt;

            TArray<int> Indexes;

            // 1. first, find our peaks

            FindPeaks( Locs, out MaxZ, out MaxCnt, out Indexes );

            // up hill but maxZ is lower?

            if( IsEndZHigherThanMaxZ( Locs, len, MaxZ, Locs[len-1].Z ) ) {

                return;

            }

            if( MaxCnt == 0 ) { // wait, a flat surface?

​

            } else if( MaxCnt == 1 ) {  //if we only have 1 peak, we can work our way from front-to-peak and back-to-peak

                TArray<int>frontWorkingIdx = new TArray<int>();

                for( int i = 0; i <= Indexes[0]; i++ ) {

                    frontWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, frontWorkingIdx );

                Print( Locs  );

                TArray<int>backWorkingIdx = new TArray<int>();

                for( int i = len-1; Indexes[Indexes.Num()-1] <= i; i-- ) {

                    backWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, backWorkingIdx );

            } else {

                FlattenPeaks( Locs, Indexes, MaxZ, MaxCnt );

                TArray<int>frontWorkingIdx = new TArray<int>();

                for( int i = 0; i <= Indexes[0]; i++ ) {

                    frontWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, frontWorkingIdx );

                Print( Locs  );

                TArray<int>backWorkingIdx = new TArray<int>();

                for( int i = len-1; Indexes[Indexes.Num()-1] <= i; i-- ) {

                    backWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, backWorkingIdx );

            }

            //is maxZ lower than startPt? all the way downhill then

            //Dictionary<FVector, int> LocIdxDict = new Dictionary<FVector, int>();

        } else { // heading dn, dnhill

            Dlog( "Elevation: " + Elevation + "; heading dn" );

            float MaxZ = 0.0f;

            int MaxCnt;

            TArray<int> Indexes;

            // 1. first, find our peaks

            FindPeaks( Locs, out MaxZ, out MaxCnt, out Indexes );

            // dn hill but maxZ is lower?

            if( IsEndZHigherThanMaxZ( Locs, len, MaxZ, Locs[0].Z ) ) {

                return;

            }

            if( MaxCnt == 0 ) { // wait, a flat surface?

​

            } else if( MaxCnt == 1 ) {  //if we only have 1 peak, we can work our way from front-to-peak and back-to-peak

                TArray<int>frontWorkingIdx = new TArray<int>();

                for( int i = 0; i <= Indexes[0]; i++ ) {

                    frontWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, frontWorkingIdx );

                Print( Locs  );

                TArray<int>backWorkingIdx = new TArray<int>();

                for( int i = len-1; Indexes[Indexes.Num()-1] <= i; i-- ) {

                    backWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, backWorkingIdx );

            } else {

                FlattenPeaks( Locs, Indexes, MaxZ, MaxCnt );

                TArray<int>frontWorkingIdx = new TArray<int>();

                for( int i = 0; i <= Indexes[0]; i++ ) {

                    frontWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, frontWorkingIdx );

                Print( Locs  );

                TArray<int>backWorkingIdx = new TArray<int>();

                for( int i = len-1; Indexes[Indexes.Num()-1] <= i; i-- ) {

                    backWorkingIdx.Add( i );

                }

                WorkOnTheSlope( Locs, backWorkingIdx );

            }

        }

        Dlog( "------------------" );

        Print( Locs  );

    }

}