Loops to merge documents and renumber pages

Question

I have a for loop implementation for merging documents and page re-numbering. But since I am modifying the collection while iterating, I suspect that the code might break. As foreach doesn't allow collection modification, I have implemented it with for.

Is there any better way to implement/optimize this part of code? Also, is it possible to reduce these 3 loops to a single one?

// Merge Document Sequence
for (int k = 0; k < response.documents.Count; k++)
{
    string presentDocument = string.Empty;
    string laterDocument = string.Empty;

    presentDocument = response.documents[k].docType;
    if ((response.documents.Count - 1) != k)
        laterDocument = response.documents[k + 1].docType;

    if ((laterDocument == presentDocument))
    {
        response.documents[k].pages.AddRange(response.documents[k + 1].pages);
        response.documents.RemoveAt(k + 1);
        k = k - 1;
    }
}

// Page Re-numbering                    
for (int i = 0; i < response.documents.Count; i++)
{
    for (int j = 0; j < response.documents[i].pages.Count; j++)
        response.documents[i].pages[j].pageNo= j + 1;
}

Answer 1

First I would rewrite it to make it little bit more self-explicative.

foreach (var documentsByType in GroupDocumentsByType(response.documents))
{
    MergeDocumentsIntoFirstOne(documentsByType);

    // First one is what we keep, all the others can be removed
    foreach (var document in documentsByType.Skip(1))
        response.Documents.Remove(document);
}

Good, now I don't need to read whole method to understand what it is doing and how. I then need an implementation for GroupDocumentsByType(). It has to return batches of documents (regardless their order, in this case) grouped by their type. As return type I used IEnumerable<List<Document>> instead of - for example - Document[][] just because it seems more clear (to me).

static IEnumerable<List<Document>> GroupDocumentsByType(IEnumerable<Document> documents)
{
    return documents
        .GroupBy(x => x.docType)
        .Select(x => x.ToList())
        .ToArray();
}

MergeDocumentsIntoFirstOne() is even simpler, it concatenates all documents in the list into first document in the list:

static void MergeDocumentsIntoFirstOne(List<Document> documents)
{
    for (int i=1; i < documents.Length; ++i)
        documents[0].pages.AddRange(documents[i].pages);

   RenumberPages(documents[0]);
}

And finally a specific method to perform renumbering. Nothing special here but it may be optimized to skip renumbering for pages in the first document (for example using a startIndex parameter).

static void RenumberPages(Document document)
{
    for (int i=0; i < document.pages.Count; ++i)
        document.pages[i].pageNo = i + 1;
}

---

Note that to make code more readable not always make it faster. If (and only if) speed is a measured issue (emphasis on both words: it has to be an issue and this method is a measured bottleneck of your application, no guesses) then you can make it faster. Your original code isn't bad in this sense but I'd change few minor issues:

• You don't need to check if next document exists, simply stop before last one (because last one can be merged - eventually - only with previous one).
• Perform partial renumbering each time you add new pages.

In code:

for (int i = 0; i < response.documents.Count - 1; /* nop */)
{
    var thisDocument = response.Documents[i];
    var nextDocument = response.Documents[i + 1];

    if (thisDocument.docType == nextDocument.docType)
    {
        int previousPageCount = thisDocument.pages.Count;

        thisDocument.pages.AddRange(nextDocument.pages);
        response.documents.Remove(nextDocument); // RemoveAt() is faster

        for (int j=previousPageCount; j < thisDocument.pages.Count; ++j)
        {
            thisDocument.pages[j] = j + 1;
        }
    }
    else // If I didn't merge I can move to next document
        ++i;
}

Note that you can still make this code more readable extracting some methods to clarify intent (especially ++i needs to be explained). Also I'd avoid to use == for string comparison in favor of String.Equals() using an explicit StringComparison.

Answer 2

One way to make it easier to follow is to construct your merged documents result separately from your input (above code is not tested).

Construct a dictionary to easily get the document to append to, based on type. It also ensures a fast operation. For each document from the input, append its pages in the dictionary:

// type => merged document mapping
var mergedDocsDict = new Dictionary<String, Document>();

response.documents.ForEach(doc => 
    {
       if (!mergedDocDict.ContainsKey(doc.docType))
          mergedDocDict.Add(doc.docType, new Document());

       mergedDocDict[doc.docType].pages.AddRange(doc.pages);
    };

Finally renumbering all the pages:

mergedDocDict.Keys.ForEach(key => 
   { 
       var doc = mergedDocDict[key];
       int pageCount = doc.pages.Count;
       for (int i = 0; i < pageCount; i ++)
          doc.pages[i].pageNo = i + 1;
   };

You result can be obtain from the dictionary:

mergedDocDict.Values.ToList();

This solution should be easier to understand, but uses extra memory for the result.

This can be overcome, by reusing the same documents:

response.documents.ForEach(doc => 
    {
       if (!mergedDocDict.ContainsKey(doc.docType))
          mergedDocDict.Add(doc.docType, doc);
       else
          mergedDocDict[doc.docType].pages.AddRange(doc.pages);
    };

Also, page renumbering can be done in the first loop, obtaining a single foreach:

response.documents.ForEach(doc => 
    {
       if (!mergedDocDict.ContainsKey(doc.docType))
          mergedDocDict.Add(doc.docType, doc);
       else
       {
          int existingCount = mergedDocDict[doc.docType].pages.Count;
          mergedDocDict[doc.docType].pages.AddRange(doc.pages);
          int newCount = doc.pages.Count + existingCount;
          for (int i = existingCount; i < newCount; i ++)
            mergedDocDict[doc.docType].pages[i].pageNo = i + 1; 
       }
    };

Complexity should be O(number_of_docs * number_of_pages) as all dictionary operations are done in O(1).

If your documents were copied from some other data structure to your response, I think it is better to construct the dictionary from that data structure and obtain respose.documents from the merged data. Otherwise, you have to use a for loop to remove documents already merged (somewhat more convoluted than foreach version).

Answer 3

Hello this is a more elegant solution for your implementation, going to check about performance and going to edit it after: The class BDoc should be the type of your response.documents, and BPage the type of your pages.

response.documents.GroupBy(rd => rd.docType).Select(
                gd => 
                    gd.Aggregate((gd1,gd2) =>  new BDoc()
                    {
                        docType = gd.Key,
                        pages = new List<BPage>(gd1.pages.Select((p, index) => { p.pageNo = index; return p;}))
                                         .Union(gd2.pages.Select((p, index) => { p.pageNo = index + gd1.pages.Count(); return p; })),
                    })).ToList();

The first part of the given solution is a groupBy, we going to group the collection of the documents that you receive by the propertie "docType" this will generate an IGrouping of type IEnumerable> this way your documents will be grouped with the key "docType".

The next step is to make an select so we can retrieve the data from the grouping mapped from our own convenience. Note that you can skip this and just iterate over the collection. To avoid unnecessary loops we going to make an aggregation of the results in the grouping recreating the object BDoc and just atribute to the pages of the new object the union of the pages grouped before.

The step for reordering the pages. I didn´t find good documentation on the select with index but find this link to an example usage. Here i did not create a new object because i just wanted to change the value pageNo of each page.

EDIT

Actually this implementation is taking more time in my machine your code for the same test case runs on ~=1ms and mine code on ~=7ms. But... my code is merging all the documents the are on the list with the same type, while your only merge the documents if the closest document have the same type as itself. So depending in what you want if you want to merge the documents on type and if they are neighbors or to merge if they have the same type.