The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Feb. 08, 2022
Filed:
Jul. 15, 2018
Microsoft Technology Licensing, Llc, Redmond, WA (US);
Peng Lyu, Issaquah, WA (US);
Alexandru Ioan Dima, Zurich, CH;
Microsoft Technology Licensing, LLC, Redmond, WA (US);
Abstract
A family of piece tree data structures and related algorithms are described, for buffering editable text in a digital memory. A piece tree includes one or more string buffers and a tree, such as a balanced binary tree. Tree nodes identify respective substrings in the buffer(s), and correspond to edits of the content loaded into a text editor. Specific changes in data structures and the impact of those changes on performance relative to other buffering structures are discussed, including reduced memory usage, faster file loading, and the impact of accumulated edit operations. Offsets of text items such as line breaks are tracked, permitting optimizations for locating them in a text. Benchmark testing results are presented. Source code editors provide examples, but the piece tree buffering structures and their related traversal, (re)configuration, and other algorithms can be part of text editors in a variety of application or subject matter areas.