// Copyright 2013 Google Inc. All Rights Reserved. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // // Author: [email protected] (Dick Sites) // #ifndef SCRIPT_SPAN_OFFSETMAP_H_ #define SCRIPT_SPAN_OFFSETMAP_H_ #include <string> // for string #include "integral_types.h" // for uint32 // ***************************** OffsetMap ************************** // // An OffsetMap object is a container for a mapping from offsets in one text // buffer A' to offsets in another text buffer A. It is most useful when A' is // built from A via substitutions that occasionally do not preserve byte length. // // A series of operators are used to build the correspondence map, then // calls can be made to map an offset in A' to an offset in A, or vice versa. // The map starts with offset 0 in A corresponding to offset 0 in A'. // The mapping is then built sequentially, adding on byte ranges that are // identical in A and A', byte ranges that are inserted in A', and byte ranges // that are deleted from A. All bytes beyond those specified when building the // map are assumed to correspond, i.e. a Copy(infinity) is assumed at the // end of the map. // // The internal data structure records positions at which bytes are added or // deleted. Using the map is O(1) when increasing the A' or A offset // monotonically, and O(n) when accessing random offsets, where n is the // number of differences. // namespace chrome_lang_id { namespace CLD2 { class OffsetMap { … }; } // namespace CLD2 } // namespace chrome_lang_id #endif // SCRIPT_SPAN_OFFSETMAP_H_