Существует ли реализация с открытым исходным кодом (не GPL) функциональной версии .NET StringBuilder? - PullRequest
Новая
       9

Существует ли реализация с открытым исходным кодом (не GPL) функциональной версии .NET StringBuilder?

2 голосов
/ 01 декабря 2011

Я ищу функциональную (как и не обязательную) реализацию StringBuilder или ее эквивалент. Я видел несколько реализаций функциональных массивов, но они не поддерживают вставку изначально. Бонус за открытый исходный код, не (L? A?) GPL, бонус за F #, но я могу перевести с Haskell / OCaml / SML при необходимости.

Предложения по алгоритмам приветствуются.

Ответы [ 2 ]

3 голосов
/ 01 декабря 2011
Преимущество

StringBuilder s над string обусловлено минимизацией распределений.Он предварительно выделяет буфер, чтобы избежать выделения для каждой вставки / добавления.Это требует изменчивости - некоторый объект должен владеть (и мутировать) буфером.

Кстати, System.String уже соответствует (что я могу сделать) вашему описанию: он неизменен и поддерживает конкатенацию, вставка MSDN и удаление MSDN .

ОБНОВЛЕНИЕ

Идея Томаса заинтриговала меня.Взяв его идею, вот что я придумал 

type StringBuilder =
  private
  | Empty
  | StringBuilder of int * string * int * StringBuilder
  member this.Length =
    match this with 
    | Empty -> 0
    | StringBuilder(_, _, n, _) -> n
  override this.ToString() =
    let rec rev acc = function
      | Empty -> acc
      | StringBuilder(idx, str, _, bldr) -> rev ((idx, str)::acc) bldr
    let buf = ResizeArray(this.Length)
    for idx, str in rev [] this do buf.InsertRange(idx, str)
    System.String(buf.ToArray())

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
[<RequireQualifiedAccess>]
module StringBuilder =
  let empty = Empty
  let length (bldr:StringBuilder) = bldr.Length
  let insert index str bldr = 
    if index < 0 || index > (length bldr) then invalidArg "index" "out of range"
    StringBuilder(index, str, str.Length + bldr.Length, bldr)
  let create str = insert 0 str empty
  let append str bldr = insert (length bldr) str bldr
  let remove index count (bldr:StringBuilder) = create <| bldr.ToString().Remove(index, count)

Использование 

let bldr = 
  StringBuilder.create "abcdef"
  |> StringBuilder.insert 1 "xyz"
  |> StringBuilder.append "123"
  |> StringBuilder.remove 1 2

bldr.ToString() //azbcdef123

Он постоянен и вставка O (1).

0 голосов
/ 02 декабря 2011

Я не знаю ни о какой реализации, которая бы делала именно то, что вы хотите. Однако я не думаю, что вы когда-либо сможете получить O (1) сложность вставки (по произвольному индексу) и O (n) сложность итерации по результатам.

Если вы готовы пожертвовать сложностью вставки, вы можете использовать string, как предлагает Даниэль. С другой стороны, если вы готовы пожертвовать сложностью toString, то вы можете сделать неизменную структуру данных с вставкой O (1) в любом месте, используя список строк и индексов: 

type InsertList = IL of (int * string) list 

// Insert string 'str' at the specified index 
let insertAt idx str (IL items) = IL (idx, str)::items

// Create insert list from a string
let ofString str = IL [str]

Преобразование в строку немного сложнее. Тем не менее, я думаю, что вы можете получить сложность O (n log n), используя изменяемый LinkedList и вставляя отдельные символы в нужное место, перебирая вставки с конца. Использование LinkedList будет локализовано до toString, поэтому структура данных все еще является чисто функциональной.

...