DefaultInsertionPredicate.java

public class DefaultInsertionPredicate<S, T> implements InsertionPredicate<S, T> {

    @Override
    public boolean canInsert(@Nonnull Section<S, T> section, @Nonnull T item) {
        return true;
    }
}

EntityItem.java

public class EntityItem<T> implements Item {

    private T data;

    public EntityItem(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        EntityItem that = (EntityItem) o;

        return data != null ? data.equals(that.data) : that.data == null;
    }

    @Override
    public int hashCode() {
        return data != null ? data.hashCode() : 0;
    }

    @Override
    public String toString() {
        return "EntityItem{" +
                "data=" + data +
                '}';
    }
}

HeaderItem.java

public class HeaderItem<T> implements Item {

    private T title;

    public HeaderItem(T title) {
        this.title = title;
    }

    public T getTitle() {
        return title;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        HeaderItem that = (HeaderItem) o;

        return title != null ? title.equals(that.title) : that.title == null;
    }

    @Override
    public int hashCode() {
        return title != null ? title.hashCode() : 0;
    }

    @Override
    public String toString() {
        return "HeaderItem{" +
                "title=" + title +
                '}';
    }
}

Inserter.java

public interface Inserter<T> {

    int insert(List<T> localList, @Nonnull T item);
}

InsertionObserver.java

public interface InsertionObserver {

    void onInserted(@Nonnull Item item, int position);
}

InsertionPredicate.java

public interface InsertionPredicate<S, T> {

    boolean canInsert(@Nonnull Section<S, T> section, @Nonnull T item);
}

Item.java

public interface Item {
}

RemoveObserver.java

public interface RemoveObserver {

    void onRemoved(@Nonnull Item item, int position);
}

Section.java

public class Section<S, T> {

    @Nonnull
    private S sectionDescription;

    @Nonnull
    private final List<Item> items;
    private final List<T> localItems = new ArrayList<>();

    private InsertionPredicate<S, T> insertionPredicate;

    Section(@Nonnull S sectionDescription,
            @Nonnull InsertionPredicate<S, T> insertionPredicate,
            @Nonnull List<Item> items) {
        this.sectionDescription = sectionDescription;
        this.insertionPredicate = insertionPredicate;
        this.items = items;
    }

    @Nonnull
    public S getSectionDescription() {
        return sectionDescription;
    }

    @Nonnull
    public List<T> getLocalItems() {
        return localItems;
    }

    void insert(T item,
                int sectionOffset,
                Inserter<T> inserter,
                InsertionObserver insertionObserver) {
        if (localItems.isEmpty()) {
            HeaderItem<S> headerItem = new HeaderItem<>(sectionDescription);
            items.add(sectionOffset, headerItem);
            insertionObserver.onInserted(headerItem, sectionOffset);
        }
        int localIndex = inserter.insert(localItems, item);
        if (localIndex != -1) {
            localIndex++;//header
            EntityItem<T> entityItem = new EntityItem<>(item);
            int index = sectionOffset + localIndex;
            items.add(index, entityItem);
            insertionObserver.onInserted(entityItem, index);
        }
    }

    boolean canContain(T item) {
        return insertionPredicate.canInsert(this, item);
    }

    void remove(T item, RemoveObserver removeObserver) {
        EntityItem<T> entityItem = new EntityItem<>(item);
        int index = items.indexOf(entityItem);
        if (index != -1) {
            items.remove(index);
            removeObserver.onRemoved(entityItem, index);

            localItems.remove(item);
            if (localItems.isEmpty()) {
                index--;
                items.remove(index);
                removeObserver.onRemoved(new HeaderItem<>(sectionDescription), index);
            }
        }
    }

    @Override
    public String toString() {
        return "Section{" +
                "sectionDescription=" + sectionDescription +
                ", localItems=" + localItems +
                '}';
    }

    public void clear() {
        localItems.clear();
    }
}

Sections.java

public class Sections<S, T> {

    private final List<Section<S, T>> sections;
    private final List<Item> items;

    @Nullable
    private InsertionObserver insertionObserver;

    @Nullable
    private RemoveObserver removeObserver;

    Sections(List<Section<S, T>> sections,
             List<Item> items,
             @Nullable InsertionObserver insertionObserver,
             @Nullable RemoveObserver removeObserver) {
        this.sections = sections;
        this.items = items;
        this.insertionObserver = insertionObserver;
        this.removeObserver = removeObserver;
    }

    public void addItem(T item) {
        addItem(item, new SimpleInserter<>());
    }

    public void addItem(T item, Inserter<T> inserter) {
        for (int i = 0; i < sections.size(); i++) {
            Section<S, T> section = sections.get(i);
            if (section.canContain(item)) {
                int sectionOffset = 0;
                if (i > 0) {
                    Section<S, T> previousSection = sections.get(i - 1);
                    List<T> localItems = previousSection.getLocalItems();
                    if (!localItems.isEmpty()) {
                        T lastItem = localItems.get(localItems.size() - 1);
                        sectionOffset = items.indexOf(new EntityItem<>(lastItem)) + 1;
                    }
                }
                section.insert(item, sectionOffset, inserter, insertionObserver);
                break;
            }
        }
    }

    public void remove(T item) {
        for (Section<S, T> section: sections) {
            if (section.canContain(item)) {
                section.remove(item, removeObserver);
            }
        }
    }

    public void clear() {
        items.clear();
        for (Section section: sections) {
            section.clear();
        }
    }

    public List<Item> getItems() {
        return items;
    }

    public static class Builder<S, T> {

        private final List<Item> items = new ArrayList<>();
        private final List<Section<S, T>> sections = new ArrayList<>();

        @Nullable
        private InsertionObserver insertionObserver;

        @Nullable
        private RemoveObserver removeObserver;

        public Builder<S, T> onInsert(InsertionObserver insertionObserver) {
            this.insertionObserver = insertionObserver;
            return this;
        }

        public Builder<S, T> onRemove(RemoveObserver removeObserver) {
            this.removeObserver = removeObserver;
            return this;
        }


        public Builder<S, T> section(@Nonnull S sectionDescription,
                                     @Nonnull InsertionPredicate<S, T> insertionPredicate) {
            sections.add(new Section<>(sectionDescription, insertionPredicate, items));
            return this;
        }

        public Builder<S, T> section(@Nonnull S sectionDescription) {
            return section(sectionDescription, new DefaultInsertionPredicate<>());
        }

        public Sections<S, T> build() {
            return new Sections<>(sections, items, insertionObserver, removeObserver);
        }

    }
}

SimpleInserter.java

public class SimpleInserter<T> implements Inserter<T> {

    @Override
    public int insert(List<T> localList, @Nonnull T item) {
        localList.add(item);
        return localList.size() - 1;
    }
}