Algorithm for filtering collection
I have object Country, which has Areas. Areas has Provinces. Provinces has Cities, and Cities, and Cities has hotels.
I want to filter list of regions to have only objects with property userHaveBeenThere set to true(Areas,Provinces,Cities,and hotels.
I'm going to bind this list to treeview.
The worst part of this algorith situation, when for example:
region doesn't have userHaveBeenThere==true,all provinces too,all cities too, but in one city one of ten hotels has userHaveBeenThere as true. So I must show user this region, with only one province, with only one city, and with only one hotel.
Other scary thing is, that I have two treeviews. At first I must show full structure, and at second filtered, so I'm little scare about references while using through this filtering operations like remove.
So the question is how to filter this list ?
TreeView1
Region1
-Area1
-Province1
-City1
-City2
-Hotel1
-Hotel2
-Hotel3
-Province2
-City3
-City4
-Hotel4
-Hotel5
-Hotel6
-Area2
Region2
-Area21
-Province21
-City21
-City22
-Hotel21
-Hotel22
-Hotel23
-Province22
-City23
-City24
-Hotel24
-Hotel25
-Hotel26
-Area22
Filtered list
Region1
-Area1
-Province1
-City2
-Hotel3
Region2
-Area21
-Province22
-City2开发者_StackOverflow4
-Hotel24
I don't want answer how to bind :) Only answer how to filter :)
This is my solution:
var copiedCountry = CloneObject(_package.Country);
for (int indexOfRegion = 0; indexOfRegion < copiedCountry.ListOfRegions.Count; indexOfRegion++)
{
var region = copiedCountry.ListOfRegions[indexOfRegion];
if (region.ListOfProvinces.Count > 0)
{
for (int indexOfProvince = 0; indexOfProvince < region.ListOfProvinces.Count; indexOfProvince++)
{
var province = region.ListOfProvinces[indexOfProvince];
if (province.ListOfCities.Count > 0)
{
for (int indexOfCity = 0; indexOfCity < province.ListOfCities.Count; indexOfCity++)
{
var city = province.ListOfCities[indexOfCity];
int numberOfHotels = city.ListOfHotels.Count;
for (int indexOfHotel = 0; indexOfHotel < numberOfHotels; indexOfHotel++)
{
var hotel = city.ListOfHotels[indexOfHotel];
if (hotel.userHaveBeenThere == false)
{
city.ListOfHotels[indexOfHotel] = null;
}
}
city.ListOfHotels.RemoveAll(h => h == null);
if (city.ListOfHotels.Where(h => h.userHaveBeenThere == true).Count() > 0)
{
}
else
{
if (city.userHaveBeenThere == false)
{
province.ListOfCities[indexOfCity]=null;
}
}
}
province.ListOfCities.RemoveAll(c => c == null);
if (province.ListOfCities.Count == 0)
{
if (province.userHaveBeenThere == false)
{
region.ListOfProvinces[indexOfProvince]=null;
}
}
}
else
{
if (province.userHaveBeenThere == false)
{
region.ListOfProvinces[indexOfProvince] = null;
}
}
}
region.ListOfProvinces.RemoveAll(p => p == null);
if (region.ListOfProvinces.Count == 0)
{
if (region.userHaveBeenThere == false)
{
copiedCountry.ListOfRegions[indexOfRegion]=null;
}
}
}
else
{
if (region.userHaveBeenThere == false)
{
copiedCountry.ListOfRegions[indexOfRegion]=null;
}
}
copiedCountry.ListOfRegions.RemoveAll(r => r == null);
}
public static T CloneObject<T>(T item)
{
using (MemoryStream ms = new MemoryStream())
{
BinaryFormatter bf = new BinaryFormatter(null,
new StreamingContext(StreamingContextStates.Clone));
try
{
bf.Serialize(ms, item);
}
catch (Exception e)
{
throw;
}
ms.Seek(0, SeekOrigin.Begin);
return (T)bf.Deserialize(ms);
}
}
Instead of using a bool to know if the user has been there, consider using a bool?. Set it to null when you want to redirect to the child object's userHasBeenThere.
Here is a concrete example, the magic happens when you will set one of thoses object's userHasBeenThere to true.
Here is an example of the pattern:
public abstract class AUserTracker
{
private IEnumerable<AUserTracker> _children;
public IEnumerable<AUserTracker> Children
{
get { return _children; }
set { _children = value; }
}
private bool? _userHasBeenThere;
public bool UserHasBeenThere
{
get
{
if (_userHasBeenThere == null)
{
_userHasBeenThere = false;
// Uses OR operator, any child will trigger the show up.
foreach (AUserTracker child in Children)
_userHasBeenThere |= child.UserHasBeenThere;
}
return _userHasBeenThere ?? false;
}
}
}
This would be the base class for all your objects. Then you can use WPF HierarchicalDatatemplate to show up your objects in the TreeView.
{enjoy}
Can you add to all of your objects a variable "BeenThereInHere" (or whatever name you want) that would be set to true if one of his children has userHaveBeenThere==true, that way, you can quickly nail down where to scan and where you can skip it to save time.
Is the data in a database or stored as a graph?
If it's a database, you could set up queries to get the right data.
If it's a graph, you could made it bidirectional, start at the bottom ( visited hotels ) and walk to each root ( regions ) inserting the parents into a new object.
I would suggest using recursion. For node that can be Country, Province, City, Hotel do as follow:
bool ShouldDisplayNode(Node n){
if (n.Type == Hotel){
return n.HasBeenThere;
}
bool display = false;
foreach (var child in n.Children){
display |= ShouldDisplayNode(child);
}
return display;
}
I don't know exact data structure but above method would be very useful when you will use Composite Pattern to represent this hierarchical structure. You will also need to have some kind of dictionary or property in item to store calculated flags.
This is my solution:
var copiedCountry = CloneObject(_package.Country);
for (int indexOfRegion = 0; indexOfRegion < copiedCountry.ListOfRegions.Count; indexOfRegion++)
{
var region = copiedCountry.ListOfRegions[indexOfRegion];
if (region.ListOfProvinces.Count > 0)
{
for (int indexOfProvince = 0; indexOfProvince < region.ListOfProvinces.Count; indexOfProvince++)
{
var province = region.ListOfProvinces[indexOfProvince];
if (province.ListOfCities.Count > 0)
{
for (int indexOfCity = 0; indexOfCity < province.ListOfCities.Count; indexOfCity++)
{
var city = province.ListOfCities[indexOfCity];
int numberOfHotels = city.ListOfHotels.Count;
for (int indexOfHotel = 0; indexOfHotel < numberOfHotels; indexOfHotel++)
{
var hotel = city.ListOfHotels[indexOfHotel];
if (hotel.userHaveBeenThere == false)
{
city.ListOfHotels[indexOfHotel] = null;
}
}
city.ListOfHotels.RemoveAll(h => h == null);
if (city.ListOfHotels.Where(h => h.userHaveBeenThere == true).Count() > 0)
{
}
else
{
if (city.userHaveBeenThere == false)
{
province.ListOfCities[indexOfCity]=null;
}
}
}
province.ListOfCities.RemoveAll(c => c == null);
if (province.ListOfCities.Count == 0)
{
if (province.userHaveBeenThere == false)
{
region.ListOfProvinces[indexOfProvince]=null;
}
}
}
else
{
if (province.userHaveBeenThere == false)
{
region.ListOfProvinces[indexOfProvince] = null;
}
}
}
region.ListOfProvinces.RemoveAll(p => p == null);
if (region.ListOfProvinces.Count == 0)
{
if (region.userHaveBeenThere == false)
{
copiedCountry.ListOfRegions[indexOfRegion]=null;
}
}
}
else
{
if (region.userHaveBeenThere == false)
{
copiedCountry.ListOfRegions[indexOfRegion]=null;
}
}
copiedCountry.ListOfRegions.RemoveAll(r => r == null);
}
public static T CloneObject<T>(T item)
{
using (MemoryStream ms = new MemoryStream())
{
BinaryFormatter bf = new BinaryFormatter(null,
new StreamingContext(StreamingContextStates.Clone));
try
{
bf.Serialize(ms, item);
}
catch (Exception e)
{
throw;
}
ms.Seek(0, SeekOrigin.Begin);
return (T)bf.Deserialize(ms);
}
}
I think that there is a lot to optimize :/
加载中,请稍侯......
精彩评论