[PHP] Array mergen en waardes tussendoor/invoegen

[Xanland]

Heren/Raketgeleerden,

Al een ruime tijd ben ik bezig met een website, soms weer even actief - soms weer even niet, met behulp van MySQL database in combinatie met PHP. Hierbij heb ik onder andere een hele grote en lange lijst van haltes van een bepaalde buslijn (ja, die data is legaal openbaar), tot zover appeltje eitje en kan ik zien hoe laat een bepaalde lijn een halte passeert etc etc.

Nu komt het fijne; een bepaalde rit kan nog weleens een andere route rijden waarbij er een verschil van haltes is. Nu is mijn bedoeling om één lijst van alle haltes te laten zien waar de tijden naast staan van de verschillende routes/afwijkingen. Komt die bepaalde rit niet langs halte x, maar wel halte y dan staat er respectievelijk een - en een bepaalde tijd.
Op dit moment laat ik steeds "halte - tijd" zien waarbij dus de lijst haltes en tijden iets langer of korter kan zijn dan de standaardritten.

Klein voorbeeldje hoe het er nu uit ziet:

code:

Klaasstraat, Zeveren = 08:00
Janstraat, Lutseren  = 08:15
Pietstraat, Treleren = 08:30

Klaasstraat, Zeveren = 08:30
Janstraat, Lutseren  = 08:45
Henkstraat, Lutseren = 08:50
Pietstraat, Treleren = 09:00

Klaasstraat, Zeveren = 09:00
Ambtstraat, Lutseren = 09:17
Pietstraat, Treleren = 09:30

Waar ik naar toe zou willen:

code:

Klaasstraat, Zeveren = 08:00 | 08:30 | 09:00
Ambtstraat, Lutseren = --:-- | --:-- | 09:17
Janstraat, Lutseren  = 08:15 | 08:45 | --:--
Henkstraat, Lutseren = --:-- | 08:50 | --:--
Pietstraat, Treleren = 08:30 | 09:00 | 09:30

Valkuil:
Dit lijkt inderdaad makkelijk om te zeggen: "Hé, maar dan gebruik je toch die tweede lijst"? Nee, dat kan dus helaaas niet.

Heb mijzelf hier al meerdere keren op stukgezocht en mergen van complete array's enzoverder. Het punt met zoeken is dat ik eigenlijk slecht weet waar ik op moet zoeken behalve 'php array merge'. Maar ik mis het woord om wat specifieker te kunnen zoeken, want met zomaar mergen komen de nieuwste dingen achteraan.
Dat moet ik niet hebben aangezien het wel op bepaalde plekken ertussen moeten komen. Iemand die mij hiermee kan helpen?

[GlowMouse]

Het makkelijkste hier is om met één route te beginnen, en dan de haltes van andere routes in te voegen. Bijvoorbeeld, om de eerste twee routes samen te voegen, wil je de eerste route opknippen tussen de Janstraat en de Pietstraat, en daartussenin de Henkstraat plaatsen. Dit kan met array_merge en array_slice.

[Tribits]

GlowMouse schreef op zaterdag 26 juli 2014 @ 01:03:
Het makkelijkste hier is om met één route te beginnen, en dan de haltes van andere routes in te voegen. Bijvoorbeeld, om de eerste twee routes samen te voegen, wil je de eerste route opknippen tussen de Janstraat en de Pietstraat, en daartussenin de Henkstraat plaatsen. Dit kan met array_merge en array_slice.

Het tussenvoegen van een element in een array moet nog wel lukken maar ik zie in het gegeven voorbeeld niet hoe de volgorde van de haltes vastgesteld moet worden. De 'Ambtstraat' duikt op tussen de 'Klaasstraat' en de 'Pietstraat' maar op basis van de huidige gegevens kan je applicatie niet bepalen of die voor, tussen of na de 'Janstraat' en de 'Henkstraat' moet komen.

Ik denk dat je naar een manier moet zoeken om een lijstje met alle mogelijke haltes voor een bepaalde route in de juiste volgorde uit de database te krijgen en op basis daarvan de routetabel met tijden op te bouwen. Als dat niet mogelijk is dan mist je database feitelijk de informatie die nodig is om de getoonde tabel op te bouwen.

[ValHallASW]

Als we er even uitgaan dat
1) de sorteervolgorde consistent is, en je dus nooit hebt dat de ene bus K->J rijdt en de andere J->K, ofwel dat dat niet zo is, maar dat het in die gevallen niet uitmaakt wat de volgorde van K en J is, en
2) het niet uitmaakt wat de volgorde is als er geen volgorde te bepalen is (dwz dat AJH en JHA in je voorbeeld beiden OK zijn)

dan kan het als volgt (python):

Python:

routes = ["kjp", "kjhp", "kap"]
print "Bekende routes zijn: ", ",".join(routes)
stops = set("".join(routes))
print "Mogelijk stops zijn: ", stops


def sortcmp(x,y):
    for route in routes:
        try:
            return cmp(route.index(x), route.index(y))
        except ValueError:
            pass
    return 0
    
print sorted(stops, cmp=sortcmp)

Online: http://repl.it/Vvc

De methode is de volgende: elke programmeertaal heeft een optie om zelf de 'comparison'-functie tussen twee objecten op te geven (in php is dat usort). Dat is een functie f(x,y) die -1 geeft als x<y, 0 als x==y en 1 als x>y. In dit geval bouw ik zelf een comparisonfunctie, die op basis van de routelijsten vertelt wat de relatieve ordening van haltes is.

Dat is de functie 'sortcmp'. Wat ik daar doe is het volgende: itereer over de routelijsten. Als beide items daar in voorkomen, pak dan beide indices (route.index(x) en route.index(y)) en vergelijk die met de ingebouwde vergelijk-functie ('cmp'). Die zal dus -1 geven als x eerder in de route voorkomt dan y, en 1 als dat andersom is.
Mochten beide items niet in de lijst voorkomen dat wordt er een ValueError geraised. Die negeren we dan, en we gaan verder met de volgende route.

Mochten nu in geen van de routes beide haltes voorkomen dan wordt er '0' teruggegeven -- i.a.w. beide haltes zijn 'gelijk'.

[Xanland]

@GlowMouse: Held, je hebt me aan het denken gezet waar ik tot een grotendeelse oplossing kwam. Hierbij had ik nog array_search benodigd, maar het zetje van jou werkte wel - thnx!
@Tribits: In mijn database staat een rit, waarbij de haltes een zogeheten StopOrder hebben en hierop is alles gesorteerd. In OV-land worden haltes die afwijken van een bepaalde rit steeds erboven toegevoegd, daarbij is hier de juiste volgorde dus AJH. Mijn voorbeeld was inderdaad ook niet compleet helder.

Ah, een uitgebreidere uitleg - zeer interesting! Als ik het zo bekijk heb ik ongeveer het zelfde geschreven, maar toch net ff iets anders in verband met iets waar ik geen rekening mee heb/had gehouden:

PHP:

$originalFullStopList = $stopLists[0];
$lastStop = array_pop ($originalFullStopList);
unset ($stopLists[0]);
foreach ($stopLists as $stopList) // $stopLists is een array met ritten met hun desbetreffende haltes
{
    $previousData['originalStopListKey'] = -1;
    array_pop ($stopList);
    foreach ($stopList as $key => $stop)
    {
        $found = array_search($stop, $originalFullStopList); // $origi is de haltelijst van de eerste rit, daar ga ik van uit!
        if ($found === false)
        {
            $startOfOFSL = array_slice($originalFullStopList, 0, $previousData['originalStopListKey']+1);
            $endOfOFSL = array_slice($originalFullStopList, $previousData['originalStopListKey']+1);
            $originalFullStopList = array_merge ((array) $startOfOFSL, (array) $stop, (array) $endOfOFSL);
        }

        $previousData['originalStopListKey'] = array_search($stop, $originalFullStopList);
    }
}
$originalFullStopList[] = $lastStop;

Het bovenste werkt, inclusief ringlijnen waarbij de begin- en eindhalte hetzelfde zijn. Een eerste rit wil nog weleens halverwege de route beginnen en de laatste halte is bij een volledige rit hetzelfde als de eerste halte. Voor de duidelijkheid voeg ik hem wel toe.

[Montaner]

Als je de naam van de halte als key van de array gebruikt, kan je daarna toch simpelweg alles toevoegen?

In het kort (heel netjes ja ):

PHP:

$arrays = array(

$array_1 = array(
"Klaasstraat, Zeveren" => "08:00", 
"Janstraat, Lutseren" => "08:15", 
"Pietstraat, Treleren" => "08:30"
),

$array_2 = array(
"Klaasstraat, Zeveren" => "08:05", 
"Janstraat, Lutseren" => "08:20", 
"Pietstraat, Treleren" => "08:35"
),

$array_3 = array(
"Klaasstraat, Zeveren" => "08:10", 
"Janstraat, Lutseren" => "08:25", 
"Pietstraat, Treleren" => "08:40"
));

$array_count = 3;

$final_array = array();


    foreach($arrays as $key => $value)
    {
        foreach($value as $key_1 => $value_1)
        {
            if(!isset($final_array[$key_1]))
            {
                $final_array[$key_1] = array();
            }
            
            $final_array[$key_1][] = $value_1;
        }
    }

Output:

code:

Array
(
    [Klaasstraat, Zeveren] => Array
        (
            [0] => 08:00
            [1] => 08:05
            [2] => 08:10
        )

    [Janstraat, Lutseren] => Array
        (
            [0] => 08:15
            [1] => 08:20
            [2] => 08:25
        )

    [Pietstraat, Treleren] => Array
        (
            [0] => 08:30
            [1] => 08:35
            [2] => 08:40
        )

)

Ik heb de "missende" tijden over het hoofd gezien. Oops . Denk nog even verder..

[ Voor 3% gewijzigd door Montaner op 28-07-2014 12:52 ]

[HuHu]

Zomaar een vraag: waarom komt Henkstraat voor Ambtstraat? Als je de tijden sinds vertrek er bij pakt:

code:

Klaasstraat, Zeveren = 08:00 +0:00
Janstraat, Lutseren  = 08:15 +0:15
Pietstraat, Treleren = 08:30 +0:30

Klaasstraat, Zeveren = 08:30 +0:00
Janstraat, Lutseren  = 08:45 +0:15
Henkstraat, Lutseren = 08:50 +0:20
Pietstraat, Treleren = 09:00 +0:30

Klaasstraat, Zeveren = 09:00 +0:00
Ambtstraat, Lutseren = 09:17 +0:17
Pietstraat, Treleren = 09:30 +0:30

Ik zou op basis hiervan het volgende verwachten:

code:

Klaasstraat, Zeveren = 08:00 | 08:30 | 09:00
Janstraat, Lutseren  = 08:15 | 08:45 | --:--
Ambtstraat, Lutseren = --:-- | --:-- | 09:17
Henkstraat, Lutseren = --:-- | 08:50 | --:--
Pietstraat, Treleren = 08:30 | 09:00 | 09:30

[.oisyn]

Feitelijk boeit dat niet als er geen rit bestaat die beide haltes in zich heeft. Dit betekent wel dat de suggestie van GlowMouse niet afdoende werkt - als er een 4e rit bijzit die zowel Ambtstraat als Henkstraat aandoet dan klopt de volgorde mogelijk niet als je eerder Ambtstraat na Henkstraat hebt geïnsert.

Jouw conclusie vind ik wat te kort door de bocht overigens. Het feit dat hij eerder bij Ambtstraat is dan bij Henkstraat wil niet zeggen dat die ook eerder komt - wellicht moet ie voor Henkstraat een stukje omrijden, maar ligt het logischerwijs nog wel voor Ambtstraat (bijvoorbeeld als ie er alsnog wel langsrijd maar er niet stopt). Verder stopt ie ook niet bij Janstraat in de route van Amtstraat, dus dat kan ook voor de nodige tijdwinst zorgen

[ Voor 56% gewijzigd door .oisyn op 28-07-2014 14:19 ]

[HuHu]

Daarom was het ook een vraag . Op basis van de gegevens in de OP kan ik niet aangeven waarom Henkstraat eerder komt dan Ambstraat. Behalve dan dat Henkstraat als eerste in een eerdere rit gereden wordt.

[Xanland]

Waarschijnlijk over het hoofd gezien, wat ik al eerder had gezegd :P: "In OV-land worden haltes die afwijken van een bepaalde rit steeds erboven toegevoegd, daarbij is hier de juiste volgorde dus AJH. Mijn voorbeeld was inderdaad ook niet compleet helder." De reden dat nieuwe haltes "bovenaan" worden toegevoegd is inderdaad wat .oisyn zegt, je weet niet al te veel over de haltes.
Heb net nog even mijn voorbeeld geüpdate. Had daar ook nog niet helemaal op gelet.

Als hij wel langs een halte rijdt die niet in de dienstregelingtabel zit, dan maakt die halte uiteraard geen fluit uit.

[ Voor 15% gewijzigd door Xanland op 30-07-2014 02:32 ]

[HuHu]

Had ik inderdaad gemist, maar dan vind ik het nog raarder . Ik begrijp dat je weinig weet over de volgorde van de haltes, maar als je veel ritten hebt, dan moet je toch wel iets kunnen afleiden over de meest logische volgorde? Ik zou verwachten dat je iets slimmers kunt doen dan gewoon maar bovenaan toevoegen.

Wat nu als er een rit K -> J -> A -> P is om 10 uur? Ga je dan J opnieuw toevoegen boven A? Of laat je ze staan en klopt de volgorde van de tijden niet meer? Ik vind het maar gek. Als je eerst alle ritten verzameld en dan op een slimme manier de haltes sorteert, dan krijg je wellicht een betere volgorde eruit?

Zomaar een gedachtenspinsel: bouw een directed graph uit alle ritten die je hebt (van één dag(deel) ofzo). Uit je OP:


Als er dan een rit K -> J -> A -> P bij komt:


Als het resultaat acyclisch is, dan kun je hem eenvoudig printen. Als hij dat niet is (bijvoorbeeld als in een rit A -> J en een andere rit J -> A), dan moet je een node dupliceren en de cycle oplossen.