Переместить в двусвязный список Рамда. js - PullRequest
Новая
       10

Переместить в двусвязный список Рамда. js

0 голосов
/ 19 февраля 2020

Когда я начал использовать двусвязный список, стало сложнее управлять prev_id & next_id. 

const dll = [
  {id: '14', prev_id: null, next_id: '41'}, // <- source
  {id: '41', prev_id: '14', next_id: '22'}, 
  {id: '22', prev_id: '41', next_id: '45'},
  {id: '45', prev_id: '22', next_id: null}, // <- destination
]

Например, я хочу переместить объект 14 в конец, поэтому массив должен стать: 

const dll_result = [
  {id: '41', prev_id: null, next_id: '22'}, 
  {id: '22', prev_id: '41', next_id: '45'},
  {id: '45', prev_id: '22', next_id: '14'},
  {id: '14', prev_id: '45', next_id: null},
]

Самое сложное, что мне нужно сделать, чтобы изменить prev_id & next_id объектов?

Моя попытка: 

.as-console-wrapper { max-height: 100% !important; top: 0; }
<script type="text/javascript" charset="utf8" src="//cdn.jsdelivr.net/npm/ramda@0.27.0/dist/ramda.min.js"></script>
<script>
  const {move} = R

  const dll = [
    {id: '14', prev_id: null, next_id: '41'}, //<- source
    {id: '41', prev_id: '14', next_id: '22'}, //<- destination
    {id: '22', prev_id: '41', next_id: '45'}, 
    {id: '45', prev_id: '22', next_id: null}, 
  ]

  const fromId = '14'
  const toId = '41' 

  const fromItem = dll.find(item => item.id === fromId)
  const toItem = dll.find(item => item.id === toId)

  const updated = dll.map(item => {
    if (item.id === fromId) {
      return {...item, prev_id: toId, next_id: toItem.next_id}
    } else if (item.prev_id === fromId) {
      return {...item, prev_id: fromItem.prev_id}
    } else if (item.id === toItem.next_id) {
      return {...item, prev_id: fromId} 
    } else if (item.id === toId) {
      return {...item, next_id: fromId}    
    } else {
      return item
    }
  })

  console.log(JSON.stringify(move(0, 1, updated), null, 2))
</script>

Ответы [ 2 ]

2 голосов
/ 19 февраля 2020

Как я упоминал в моих комментариях, я обнаружил, что это маловероятная структура данных, не получающая ни одного из преимуществ истинно двусвязного списка. Также в комментариях я спрашивал о до против после при вставке или перемещении элемента. В этой версии предполагается, что предполагалось переместить после указанного узла, отметив, где нам также может потребоваться до версий функций.

Справедливое предупреждение, это уродливый императивный код, изменяющий структуры данных волей-неволей внутри своих функций. (Хотя нет, конечно, на границах функций; я не варвар!)

Вы сказали в комментарии, что у вас уже есть функции insert и delete. Если это так, вы можете написать простую версию move так, как я делаю здесь, просто вставив измененную копию удаленного узла после целевого.

Я не пытаюсь разместить вставленный узел в любом конкретном месте в массиве; Из структуры данных я предполагаю, что просто поместить ее в конец не проблема. Если бы это было так, нам бы тоже пришлось начать дурачиться с индексами. Это не сложно, но некрасиво.

В этом коде нет проверки ошибок, оставляя это в качестве упражнения для читателя. Если вы используете идентификатор, которого нет в списке, мы не несем ответственности за то, что происходит. Это может делить на ноль, запускать ракеты или украсть вашего парня. Вы были предупреждены. 

// or Ramda's `clone`, or whatever
const clone = (o) => JSON .parse (JSON .stringify (o))

const removeNode = (dll, id) => {
  const list = clone (dll)
  const byId  = (i) => list .find (({id}) => id === i)
  const node = byId (id)
  const prevNode = node .prev_id ? byId (node .prev_id) : null
  const nextNode = node .next_id ? byId (node .next_id) : null
  if (prevNode) prevNode .next_id = node .next_id
  if (nextNode) nextNode .prev_id = node .prev_id
  return list.filter(node => node .id !== id)
}

const insertAfter = (dll, id, item) => {
  const list = clone (dll)
  const byId  = (i) => list .find (({id}) => id === i)
  const node = byId (id)
  const nextNode = node .next_id ? byId (node .next_id) : null
  node .next_id = item .id
  if (nextNode) nextNode .prev_id = item .id
  return [...list, {
    ...item, 
    prev_id: node .id,
    next_id: nextNode ? nextNode .id : null
  }]
}

const moveAfter = (dll, fromId, afterId) => {
  const node = dll .find (({id}) => id == fromId)
  return insertAfter (removeNode (dll, fromId), afterId, node)
}

// and insertBefore, moveBefore

const dll = [
  {id: '14', prev_id: null, next_id: '41'},
  {id: '41', prev_id: '14', next_id: '22'},
  {id: '22', prev_id: '41', next_id: '45'}, 
  {id: '45', prev_id: '22', next_id: null}, 
]

console.log (
  moveAfter (dll, '14', '41')
)
1 голос
/ 20 февраля 2020

Я бы сделал что-то вроде этого, надеюсь, это поможет ...

Перемещение элемента в двойном списке не является идеальным, поскольку тогда вам нужно переместить все ссылки ... 

const move = (id, toIndex, list) => {
  const fromIndex = R.findIndex(
    R.whereEq({ id }), 
    list,
  );
  
  return R.move(fromIndex, toIndex, list);
};

// R.nth would cause cyclic dbl-list
const pickId = (i, list) => R.propOr(null, 'id', list[i]);

const shiftLinks = (item, i, list) => R.mergeRight(item, {
  prev: pickId(R.dec(i), list),
  next: pickId(R.inc(i), list),
});

const moveById = R.pipe(
  move,
  R.addIndex(R.map)(shiftLinks),
);  


// ==
const data = [
  {id: 'first', prev: null, next: 'second'}, 
  {id: 'second', prev: 'first', next: 'third'},
  {id: 'third', prev: 'second', next: 'fourth'},
  {id: 'fourth', prev: 'third', next: null},
];
console.log(
  // id: 'second', toIndex: 3, data: data
  moveById('second', 3, data),
);
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.0/ramda.js" integrity="sha256-buL0byPvI/XRDFscnSc/e0q+sLA65O9y+rbF+0O/4FE=" crossorigin="anonymous"></script>
...