[Alg/Java] Berekenen van ranges

[-FoX-]

Afhankelijk van het aantal transacties kan een klant korting krijgen op een bepaalde formule.
Deze regels worden vastgelegd per product en uitgedrukt in ranges. De ranges moet elk op elkaar volgen
en de laatste range moet tot oneindig gaan.

vb:

	FROM		TO		PERCENTAGE
	----		--		----------
	   0	-	1000	-	2%
	1000	-	5000	-	3%
	5000	-	~	-	5%

Als deze door een reseller sequentieel worden ingegeven is er geen probleem.


* Maar stel dat er nu nog een range tussen moet komen. vb:

	FROM		TO		PERCENTAGE
	----		--		----------
	3000	-	5000	-	4%

Dan moeten al de andere ranges herberekend en geupdate worden:

	FROM		TO		PERCENTAGE
	----		--		----------
	   0	-	1000	-	2%
	1000	-	3000	-	3%
	3000	-	5000	-	4%
	5000	-	~	-	5%

* Of indien range 1 en 2 weer verwijderd worden, moet ook weer alles herberekend worden tot:

	FROM		TO		PERCENTAGE
	----		--		----------
	   0	-	5000	-	4%
	5000	-	~	-	5%

* Ook indien er een range geupdate wordt, vb: range1 -> 0-500:

	FROM		TO		PERCENTAGE
	----		--		----------
	   0	-	500	-	4%
	 500	-	~	-	5%

Op welke manier kan dit, zonder omslachtig te wezen, het beste verwezenlijkt worden?
Eén manier is om iedere keer alle ranges te gaan ophalen, te bepalen waar de nieuwe tussen hoort te komen, en op deze manier de rest up te daten.. Maar zo moeten telkens alle ranges weer opgehaald worden.

Is er misschien een bepaald algoritme dat ik voor dit probleem kan gebruiken?


_{De tabel ziet er als volgt uit:
RANGE
------------
RangeId
From
To
Percentage}

[Verwijderd]

Ik zou werken met een tabel
RangeId
From
Percentage

Zonder To dus

Dan vul je op

code:

Range From %
1     0    2
2     1000 3
3     5000 5

* Range ertussen:

code:

Range From %
1     0    2
2     1000 3
3     5000 5
4     3000 4

* 1 en 2 weg
dan moet je de rij met rangeId 1 aanpassen

enz
Zonder absolute from en to is het veel meer variabel.

[-FoX-]

Dat klinkt inderdaad aanvaardbaar.

Het probleem echter is dat het db-model redelijk vast ligt en er niet veel meer aan verandert zal kunnen worden. Tevens wordt er voor iedere aanpassing ook een history tabel bijgehouden hetgeen de zaken nog iets complexer maakt. Want wat gebeurd er bijvoorbeeld met de history entries van de tabellen die overspannen worden door een nieuwere waarde?! Ik denk dat ik deze gewoon als 'afgehandeld' ga bestempelen.

Ik zou het algoritme van deze case ook zo proper mogelijk willen houden zonder lelijke workarounds of dergelijke. De mogelijkheid om alle ranges op te halen en ze stuk voor stuk te vergelijken met de nieuwe entry en al dan niet aanpassen vind ik namelijk niet zo netjes...

[4VAlien]

hoe moeilijk is het om bij een update ff de gesorteerde rijen door te lopen en te kijken welke Id's je moet aanpassen? Het zijn er maximaal 2. Sterker nog als je gaat inserten hoef je alleen de conflicterende rijen te wijzigen. Als je gewoon die rijen met Id,from,to ophaalt is dat toch zo gebeurd? Bij delete moet je de alleen zorgen dat er een sequentiele reeks blijft staan, dit dus het updaten van hooguit 1 record.

[ Voor 51% gewijzigd door 4VAlien op 17-05-2005 13:11 ]

[Robtimus]

Aanwezig:
0-1000
1000-5000

Toevoegen: 1000-3000:
UPDATE tabel SET FROM=3000 WHERE FROM=1000
INSERT INTO tabel <nieuwe>

Aanwezig:
0-1000
1000-3000
3000-5000
DELETE FROM tabel WHERE FROM=1000 AND TO=3000
UPDATE tabel SET FROM=1000 WHERE FROM=3000

Zoiets?


Anders kun je het alsnog proberen om het zoals Hello_Kitty zei te doen. De TO mag waarschijnlijk NULL worden bij de laatste, dus je laat die NULL worden bij alle records en negeert het verder (werkt alleen als iedereen die de data ophaalt hiervanuit gaat).

[.oisyn]

Zit ik ernaast als dit meer over SQL gaat dan Java of zelfs algemeen?

[-FoX-]

Ik had er eigenlijk best van in het begin bij vertelt dat het hier om een EJB applicatie gaat met EntityBeans en CMP. Het is daarom niet minder mogelijk om dit met SQL te doen, maar ik had het toch het liefst in de CMP-context gehouden.

Ik zal dus eerst een finder (EQL) moeten schrijven, die de betreffende records ophaalt (binnen de span van de nieuwe record) en op basis hiervan bewerkingen uitvoeren. Het geheel dan terugplaatsen en het door de container laten afhandelen.
Dit kan op verschillende manieren gedaan worden, maar ik had hiervoor graag eens wat extra tijd uitgerokken om al dan niet de best mogelijke oplossing te implementeren. Daarmee dat ik dit topic even hier plaatste, zodat ik al wat kon vooruitdenken.

De effectieve implementatie ga ik waarschijnlijk morgen pas toekomen.. Maar ik hou jullie niet tegen om alvast mee te denken in de goede richting

_{Een title fix misschien op zijn plaats?}

[Robtimus]

Als je eerst alles in Java aanpast en daarna pas een bulkupdate in SQL dan loop je tegen het probleem aan dat je precies moet bijhouden wat je precies hebt aangepast en in welke volgorde. Je gaat ahw alles precies zo doen zoals je net al hebt gedaan, maar dan op de database ipv je logische in-memory view.
Een andere mogelijkheid is alles verwijderen (van de huidige set) en opnieuw inserten. Dan is een bulkupdate eenvoudiger, maar mogelijk ook intensiever.

[-FoX-]

Kleine update.

Het is dus uiteindelijk de bedoeling dat de ranges vooraf gevalideerd worden alvorens er een call naar de database gebeurd. Ik ben pas begonnen met het implementeren van de ranges.

Ik heb een Struts FormBean die over een TreeMap beschikt van de ranges. Als de gebruiker een range invult (0, 100, 25%), dan worden deze waarden omgezet naar een Range-object, waarna deze in de Map gestopt wordt, met als key de FROM value en als value het Range-object. Deze ranges moeten dus dynamisch zijn. Daarmee bedoel ik dat deze op elkaar moeten aansluiten en zich eventueel moeten kunnen aanpassen aan een range die ertussen gestopt wordt óf een aantal ranges overspant. Het sequentieel invoeren van ranges levert geen problemen op.

Nu ben ik op zoek naar het beste algoritme om deze bewerking gedaan te krijgen (zie startpost voor enkele voorbeelden).

Zelf had ik gedacht om een TreeMap te gebruiken (sortering, unieke keys, b-tree), en afhankelijk van de nieuwe entry, de berekening gaan doen.

Iemand goede raad hoe ik dit het beste aanpak?

[-FoX-]

Een eerste poging:

ADD RANGE (X, Y)
----------------
* TreeMap<key, Range> map
     - map.subMap(key X, key Y)
               - s1, s2, ..., sn
     - map.remove(key sn)
     - map.put(key, Range)
     -> continue ranges:
               - map.tailMap(key X + 1)
                    - from = to - 1
               - map.headMap(key X)
                    - to = from + 1

Maar ben er nog niet tevreden mee... c&c welcome