Merging of two Lists

Discussion in 'Spigot Plugin Development' started by ExoBiTe, Sep 11, 2019.

  1. Hey guys
    I´ve got a small Designing Question.

    I´ve got two Lists filled with different BlockData (e.g. Location of the Block and Material/BlockState). Both Lists contain BlockData which will get pasted into the same (defined) Area, but none of them contains all Blocks. At Last i want to fill each Block that is in the defined Area, but doesnt appear in any of these Lists with Air.
    And all of this Data should be contained in one List at the end.

    Example:
    Blocks Listed in List 1 are a "X", Blocks from List 2 are "Y". Air gets represented by an "A".
    The following Rows present a simple 2D-Area, viewed from the top.

    AAXAA
    YYAYY
    XAYAX
    AXYXA

    And at the end i want a List, that contains all Positions and Blocks with the correct data, so here it would be a List with a Size of 5*4=20 Entries.

    The thing is i dont know how to do this nicely, and not in a "it´s working" way.
    The first idea i had, was creating a List filled with blanks of the Area. And then i iterate through both lists, and remove the existing entrys from the "blank" list and add the entrys to the "final" List. At the end of both iterations, i add all remaining entrys from the "blank" list to the "final" list, and fill these Locations with air.
    But i think that is very poorly done, and i can´t think of a better solution myself.

    And what makes it even worse is, i don´t know how to easily compare two Locations, as i am using int Arrays with a size of 3 (x, y, z). So if i wanted to check if a Position is already existing, i would need to iterate through the whole target List and check every number seperately, as i can´t compare arrays of integer with
    List.contains(new int[]{1, 2, 3}).

    Anyone got Ideas of how to do this nicely and not that messy?
    Hope you understand what i mean.
    If not, i´ll answer any questions.

    Thanks in advance :)
     
  2. Is the defined area a cuboid? If yes, you can first create a 3d array of appropriate size. Then, iterate over your lists, and insert each element into its corresponding position in the array. Then, if you need a List, create one and iterate over the array, adding every element to the new list, replacing null with air.
    You could also use a 1d array and convert the 3d indizes into 1d indizes. This would give the advantage that you could directly create the list using Arrays.asList(theArray) and just had to replace the null values, not copy all elements.
     
  3. You have a mutiltude of issues here, for one - lists have horrible contains performance as you have to compare every single entry within your listing. Sets and maps are more optimized for these operations.

    Your case sounds a bit like if you are trying to create a custom schematic esque format to paste things into the world, so I would recommend you to use the following syntax for things: "X Y Z MATERIAL BLOCK_DATA", you can extract the data by splitting at every blankspace (X, Y, Z, MATERIAL) and use a StringBuffer to concat everything else and serialize the blockdata (There is a bukkit method for this.)

    Additionally to that, should you intend to store larger structures I recommend you to use a linked list. Owing its queue like behaviour its the fastest when directly iterated (But dont use indexed based iteration for it, you'll suffer horrible performance ilke that.)

    Finally, to detect non contained blocks I would suggest you to do that right upon loading your blocks so you have minimalized performance overhead. Generate all (Relative) locations that are meant to be set to air upon loading your schematic.

    You do this by generating a minimum vector and a maximum vector, (Math#min and Math#max on each X/Y/Z) then you can run three nested iterations. Something like "FOR (x = min.x; x <= max.x; x++)" etc. Prior to that iteration you would also iterate over every single entry that you had and pool everything up into a Set<Vector> so you can just run a set#contains which is much master then everything else.

    All in all I would say that you'd be the fastest by storing everything in a Queue/LinkedList and running a generic iteration. Like that you will be spared of having to convert the flat mapped values to a three dimensional coordinate, but eat up a bit more ram. But it shouldn't be too much a resource occupation. If you intend on storing massive constructions like that I would suggest that you would stick to a short rather then an integer as it reserves less memory.
     
    • Like Like x 1
  4. If your lists don't contain same locations (ie. no overlap) then easiest method is Collection#addAll (Or List#addAll in this case) to add both lists together. Air can be filtered out from the second list before adding it on top.

    If the lists contain overlaps, then a Map is indeed better suited for the task. TreeMap<Location, BlockData> with an appropriate Comparator<Location> (For example one that sorts lists to smallest x, y, z) will also make the iteration over the Map easier, since the Locations will be in order after the Map has been filled.

    BlockData contains location so you might be able to use TreeSet<BlockData> with a Comparator<BlockData>, I put the TreeMap as example above, since TreeSet is based on TreeMap. With TreeSet implementation it is possible to leave Air out and instead insert air between the entries when iterating, with a bit of work.
     
    • Like Like x 1
  5. The Thing is, i can´t really use Set(s) for this, as i am pasting them with a delay in a repeating task, so i can´t/won´t iterate over the whole set in one "cycle". And i don´t saw a way to "save" the current Position from the Set for the next "cycle", thats why i am using a List for this Task.
    For better explaining, here´s my Task which pastes Blocks into the World:

    The "Task":
    Code (Text):
    public static Task getDefaultBlockPlaceTask(List<BlockData> bList, World w) {
            Set<BlockData> lastTick = new HashSet<>();
            Task ts = new Task(true) {

                @Override
                protected boolean doTask() {
                    int maxPastes = this.cachedPointer[0] + Config.conf_paste_blocksPerTick;
                    int i = 0, pasted = 0;
                    for(i=cachedPointer[0];i<bList.size() && pasted<maxPastes;i++) {
                        BlockData curr = bList.get(i);
                     
                        try {
                            org.bukkit.block.data.BlockData bDat = curr.getMaterial().createBlockData();
                         
                            if(bDat instanceof Powerable || bDat instanceof Door || bDat instanceof Chest) {
                                lastTick.add(curr);
                                continue;
                            }
                        }catch(IllegalArgumentException e) {}
                     
                        if(placeBlock(curr)) pasted++;
                     
                        //System.out.println(b.toString());
                    }
                    cachedPointer[0] = i;
                    if(cachedPointer[0]>=bList.size()-1) {
                        for(BlockData bd:lastTick) {
                            placeBlock(bd);
                        }
                    }
                    return cachedPointer[0]>=bList.size()-1;
                }
             
                private boolean placeBlock(BlockData bd) {
                    int[] pos = bd.getPosition();
                    Block b = w.getBlockAt(pos[0], pos[1], pos[2]);
                    if(!b.getChunk().isLoaded()) {
                        b.getChunk().load();
                    }
                    if(b.getBlockData().getAsString().equals(bd.getBlockData()) && bd.getBase64Data()==null) return false;
                    BlockUtils.setBlockData(b, bd); //This just places the Block in the World with some additional Stuff like setting Chests Inventories etc.
                    return true;
                }
             
            };
            return ts;
        }
    The Array "cachedPointer" saves the Position where the last Block got pasted, and saves it for the next Call.
    My TaskManager calls the doTask() Method every x ticks, until it returns true.
    Also it saves the cachedPointer field from the last execution and writes the saved stuff into the cachedPointer field before the doTask() is called.

    //Edit: As you may have noticed, i am using a custom self written "BlockData", don´t mistake it with Bukkits BlockData. By the Time i created it, i didn´t really thought about that there is already a class like that, and i am changing the Name later.

    Thanks for the Tips related to the saving of the Data, but i already managed that part in a very similiar way you described it. :)
    Also i already got all Locations, using 3 for-loops and as i mentioned in the first post, my problem is i don´t know a smart way to check if the Set contains an Position, as i stored them using an Integer Array with a Length of 3 (btw, nice Idea to use Shorts for this, didn´t thought of that and i´m gonna change that). But you can´t use Set#contains(new int[]{x, y, z}), as this would create new instances and wouldn´t search for the already existing Arrays even if they have the same content.

    For example:
    Code (Text):
    Set<int[]> test = new HashSet<>();
    test.add(new int[]{1, 2, 3});
    System.out.println(test.contains(new int[]{1, 2, 3}));
    Would print "false".

    But i think i´ll try giving it a Shot to use a Queue, and paste them one after another using Queue#poll(), that way i already can remove the "cachedPointer"-Part from my Code from before.

    //Edit2:
    So i´ve wrote this one now, i´m gonna test it later.
    But i think this is how you´ve meant it?
    Code (Text):
        public static Task getDefaultBlockPlaceTask(final Queue<BlockData> toPaste, final World w) {
            Set<BlockData> lastTick = new HashSet<>();
            Task ts = new Task(true) {

                @Override
                protected boolean doTask() {
                    int pasted = 0;
                    while(pasted<=Config.conf_paste_blocksPerTick && !toPaste.isEmpty()) {
                        BlockData curr = toPaste.poll();
                        try {
                            org.bukkit.block.data.BlockData bDat = curr.getMaterial().createBlockData();
                           
                            if(bDat instanceof Powerable || bDat instanceof Door || bDat instanceof Chest) {
                                lastTick.add(curr);
                                continue;
                            }
                        }catch(IllegalArgumentException e) {/*Just do nothing.*/}
                        if(placeBlock(curr)) pasted++;
                    }
                   
                    if(toPaste.isEmpty() && !lastTick.isEmpty()) {
                        for(BlockData bd:lastTick) {
                            placeBlock(bd);
                        }
                    }
                    return toPaste.isEmpty() && lastTick.isEmpty();
                }
               
                private boolean placeBlock(BlockData bd) {
                    int[] pos = bd.getPosition();
                    Block b = w.getBlockAt(pos[0], pos[1], pos[2]);
                    if(!b.getChunk().isLoaded()) {
                        b.getChunk().load();
                    }
                    if(b.getBlockData().getAsString().equals(bd.getBlockData()) && bd.getBase64Data()==null) return false;
                    BlockUtils.setBlockData(b, bd);
                    return true;
                }
               
            };
            return ts;
        }
    Oh yeah, totally forgot about List#addAll, thanks for that.
    There is no need to filter out air, as none of these Lists ever contain Air.
    The Air is only needed to remove older Blocks that may be in this Location.
     
    #5 ExoBiTe, Sep 12, 2019
    Last edited: Sep 12, 2019
  6. Sounds like you might be able to use Set#iterator (On TreeSet the iterator would be ordered) :)
     
  7. But wouldn´t Iterator#next & Iterator#remove be the same as Queue#poll?
    Because that´s what i am using in my new Code (i posted it two posts above).
    And i don´t really need an ordered List, the only important thing is that every Position is filled.

    And basically my only Problem is to fill the "not-block" positions with Air.
    So i´ve got a Queue<BlockData> (BlockData contains Positions) filled with all Blocks to place, as well as i got all Possible Positions (whether in a Iterable<short[]> or Iterable<BlockData>, but i think using shorts instead of the whole BlockData would be performance-friendlier).